網(wǎng)絡(luò)社區(qū)劃分算法

1、網(wǎng)絡(luò)社區(qū)劃分算法目錄· 1 簡(jiǎn)介· 2 構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò)· 3 網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路：拓?fù)浞治龊土鞣治?#183; 4 拓?fù)浞治鰋 4.1 計(jì)算網(wǎng)絡(luò)的模塊化程度Q-Modularityo 4.2 計(jì)算網(wǎng)絡(luò)的連邊緊密度Edge betweennesso 4.3 計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量Leading eigenvectoro 4.4 通過(guò)fast greedy方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值o 4.5 通過(guò)multi level方法搜索網(wǎng)絡(luò)模

2、塊化程度Q-Modularity的最大值· 5 流分析o 5.1 隨機(jī)游走算法Walk Trapo 5.2 標(biāo)簽擴(kuò)散算法label propagationo 5.3 流編碼算法 the Map Equationo 5.4 流層級(jí)算法 Role-based Similarity· 6 總結(jié) 簡(jiǎn)介使用許多互聯(lián)網(wǎng)數(shù)據(jù)，我們都可以構(gòu)建出這樣的網(wǎng)絡(luò)，其節(jié)點(diǎn)為某一種信息資源，如圖片，視頻，帖子，新聞等，連邊為用戶在資源之間的流動(dòng)。對(duì)于這樣的網(wǎng)絡(luò)，使用社區(qū)劃分算法可以揭示信息資源之間的相關(guān)性，這種相關(guān)性的發(fā)現(xiàn)利用了用戶對(duì)信息資源

3、的處理信息，因此比起單純使用資源本身攜帶的信息來(lái)聚類（例如，使用新聞包含的關(guān)鍵詞對(duì)新聞資源進(jìn)行聚類），是一種更深刻的知識(shí)發(fā)現(xiàn)。 構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò)假設(shè)我們手頭有一批用戶在一段期間內(nèi)訪問(wèn)某類資源的數(shù)據(jù)。為了減少數(shù)據(jù)數(shù)理規(guī)模，我們一般只考慮最經(jīng)常被訪問(wèn)的一批資源。因此在數(shù)據(jù)處理中，我們考慮UV（user visit）排名前V的資源，得到節(jié)點(diǎn)集合|V|，然后對(duì)于一個(gè)用戶i在一段時(shí)間內(nèi)（例如一天）內(nèi)訪問(wèn)的資源，選擇屬于|V|的子集vi。如果我們有用戶訪問(wèn)資源的時(shí)間，就可以按照時(shí)間上的先后順序，從vi中產(chǎn)生vi-1條有向邊。如果我們沒(méi)有時(shí)間的數(shù)據(jù)，可以vi兩兩間建立聯(lián)系，形成vi(vi-1)/2條無(wú)向邊

4、。因?yàn)楹笳邔?duì)數(shù)據(jù)的要求比較低，下文中，暫時(shí)先考慮后者的情況。 對(duì)于一天內(nèi)的n個(gè)用戶做這個(gè)操作，最后將得到的總數(shù)為 的連邊里相同的邊合并，得到|M|個(gè)不同的邊，每條邊上都帶有權(quán)重信息。這樣，我們就得到了V個(gè)節(jié)點(diǎn)，M條邊的一個(gè)加權(quán)無(wú)向網(wǎng)絡(luò)，反應(yīng)的是在一天之內(nèi)用戶在主要的信息資源間的流動(dòng)情況。在這個(gè)網(wǎng)絡(luò)上，我們可以通過(guò)社區(qū)劃分的算法對(duì)信息資源進(jìn)行分類。 網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路：拓?fù)浞治龊土鞣治錾鐓^(qū)劃分的算法比較多，但我個(gè)人認(rèn)為大致可以分為兩大類：拓?fù)浞治龊土鞣治?。前者一般適用于無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，思路是社區(qū)內(nèi)部的連邊密度要高于社區(qū)間。后者適用于有向有權(quán)網(wǎng)絡(luò)，思路是發(fā)現(xiàn)在網(wǎng)絡(luò)的某種流動(dòng)（物質(zhì)、能量、信息

