图网络中的社群及社群发现算法
導讀：本文來自作者的學習筆記。主要講解Graph中社群的概念，然后介紹了一種簡單的社群發現算法Louvain Algorithm，最后提供可重疊的社群發現，提出BigCLAM算法，用來識別節點從屬關系。
01
Granovetter's theory
馬克·格蘭諾維特（Mark Granovetter，1943年10月20日－），美國社會學家，斯坦福大學教授。格蘭諾維特是論文被引用最多的學者之一，根據 Web of Science 的數據，社會學論文被引數排名第一和第三的文章皆出自格蘭諾維特之手。格蘭諾維特因為對社會網絡和經濟社會學的研究而成名。其最著名成就是1974年提出的弱連接理論：與自己頻繁接觸的親朋好友之間是一種“強連接”，通過這種連接獲取到的往往是同質性的信息；但社會上更為廣泛的是一種并不深入的人際關系，這種弱關系能夠使個體獲得通過強關系無法獲取到的信息，從而在工作和事業上、在信息的擴散上起到決定作用。
格蘭諾維特的研究認為如果兩個人之間有共同的朋友，那他們成為朋友的可能性較大。
格蘭諾維特的研究也在真實的數據上得到了驗證：
1. Edge Overlap
簡單解釋下，Edge Overlap表示兩個節點的鄰居節點的重合程度（本身節點不在計算范圍內），下圖中右邊部分右上圖，N(i)=4,N(j)=4，去除本身i, j所以N(i)=4,N(j)=4，N(i)∩N(j)=2，所以Oij=1/3。
Edge Overlap被用來當做節點間鏈接的強弱的一種度量，通過在實際數據集（歐洲通話網絡數據集得到驗證），在實際數據中，具有高邊重疊的邊，確實是有著強連接關系的， 這里的強連接關系即用節點間通話次數來表示關系強弱；
2. 社區內強連接，社區間弱連接
上面的研究表明，在圖中確實會存在緊密連接的社群概念，社群內的鏈接基本是強連接， 而社群間的連接是弱連接，強鏈接偏向將信息流鎖緊在社群內部，而邊緣連接由于涉及到多個社群之間，在信息傳播上更有優勢。
02
網絡社群的基本概念
網絡中的社群的基礎定義：緊密連接的節點集合，這些節點間有較多的內部連接，而相對較少的外部連接；
Zachary空手道俱樂部一個在圖這塊入門級的數據集，用來展示圖網絡中基本的問題如節點分類、社區發現等等；
如下圖，僅靠圖的結構化關系，可以比較合理地將俱樂部進行切分，即規劃至各自的社群：
另一個例子是NCAA FootBall Network：
1. 如何尋找網絡中的社群？
Modularity Q用來衡量網絡中社群劃分的指標， 其基礎含義如下：
其中??需要構建null model，保證相同的degree distribution且連接概率為均勻隨機，假定兩個節點i,j，其度分別為ki,kj，那么節點間邊的期望為p(i,j)=kikj/2m，所以這個圖里面所有邊的期望為：
所以Modularity Q從：
表示為：
其中：
Q值域為[-1, 1]，正值表示社群內的邊多于期望，當Q為0.3-0.7之間表明有顯著的社群結構。
2. Louvain Algorithm
Louvain Algorithm是一個最大化Modularity Q的貪心算法，主要由兩步構成：
過程1：Partitioning
初始化的時候給所有節點分配一個單獨的社區；
針對每一個節點i，進行以下步驟：
計算該節點被劃分到其鄰居節點j所在的社群，并且計算該社群的modularity delta；
將節點i移入至最好modularity delta的社群；
迭代，直到modularity delta不再增加；
其中modularity delta ΔQ， 應該包括Δ(i-＞C)?( 將節點i移入community C增加的Q值 ) 與Δ(D-＞i)?(?將節點i溢出Community D )，因為Δ(D-＞i)，在步驟1中都一樣， 所以ΔQ公式主要依賴于Δ(i-＞C)，如下：
其中：
∑in表示社群內節點之間的邊權重和（社群內邊）；
∑tot表示社群中節點所有的邊的邊權重和（社群內邊與社群外邊均考慮）；
ki,in表示社群中節點i與其他節點的邊權重和；
ki表示節點i連接的所有邊的權重和。
過程2：Restructuring
經過第一步之后，會出現很多超級節點，這些超級節點間所在的社群間如果有任意的邊連接，那么我們要連接超級節點，超級節點間的邊的權重等于他們相應的社群間所有邊權重的和；
具體的偽代碼如圖，邏輯還是相對比較簡單的：
3. 回顧與真實數據展示
每一個pass包含：partitioning和restructuring兩個部分，如下，迭代直到收斂：
真實數據集上的一個例子：
03
檢測有重疊的社群算法：BigCLAM
1. 何謂有重疊的社群？
無重疊的社群與有重疊的社群：
?
很多實際數據集中，存在有重疊的社群：
facebook的Ego-Network：
PPI
2. BigCLAM
BigCLAM主要步驟如下：
基于節點所屬的社群，構造一個圖生成模型，構造方法為AGM ( Community Affiliation Graph Model )；
根據我們實際的圖G，假設它是用AGM生成的。尋找一個最優的AGM，能產生我們實際的圖G， 通過這個AGM，確定每個節點所屬的社區
Community Affiliation Graph Model
如下圖，左邊部分主要包括節點V，社群C，從屬關系，其中每一個社群的概率為pc：
1. 社群c內的節點，彼此連接形成邊的概率是pc;
2. 對于從屬于多個社群的節點，如果其在一個社群內沒有連接，其邊在另外社群的連接也是可能存在的；
AGM可以生成多種不同的社群結構，如Non-overlapping, Overlapping, Nested：
Detecting Communities with AGM
使用AGM來做社群發現就轉換成一個給定graph G，如何反推AGM的各個參數F：Affiliation Graph M，社群個數C，以及社群內連接概率pc。
給定G和F，計算器似然函數：
上式中前一個連乘表示圖當中所有的邊的似然函數，后一個表示不在該graph邊集合的似然。考慮到每個節點屬于各個社區的權重是不同的，向量Fu表示節點u屬于各個社群的權重，加上log轉換，所以log似然函數為：
這里和lr的梯度下降很類似，其實就是一樣，只需要用梯度下降公式帶進去自然就可以算出收斂時的F的參數；
有了F之后， 我們的節點從屬社群關系就極其明顯了。
04
總結
今天，主要講解的是graph中社群的概念，通過Granovetter's theory和真實數據的對比，驗證了圖當中的強弱連接，從而引出社群概念，然后介紹了一種簡單的社群發現算法Louvain Algorithm，通過最大化Modularity Q來保證節點與社群的從屬， 最后提供可重疊的社群發現，提出BigCLAM算法，通過最大化log似然函數優化AGM生成對應真實Graph，來得到AGM， 從而得到包括社群從屬關系在內的各個參數，進而識別節點從屬。
原文鏈接：
https://zhuanlan.zhihu.com/p/262235147
總結
以上是生活随笔為你收集整理的图网络中的社群及社群发现算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 深度剖析 synchronized
- 下一篇： 图解 ElasticSearch 搜索原