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

1、 網(wǎng)絡(luò)社區(qū)劃分算法 目錄 簡(jiǎn)介? 1 構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò)2 ? 網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路：拓?fù)浞治龊土鞣治? 3 拓?fù)浞治? ? Q-Modularity 4.1 計(jì)算網(wǎng)絡(luò)的模塊化程度o o Edge betweenness4.2 計(jì)算網(wǎng)絡(luò)的連邊緊密度 oLeading eigenvector 4.3 計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量 o 方法搜索網(wǎng)絡(luò)模塊化程度fast greedyQ-Modularity的最大值4.4 通過 方法搜索網(wǎng)絡(luò)模塊化程度 oQ-Modularity的最大值4.5 通過multi level 5 流分析? Walk Trap5.1 o隨機(jī)游走算法5.2 標(biāo)簽擴(kuò)散算法

2、label propagation o 5.3 流編碼算法 o the Map Equation 5.4 o 流層級(jí)算法 Role-based Similarity 6 總結(jié) ?簡(jiǎn)介 1使用許多互聯(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ì)信息資源的處理信息，因此比起單純使用資源本身攜帶的信息來聚類（例如，使用新聞包含的關(guān)鍵詞對(duì)新聞資源進(jìn)行聚類），是一種更深刻的知識(shí)發(fā)現(xiàn)。 構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò) 2假設(shè)我們手頭有一批用戶在一段期間訪問某

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

4、就得到了V個(gè)節(jié)點(diǎn)，M條邊的一個(gè)加權(quán)無向網(wǎng)絡(luò)，反應(yīng)的是在一天之用戶在主要的信息資源間的流動(dòng)情況。在這個(gè)網(wǎng)絡(luò)上，我們可以通過社區(qū)劃分的算法對(duì)信息資源進(jìn)行分類。 網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路：拓?fù)浞治龊土鞣治?3社區(qū)劃分的算法比較多，但我個(gè)人認(rèn)為大致可以分為兩大類：拓?fù)浞治龊土鞣治?。前者一般適用于無向無權(quán)網(wǎng)絡(luò)，思路是社區(qū)部的連邊密度要高于社區(qū)間。后者適用于有向有權(quán)網(wǎng)絡(luò)，思路是發(fā)現(xiàn)在網(wǎng)絡(luò)的某種流動(dòng)（物質(zhì)、能量、信息）中形成的社區(qū)結(jié)構(gòu)。這兩種分析各有特點(diǎn)，具體應(yīng)用取決于網(wǎng)絡(luò)數(shù)據(jù)本身描述的對(duì)象和研究者想要獲得的信 息。 我們可以將已知的一些算法歸入這兩類：計(jì)算復(fù)雜適用情況 局限 優(yōu)化目標(biāo) R 算法 度 拓?fù)?/p>

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

6、) 量 索最大Q-munity multilevel 無向有權(quán)多分使用社區(qū)展開算法來快速搜Multi Level V| 不適用小網(wǎng)絡(luò) 量 索最大Q-munity 流分析walktrap 不太適合網(wǎng)絡(luò) 無向有權(quán)單分?jǐn)?shù)量較小的情E|*|V|2 Walk Trap 最大化社區(qū)間的流距離 量.community 況pagation 每個(gè)節(jié)點(diǎn)取鄰居中最流行的無向有權(quán)單分V| + |E| 結(jié)果不穩(wěn)定 Label Propagation 標(biāo)簽，迭代式收斂量 .community clique 有向有權(quán)單分 V|*(|V|+|E|) 最

7、小化隨機(jī)流的編碼長(zhǎng)度 Info map 量.community 劃分出在流中地位類似的節(jié)有向有權(quán)單分結(jié)果不穩(wěn)定 Role-based community V|3 量點(diǎn) component）指在網(wǎng)絡(luò)中的獨(dú)立“團(tuán)塊”。有向網(wǎng)絡(luò)里，分量有強(qiáng)弱之分，強(qiáng)分量上表中的分量（strong component ）中任意一個(gè)節(jié)點(diǎn)都可到達(dá)另外一個(gè)節(jié)點(diǎn)，弱分量（weak component）中如果忽略連邊方向，則構(gòu)成強(qiáng)分量。無向網(wǎng)里分量沒有強(qiáng)弱之分。在網(wǎng)絡(luò)中識(shí)別強(qiáng)分量的算法有Kosaraju算法，Tarjan算法及其變形Gabow算法等。在這里不展開敘述。 接下來，我們逐一討論拓?fù)浞治龊土鞣治鲋械母鞣N算法的具體思路

8、。 拓?fù)浞治?4計(jì)算網(wǎng)絡(luò)的模塊化程度Q-Modularity 4.1Q-Modularity是一個(gè)定義在-0.5,1)區(qū)間的指標(biāo)，其算法是對(duì)于某一種社區(qū)結(jié)構(gòu)，考慮每個(gè)社區(qū)連邊數(shù)與期待值之差。實(shí)際連邊越是高于隨機(jī)期望，說明節(jié)點(diǎn)越有集中在某些社區(qū)的趨勢(shì)，即網(wǎng)絡(luò)的模塊化結(jié)構(gòu)越明顯。Newman在2004年提出這個(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)之間

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

10、部節(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，其元素為 該矩陣的行列和都是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)單的形式： 通過對(duì)社區(qū)的劃分可能空間進(jìn)行搜索，可以得到最大化Q值的社區(qū)劃分。在這個(gè)過程會(huì)涉及數(shù)值優(yōu)化的部分，例如表一中的fast