5、）中形成的社區(qū)結(jié)構(gòu)。這兩種分析各有特點(diǎn)，具體應(yīng)用取決于網(wǎng)絡(luò)數(shù)據(jù)本身描述的對(duì)象和研究者想要獲得的信息。我們可以將已知的一些算法歸入這兩類：算法優(yōu)化目標(biāo)計(jì)算復(fù)雜度適用情況局限拓?fù)浞治鯭 Modularity最大化Q-modularityV|2無(wú)向無(wú)權(quán)多分量不適用小網(wǎng)絡(luò)Edge-Betweenness最小化社區(qū)間連邊的betweennessV|*|E|2有向有權(quán)多分量慢Leading Eigenvector對(duì)拉普拉斯矩陣第二小特征根對(duì)應(yīng)的特征向量聚類V|2+ |E|無(wú)向無(wú)權(quán)多分量Fast Greedy使用社區(qū)合并算法來(lái)快速搜索最大Q-modularityE|*log(|V|)無(wú)向有權(quán)多分量不適用小網(wǎng)

6、絡(luò)Multi Level使用社區(qū)展開算法來(lái)快速搜索最大Q-modularityV|無(wú)向有權(quán)多分量不適用小網(wǎng)絡(luò)流分析Walk Trap最大化社區(qū)間的流距離E|*|V|2無(wú)向有權(quán)單分量Label Propagation每個(gè)節(jié)點(diǎn)取鄰居中最流行的標(biāo)簽，迭代式收斂V| + |E|無(wú)向有權(quán)單分量結(jié)果不穩(wěn)定Info map最小化隨機(jī)流的編碼長(zhǎng)度V|*(|V|+|E|)有向有權(quán)單分量Role-based community劃分出在流中地位類似的節(jié)點(diǎn)V|3有向有權(quán)單分量結(jié)果不穩(wěn)定上表中的分量（component）指在網(wǎng)絡(luò)中的獨(dú)立“團(tuán)塊”。有向網(wǎng)絡(luò)里，分量有強(qiáng)弱之分，強(qiáng)分量（strong component ）中

7、任意一個(gè)節(jié)點(diǎn)都可到達(dá)另外一個(gè)節(jié)點(diǎn)，弱分量（weak component）中如果忽略連邊方向，則構(gòu)成強(qiáng)分量。無(wú)向網(wǎng)里分量沒(méi)有強(qiáng)弱之分。在網(wǎng)絡(luò)中識(shí)別強(qiáng)分量的算法有Kosaraju算法，Tarjan算法及其變形Gabow算法等。在這里不展開敘述。 接下來(lái)，我們逐一討論拓?fù)浞治龊土鞣治鲋械母鞣N算法的具體思路。 拓?fù)浞治?計(jì)算網(wǎng)絡(luò)的模塊化程度Q-ModularityQ-Modularity是一個(gè)定義在-0.5,1)區(qū)間內(nèi)的指標(biāo)，其算法是對(duì)于某一種社區(qū)結(jié)構(gòu)，考慮每個(gè)社區(qū)內(nèi)連邊數(shù)與期待值之差。實(shí)際連邊越是高于隨機(jī)期望，說(shuō)明節(jié)點(diǎn)越有集中在某些社區(qū)內(nèi)的趨勢(shì)，即網(wǎng)絡(luò)的模塊化結(jié)構(gòu)越明顯。Newman在2004年提出

8、這個(gè)概念最初是為了對(duì)他自己設(shè)計(jì)的社區(qū)劃算法進(jìn)行評(píng)估，但因?yàn)檫@個(gè)指標(biāo)科學(xué)合理，而且彌補(bǔ)了這個(gè)方面的空白，迅速成為一般性的社區(qū)劃分算法的通用標(biāo)準(zhǔn)。 Q的具體計(jì)算公式如下： 其中A是網(wǎng)絡(luò)G對(duì)應(yīng)的鄰接矩陣，如果從i到j(luò)存在邊，則Aij=1，否則為0。m是總連接數(shù)，2m是總度數(shù)，Aij/2m是兩節(jié)點(diǎn)之間連接的實(shí)際概率。Ki和kj分別是i和j的度數(shù)。如果我們保持一個(gè)網(wǎng)絡(luò)的度分布但對(duì)其連邊進(jìn)行隨機(jī)洗牌，任意一對(duì)節(jié)點(diǎn)在洗牌后存在連接的概率為kikj/(2m)2。上式中中括號(hào)表達(dá)的就是節(jié)點(diǎn)之間的實(shí)際連邊概率高于期待值的程度。后面跟著一個(gè)二元函數(shù)，如果節(jié)點(diǎn)ij屬于同一個(gè)社區(qū)，則為1，否則為0，這就保證了

