一種新的基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法

沈海燕　李星毅

摘要摘要：發(fā)現(xiàn)高質(zhì)量的社區(qū)是社區(qū)網(wǎng)絡(luò)問題的研究熱點(diǎn)。目前，社區(qū)發(fā)現(xiàn)算法大多針對(duì)非重疊社區(qū)，重疊社區(qū)發(fā)現(xiàn)算法較少?；跇?biāo)簽傳播的算法是現(xiàn)有重疊社區(qū)發(fā)現(xiàn)算法中的一類，其中COPRA為典型算法。盡管該算法具有接近線性的時(shí)間復(fù)雜度，但存在隨機(jī)因素，結(jié)果不穩(wěn)定，產(chǎn)生的社區(qū)結(jié)構(gòu)存在一定差異。為此，提出一種新的基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法，實(shí)驗(yàn)表明該算法在復(fù)雜度相近的情況下能明顯提高所發(fā)現(xiàn)社區(qū)的質(zhì)量，且具有較好的穩(wěn)定性。

關(guān)鍵詞關(guān)鍵詞：社區(qū)發(fā)現(xiàn)；重疊社區(qū)；標(biāo)簽傳播；穩(wěn)定性

DOIDOI：10.11907/rjdk.1431038

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)

文章編號(hào)：16727800（2015）004005904

1重疊社區(qū)及其發(fā)現(xiàn)算法

近年來，復(fù)雜網(wǎng)絡(luò)研究受到廣泛關(guān)注，主要涉及系統(tǒng)科學(xué)、統(tǒng)計(jì)物理學(xué)、社會(huì)科學(xué)、生物學(xué)等多個(gè)領(lǐng)域[1]。隨著通信和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，人們發(fā)現(xiàn)眾多網(wǎng)絡(luò)都存在社區(qū)結(jié)構(gòu)[2]這一特征。所謂社區(qū)結(jié)構(gòu)，簡(jiǎn)單來說，就是網(wǎng)絡(luò)中的節(jié)點(diǎn)存在分組，一般組內(nèi)的邊連接比較稠密，而組間的邊連接比較稀疏。社區(qū)結(jié)構(gòu)在一定程度上可以反映出真實(shí)網(wǎng)絡(luò)的拓?fù)潢P(guān)系。社區(qū)發(fā)現(xiàn)可以幫助更好地理解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其功能，從而更好地利用和改造網(wǎng)絡(luò)，例如挖掘網(wǎng)絡(luò)中的未知功能、控制疾病傳播等。社區(qū)發(fā)現(xiàn)在某些特定應(yīng)用環(huán)境中也有現(xiàn)實(shí)意義，例如發(fā)現(xiàn)恐怖分子、尋找犯罪團(tuán)體等。

然而，真實(shí)網(wǎng)絡(luò)存在一些同時(shí)屬于多個(gè)社區(qū)的節(jié)點(diǎn)，這些節(jié)點(diǎn)叫作“重疊節(jié)點(diǎn)”，與其它社區(qū)存在重疊節(jié)點(diǎn)的社區(qū)就叫作“重疊社區(qū)”。例如在社會(huì)關(guān)系網(wǎng)絡(luò)中，小王既參加了臺(tái)球俱樂部，又參加了乒乓球俱樂部，那么小王就是這兩個(gè)社區(qū)的重疊節(jié)點(diǎn)，臺(tái)球俱樂部和乒乓球俱樂部是兩個(gè)重疊社區(qū)。重疊社區(qū)較之非重疊社區(qū)具有更好的現(xiàn)實(shí)意義：一方面，重疊節(jié)點(diǎn)是網(wǎng)絡(luò)中關(guān)鍵點(diǎn)，重疊社區(qū)因此而產(chǎn)生聯(lián)系；另一方面，重疊社區(qū)反映了更加真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)。因此，研究重疊社區(qū)更符合真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)。

圖1為非重疊社區(qū)結(jié)構(gòu)， 圖2為接近真實(shí)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)。目前，能夠發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)的算法主要包括以下3類：

（1）基于clique的方法。典型算法有CPM算法[3]、EAGLE算法[6]和GCE算法[7]。

