1、 網絡社區劃分算法 目錄 簡介? 1 構建一個點擊流網絡2 ? 網絡社區劃分的兩種主要思路：拓撲分析和流分析? 3 拓撲分析4 ? Q-Modularity 4.1 計算網絡的模塊化程度o o Edge betweenness4.2 計算網絡的連邊緊密度 oLeading eigenvector 4.3 計算網絡拉普拉斯矩陣的特征向量 o 方法搜索網絡模塊化程度fast greedyQ-Modularity的最大值4.4 通過 方法搜索網絡模塊化程度 oQ-Modularity的最大值4.5 通過multi level 5 流分析? Walk Trap5.1 o隨機游走算法5.2 標簽擴散算法

2、label propagation o 5.3 流編碼算法 o the Map Equation 5.4 o 流層級算法 Role-based Similarity 6 總結 ?簡介 1使用許多互聯網數據，我們都可以構建出這樣的網絡，其節點為某一種信息資源，如圖片，視頻，帖子，新聞等，連邊為用戶在資源之間的流動。對于這樣的網絡，使用社區劃分算法可以揭示信息資源之間的相關性，這種相關性的發現利用了用戶對信息資源的處理信息，因此比起單純使用資源本身攜帶的信息來聚類（例如，使用新聞包含的關鍵詞對新聞資源進行聚類），是一種更深刻的知識發現。 構建一個點擊流網絡 2假設我們手頭有一批用戶在一段期間訪問某

3、類資源的數據。為了減少數據數理規模，我們一般只考慮最經常被訪問的一批資源。因此在數據處理中，我們考慮UV（user visit）排名前V的資源，得到節點集合|V|，然后對于一個用戶i在一段時間（例如一天）訪問的資源，選擇屬于|V|的子集vi。如果我們有用戶訪問資源的時間，就可以按照時間上的先后順序，從vi中產生vi-1條有向邊。如果我們沒有時間的數據，可以vi兩兩間建立聯系，形成vi(vi-1)/2條無向邊。因為后者對數據的要求比較低，下文中，暫時先考慮后者的情況。 對于一天的n個用戶做這個操作，最后將得到的總數為 的連邊里相同的邊合并，得到|M|個不同的邊，每條邊上都帶有權重信息。這樣，我們

4、就得到了V個節點，M條邊的一個加權無向網絡，反應的是在一天之用戶在主要的信息資源間的流動情況。在這個網絡上，我們可以通過社區劃分的算法對信息資源進行分類。 網絡社區劃分的兩種主要思路：拓撲分析和流分析 3社區劃分的算法比較多，但我個人認為大致可以分為兩大類：拓撲分析和流分析。前者一般適用于無向無權網絡，思路是社區部的連邊密度要高于社區間。后者適用于有向有權網絡，思路是發現在網絡的某種流動（物質、能量、信息）中形成的社區結構。這兩種分析各有特點，具體應用取決于網絡數據本身描述的對象和研究者想要獲得的信 息。 我們可以將已知的一些算法歸入這兩類：計算復雜適用情況 局限 優化目標 R 算法 度 拓撲

5、分析 spinglass 無向無權多分不適用小網絡V|2 最大化Q-modularityQ Modularity 量.community edge.betweenness 有向有權多分最小化社區間連邊的Edge-Betweenness V|*|E|2 慢 量betweenness .community leading.eigenvector 無向無權多分對拉普拉斯矩陣第二小特征 V|2+ |E| Leading Eigenvector 根對應的特征向量聚類量.community fastgreedy 無向有權多分使用社區合并算法來快速搜不適用小網絡 Fast Greedy E|*log(|V|

6、) 量 索最大Q-munity multilevel 無向有權多分使用社區展開算法來快速搜Multi Level V| 不適用小網絡 量 索最大Q-munity 流分析walktrap 不太適合網絡 無向有權單分數量較小的情E|*|V|2 Walk Trap 最大化社區間的流距離 量.community 況pagation 每個節點取鄰居中最流行的無向有權單分V| + |E| 結果不穩定 Label Propagation 標簽，迭代式收斂量 .community clique 有向有權單分 V|*(|V|+|E|) 最

7、小化隨機流的編碼長度 Info map 量.community 劃分出在流中地位類似的節有向有權單分結果不穩定 Role-based community V|3 量點 component）指在網絡中的獨立“團塊”。有向網絡里，分量有強弱之分，強分量上表中的分量（strong component ）中任意一個節點都可到達另外一個節點，弱分量（weak component）中如果忽略連邊方向，則構成強分量。無向網里分量沒有強弱之分。在網絡中識別強分量的算法有Kosaraju算法，Tarjan算法及其變形Gabow算法等。在這里不展開敘述。 接下來，我們逐一討論拓撲分析和流分析中的各種算法的具體思路

