CS224W-圖神經網絡 筆記4.3：Community Structure in Networks - 網絡中重疊社區(qū)的挖掘——BigCLAM 算法
本文總結之日CS224W Winter 2021只更新到了第四節(jié)钞澳，所以下文會參考2021年課程的PPT并結合2019年秋季課程進行總結以求內容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦噶撸】CS224W：圖機器學習( 中英字幕 | 2019秋)
[toc]
1 引言
上面介紹了非重疊社區(qū)挖掘的Louvin算法送淆，本節(jié)聊聊重疊社區(qū)的挖掘過程。兩類社區(qū)區(qū)別可以反映在鄰接矩陣上宅此。
2 BigClAM 算法
2.1 主要思路
通過前面的介紹，基于圖生成模型，可以生成一個網絡删壮。相反的基于一個網絡铐拐，能否確定一個圖生成模型徘键。并且模型自動劃分節(jié)點的社區(qū)結構。
聽起來好像想的過分美好遍蟋，但實際上是真實可行的吹害。而這個特殊的圖生成模型就是 AGM模型（Community-Affiliation Graph Model）。
整個算法步驟分為三步
- 利用AGM(Community Affiliation Graph Model)構造一個圖生成模型虚青。
- 根據我們實際的圖G它呀，迭代AGM的模型參數，尋找一個最優(yōu)擬合（fitting）實際圖的AGM棒厘。
- 通過這個AGM纵穿，確定每個節(jié)點所屬的社區(qū)
2.2 AGM模型（Community-Affiliation Graph Model）
模型是一個二部圖結構。用表示.四個參數含義如下：
- 社區(qū) A 內部的每對節(jié)點相連的概率為
.每個社區(qū)對應一個奢人。
- 兩個社區(qū)重疊的部分越多谓媒，則重疊區(qū)域的節(jié)點彼此相連的概率越高
- 對于彼此之間沒有共同社區(qū)的兩個節(jié)點之間的連接概率并不為0，而為??(??,??)=??何乎，叫做
背景社區(qū)稱為句惯。論文中建議
雖然，AMG模型是在重疊社區(qū)挖掘的時候引入的宪赶，但并不意味著AMG模型只能生成有重疊社區(qū)的網絡宗弯。事實上，其非常靈活搂妻，可以生成不同類型的社區(qū)結構蒙保。如
3 圖擬合
通過上面可以看到AGM的參數主要有三個：
- 節(jié)點歸屬關系 Membership ??
- 社區(qū)內連接概率
- 社區(qū)數 ??
3.1 確定M
對于歸屬關系M 用矩陣F(Factor Matrix)表示，矩陣的列為社區(qū)數欲主，列為對應節(jié)點邓厕，每元素表示該節(jié)點歸屬社區(qū)的強度。從強度到節(jié)點間連接概率的推導過程如下圖：
看到連乘和求大值扁瓢，很自然會想到取對數详恼，轉化為求和,便于求導。優(yōu)化采用梯度下降優(yōu)化參數引几。
3.2 確定社區(qū)內連接概率
從確定的節(jié)點強度舉證就可以反推得到社區(qū)內部節(jié)點之間的連接概率昧互。
3.3 確定社區(qū)數 ??
社區(qū)數，決定了因子矩陣F的列數。論文中采用的做法也非常巧妙敞掘，將其初始化一個較大的社區(qū)數 叽掘，通過在優(yōu)化函數上加入L1正則，讓模型自己學習玖雁。類似邏輯回歸中對于特征的選則更扁。最終列不全為零的個數就是最終的社區(qū)數。
通過最終的AGM模型可以很容易得到最終的社區(qū)結構赫冬。
4 總結
本算法是老師在2014年提出的算法（原論文為參考資料3）浓镜，其時間復雜度低，可以運用于大型網絡數據劲厌。另外一提膛薛，cs224w 每年老師講的內容的詳細程度不盡相同，建議大家結合起來一起看脊僚。