9、我們只考慮社區(qū)內(nèi)部的連邊。剛才這個(gè)定義是以節(jié)點(diǎn)為分析單位。實(shí)際上，如果以社區(qū)為分析單位看Q指標(biāo)，可以進(jìn)一步將其化簡(jiǎn)為eii和ai之間的差。其中eii是在第i個(gè)社區(qū)內(nèi)部的link占網(wǎng)絡(luò)總link的比例，ai是第i個(gè)社區(qū)和所有其他社區(qū)的社區(qū)間link數(shù)。上式已經(jīng)清楚定義了Q，但在實(shí)際計(jì)算里，上式要求對(duì)社區(qū)及其內(nèi)部節(jié)點(diǎn)進(jìn)行遍歷，這個(gè)計(jì)算復(fù)雜度是很大的。Newman(2006)對(duì)上式進(jìn)行了化簡(jiǎn)，得到矩陣表達(dá)如下： 我們定義Sir為n * r的矩陣，n是節(jié)點(diǎn)數(shù)，r是社區(qū)數(shù)。如果節(jié)點(diǎn)i屬于社區(qū)r，則為1，否則為0。則有 于是有其中B是modularity matrix，其元素為該矩陣的行列和都是

10、0，因?yàn)閷?shí)際網(wǎng)絡(luò)和隨機(jī)洗牌后的網(wǎng)絡(luò)度分布是不變的。特別地，在僅僅有兩個(gè)社區(qū)的情況下（r=2），可以s定義為一個(gè)n長(zhǎng)的向量，節(jié)點(diǎn)屬于一個(gè)社區(qū)為1，屬于另一個(gè)社區(qū)為-1，Q可以寫成一個(gè)更簡(jiǎn)單的形式：通過(guò)對(duì)社區(qū)的劃分可能空間進(jìn)行搜索，可以得到最大化Q值的社區(qū)劃分。在這個(gè)過(guò)程會(huì)涉及數(shù)值優(yōu)化的部分，例如表一中的fast greedy和multilevel就是用不同方法進(jìn)行快速搜索的例子。以fast greedy為例Newman（2006），它通過(guò)不斷合并社區(qū)來(lái)觀察Q的增加趨勢(shì)，得到了一個(gè)在最差的情況下復(fù)雜度約為O( |E|*log(|V|) )，在最好的情況下接近線性復(fù)雜度的算法。 計(jì)算網(wǎng)絡(luò)的連邊緊密度

11、Edge betweenness這個(gè)思路出現(xiàn)得比較早(Newman, 2001)。Freeman (1975) 提出過(guò)一個(gè)叫betweenness的指標(biāo)，它衡量的是網(wǎng)絡(luò)里一個(gè)節(jié)點(diǎn)占據(jù)其他n-1節(jié)點(diǎn)間捷徑的程度。具體而言，首先對(duì)每一對(duì)節(jié)點(diǎn)尋找最短路徑，得到一個(gè)n * (n-1)/2的最短路徑集合S，然后看這個(gè)集合中有多少最短路徑需要通過(guò)某個(gè)具體的節(jié)點(diǎn)。Newman借鑒了這個(gè)標(biāo)準(zhǔn)，但不是用來(lái)分析節(jié)點(diǎn)而是分析連邊。一個(gè)連邊的edge betweenness就是S集合里的最短路徑包含該連邊的個(gè)數(shù)。 定義了連邊的betweenness后，就可以通過(guò)迭代算法來(lái)進(jìn)行社區(qū)劃分了。具體做法是先計(jì)算所有連邊的be