（2）基于合并社區(qū)核心和擴(kuò)展社區(qū)的方法[8]。

（3）基于標(biāo)簽傳播的方法典型算法有LPA算法[4]和COPRA算法[5]。

CPM算法是一種派系過濾算法，主要通過尋找Kclique派系社區(qū)對(duì)社區(qū)進(jìn)行劃分。雖然CPM能夠發(fā)現(xiàn)重疊點(diǎn)，但該算法在實(shí)際應(yīng)用中依賴參數(shù)K的選取，不同K值導(dǎo)致劃分出來的社區(qū)結(jié)構(gòu)有很大差別。因此，在實(shí)際應(yīng)用中存在一定局限性。同樣地，EAGLE和GCE算法是CPM的改進(jìn)算法，存在同樣的局限。

基于合并社區(qū)核心和擴(kuò)展社區(qū)的算法需要人為指定兩個(gè)參數(shù)，這兩個(gè)參數(shù)需要先驗(yàn)知識(shí)，和具體網(wǎng)絡(luò)相關(guān)并影響社區(qū)發(fā)現(xiàn)結(jié)果的好壞。

基于標(biāo)簽傳播的算法是一類具有接近線性時(shí)間復(fù)雜度的算法，該算法的優(yōu)點(diǎn)是計(jì)算過程簡(jiǎn)單，計(jì)算速度快，而它的缺點(diǎn)是算法穩(wěn)定較差，每次運(yùn)行的結(jié)果可能都不一樣。本文提出一種新的標(biāo)簽算法，該算法對(duì)COPRA 算法的初始化過程和隨機(jī)選擇過程作出了改進(jìn)，從而大大提高算法的穩(wěn)定性。

2標(biāo)簽傳播算法

本文重點(diǎn)對(duì)標(biāo)簽傳播算法中的COPRA算法進(jìn)行改進(jìn)，故簡(jiǎn)要介紹標(biāo)簽傳播思想和LPA算法，并分析COPRA算法與LPA的區(qū)別。

2.1算法思想

標(biāo)簽傳播算法最早由zhu等[9]于2002年提出，是基于圖的半監(jiān)督學(xué)習(xí)方法，其基本思想是通過標(biāo)記節(jié)點(diǎn)的標(biāo)簽信息預(yù)測(cè)還未標(biāo)記節(jié)點(diǎn)的標(biāo)簽情況。節(jié)點(diǎn)之間的標(biāo)簽傳播主要依照標(biāo)簽相似度來進(jìn)行，在傳播過程中，未標(biāo)記的節(jié)點(diǎn)根據(jù)鄰接點(diǎn)的標(biāo)簽情況來迭代更新自身的標(biāo)簽信息，如果其鄰接點(diǎn)與其相似度越相近，則表示對(duì)其所標(biāo)注的影響權(quán)值就越大，鄰接點(diǎn)的標(biāo)簽就更容易進(jìn)行傳播。

圖3為標(biāo)簽傳播過程。每個(gè)頂點(diǎn)都有一個(gè)唯一的標(biāo)簽作為社區(qū)標(biāo)識(shí)，對(duì)圖中所有的頂點(diǎn)進(jìn)行標(biāo)簽迭代更新。在迭代過程中，每個(gè)頂點(diǎn)標(biāo)簽為其鄰接點(diǎn)中出現(xiàn)次數(shù)最多的節(jié)點(diǎn)的標(biāo)簽。如果多個(gè)標(biāo)簽的數(shù)量都是最大值，則隨機(jī)選擇一個(gè)作為該頂點(diǎn)的標(biāo)簽。經(jīng)過若干次迭代，最終形成一個(gè)完全連通圖（代表一個(gè)社區(qū)），并且該圖內(nèi)所有頂點(diǎn)都擁有相同標(biāo)簽。

2.2LPA算法

