【圖機器學習】cs224w Lecture 4 - 社區結構

目錄

• Community
  • Configuration Model
  • Louvain Algorithm
• BigCLAM

Community

轉自本人：https://blog.csdn.net/New2World/article/details/105328390

之前講到了網路中節點扮演不同角色，而角色這個概念和社區互補，那么接下來就討論下社區這個概念，

以找作業為例，曾經學者 Granovetter 調查過人們的作業是由誰介紹的，結果很意外，大部分人的作業是由“熟人”，或者說關系并不是很密切的人介紹的，然后 Granovetter 分析后提出了他的解釋：這種“熟人”可能涉及整個社交網路很廣泛的區域 (普遍來說通過 \(6.6\) 個人就能認識全世界任何人)，這樣一來他們很可能覆寫了很多行業，其中一個就是你的專業，然后將這個解釋整理一下就得到了如下兩個方面的結論：

1. 結構上連接緊密的邊的社會性更強；跨度大的邊連接了網路不同的兩個或多個領域反而社會性不穩定
2. 從資訊傳播的角度來看，跨度大的邊能傳遞不同領域的資訊，在找作業方面更有利；而結構上連接密的邊過于冗余因此無法提供新的資訊

Granovetter 的這個理論在后來電話網路中得到了印證，即連接更強的邊一般都有更頻繁的電話聯絡，這里提到一個 edge overlap 需要記錄一下，它衡量了兩個點間連接的緊密程度，當某條邊是 local bridge 時，重疊率為 \(0\)，

\[O_{ij}=\frac{|(N(i)\cap N(j))\text{\textbackslash}\{i,j\}|}{|(N(i)\cup N(j))\text{\textbackslash}\{i,j\}|} \]

那如果我們按重疊率從小到大來移除邊，那整個網路會很快變成不相連的幾個部分，也就是說網路的最大相連的部分大小會很快縮小，如此一來我們就可以斷定這個網路里存在不同的社區，那么給出社區的定義：包含大量內部連接和少量外部連接的節點集合，一個比較經典的社團網路是 Zachary 的 Karate club network

給出具有明顯社區的網路的鄰接矩陣，按一定順序排列節點可以明顯看出有分塊的趨勢，

按套路來說，這時候應該要提出一個用來衡量網路是否具有典型的社區的標準了，那么他來了：modularity \(Q\)，給定網路中的一些點作為一個劃分 \(s\in S\)