12、tweenness，然后去除最高值連邊，再重新計(jì)算，再去除最高值連邊，如此反復(fù)，直到網(wǎng)絡(luò)中的所有連邊都被移除。在這個(gè)過(guò)程中網(wǎng)絡(luò)就逐漸被切成一個(gè)個(gè)越來(lái)越小的component。在這個(gè)過(guò)程中，我們同樣可以用Q-modularity來(lái)衡量社區(qū)劃分的結(jié)果。這種算法定義比較清晰，也不涉及矩陣數(shù)學(xué)等運(yùn)算，但問(wèn)題是計(jì)算復(fù)雜度比較大。 計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量Leading eigenvector一個(gè)有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)G可以被表達(dá)為一個(gè)n x n的鄰接矩陣（adjacency matrix）A。在這個(gè)矩陣上，如果節(jié)點(diǎn)i和j之間存在連邊，則Aij=1，否則為0。當(dāng)網(wǎng)絡(luò)是無(wú)向的時(shí)候，Aij=Aji。另外我們可

13、以構(gòu)造n x n的度矩陣（degree matrix）D。D對(duì)角線上的元素即節(jié)點(diǎn)度數(shù)，例如Dii為節(jié)點(diǎn)i的度數(shù)，所有非對(duì)角線的元素都是0。無(wú)向網(wǎng)的分析不存在度數(shù)的選擇問(wèn)題，有向網(wǎng)則要根據(jù)分析目標(biāo)考慮使用出度還是入度。將度數(shù)矩陣減去鄰接矩陣即得到拉普拉斯矩陣，即L = D-A。L的特征根存在一些有趣性質(zhì)。首先，最小的特征根總等于0。因?yàn)槿绻麑乘以一個(gè)有n個(gè)元素的單位向量，相當(dāng)于計(jì)算每一行的和，剛好是節(jié)點(diǎn)的度的自我抵消，結(jié)果等于0。其次，特征根中0 的個(gè)數(shù)即無(wú)向網(wǎng)G中分量的個(gè)數(shù)。這意味著如果除了最小特征根，沒(méi)有別的特征根為0，則整個(gè)網(wǎng)絡(luò)構(gòu)成一個(gè)整體。在這些特征根里，第二小的特征根（或者最小的非零

14、特征根）又叫做代數(shù)連通性（algebraic connectivity），其對(duì)應(yīng)的特征向量叫做Fidler vector。當(dāng)，說(shuō)明網(wǎng)絡(luò)是一個(gè)整體。越大，說(shuō)明網(wǎng)絡(luò)彼此間的鏈接越緊密。從這個(gè)定義來(lái)看，非常像前面討論的Q-Modularity，實(shí)際上在Newman2006的文章里，確實(shí)討論了二者在數(shù)學(xué)上的對(duì)應(yīng)關(guān)系。例如對(duì)示例網(wǎng)絡(luò)所對(duì)應(yīng)的進(jìn)行分析，可以得到拉普拉斯矩陣如下：這個(gè)矩陣的特征根如下：5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0。取時(shí)， Fidler vector=0.29, 0.00, 0.29, 0.29, 0.29, -0.58, -0.58, 0.00。因

15、為Fidler vector的值分別對(duì)應(yīng)著圖里的節(jié)點(diǎn)，于是可以寫成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ù)號(hào)就可以看出，該分析建議我們把f和g節(jié)點(diǎn)與其他節(jié)點(diǎn)分開，更細(xì)致的，對(duì)元素值大小的考察則建議把矩陣分成三個(gè)社區(qū)，a, c, d, e, b, h, e, f?；氐綀D中考察，我們發(fā)現(xiàn)這個(gè)社區(qū)分類基本是合理的。 通過(guò)fast greedy方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值 通過(guò)multi level方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值因?yàn)橐陨蟽煞N方法都

16、是基于Q-modularity的，只不過(guò)是搜索策略的不同，所以在此不展開討論。 流分析 隨機(jī)游走算法Walk TrapP. Pons 和 M. Latapy 2005年提出了一個(gè)基于隨機(jī)游走的網(wǎng)絡(luò)社區(qū)劃分算法。他們提出可以使用兩點(diǎn)到第三點(diǎn)的流距離之差來(lái)衡量?jī)牲c(diǎn)之間的相似性，從而為劃分社區(qū)服務(wù)。其具體過(guò)程如下：首先對(duì)網(wǎng)絡(luò)G所對(duì)應(yīng)的鄰接矩陣A按行歸一化，得到概率轉(zhuǎn)移矩陣（transition matrix）P。使用矩陣計(jì)算表達(dá)這個(gè)歸一化過(guò)程，可以寫作其中A是鄰接矩陣，D是度矩陣。利用P矩陣的馬可夫性質(zhì)可知，它的t次方的元素Pijt就代表著隨機(jī)游走的粒子經(jīng)過(guò)t步從節(jié)點(diǎn)i到j(luò)的概率。其次，定義兩點(diǎn)ij