8、。 拓撲分析 4計算網絡的模塊化程度Q-Modularity 4.1Q-Modularity是一個定義在-0.5,1)區間的指標，其算法是對于某一種社區結構，考慮每個社區連邊數與期待值之差。實際連邊越是高于隨機期望，說明節點越有集中在某些社區的趨勢，即網絡的模塊化結構越明顯。Newman在2004年提出這個概念最初是為了對他自己設計的社區劃算法進行評估，但因為這個指標科學合理，而且彌補了這個方面的空白，迅速成為一般性的社區劃分算法的通用標準。 Q的具體計算公式如 下： 其中A是網絡G對應的鄰接矩陣，如果從i到j存在邊，則Aij=1，否則為0。m是總連接數，2m是總度數，Aij/2m是兩節點之間

9、連接的實際概率。Ki和kj分別是i和j的度數。如果我們保持一個網絡的度分布但對其連邊進行隨機2。上式中中括號表達的就是節點之間的實際連邊概率高kikj/(2m)洗牌，任意一對節點在洗牌后存在連接的概率為于期待值的程度。后面跟著一個二元函數，如果節點ij屬于同一個社區，則為1，否則為0，這就保證了我們只考慮社區部的連邊。剛才這個定義是以節點為分析單位。實際上，如果以社區為分析單位看Q指標，可以進一步將其化簡為eii和ai之間的差。其中eii是在第i個社區部的link占網絡總link的比例，ai是第i個社區和所有其他社區的社區間link數。 上式已經清楚定義了Q，但在實際計算里，上式要求對社區及其

10、部節點進行遍歷，這個計算復雜度是很大的。Newman(2006)對上式進行了化簡，得到矩陣表達如下： 我們定義Sir為n * r的矩陣，n是節點數，r是社區數。 如果節點i屬于社區r，則為1，否則為0。則有 于是有 其中B是modularity matrix，其元素為 該矩陣的行列和都是0，因為實際網絡和隨機洗牌后的網絡度分布是不變的。特別地，在僅僅有兩個社區的情況下（r=2），可以s定義為一個n長的向量，節點屬于一個社區為1，屬于另一個社區為-1，Q可以寫成一個更簡單的形式： 通過對社區的劃分可能空間進行搜索，可以得到最大化Q值的社區劃分。在這個過程會涉及數值優化的部分，例如表一中的fast

11、 greedy和multilevel就是用不同方法進行快速搜索的例子。以fast greedy為例Newman（2006），它通過不斷合并社區來觀察Q的增加趨勢，得到了一個在最差的情況下復雜度約為O( |E|*log(|V|) )，在最好的情況下接近線性復雜度的算法。 計算網絡的連邊緊密度Edge betweenness 4.2這個思路出現得比較早(Newman, 2001)。Freeman (1975) 提出過一個叫betweenness的指標，它衡量的是網絡里一個節點占據其他n-1節點間捷徑的程度。具體而言，首先對每一對節點尋找最短路徑，得到一個n * (n-1)/2的最短路徑集合S，然后

12、看這個集合中有多少最短路徑需要通過某個具體的節點。Newman借鑒了這個標準，但不是用來分析節點而是分析連邊。一個連邊的edge betweenness就是S集合里的最短路徑包含該連邊的個數。 定義了連邊的betweenness后，就可以通過迭代算法來進行社區劃分了。具體做法是先計算所有連邊的betweenness，然后去除最高值連邊，再重新計算，再去除最高值連邊，如此反復，直到網絡中的所有連邊都被移除。在這個過程中網絡就逐漸被切成一個個越來越小的component。在這個過程中，我們同樣可以用Q-modularity來衡量社區劃分的結果。這種算法定義比較清晰，也不涉及矩陣數學等運算，但問題是

13、計算復雜度比較大。 計算網絡拉普拉斯矩陣的特征向量Leading eigenvector 4.3一個有n個節點的網絡G可以被表達為一個n x n的鄰接矩陣（adjacency matrix）A。在這個矩陣上，如果節點i和j之間存在連邊，則Aij=1，否則為0。當網絡是無向的時候，Aij=Aji。另外我們可以構造n x n的度矩陣（degree matrix）D。D對角線上的元素即節點度數，例如Dii為節點i的度數，所有非對角線的元素都是0。無向網的分析不存在度數的選擇問題，有向網則要根據分析目標考慮使用出度還是入度。將度數矩陣減去鄰接矩陣即得到拉普拉斯矩陣，即L = D-A。 L的特征根存在一