LPA算法基于標(biāo)簽傳播算法思想來發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。該算法由Raghavan[4]提出，根據(jù)每個(gè)節(jié)點(diǎn)鄰接點(diǎn)的社區(qū)情況來選擇所要加入的社區(qū)。其主要思想是起初每個(gè)節(jié)點(diǎn)擁有獨(dú)立的標(biāo)簽，每次迭代中對(duì)于每個(gè)節(jié)點(diǎn)將其標(biāo)簽更改為其鄰接點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽，如果這樣的標(biāo)簽有多個(gè)，則隨機(jī)選擇一個(gè)。通過迭代，直到每個(gè)節(jié)點(diǎn)的標(biāo)簽與其鄰接點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽相同，則達(dá)到穩(wěn)定狀態(tài)，算法結(jié)束。此時(shí)具有相同標(biāo)簽的節(jié)點(diǎn)即屬于同一個(gè)社區(qū)。

LPA算法的執(zhí)行步驟：

（1）初始化過程即為網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)分配一個(gè)唯一的標(biāo)簽，對(duì)于節(jié)點(diǎn)x，有Gx（0）=x。

（2）設(shè)置t=1。

（3）將網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)排序，假設(shè)順序?yàn)閤。

（4）對(duì)x中每個(gè)節(jié)點(diǎn)x，將x的標(biāo)簽設(shè)置為新的標(biāo)簽Cx（t）=f（Cx1（t），..，Cxm，Cxm+1（t-1）），f函數(shù)返回節(jié)點(diǎn)x的鄰接點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽。如果有多個(gè)，則隨機(jī)選擇一個(gè)。

（5）如果每個(gè)節(jié)點(diǎn)的標(biāo)簽都與其鄰接點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽相同，則算法結(jié)束，否則設(shè)置t=t+1，返回步驟3繼續(xù)執(zhí)行。

2.3COPRA算法

LPA算法雖然有很多優(yōu)勢(shì)，但無(wú)法挖掘出重疊社區(qū)結(jié)構(gòu)。對(duì)此，Steve[5]基于原先的算法，引入了新的標(biāo)簽結(jié)構(gòu)（c，b），對(duì)每個(gè)節(jié)點(diǎn)x，x∈G（x），都擁有這樣的標(biāo)簽。其中，c表示社區(qū)標(biāo)識(shí)符，b表示節(jié)點(diǎn)x在社區(qū)c中的從屬系數(shù)，且0≤b≤1。

COPRA算法的執(zhí)行過程如下：

（1）初始化，對(duì)任意的節(jié)點(diǎn)x，x∈G（x）分配一個(gè)唯一的標(biāo)簽（cx，1）。

（2）節(jié)點(diǎn)x根據(jù)其鄰接點(diǎn)集的標(biāo)簽情況更新自己的標(biāo)簽。如果有多個(gè)可選標(biāo)簽，算法會(huì)隨機(jī)選取其中的v個(gè)標(biāo)簽作為結(jié)果。其中，0

（3）如果每個(gè)節(jié)點(diǎn)的標(biāo)簽都與其鄰接點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽相同，則算法結(jié)束，否則返回步驟2繼續(xù)執(zhí)行。

（4）將具有相同社區(qū)標(biāo)簽節(jié)點(diǎn)合并為同一社區(qū)。

3社區(qū)質(zhì)量評(píng)價(jià)指標(biāo)

對(duì)于社區(qū)發(fā)現(xiàn)算法所產(chǎn)生的社區(qū)，需要通過量化指標(biāo)衡量其質(zhì)量好壞，從而進(jìn)一步評(píng)估各種社區(qū)發(fā)現(xiàn)算法的優(yōu)劣。Newman 和 Girvan [12]提出了一個(gè)評(píng)價(jià)社區(qū)質(zhì)量的指標(biāo)，稱之為模塊化度量Q。

考慮某種劃分形式，將網(wǎng)絡(luò)劃分為K個(gè)社區(qū)。令eij為網(wǎng)絡(luò)中連接社區(qū)i到社區(qū)j的頂點(diǎn)之間邊的一半，對(duì)角線元素為eii，則對(duì)角線上的各元素之和為Tre=∑ieii，表示網(wǎng)絡(luò)中連接某一個(gè)社區(qū)內(nèi)部各個(gè)節(jié)點(diǎn)的邊在所有邊的數(shù)目中的比例。ai=∑jeij為每行（或者每列）中各元素之和，表示與第i 個(gè)社區(qū)中的節(jié)點(diǎn)相連的邊在所有邊中的比例。在此基礎(chǔ)上，用下式來定義模塊性的衡量標(biāo)準(zhǔn)：