17、間的距離如下：其中t是流的步長(zhǎng)。步長(zhǎng)必須恰當(dāng)選擇，因?yàn)槿绻鹴太小，不足以體現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)特征，如果t太大，則Pijt趨近于與j的度數(shù)d(j)成正比， 隨機(jī)游出發(fā)點(diǎn)i的拓?fù)湫畔⒈荒ㄈ?。作者建議的t經(jīng)驗(yàn)值為3到5之間。k是某一個(gè)目標(biāo)節(jié)點(diǎn)。所以這個(gè)公式描述的是經(jīng)過(guò)t步，ij到目標(biāo)節(jié)點(diǎn)k的平均流轉(zhuǎn)移概率（因?yàn)檫@個(gè)概率與中間節(jié)點(diǎn)k的度數(shù)d(k)成正比，所以要除以d(k)來(lái)去除這個(gè)影響）。ij到網(wǎng)絡(luò)所有其他點(diǎn)之間的距離差別越小，說(shuō)明ij很可能位于及其類似的位置上，彼此之間的距離也越接近。值得注意的是，這個(gè)思路如果只考慮一個(gè)或少數(shù)的目標(biāo)節(jié)點(diǎn)，是不合適的。因?yàn)閞ij實(shí)際上只是結(jié)構(gòu)對(duì)稱性。有可能ij在網(wǎng)絡(luò)的兩端，

18、距離很遠(yuǎn)，但到中間某個(gè)節(jié)點(diǎn)的距離是相等的。但因?yàn)楣揭髃要遍歷網(wǎng)絡(luò)中除了ij以外的所有節(jié)點(diǎn)，這個(gè)時(shí)候ij如果到所有其他節(jié)點(diǎn)的流距離都差不多，比較可能是ij本身就是鄰居，而不僅僅是結(jié)構(gòu)上的對(duì)稱。如公式所示，rij表達(dá)可以寫成矩陣表達(dá)，其中Pti是第P的t次方后第i行。定義了任意兩點(diǎn)之間的距離rij后，就可以將其推廣，得到社區(qū)之間的距離rc1c2了：容易看出，這個(gè)距離與節(jié)點(diǎn)之間的距離很相似，只不過(guò)這次是計(jì)算兩個(gè)社區(qū)分別到目標(biāo)節(jié)點(diǎn)k的流距離，而計(jì)算單個(gè)社區(qū)C到節(jié)點(diǎn)k的流距離時(shí)，又是對(duì)社區(qū)C內(nèi)所有節(jié)點(diǎn)到k流距離取平均。一旦從流結(jié)構(gòu)中提取了節(jié)點(diǎn)相似性，社區(qū)劃分就是一個(gè)比較簡(jiǎn)單的聚類問(wèn)題。例如可以采取合

19、并式聚類法如下：先將每個(gè)節(jié)點(diǎn)視為一個(gè)社區(qū)，然后計(jì)算所有存在連邊的社區(qū)之間的流距離。然后，取兩個(gè)彼此連接且流距離最短社區(qū)進(jìn)行合并，重新計(jì)算社區(qū)之間的距離，如此不斷迭代，直到所有的節(jié)點(diǎn)都被放入同一個(gè)社區(qū)。這個(gè)過(guò)程社區(qū)的數(shù)目不斷減小，導(dǎo)致出現(xiàn)一個(gè)樹圖分層（dendrogram）結(jié)構(gòu)。在這個(gè)過(guò)程中，可以使用Q-modularity的變化來(lái)指導(dǎo)搜索的方向。 標(biāo)簽擴(kuò)散算法label propagation這種算法的思路源于馮諾依曼在50年代提出的元胞自動(dòng)機(jī)模型（cellular automata）和Bak等人在2002年左右做的沙堆模型。該算法的基本原理如下：首先，給全網(wǎng)每個(gè)節(jié)點(diǎn)分配一個(gè)不重復(fù)的標(biāo)簽（la