14、些有趣性質。首先，最小的特征根總等于0。因為如果將L乘以一個有n個元素的單位向量，相當于計算每一行的和，剛好是節點的度的自我抵消，結果等于0。其次，特征根中0 的個數即無向網G中分量的個數。這意味著如果除了最小特征根，沒有別的特征根為0，則整個網絡構成一個整體。 在這些特征根里，第二小的特征根（或者最小的非零特征根）又叫做代數連通性（algebraic connectivity），其 越大，說明網絡彼此間的越緊密。從這對應的特征向量叫做Fidler vector。當，說明網絡是一個整體。個定義來看，非常像前面討論的Q-Modularity，實際上在Newman2006的文章里，確實討論了二者在

15、數學上的對應關系。例如對示例網絡所對應的進行分析，可以得到拉普拉斯矩陣如下： Fidler vector=0.29, 0.00, 0.29, 0.29, 5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0。取這個矩陣的特征根如下：時，0.29, -0.58, -0.58, 0.00。因為Fidler vector的值分別對應著圖里的節點，于是可以寫成a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00。僅僅從元素的正負號就可以看出，該分析建議我們把f和g節點與其他節點分開，更細致的，對元素值大小

16、的考察則建議把矩陣分成三個社區，a, c, d, e, b, h, e, f。回到圖中考察，我們發現這個社區分類基本是合理的。 通過fast greedy方法搜索網絡模塊化程度Q-Modularity的最大值 4.4multi level方法搜索網絡模塊化程度Q-Modularity的最大值 通過4.5因為以上兩種方法都是基于Q-modularity的，只不過是搜索策略的不同，所以在此不展開討論。 流分析 5隨機游走算法Walk Trap 5.1P. Pons 和 M. Latapy 2005年提出了一個基于隨機游走的網絡社區劃分算法。他們提出可以使用兩點到第三點的流距離之差來衡量兩點之間的相

17、似性，從而為劃分社區服務。其具體過程如下：首先對網絡G所對應的鄰接矩陣A按行歸一化，得到概率轉移矩陣（transition matrix）P。使用矩陣計算表達這個歸一化過程，可以寫作 其中A是鄰接矩陣，D是度矩陣。利用P矩陣的馬可夫性質可知，它的t次方的元素Pijt就代表著隨機游走的粒子經過t步從節點i到j的概率。其次，定義兩點ij間的距離如下： 其中t是流的步長。步長必須恰當選擇，因為如果t太小，不足以體現網絡的結構特征，如果t太大，則Pijt趨近于與j的度數d(j)成正比， 隨機游出發點i的拓撲信息被抹去。作者建議的t經驗值為3到5之間。k是某一個目標節點。所以這個公式描述的是經過t步，i

18、j到目標節點k的平均流轉移概率（因為這個概率與中間節點k的度數d(k)成正比，所以要除以d(k)來去除這個影響）。ij到網絡所有其他點之間的距離差別越小，說明ij很可能位于及其類似的位置上，彼此之間的距離也越接近。值得注意的是，這個思路如果只考慮一個或少數的目標節點，是不合適的。因為rij實際上只是結構對稱性。有可能ij在網絡的兩端，距離很遠，但到中間某個節點的距離是相等的。但因為公式要求k要遍歷網絡中除了ij以外的所有節點，這個時候ij如果到所有其他節點的流距離都差不多，比較可能是ij本身就是鄰居，而不僅僅是結構上的對稱。如公式所示，rij表達可以寫成矩陣表達，其中Pti?是第P的t次方后第

19、i行。 定義了任意兩點之間的距離rij后，就可以將其推廣，得到社區之間的距離rc1c2了： 容易看出，這個距離與節點之間的距離很相似，只不過這次是計算兩個社區分別到目標節點k的流距離，而計算單 流距離取平均。k所有節點到C的流距離時，又是對社區k到節點C個社區一旦從流結構中提取了節點相似性，社區劃分就是一個比較簡單的聚類問題。例如可以采取合并式聚類法如下：先將每個節點視為一個社區，然后計算所有存在連邊的社區之間的流距離。然后，取兩個彼此連接且流距離最短社區進行合并，重新計算社區之間的距離，如此不斷迭代，直到所有的節點都被放入同一個社區。這個過程社區的數目不斷減小，導致出現一個樹圖分層（dend

20、rogram）結構。在這個過程中，可以使用Q-modularity的變化來指導搜索的方向。 標簽擴散算法label propagation 5.2這種算法的思路源于諾依曼在50年代提出的元胞自動機模型（cellular automata）和Bak等人在2002年左右做的沙堆模型。該算法的基本原理如下：首先，給全網每個節點分配一個不重復的標簽（label）；其次，在迭代的每一步，讓一個節點采用在它所有的鄰居節點中最流行的標簽（如果最佳候選標簽超過一個，則在其中隨機抽一個），；最后，在迭代收斂時，采用同一種標簽的節點被歸入同一個社區。 這個算法的核心是通過標簽的擴散來模擬某種流在網絡上的擴散。其優