Q=∑i（eii-ai2）=Tre-‖e2‖（1）

其中，‖χ2‖表示矩陣χ中所有元素之和。式（1）表示在同樣社區(qū)結(jié)構(gòu)下，網(wǎng)絡(luò)中連接兩個(gè)同類型的節(jié)點(diǎn)的邊的比例減去任意連接這兩個(gè)節(jié)點(diǎn)的邊的比例的期望值。若社區(qū)內(nèi)部邊的比例小于或者等于任意連接時(shí)的值，則Q為0。Q的上限為1，Q越接近1，說明社區(qū)結(jié)構(gòu)越明顯。實(shí)際上，該值通常為0.3～0.7。

Q函數(shù)只是用來評(píng)價(jià)非重疊社區(qū)結(jié)構(gòu)的指標(biāo)。Shen等[10]對(duì)Q函數(shù)作了擴(kuò)展，得到一種可以用來評(píng)價(jià)重疊社區(qū)結(jié)構(gòu)的指標(biāo)—EQ函數(shù)，其公式為：

EQ=12m∑i∑v∈ci，w∈ci1OvOw[Avw-kvkw2m]（2）

其中，Ov是節(jié)點(diǎn)v可以同時(shí)從屬的社區(qū)數(shù)目，A表示由網(wǎng)絡(luò)轉(zhuǎn)換而成的鄰接矩陣。

4算法改進(jìn)

根據(jù)上述LPA算法和COPRA算法描述，可以看出算法標(biāo)簽初始階段是給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分配唯一的標(biāo)簽，此后標(biāo)簽會(huì)不斷更新，網(wǎng)絡(luò)規(guī)模越大，更新標(biāo)簽所需要的資源消耗就越大。在標(biāo)簽更新階段，如果存在多個(gè)標(biāo)簽可選，則進(jìn)行一次隨機(jī)選擇，這樣導(dǎo)致算法的結(jié)果非常不穩(wěn)定。鑒于上述缺點(diǎn)，本文對(duì)COPRA算法標(biāo)簽初始化和標(biāo)簽選擇進(jìn)行改進(jìn)。

4.1標(biāo)簽初始階段

對(duì)標(biāo)簽的初始化主要是借鑒CPM算法中Clique思想。Clique代表網(wǎng)絡(luò)中完全子圖，用完全子圖來代替大量的節(jié)點(diǎn)。這樣就不需要對(duì)所有的節(jié)點(diǎn)進(jìn)行處理，只要對(duì)每個(gè)完全子圖分配標(biāo)簽。

標(biāo)簽預(yù)處理算法步驟如下：

（1）初始化節(jié)點(diǎn)數(shù)據(jù)。

（2）遍歷節(jié)點(diǎn)，根據(jù)鄰接點(diǎn)依次尋找網(wǎng)絡(luò)中KClique，在此過程中，對(duì)從屬于完全子圖的節(jié)點(diǎn)進(jìn)行標(biāo)注，以防完全子圖出現(xiàn)重疊節(jié)點(diǎn)。

（3）對(duì)所發(fā)現(xiàn)的完全子圖按綜合度數(shù)排序，按照排序在標(biāo)簽傳播過程中優(yōu)先處理。

（4）為每個(gè)Clique和剩余節(jié)點(diǎn)分配一個(gè)唯一的標(biāo)簽。

4.2標(biāo)簽選擇過程改進(jìn)

COPRA算法第二步涉及隨機(jī)選擇，可以將此隨機(jī)選擇進(jìn)行弱化， 本文主要引入標(biāo)簽影響值來進(jìn)行弱化。

對(duì)每一個(gè)標(biāo)簽節(jié)點(diǎn)進(jìn)行標(biāo)簽更新時(shí)，若其鄰接點(diǎn)都沒有標(biāo)簽，則不進(jìn)行更新。若其鄰接點(diǎn)中有標(biāo)簽存在，則在所有鄰接點(diǎn)上的標(biāo)簽組成的集合中，選擇其中一個(gè)作為x的標(biāo)簽。影響x的因素有：每個(gè)標(biāo)簽存在的個(gè)數(shù)；所在邊的權(quán)重以及其所在鄰接點(diǎn)的度。綜合考慮這些因素的影響力及其主次關(guān)系，最終提出將平均權(quán)重作為影響標(biāo)簽選擇的主要因素，鄰接點(diǎn)的度作為次要因素。

