版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、共享知識(shí)分享快樂網(wǎng)絡(luò)社區(qū)劃分算法目錄1 簡(jiǎn)介2 構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò)3 網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路:拓?fù)浞治龊土鞣治? 拓?fù)浞治鰋4.1計(jì)算網(wǎng)絡(luò)的模塊化程度Q-Modularityo4.2計(jì)算網(wǎng)絡(luò)的連邊緊密度Edge betweennesso4.3計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量Leading eigenvectoro4.4通過 fast greedy方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值o4.5通過 multi level方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值5 流分析o5.1隨機(jī)游走算法Walk Trapo5.2標(biāo)簽擴(kuò)散算法label propagationo5
2、.3流編碼算法the Map Equationo 5.4 流層級(jí)算法 Role-based Similarity6 總結(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ì)信息資源的處理信息,因此比起單純使用資源本身攜帶的信息來聚類(例如,使用新聞包含的關(guān)鍵詞對(duì)新聞資源進(jìn)行聚類),是一種更深刻的知識(shí)發(fā)現(xiàn)。構(gòu)建一個(gè)點(diǎn)擊流網(wǎng)絡(luò)假設(shè)我們手頭有一批用戶在一段期間內(nèi)訪問某類資源的數(shù)據(jù)。為了減少數(shù)據(jù)數(shù)理規(guī)模,我們一般只考慮最經(jīng)常被訪問的一
3、批資源。因此在數(shù)據(jù)處理中,我們考慮UV ( user visit )排名前V 的資源,得到節(jié)點(diǎn)集合|V| ,然后對(duì)于一個(gè)用戶 i 在一段時(shí)間內(nèi)(例如一天)內(nèi)訪問的資源,選擇屬于|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èi)的 n 個(gè)用戶做這個(gè)操作,最后將得到的總數(shù)為 的連邊里相同的邊合并,得到 |M| 個(gè)不同的邊,每條邊上都帶有權(quán)重信息。這樣,我們就得到
4、了 V 個(gè)節(jié)點(diǎn), M 條邊的一個(gè)加權(quán)無向網(wǎng)絡(luò),反應(yīng)的是在一天之內(nèi)用戶在主要的信息資源間的流動(dòng)情況。在這個(gè)網(wǎng)絡(luò)上,我們可以通過社區(qū)劃分的算法對(duì)信息資源進(jìn)行分類。網(wǎng)絡(luò)社區(qū)劃分的兩種主要思路:拓?fù)浞治龊土鞣治鲰撁純?nèi)容共享知識(shí)分享快樂社區(qū)劃分的算法比較多,但我個(gè)人認(rèn)為大致可以分為兩大類:拓?fù)浞治龊土鞣治?。前者一般適用于無向無權(quán)網(wǎng)絡(luò),思路是社區(qū)內(nèi)部的連邊密度要高于社區(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ì)象和研究者想要獲得的信息。我們可以將已知的一些算法歸入這兩類:算法優(yōu)化目標(biāo)計(jì)算復(fù)雜局限適
5、用情況度拓?fù)浞治鯭 Modularity最大化 Q-modularity無向無權(quán)多分不適用小網(wǎng)V|2絡(luò)量有向有權(quán)多分Edge-Betweenness最小化社區(qū)間連邊的betweennessV|*|E|2慢量Leading Eigenvector對(duì)拉普拉斯矩陣第二小特征根對(duì)應(yīng)的特征向量V|2+ |E|無向無權(quán)多分聚類量Fast Greedy使用社區(qū)合并算法來快速搜索最大E|*log(|V|)無向有權(quán)多分不適用小網(wǎng)頁眉內(nèi)容共享知識(shí)分享快樂Q-modularity量絡(luò)使用社區(qū)展開算法來快速搜索最大無向有權(quán)多分不適用小網(wǎng)Multi LevelV|絡(luò)Q-modularity量流分析無向有權(quán)單分Walk
6、Trap最大化社區(qū)間的流距離E|*|V|2量無向有權(quán)單分Label Propagation每個(gè)節(jié)點(diǎn)取鄰居中最流行的標(biāo)簽,迭代式收斂V| + |E|結(jié)果不穩(wěn)定量有向有權(quán)單分Info map最小化隨機(jī)流的編碼長(zhǎng)度V|*(|V|+|E|)量Role-basedV|3有向有權(quán)單分劃分出在流中地位類似的節(jié)點(diǎn)結(jié)果不穩(wěn)定community量上表中的分量 ( 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)里分量沒
7、有強(qiáng)弱之分。 在網(wǎng)絡(luò)中識(shí)別強(qiáng)分量的算法有 Kosaraju 算法, Tarjan 算法及其變形 Gabow 算法等。里不展開敘述。 接下來,我們逐一討論拓?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ī)期望,說明節(jié)點(diǎn)越有集中在某些社區(qū)內(nèi)的趨勢(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è)方面
8、的空白,迅速成為一般性的社區(qū)劃分算法的通用標(biāo)準(zhǔn)。Q 的具體計(jì)算公式如下:頁眉內(nèi)容共享知識(shí)分享快樂其中 A 是網(wǎng)絡(luò) G 對(duì)應(yīng)的鄰接矩陣,如果從 i 到 j 存在邊, 則 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 ,這就保證了我們只考慮社區(qū)內(nèi)部的連邊。
9、剛才這個(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 matri
10、x,其元素為該矩陣的行列和都是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 greedy和 multilevel就是用不同方法進(jìn)行快速搜索的例子。以fast greedy為例 Newman ( 2006 ),它通過不斷合并社區(qū)來觀察Q 的增加趨勢(shì), 得到了一個(gè)在最差的情況下復(fù)雜度約為O( |E|*log(|V
11、|) ),在最好的情況下接近線性復(fù)雜度的算法。計(jì)算網(wǎng)絡(luò)的連邊緊密度Edge betweenness這個(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,然后看這個(gè)集合中有多少最短路徑需要通過某個(gè)具體的節(jié)點(diǎn)。Newman 借鑒了這個(gè)標(biāo)準(zhǔn),但不是用來分析節(jié)點(diǎn)而是分析連邊。一個(gè)連邊的edge betweenness 就是 S 集合里的最短路徑包含該連邊的個(gè)數(shù)。定義了連邊的 betwee
12、nness 后,就可以通過迭代算法來進(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)算,但問題是計(jì)算復(fù)雜度比較大。計(jì)算網(wǎng)絡(luò)拉普拉斯矩陣的特征向量Leading eigenvector頁眉內(nèi)容共享知識(shí)分享快樂一個(gè)有 n 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)G 可以被表達(dá)為一個(gè)n x n 的鄰接矩陣(adjacency matrix)
13、A。在這個(gè)矩陣上,如果節(jié)點(diǎn)i和 j 之間存在連邊, 則 Aij=1 ,否則為 0 。當(dāng)網(wǎng)絡(luò)是無向的時(shí)候,Aij=Aji 。另外我們可以構(gòu)造n x n 的度矩陣 (degreematrix )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 的特征根存在一些有趣性質(zhì)。首先,最小的特征根總等于0。因?yàn)槿绻麑 乘以一個(gè)有 n 個(gè)元素的單位向量,相當(dāng)于計(jì)算每一行的和,剛好是節(jié)點(diǎn)的度的自我抵消,結(jié)果等于0。其次,特
14、征根中 0 的個(gè)數(shù)即無向網(wǎng)G 中分量的個(gè)數(shù)。這意味著如果除了最小特征根,沒有別的特征根為0 ,則整個(gè)網(wǎng)絡(luò)構(gòu)成一個(gè)整體。在這些特征根里,第二小的特征根(或者最小的非零特征根)又叫做代數(shù)連通性(algebraic connectivity),其對(duì)應(yīng)的特征向量叫做Fidler vector 。當(dāng),說明網(wǎng)絡(luò)是一個(gè)整體。越大,說明網(wǎng)絡(luò)彼此間的鏈接越緊密。從這個(gè)定義來看,非常像前面討論的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
15、.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 。因?yàn)?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。回到圖中考察,我們發(fā)現(xiàn)這個(gè)社區(qū)分類基本是合理的。 通
16、過 fast greedy方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值通過 multi level方法搜索網(wǎng)絡(luò)模塊化程度Q-Modularity的最大值因?yàn)橐陨蟽煞N方法都是基于Q-modularity的,只不過是搜索策略的不同,所以在此不展開討論。頁眉內(nèi)容共享知識(shí)分享快樂流分析隨機(jī)游走算法Walk TrapP. Pons和 M. Latapy 2005年提出了一個(gè)基于隨機(jī)游走的網(wǎng)絡(luò)社區(qū)劃分算法。他們提出可以使用兩點(diǎn)到第三點(diǎn)的流距離之差來衡量?jī)牲c(diǎn)之間的相似性,從而為劃分社區(qū)服務(wù)。其具體過程如下:首先對(duì)網(wǎng)絡(luò)G 所對(duì)應(yīng)的鄰接矩陣按行歸一化,得到概率轉(zhuǎn)移矩陣(transition matri
17、x) P。使用矩陣計(jì)算表達(dá)這個(gè)歸一化過程,可以寫作A其中經(jīng)過A 是鄰接矩陣, t 步從節(jié)點(diǎn) i 到 jD 是度矩陣。利用 P 矩陣的馬可夫性質(zhì)可知,它的的概率。其次,定義兩點(diǎn) ij 間的距離如下:t 次方的元素Pijt就代表著隨機(jī)游走的粒子其中 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 步, ij 到目標(biāo)節(jié)點(diǎn) k 的平均流轉(zhuǎn)移概率(因?yàn)檫@個(gè)概率與中間節(jié)點(diǎn)k 的度數(shù)
18、 d(k)成正比,所以要除以 d(k) 來去除這個(gè)影響)。ij 到網(wǎng)絡(luò)所有其他點(diǎn)之間的距離差別越小,說明ij 很可能位于及其類似的位置上, 彼此之間的距離也越接近。值得注意的是, 這個(gè)思路如果只考慮一個(gè)或少數(shù)的目標(biāo)節(jié)點(diǎn),是不合適的。因?yàn)?rij 實(shí)際上只是結(jié)構(gòu)對(duì)稱性。有可能ij 在網(wǎng)絡(luò)的兩端,距離很遠(yuǎn),但到中間某個(gè)節(jié)點(diǎn)的距離是相等的。但因?yàn)楣揭?k 要遍歷網(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)
19、之間的距離rij 后,就可以將其推廣,得到社區(qū)之間的距離rc1c2 了:容易看出,這個(gè)距離與節(jié)點(diǎn)之間的距離很相似,只不過這次是計(jì)算兩個(gè)社區(qū)分別到目標(biāo)節(jié)點(diǎn)個(gè)社區(qū) C 到節(jié)點(diǎn) k 的流距離時(shí),又是對(duì)社區(qū) C 內(nèi)所有節(jié)點(diǎn)到 k 流距離取平均。k 的流距離,而計(jì)算單一旦從流結(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這種算法的思路源于馮諾依曼在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è)),;頁眉內(nèi)容共享知識(shí)分享快樂最后,在迭代收斂時(shí),采用同一種標(biāo)簽的節(jié)點(diǎn)被歸入同一個(gè)社區(qū)。這個(gè)算法的核心是通過標(biāo)簽的擴(kuò)
21、散來模擬某種流在網(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年提出了一種很有意思的方法來研究網(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ī)游走的粒子的
22、軌跡,然后對(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)被訪問的概率并不一樣。為了改進(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ū)編碼的好處是,兩
23、個(gè)或多個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)編碼是可以重復(fù)的,這就進(jìn)一步降低了信息長(zhǎng)度。需要注意的是,兩層編碼并不意味著像國際電話區(qū)號(hào)那樣,在每個(gè)節(jié)點(diǎn)前加一個(gè)社區(qū)前綴碼,因?yàn)檫@樣的話其實(shí)就和單層編碼沒有什么區(qū)別了。這里的兩層編碼實(shí)際上是在利用流的“局域性 ”。只需要我們標(biāo)識(shí)出社區(qū)的入口(即社區(qū)編碼)和出口(定義在社區(qū)間連邊上的編碼),在此區(qū)域內(nèi)訪問的節(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è)社
24、區(qū)出口連邊(exit )編碼,使用了這個(gè)編碼意味著節(jié)點(diǎn)要跳轉(zhuǎn)社區(qū),接下來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 codebook ),決定每個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)的編碼。一旦對(duì)網(wǎng)絡(luò)的社區(qū)劃分P ( partition )給定,就存在一個(gè)社區(qū)碼表,一個(gè)傳送門碼表,和 m 個(gè)節(jié)點(diǎn)碼
25、表,其中m 是社區(qū)的個(gè)數(shù)。最后,社區(qū)劃分的目標(biāo)就是要最小化所有碼表的總長(zhǎng),或者按論文中的說法,平均隨機(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ū)劃分,那么主碼表和傳送門碼表被調(diào)用的次數(shù)將會(huì)很多。特別是傳送門碼表,也就是錯(cuò)誤的社區(qū)劃分會(huì)大大加大這個(gè)碼長(zhǎng)。一個(gè)總結(jié)了以上思想的公式可以表達(dá)如下,作者稱之為the map
26、equation。頁眉內(nèi)容共享知識(shí)分享快樂其中 M 即對(duì)網(wǎng)絡(luò)的某種社區(qū)劃分得到m 個(gè)社區(qū)。 L 是該劃分所對(duì)應(yīng)的信息描述長(zhǎng)度。qi-> 代表進(jìn)出第i 個(gè)社區(qū)的概率(先考慮無向網(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)過展開化簡(jiǎn),可以得到簡(jiǎn)化形式如下:最后,使用某種社區(qū)劃分的搜索策略(主要有細(xì)分與合并兩種)來尋找該描述長(zhǎng)度的最小值即可。值得注意的是,在實(shí)際計(jì)算中,節(jié)點(diǎn)層的信息量(第三項(xiàng))是不需要考慮的。 流層級(jí)算法Role-based SimilarityCooper 和 Barahona在 2010 年提出了一個(gè)算法,可以揭示網(wǎng)絡(luò)中流的層級(jí)關(guān)系。他們認(rèn)為,通過對(duì)網(wǎng)絡(luò)的鄰接矩陣 A 進(jìn)行分析,可以得到一個(gè)節(jié)點(diǎn)從一步到k 步的出流或入流的畫像(flow profile ),在任意兩個(gè)節(jié)點(diǎn)之間比較這種流畫像,就可以得到節(jié)點(diǎn)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度個(gè)人房屋裝修貸款合同模板8篇
- 2025年度城市更新項(xiàng)目土地使用權(quán)收購協(xié)議4篇
- 二零二五版貨運(yùn)車輛租賃合同示范文本(含實(shí)時(shí)跟蹤服務(wù))2篇
- 個(gè)人房屋建筑施工安全合同2024年度2篇
- 二零二五版虛擬現(xiàn)實(shí)(VR)教育培訓(xùn)服務(wù)合同
- 科學(xué)課堂上的商業(yè)思維啟蒙-小學(xué)案例分享
- 教育信息化與嵌入式技術(shù)的融合路徑
- 二零二五版?zhèn)€人獨(dú)資企業(yè)股權(quán)出售與競(jìng)業(yè)禁止協(xié)議3篇
- 二零二五年度物業(yè)服務(wù)合同:某大型商場(chǎng)物業(yè)服務(wù)管理協(xié)議6篇
- 安裝購銷合同
- 2024年醫(yī)銷售藥銷售工作總結(jié)
- GB/T 44888-2024政務(wù)服務(wù)大廳智能化建設(shè)指南
- 2023-2024學(xué)年江西省萍鄉(xiāng)市八年級(jí)(上)期末物理試卷
- 四則混合運(yùn)算100道題四年級(jí)上冊(cè)及答案
- 四川省高職單招電氣技術(shù)類《電子基礎(chǔ)》歷年考試真題試題庫(含答案)
- 2024年江西生物科技職業(yè)學(xué)院?jiǎn)握新殬I(yè)技能測(cè)試題庫帶解析答案
- 橋本甲狀腺炎-90天治療方案
- (2024年)安全注射培訓(xùn)課件
- 2024版《建設(shè)工程開工、停工、復(fù)工安全管理臺(tái)賬表格(流程圖、申請(qǐng)表、報(bào)審表、考核表、通知單等)》模版
- 酒店人防管理制度
- 油田酸化工藝技術(shù)
評(píng)論
0/150
提交評(píng)論