21、勢是算法簡單，特別適用于分析被流所塑造的網絡。在大多數情況下可以快速收斂。其缺陷是，迭代的結果有可能不穩定，尤其在不考慮連邊的權重時，如果社區結構不明顯，或者網絡比較小時，有可能所有的節點都被歸入同一個社區。 流編碼算法 the Map Equation 5.3Rosvall和Axelsson 2009年提出了一種很有意思的方法來研究網絡中的流動。其核心思想是，好的社區劃分要令網絡上流的平均描述長度最短。他們認為，分析有向加權網絡的一個好的視角是觀察某類實體（貨幣、能量、信息）在網絡上的流動。即使沒有實體流動的數據，我們也可以根據網絡的基本結構來推測隨機游走的粒子的軌跡，然后對得到的“平均流”

22、進行信息編碼。對“平均流”的描述長度最短的編碼機制，就對應著對社區的一種最有效劃分。 首先要討論的是節點層編碼。最簡單的方式是給每個節點分配一個獨特的二進制簽名。但這種編碼方式并不高效，因為節點被訪問的概率并不一樣。為了改進，我們可以引入一個Huffman編碼表（code book），在這個編碼表上，每個節點都對應一個獨立的二進制編碼，但碼長與節點被訪問的概率（通過轉移矩陣P在無窮步后的收斂結果來計算）相反。這樣，“平均流”的信息長度就大大被降低了。 其次，我們還可以通過引入兩層編碼，節點編碼和社區編碼，來進一步降低信息長度。有了社區編碼的好處是，兩個或多個社區部的節點編碼是可以重復的，這就進

23、一步降低了信息長度。需要注意的是，兩層編碼并不意味著像國際區號那樣，在每個節點前加一個社區前綴碼，因為這樣的話其實就和單層編碼沒有什么區別了。這里的兩層編碼實際上是在利用流的“局域性”。只需要我們標識出社區的入口（即社區編碼）和出口（定義在社區間連邊上的編碼），在此區域訪問的節點，可以直接使用節點層的編碼，不用考慮社區編碼。例如：11-0000-11-01-101-100-101-01-0001-0-110-011-00-110-00-111- 在這個流中，加粗的0前面，節點都在一個社區里游走，所以直接使用節點編碼，0001是一個社區出口連邊（exit）編碼，使用了這個編碼意味著節點要跳轉社區

24、，接下來0這個社區編碼被使用，意味著流進入0社區，在這里面再次直接使用節點編碼，直到跳出0社區（0社區的exit被使用）。 在這個兩層編碼體系中，包括三類碼表（code book）。第一個是主碼表（master code book），決定每個社區的編碼；第二個是傳送門碼表（exit code book），決定每個社區的出口連邊的編碼；第三個是節點碼表（node code book），決定每個社區的節點的編碼。一旦對網絡的社區劃分P（partition）給定，就存在一個社區碼表，一個傳送門碼表，和m個節點碼表，其中m是社區的個數。最后，社區劃分的目標就是要最小化所有碼表的總長，或者按論文中的說法

25、，平均隨機游走中的一步所耗費的信息成本。 這個思路以一種很有趣的方式利用了網絡社區的定義。網絡社區的存在，意味著社區的流動較多，跨越社區的流動較少。因此，一個好的社區劃分意味著主碼表和傳送門碼表被調用的次數都很少，描述的信息配額（quota）主要用于描述社區的流動。相反，如果待分析的是一個隨機的網絡，或者研究者構造了一種低效的社區劃分，那么主碼表和傳送門碼表被調用的次數將會很多。特別是傳送門碼表，也就是錯誤的社區劃分會大大加大這個碼長。 。the map equation一個總結了以上思想的公式可以表達如下，作者稱之為 其中M即對網絡的某種社區劃分得到m個社區。L是該劃分所對應的信息描述長度。

26、qi-代表進出第i個社區的概率（先考慮無向網絡），因此q-代表社區間跳轉的總概率。H(Q)是社區間跳轉行為的香農信息量。Pi-代表第i個社區節點間跳轉的總概率，H(Pi)是第i個社區節點間跳轉行為的香農信息量。在公式的兩個部分，信息量都用其被使用的頻率進行加權。經過展開化簡，可以得到簡化形式如下： 最后，使用某種社區劃分的搜索策略（主要有細分與合并兩種）來尋找該描述長度的最小值即可。值得注意的是，在實際計算中，節點層的信息量（第三項）是不需要考慮的。 流層級算法 Role-based Similarity 5.4Cooper和Barahona 在2010年提出了一個算法，可以揭示網絡中流的層級關系。他們認為，通過對網絡的鄰接矩陣A進行分析