對(duì)x鄰接點(diǎn)中出現(xiàn)的每一個(gè)標(biāo)簽l進(jìn)行標(biāo)簽影響值influence（l）的計(jì)算，其定義如下：

influence（l）=∑w（li）C（l）+（1-e-∑d（li））（3）

其中，l∈L，w（li）表示每一個(gè)標(biāo)簽為l的頂點(diǎn)所在邊的權(quán)重值；C（l）表示標(biāo)簽l的總個(gè)數(shù)；∑d（li）表示所有標(biāo)簽為l的頂點(diǎn)度之和。

假設(shè)邊的權(quán)重為正整數(shù)，則∑w（li）C（l）>1，而1-e-∑d（li）<1。因此，比較兩個(gè)標(biāo)簽時(shí)，若平均權(quán)重的差值大于1，則平均權(quán)重起主要決定作用；若值小于1，則由平均權(quán)重和頂點(diǎn)之和共同決定。故對(duì)于一個(gè)頂點(diǎn)x，其標(biāo)簽為：

Label（x）=argmax（4）influence（l）=argmax[∑w（li）C（l）+（1-e-∑d（li））]（5）

5實(shí)驗(yàn)驗(yàn)證與分析

本文實(shí)驗(yàn)硬件環(huán)境為：Pentinum（R）雙核 2.7GHZ處理器，4G內(nèi)存，算法具體實(shí)現(xiàn)語(yǔ)言為JAVA。

5.1基準(zhǔn)測(cè)試集

為驗(yàn)證算法的有效性，將該算法應(yīng)用到Zacharys Karate Club Network[13]和Dolphins Social Network[14]兩個(gè)真實(shí)網(wǎng)絡(luò)中。

5.1.1Zacharys Karate Club Network

在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)研究中，該網(wǎng)絡(luò)經(jīng)常被使用，它反映一所大學(xué)空手道俱樂部成員之間的關(guān)系。該數(shù)據(jù)集包含34個(gè)節(jié)點(diǎn)，78條邊，其中節(jié)點(diǎn)表示俱樂部的成員，邊表示成員之間的關(guān)系。

從表1可以看出，由于網(wǎng)絡(luò)社區(qū)規(guī)模小，因而基于標(biāo)簽傳播的重疊社區(qū)算法并不能表現(xiàn)出優(yōu)勢(shì)。不僅如此，在速度上反而還要低于CFinder算法，而且這3種算法挖掘出的社區(qū)質(zhì)量也沒有明顯的差別。

5.1.2Dolphin social network

該數(shù)據(jù)集為L(zhǎng)usseau等對(duì)新西蘭海域一個(gè)有62個(gè)成員的寬吻海豚社會(huì)網(wǎng)絡(luò)進(jìn)行長(zhǎng)達(dá)7年（1995年到2001年）觀測(cè)后給出的寬吻海豚社會(huì)網(wǎng)絡(luò)。該網(wǎng)絡(luò)具有62個(gè)節(jié)點(diǎn)，159條邊。

通過表2可以看出，本文新算法發(fā)現(xiàn)社區(qū)的模塊化度量值比原始算法有所提高，新算法所發(fā)現(xiàn)的社區(qū)質(zhì)量有所提高。當(dāng)網(wǎng)絡(luò)越復(fù)雜時(shí)，該優(yōu)越性表現(xiàn)越明顯。

5.2抓取數(shù)據(jù)集

抓取到的數(shù)據(jù)集為L(zhǎng)eskovecsc等[15]從Arxiv網(wǎng)站上抓取的關(guān)于廣義相對(duì)論和量子宇宙學(xué)主題的論文集合，論文作者為圖的頂點(diǎn)，作者之間的合作關(guān)系為邊。該數(shù)據(jù)集總共有5 242個(gè)頂點(diǎn)和14 484條邊。

通過表3可以看出，在處理大規(guī)模數(shù)據(jù)集時(shí)，本文算法無(wú)論是在執(zhí)行效率上還是挖掘精度上較之原有的COPRA有明顯的優(yōu)勢(shì)。