\[Q\propto\sum_{s\in S}[(\#\ edges\ within\ group\ s)-(expected \#\ edges\ within\ group\ s)] \]

這個式子的結果衡量的是：到底圖里的邊或邊的權重比我們預想的多多少？如果多很多那說明存在一個社區，少很多說明是 bridge，那這里的 expected 是怎么來的呢？再一次請出零模型

Configuration Model

現在我們的目標是給定 \(n\) 個節點 \(m\) 條邊，然后生成一個具有相同度分布的隨機網路，不同于之前我們構建的零模型，這里我們只需要知道節點間邊的期望，或者對于無向圖來說就是有邊的概率，這里可以通過每個節點的度來計算節點間邊的期望 \(p(i,j)=k_i\frac{k_j}{2m}\)

那么這個圖里所有邊的期望為

\[\begin{aligned}E_{edge}&=\frac12\sum_{i\in N}\sum_{j\in N}\frac{k_ik_j}{2m} \\ &=\frac12\frac1{2m}\sum_{i\in N}k_i(\sum_{j\in N}k_j) \\ &=m\end{aligned} \]

有了這個期望后，我們將 modularity 這個概念具體化，其中 \(\delta\) 是判別函式，判斷兩個節點所屬社區是否相同，即只考慮劃分 \(s\) 內的所有邊，

\[\begin{aligned}Q(G,S)&=\frac1{2m}\sum_{s\in S}\sum_{i\in s}\sum_{j\in s}(A_{ij}-\frac{k_ik_j}{2m}) \\ &=\frac1{2m}\sum\limits_{ij}[A_{ij}-\frac{k_ik_j}{2m}]\delta(c_i,c_j)\end{aligned}\]

得到的 \(Q\) 值落在 \([-1,1]\)，正值表示圖中的邊多余預期，一般地，\(Q\) 大于 \(0.3\) ~ \(0.7\) 表明圖中存在明顯的社區結構，

Louvain Algorithm

根據上面推導到的 modularity 我們可以想到將 \(Q\) 最大化就能得到一個比較好的劃分方案，于是 Louvain 演算法就是基于這樣思想的一個貪心演算法，而且它具有

• 速度快
• 收斂快
• 結果好
• 支持嵌套社區結構

這個演算法分兩步，然后不停迭代直到收斂

1. 在區域范圍內交換節點的社區，如果交換后能使 modularity 增大則保留交換，否則回退
2. 在第一步收斂后將所有屬于同一社區的節點匯聚為一個超級節點，然后根據原圖結構連接這些超級節點形成新的圖，而邊的權重是所有對應邊的權重之和

在第一步里還有很多細節，初始化的時候給所有節點分配一個單獨的社區，交換社區怎么做呢？將節點 \(i\) 的社區改變為其任一鄰接節點 \(j\) 的社區，然后計算 \(\Delta Q\)，在得到所有鄰接節點的 \(\Delta Q\) 后取其中最大的，這里有學生問節點遍歷順序的問題，的確，遍歷順序會影響最終結果，但 Jure 在 slide 里批注到根據研究表明節點順序并不會對結果產生很大影響，因此無所謂，
那么現在還有一個問題，就是這個 \(\Delta Q\)，雖然說這是 modularity 的變化量，但思考一下，改變一個節點的社區型別其實是兩步操作：首先將這個節點從原社區移除，然后才能將其加入新的社區，那這里的 \(\Delta Q\) 就需要包括移除和加入兩步對 modularity 的影響，因此定義 \(\Delta Q(i\rightarrow C)\) 將節點 \(i\) 加入社區 \(C\)；\(\Delta Q(D\rightarrow i)\) 將節點 \(i\) 從社區 \(D\) 移除，\(\Delta Q=\Delta Q(i\rightarrow C)+\Delta Q(D\rightarrow i)\)，其中移除節點的具體表達為

\[\Delta Q(i\rightarrow C)=\big[\frac{\sum_{in}+k_{i,in}}{2m}-\big(\frac{\sum_{tot}+k_i}{2m}\big)^2\big]-\big[\frac{\sum_{in}}{2m}-\big(\frac{\sum_{tot}}{2m}\big)^2-\big(\frac{k_i}{2m}\big)^2\big] \]

• \(\sum_{in}\) 社區 \(C\) 內邊的權重之和
• \(\sum_{tot}\) 與社區 \(C\) 內所有點相連的邊的權重
• \(k_{i,in}\) 節點 \(i\) 和社區 \(C\) 內所有點的連接的權重和
• \(k_i\) 與節點 \(i\) 連接的所有邊的權重和

(目前先理解加入這一步，但沒有自己推導；而移除的運算式沒有推，后面有時間會補上)

下圖是這個計算式的 intuition ^[1]

具體偽碼有點長就不貼了，但需要說明一點，在移動了節點的社區型別后社區結構變了，看起來需要重新數邊什么的，然而可以根據改變了的節點的資訊更新社區資訊，因此只是簡單的加減法而不需要重新數，

這里學生提到一個問題，就是什么時候結束演算法？這里我們其實不需要手動中止，因為 Louvain 保證收斂，所以只要讓它跑完就行，每迭代一次都會輸出一次 modularity，而我們只需要取 modularity 最大的那一次迭代就能確定多少社區合適，并從而獲取社區的聚類，一般來說演算法最后都會收斂到剩下兩個社區，
另一個學生提問：這個演算法在多大程度上收斂到最優解，這個問題 Jure 的回答是不知道，但應該不差，

BigCLAM

Louvain 雖然好處多多應用也廣，但有個缺陷，它只能給每個節點分配一個社區，然而現在社會結構復雜，一個人可能參加多個社團或屬于多個社區，這樣就是 overlap 的問題，用鄰接矩陣來表示更直觀

這里采取的思路是：首先設計一個能生成重疊圖的模型，然后通過調整模型引數來擬合給定的圖，這個模型叫 Community Affiliation Graph Model (AGM)，它的定義很直觀，給定社區集合 \(C\)，節點集合 \(V\) 以及成員關系 \(M\) 表示某個節點屬于某個或多個社區，社區 \(c\) 內部的點互相連接的概率為 \(p_c\)，那么任意兩個節點互相連接的概率就是 \(p(\mu,\nu)=1-\prod\limits_{c\in M_{\mu}\cap M_{\nu}}(1-p_c)\)，AGM 不僅能表示重疊，還能表示嵌套的情況，因此是個很有效的模型，而現在我們要做的就是通過給定的網路結構反推 AGM 模型，包括社區個數、節點與社區的隸屬關系以及每個社區內的連接概率，即給定圖 \(G\)，找模型 \(F\)，相當于最大化概率 \(P(G|F)=\prod\limits_{(\mu,\nu)\in G}P(\mu,\nu)\prod\limits_{(\mu,\nu)\notin G}(1-P(\mu,\nu))\)

但是這種“有就是有，沒有就是沒有”的定義太死板了，需要松弛一下，所以給每個節點定義一個向量 \(F_{\mu}\) 表示這個節點屬于各個社區的權重(或概率)，這樣就需要調整節點間連接的概率 \(P(\mu,\nu)=1-\exp(-F_{\mu}F_{\nu}^T)\)，而我們需要最大化的目標就是這樣的一個似然函式

\[l(F)=\sum\limits_{(\mu,\nu)\in E}\log(1-\exp(-F_{\mu}F_{\nu}^T))-\sum\limits_{(\mu,\nu)\notin E}F_{\mu}F_{\nu}^T \]

那接下來需要做的就是

1. 隨機初始化 AGM 的引數 \(F\)
2. 固定其他節點的社區成員關系，更新節點 \(\mu\)

至于怎么做 Jure 這里因為快下課了就沒講，但是提點了一下，就是大家再熟悉不過的梯度上升了，這里梯度為

\[\nabla l(F_{\mu})=\sum\limits_{\nu\in\mathcal{N}(\mu)}F_{\nu}\frac{\exp(-F_{\mu}F_{\nu}^T)}{1-\exp(-F_{\mu}F_{\nu}^T)}-\sum\limits_{\nu\notin\mathcal{N}(\mu)}F_{\nu} \]

這里看起來是要對所有非鄰節點的 \(F_{\nu}\) 求和，但實際上只需要保存然后隨迭代更新就行了，因此這一步的復雜度是和節點的度呈線性關系的，

標籤：其他

上一篇：Kaggle競賽入門（四）：隨機森林演算法的Python實作

下一篇：記錄敲代碼生活：資料演算法（求最大公約數和最小公倍數）Java語言