20、bel）；其次，在迭代的每一步，讓一個(gè)節(jié)點(diǎn)采用在它所有的鄰居節(jié)點(diǎn)中最流行的標(biāo)簽（如果最佳候選標(biāo)簽超過(guò)一個(gè)，則在其中隨機(jī)抽一個(gè)），；最后，在迭代收斂時(shí)，采用同一種標(biāo)簽的節(jié)點(diǎn)被歸入同一個(gè)社區(qū)。 這個(gè)算法的核心是通過(guò)標(biāo)簽的擴(kuò)散來(lái)模擬某種流在網(wǎng)絡(luò)上的擴(kuò)散。其優(yōu)勢(shì)是算法簡(jiǎn)單，特別適用于分析被流所塑造的網(wǎng)絡(luò)。在大多數(shù)情況下可以快速收斂。其缺陷是，迭代的結(jié)果有可能不穩(wěn)定，尤其在不考慮連邊的權(quán)重時(shí)，如果社區(qū)結(jié)構(gòu)不明顯，或者網(wǎng)絡(luò)比較小時(shí)，有可能所有的節(jié)點(diǎn)都被歸入同一個(gè)社區(qū)。 流編碼算法 the Map EquationRosvall和Axelsson 2009年提出了一種很有意思的方法來(lái)研究網(wǎng)絡(luò)中的流動(dòng)。其核心

21、思想是，好的社區(qū)劃分要令網(wǎng)絡(luò)上流的平均描述長(zhǎng)度最短。他們認(rèn)為，分析有向加權(quán)網(wǎng)絡(luò)的一個(gè)好的視角是觀察某類實(shí)體（貨幣、能量、信息）在網(wǎng)絡(luò)上的流動(dòng)。即使沒(méi)有實(shí)體流動(dòng)的數(shù)據(jù)，我們也可以根據(jù)網(wǎng)絡(luò)的基本結(jié)構(gòu)來(lái)推測(cè)隨機(jī)游走的粒子的軌跡，然后對(duì)得到的“平均流”進(jìn)行信息編碼。對(duì)“平均流”的描述長(zhǎng)度最短的編碼機(jī)制，就對(duì)應(yīng)著對(duì)社區(qū)的一種最有效劃分。首先要討論的是節(jié)點(diǎn)層編碼。最簡(jiǎn)單的方式是給每個(gè)節(jié)點(diǎn)分配一個(gè)獨(dú)特的二進(jìn)制簽名。但這種編碼方式并不高效，因?yàn)楣?jié)點(diǎn)被訪問(wèn)的概率并不一樣。為了改進(jìn)，我們可以引入一個(gè)Huffman編碼表（code book），在這個(gè)編碼表上，每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)獨(dú)立的二進(jìn)制編碼，但碼長(zhǎng)與節(jié)點(diǎn)被訪問(wèn)的

22、概率（通過(guò)轉(zhuǎn)移矩陣P在無(wú)窮步后的收斂結(jié)果來(lái)計(jì)算）相反。這樣，“平均流”的信息長(zhǎng)度就大大被降低了。 其次，我們還可以通過(guò)引入兩層編碼，節(jié)點(diǎn)編碼和社區(qū)編碼，來(lái)進(jìn)一步降低信息長(zhǎng)度。有了社區(qū)編碼的好處是，兩個(gè)或多個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)編碼是可以重復(fù)的，這就進(jìn)一步降低了信息長(zhǎng)度。需要注意的是，兩層編碼并不意味著像國(guó)際電話區(qū)號(hào)那樣，在每個(gè)節(jié)點(diǎn)前加一個(gè)社區(qū)前綴碼，因?yàn)檫@樣的話其實(shí)就和單層編碼沒(méi)有什么區(qū)別了。這里的兩層編碼實(shí)際上是在利用流的“局域性”。只需要我們標(biāo)識(shí)出社區(qū)的入口（即社區(qū)編碼）和出口（定義在社區(qū)間連邊上的編碼），在此區(qū)域內(nèi)訪問(wèn)的節(jié)點(diǎn)，可以直接使用節(jié)點(diǎn)層的編碼，不用考慮社區(qū)編碼。例如：11-0000-1