6結(jié)語(yǔ)

本文主要采用標(biāo)簽傳播的思想從標(biāo)簽初始化和標(biāo)簽選擇兩個(gè)方面針對(duì)原有COPRA算法進(jìn)行改進(jìn)。通過在初始階段對(duì)標(biāo)簽的預(yù)處理過程來減少初始化的數(shù)目，從而提高算法執(zhí)行效率；在標(biāo)簽選擇過程中引入標(biāo)簽影響值來弱化隨機(jī)選擇，使得算法更加穩(wěn)定。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法提高了算法穩(wěn)定性，不僅能夠成功挖掘出具有較高質(zhì)量的社區(qū)，而且還能挖掘出重疊社區(qū)結(jié)構(gòu)。

本文僅僅從標(biāo)簽初始化和標(biāo)簽選擇兩個(gè)方面對(duì)算法作了改進(jìn)。對(duì)于標(biāo)簽傳播的方式卻未作出考慮。將從這方面對(duì)算法作進(jìn)一步改進(jìn)，以得到更具優(yōu)勢(shì)的算法。原有COPRA算法采用同步的方式，較之異步方式存在震蕩的問題?？梢钥紤]將這兩種方式進(jìn)行綜合得到新的傳播方式。

此外，在重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方面，可以考慮將現(xiàn)有的層次發(fā)現(xiàn)算法和重疊社區(qū)算法相融合，得到層次性重疊社區(qū)發(fā)現(xiàn)算法，較之單一的重疊社區(qū)算法所挖掘出的社區(qū)更加真實(shí)。

參考文獻(xiàn)參考文獻(xiàn)：

[1]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006，162191.

[2]TRAUD A L，KELSIC E D，MUCHA P J，PORTER M A.Comparing community structure to characteristics in online collegiate social networks[J].SIAM Rev，2011，53（3）：526543.

[3]PALLA G ，DERENYI I ，F(xiàn)ARKAS I ，et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature，2005，435：814818.

[4]RAGHAVAN U N，REKA A，SOUNDAR K.Near liner time algorithm to detect community structures in largescale networks [J].Physical Review E，2007，76：36106.

[5]GREGORY S.Finding overlapping communities using disjoint community detection algorithms [J].Studies in Computational Intelligence，2009，207：4762.

[6]HUAWEI SHEN，et al.Detect overlapping and hierarchical community structure in networks [J].Physical A：Statistical Mechanics and its Applications Volume 388，Issue 8，15 April 2009：17061712.

[7]C LEE，F(xiàn) REID，A MCDAID，et al.Detecting highly overlapping community structure by greedy clique expansion[C].Tech.Rep.arXiv，2010.

[8]S MINGSHENG，C DUANBING Z，TAO.Detecting overlapping communities based on community cores in complex networks[J].Chinese Physics Letters，2010（27）：58901.

[9]ZHU X JIAOJIN，GHAHRAMANI Z.Learning from labeled and unlabeled data with label propagation，CMUCALD[R].Pittsburghers：Carnegie Mellon University，2002：2107.

[10]XIE JIERUI ，SZYMANSKI B.Community detection using a neighborhood strength driven label propagation algorithm[C].Proc of IEEE Network Science Workshop，2011：188195.

[11]KIM Y，JEONG H.The map equation for link community [J].Physical Review E，2011，84（2）：26110.

[12]NEWMAN M，EJ GIRVAN M.Finding and evaluating community structure in Networks[J].Physical Review，2004（69）：26113.

[13]ZACHARY W W .An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research，1977，33（4）：452473 .

[14]DAVID LUESSEAU，KARSTEN SCHNEIDER，OLIVER J BOISSEAU，et al .The bottlenose dolphin community of Doubtful Sound features a large proportion of longlasting associations[J].Behavioral Ecology and Sociobiogy，2003（54）：396405.

[15]LESKOVEC J，KLEINBERG J，F(xiàn)ALOUTSOS C.Graph evolution：densification and shrinking diameters[J].ACM Trans on Knowledge Discovery from Data（ACM TKDD），2007，1（1） ：140.

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）