11、 greedy和multilevel就是用不同方法進(jìn)行快速搜索的例子。以fast greedy為例Newman（2006），它通過不斷合并社區(qū)來觀察Q的增加趨勢(shì)，得到了一個(gè)在最差的情況下復(fù)雜度約為O( |E|*log(|V|) )，在最好的情況下接近線性復(fù)雜度的算法。 計(jì)算網(wǎng)絡(luò)的連邊緊密度Edge betweenness 4.2這個(gè)思路出現(xiàn)得比較早(Newman, 2001)。Freeman (1975) 提出過一個(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，然后

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

13、計(jì)算復(fù)雜度比較大。 計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量Leading eigenvector 4.3一個(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ò)是無向的時(shí)候，Aij=Aji。另外我們可以構(gòu)造n x n的度矩陣（degree matrix）D。D對(duì)角線上的元素即節(jié)點(diǎn)度數(shù)，例如Dii為節(jié)點(diǎn)i的度數(shù)，所有非對(duì)角線的元素都是0。無向網(wǎng)的分析不存在度數(shù)的選擇問題，有向網(wǎng)則要根據(jù)分析目標(biāo)考慮使用出度還是入度。將度數(shù)矩陣減去鄰接矩陣即得到拉普拉斯矩陣，即L = D-A。 L的特征根存在一

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

15、數(shù)學(xué)上的對(duì)應(yīng)關(guān)系。例如對(duì)示例網(wǎng)絡(luò)所對(duì)應(yīng)的進(jìn)行分析，可以得到拉普拉斯矩陣如下： 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。取這個(gè)矩陣的特征根如下：時(shí)，0.29, -0.58, -0.58, 0.00。因?yàn)镕idler 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ì)元素值大小

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

17、似性，從而為劃分社區(qū)服務(wù)。其具體過程如下：首先對(duì)網(wǎng)絡(luò)G所對(duì)應(yīng)的鄰接矩陣A按行歸一化，得到概率轉(zhuǎn)移矩陣（transition matrix）P。使用矩陣計(jì)算表達(dá)這個(gè)歸一化過程，可以寫作 其中A是鄰接矩陣，D是度矩陣。利用P矩陣的馬可夫性質(zhì)可知，它的t次方的元素Pijt就代表著隨機(jī)游走的粒子經(jīng)過t步從節(jié)點(diǎn)i到j(luò)的概率。其次，定義兩點(diǎn)ij間的距離如下： 其中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)過t步，i

18、j到目標(biāo)節(jié)點(diǎn)k的平均流轉(zhuǎn)移概率（因?yàn)檫@個(gè)概率與中間節(jié)點(diǎn)k的度數(shù)d(k)成正比，所以要除以d(k)來去除這個(gè)影響）。ij到網(wǎng)絡(luò)所有其他點(diǎn)之間的距離差別越小，說明ij很可能位于及其類似的位置上，彼此之間的距離也越接近。值得注意的是，這個(gè)思路如果只考慮一個(gè)或少數(shù)的目標(biāo)節(jié)點(diǎn)，是不合適的。因?yàn)閞ij實(shí)際上只是結(jié)構(gòu)對(duì)稱性。有可能ij在網(wǎng)絡(luò)的兩端，距離很遠(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次方后第

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

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

21、勢(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 Equation 5.3Rosvall和Axelsson 2009年提出了一種很有意思的方法來研究網(wǎng)絡(luò)中的流動(dòng)。其核心思想是，好的社區(qū)劃分要令網(wǎng)絡(luò)上流的平均描述長(zhǎng)度最短。他們認(rèn)為，分析有向加權(quán)網(wǎng)絡(luò)的一個(gè)好的視角是觀察某類實(shí)體（貨幣、能量、信息）在網(wǎng)絡(luò)上的流動(dòng)。即使沒有實(shí)體流動(dòng)的數(shù)據(jù)，我們也可以根據(jù)網(wǎng)絡(luò)的基本結(jié)構(gòu)來推測(cè)隨機(jī)游走的粒子的軌跡，然后對(duì)得到的“平均流”

22、進(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)被訪問的概率并不一樣。為了改進(jìn)，我們可以引入一個(gè)Huffman編碼表（code book），在這個(gè)編碼表上，每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)獨(dú)立的二進(jìn)制編碼，但碼長(zhǎng)與節(jié)點(diǎn)被訪問的概率（通過轉(zhuǎn)移矩陣P在無窮步后的收斂結(jié)果來計(jì)算）相反。這樣，“平均流”的信息長(zhǎng)度就大大被降低了。 其次，我們還可以通過引入兩層編碼，節(jié)點(diǎn)編碼和社區(qū)編碼，來進(jìn)一步降低信息長(zhǎng)度。有了社區(qū)編碼的好處是，兩個(gè)或多個(gè)社區(qū)部的節(jié)點(diǎn)編碼是可以重復(fù)的，這就進(jìn)

23、一步降低了信息長(zhǎng)度。需要注意的是，兩層編碼并不意味著像國際區(qū)號(hào)那樣，在每個(gè)節(jié)點(diǎn)前加一個(gè)社區(qū)前綴碼，因?yàn)檫@樣的話其實(shí)就和單層編碼沒有什么區(qū)別了。這里的兩層編碼實(shí)際上是在利用流的“局域性”。只需要我們標(biāo)識(shí)出社區(qū)的入口（即社區(qū)編碼）和出口（定義在社區(qū)間連邊上的編碼），在此區(qū)域訪問的節(jié)點(diǎn)，可以直接使用節(jié)點(diǎn)層的編碼，不用考慮社區(qū)編碼。例如：11-0000-11-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ū)

24、，接下來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)碼表（node code book），決定每個(gè)社區(qū)的節(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)，或者按論文中的說法

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

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