23、1-01-101-100-101-01-0001-0-110-011-00-110-00-111- 在這個(gè)流中，加粗的0前面，節(jié)點(diǎn)都在一個(gè)社區(qū)里游走，所以直接使用節(jié)點(diǎn)編碼，0001是一個(gè)社區(qū)出口連邊（exit）編碼，使用了這個(gè)編碼意味著節(jié)點(diǎn)要跳轉(zhuǎn)社區(qū)，接下來(lái)0這個(gè)社區(qū)編碼被使用，意味著流進(jìn)入0社區(qū)，在這里面再次直接使用節(jié)點(diǎn)編碼，直到跳出0社區(qū)（0社區(qū)的exit被使用）。在這個(gè)兩層編碼體系中，包括三類碼表（code book）。第一個(gè)是主碼表（master code book），決定每個(gè)社區(qū)的編碼；第二個(gè)是傳送門碼表（exit code book），決定每個(gè)社區(qū)的出口連邊的編碼；第三個(gè)是節(jié)點(diǎn)碼表

24、（node code book），決定每個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)的編碼。一旦對(duì)網(wǎng)絡(luò)的社區(qū)劃分P（partition）給定，就存在一個(gè)社區(qū)碼表，一個(gè)傳送門碼表，和m個(gè)節(jié)點(diǎn)碼表，其中m是社區(qū)的個(gè)數(shù)。最后，社區(qū)劃分的目標(biāo)就是要最小化所有碼表的總長(zhǎng)，或者按論文中的說(shuō)法，平均隨機(jī)游走中的一步所耗費(fèi)的信息成本。 這個(gè)思路以一種很有趣的方式利用了網(wǎng)絡(luò)社區(qū)的定義。網(wǎng)絡(luò)社區(qū)的存在，意味著社區(qū)內(nèi)的流動(dòng)較多，跨越社區(qū)的流動(dòng)較少。因此，一個(gè)好的社區(qū)劃分意味著主碼表和傳送門碼表被調(diào)用的次數(shù)都很少，描述的信息配額（quota）主要用于描述社區(qū)內(nèi)的流動(dòng)。相反，如果待分析的是一個(gè)隨機(jī)的網(wǎng)絡(luò)，或者研究者構(gòu)造了一種低效的社區(qū)劃分，那么主碼

25、表和傳送門碼表被調(diào)用的次數(shù)將會(huì)很多。特別是傳送門碼表，也就是錯(cuò)誤的社區(qū)劃分會(huì)大大加大這個(gè)碼長(zhǎng)。一個(gè)總結(jié)了以上思想的公式可以表達(dá)如下，作者稱之為the map equation。其中M即對(duì)網(wǎng)絡(luò)的某種社區(qū)劃分得到m個(gè)社區(qū)。L是該劃分所對(duì)應(yīng)的信息描述長(zhǎng)度。qi->代表進(jìn)出第i個(gè)社區(qū)的概率（先考慮無(wú)向網(wǎng)絡(luò)），因此q->代表社區(qū)間跳轉(zhuǎn)的總概率。H(Q)是社區(qū)間跳轉(zhuǎn)行為的香農(nóng)信息量。Pi->代表第i個(gè)社區(qū)內(nèi)節(jié)點(diǎn)間跳轉(zhuǎn)的總概率，H(Pi)是第i個(gè)社區(qū)內(nèi)節(jié)點(diǎn)間跳轉(zhuǎn)行為的香農(nóng)信息量。在公式的兩個(gè)部分，信息量都用其被使用的頻率進(jìn)行加權(quán)。經(jīng)過(guò)展開化簡(jiǎn)，可以得到簡(jiǎn)化形式如下：最后，使用某種社區(qū)劃分的搜索策略（主要有細(xì)分與合并兩種）來(lái)尋找該描述長(zhǎng)度的最小值即可。值得注意的是，在實(shí)際計(jì)算中，節(jié)點(diǎn)層的信息量（第三項(xiàng)）是不需要考慮的。 流層級(jí)算法 Role-based SimilarityCooper和Barahona 在2010年提出了一個(gè)算法，可以揭示網(wǎng)絡(luò)中流的層級(jí)關(guān)系。他們認(rèn)為，通過(guò)對(duì)網(wǎng)絡(luò)的鄰接矩陣A進(jìn)行分析，可以得到一個(gè)節(jié)點(diǎn)從一步