一種改進(jìn)的標(biāo)簽傳播快速社區(qū)發(fā)現(xiàn)方法

康旭彬， 賈彩燕

（北京交通大學(xué) 計(jì) 算機(jī)與信息技術(shù)學(xué)院，北京 100044）

0 引 言

現(xiàn)實(shí)世界中的很多數(shù)據(jù)都可以建模為網(wǎng)絡(luò)形式，如社交網(wǎng)絡(luò)、蛋白質(zhì)作用網(wǎng)絡(luò)、萬(wàn)維網(wǎng)、科學(xué)家合作網(wǎng)等等［1］。這些網(wǎng)絡(luò)具有數(shù)據(jù)量大、結(jié)構(gòu)復(fù)雜的特點(diǎn)，所以被稱為“復(fù)雜網(wǎng)絡(luò)”。隨著科學(xué)研究的深入，人們發(fā)現(xiàn)這些網(wǎng)絡(luò)通常蘊(yùn)含一些統(tǒng)計(jì)特性，如小世界特性［2］、無(wú)尺度特性［3］、包含社區(qū)結(jié)構(gòu)等。其中，“社區(qū)結(jié)構(gòu)”作為復(fù)雜網(wǎng)絡(luò)的一個(gè)重要拓?fù)鋵傩?，受到了人們的極大關(guān)注。所謂“社區(qū)”是指那些聯(lián)系比較緊密的節(jié)點(diǎn)組成的點(diǎn)集。社區(qū)發(fā)現(xiàn)方法的研究對(duì)理解復(fù)雜網(wǎng)絡(luò)的功能、預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為以及分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有重要的理論意義和廣泛的應(yīng)用前景，已被應(yīng)用于社會(huì)網(wǎng)絡(luò)分析、蛋白質(zhì)交互網(wǎng)絡(luò)分析、Web文檔聚類等各個(gè)方面。目前，人們已經(jīng)給出了多種社區(qū)發(fā)現(xiàn)方法。這些方法分為基于優(yōu)化的社區(qū)發(fā)現(xiàn)方法、基于啟發(fā)式策略的社區(qū)發(fā)現(xiàn)方法及其他方法3類。

基于優(yōu)化的方法有譜方法和模塊性最大化方法。其中，譜方法是對(duì)網(wǎng)絡(luò)鄰接矩陣A的拉普拉斯矩陣M（M＝D－A）求特征值，D是由節(jié)點(diǎn)的度構(gòu)成的對(duì)角矩陣，然后根據(jù)其最大特征值對(duì)應(yīng)的特征向量對(duì)網(wǎng)絡(luò)進(jìn)行二分，如果需要?jiǎng)澐殖啥鄠€(gè)社區(qū)，一般采用不斷二分的方法；模塊性最大化方法，是對(duì)網(wǎng)絡(luò)模塊性函數(shù)（也稱為Q函數(shù)）求最大值。Q函數(shù)是指社區(qū)內(nèi)的實(shí)際連接數(shù)目與隨機(jī)情況下社區(qū)內(nèi)連接數(shù)目之差，可以在一定程度上衡量社區(qū)結(jié)構(gòu)的好壞，Q函數(shù)的表達(dá)式為：

其中，K為網(wǎng)絡(luò)社區(qū)數(shù)目；m為網(wǎng)絡(luò)的連邊數(shù)；ms為社區(qū)s中的連邊數(shù)；ds為社區(qū)s中結(jié)點(diǎn)的度之和。

基于啟發(fā)式策略方法有：GN算法［4］、WH算法［5］、MFC 算 法［6］、HITS 算 法［7］、CPM 算 法［8］等。其中，GN算法是一種基于局部搜索的社區(qū)發(fā)現(xiàn)方法，它通過(guò)反復(fù)識(shí)別和刪除那些邊介數(shù)最大的邊來(lái)發(fā)現(xiàn)社區(qū)。邊介數(shù)是指網(wǎng)絡(luò)中經(jīng)過(guò)該連邊的任意2點(diǎn)間最短路徑的數(shù)目。WH算法將網(wǎng)絡(luò)建模為電路系統(tǒng)，網(wǎng)絡(luò)中的連接看作是具有電阻的線路，不同節(jié)點(diǎn)具有不同的電勢(shì)差。它的啟發(fā)式規(guī)則是：當(dāng)在不同的社區(qū)中選取2個(gè)節(jié)點(diǎn)作為正負(fù)極后，由于社區(qū)間的電阻要大于社區(qū)內(nèi)的電阻，所以處于同一社區(qū)內(nèi)節(jié)點(diǎn)的電勢(shì)應(yīng)該大致相同，而不同社區(qū)內(nèi)節(jié)點(diǎn)的電勢(shì)相差較大。

除此之外，還有其他一些有效的社區(qū)發(fā)現(xiàn)方法，如基于層次聚類的社區(qū)發(fā)現(xiàn)方法（凝聚式和分裂式）和基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)方法等。

現(xiàn)有的社區(qū)發(fā)現(xiàn)算法存在算法復(fù)雜度高、需要事先制定社區(qū)的數(shù)目和預(yù)先制定評(píng)價(jià)指標(biāo)等缺陷，有的甚至需要給出大致的社區(qū)大小，因而限制了算法的實(shí)際應(yīng)用效率。文獻(xiàn)［9］提出了一種基于啟發(fā)式策略的快速社區(qū)發(fā)現(xiàn)算法LPA（Label Propagation Algorithm，簡(jiǎn)稱LPA），這種算法不需要指定社區(qū)數(shù)目且時(shí)間復(fù)雜度低，不需要設(shè)計(jì)目標(biāo)函數(shù)，具有便于實(shí)現(xiàn)和大規(guī)模網(wǎng)絡(luò)應(yīng)用等特點(diǎn)，但相比于前述算法，該算法準(zhǔn)確率比較低。文獻(xiàn)［10－11］分別對(duì)該算法進(jìn)行了改進(jìn)，但是這2個(gè)改進(jìn)的算法都引入了額外的參數(shù)，在實(shí)際的應(yīng)用中這些參數(shù)往往難以確定。本文提出了一種改進(jìn)的、基于相似性的、無(wú)參數(shù)的標(biāo)簽傳播算法LPALS（Label Propagation Algorithm based on Local Similarity，簡(jiǎn)稱LPALS），實(shí)驗(yàn)結(jié)果顯示該算法大大提高了原有算法的準(zhǔn)確率且具有較低的時(shí)間復(fù)雜度。

1 LPA算法

LPA算法的基本思想是一個(gè)節(jié)點(diǎn)的label決定于它的鄰居節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)有x1，x2，x3，…，xk，并且每個(gè)鄰居都帶有一個(gè)label表示它所屬的社區(qū)，那么當(dāng)某個(gè)社區(qū)包含x的鄰居節(jié)點(diǎn)數(shù)最多時(shí)，x就屬于這個(gè)社區(qū)。圖1所示為節(jié)點(diǎn)1的更新過(guò)程，其中圖1a中l(wèi)abel為1的節(jié)點(diǎn)變?yōu)閳D1b中的3，因?yàn)樗泥従庸?jié)點(diǎn)中l(wèi)abel為3的節(jié)點(diǎn)數(shù)最多。

圖1 LPA算法中節(jié)點(diǎn)1的更新過(guò)程

隨著label的傳播，那些連接稠密的節(jié)點(diǎn)會(huì)迅速得到一個(gè)一致的label。通過(guò)多次迭代，網(wǎng)絡(luò)中各節(jié)點(diǎn)的label會(huì)趨于穩(wěn)定，社團(tuán)結(jié)構(gòu)隨即也會(huì)顯現(xiàn)出來(lái)。

在LPA算法中節(jié)點(diǎn)的label有同步更新與異步更新2種更新方法。所謂同步更新，即節(jié)點(diǎn)x在第t次迭代的label依據(jù)于它的鄰居節(jié)點(diǎn)在第t－1次迭代時(shí)所得的label，更新公式如下：

其中，Cx（t）表示節(jié)點(diǎn)x在t時(shí)刻的label，f函數(shù)返回的是在x的鄰居節(jié)點(diǎn)里出現(xiàn)頻率最高的那個(gè)label。如果有多個(gè)label出現(xiàn)的頻率最高則從這些label中隨機(jī)返回一個(gè)label。由于這種方法在二分圖中可能產(chǎn)生震蕩現(xiàn)象，于是給出了異步更新方法，其更新公式如下：

其中，xi1，…，xim表示在本次迭代中已經(jīng)更新過(guò)label的節(jié)點(diǎn)；xi（m＋1），…，xik表示 在此次迭代中l(wèi)abel還沒(méi)有更新的節(jié)點(diǎn)，f函數(shù)仍如上所述。因此，節(jié)點(diǎn)x在第t次迭代的label依據(jù)于第t次迭代已經(jīng)更新過(guò)label的節(jié)點(diǎn)和第t次迭代未更新過(guò)label的節(jié)點(diǎn)在第t－1次迭代時(shí)的label。標(biāo)簽傳播算法LPA的步驟如下：

（1）初始化網(wǎng)絡(luò)中所有節(jié)點(diǎn)的label。

（2）迭代次數(shù)t＝1。

（3）隨機(jī)排列網(wǎng)絡(luò)中的節(jié)點(diǎn)，生成序列X。

（4）for（x∈X），

Cx（t）＝f（Cxi1（t），…，Cxim（t），Cxi（m＋1）（t－1），…，Cxik（t－1））。

（5）若所有節(jié)點(diǎn)的label都不再變化則結(jié)束，否則t＝t＋1并且返回步驟（3）。

如前所述，這個(gè)算法簡(jiǎn)單、高效，但準(zhǔn)確率還有待提高。原因之一是不同社團(tuán)之間節(jié)點(diǎn)的label很容易傳播，如圖2所示，圖2a中l(wèi)abel為5的節(jié)點(diǎn)如在圖2b中變?yōu)閘abel為4的節(jié)點(diǎn)，則整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)的label在圖2c中都為4。

圖2 不同社團(tuán)間節(jié)點(diǎn)label的傳播

2 改進(jìn)的LPA算法

分析發(fā)現(xiàn)LPA算法的準(zhǔn)確率低是因?yàn)樵趌abel的更新過(guò)程中平等地對(duì)待了每一個(gè)鄰居節(jié)點(diǎn)的label從而導(dǎo)致不同社區(qū)間的label很容易傳播。為了阻止這種情況發(fā)生，可以給每個(gè)label分配一個(gè)權(quán)值，當(dāng)節(jié)點(diǎn)x的某個(gè)鄰居節(jié)點(diǎn)與x屬于同一社區(qū)的可能性大時(shí)這個(gè)權(quán)值就大，反之則小?？梢杂霉?jié)點(diǎn)間的某種拓?fù)湎嗨贫缺硎緳?quán)值。其中，常用的基于局部拓?fù)湫畔⒌南嗨贫戎饕腥缦?種：

其中，Γi表示節(jié)點(diǎn)i的鄰居集合；｜Γi｜表示該集合的勢(shì)；Γi∩Γj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的共同鄰居數(shù)。在本文的算法中，使用第3種相似度，則節(jié)點(diǎn)x的label更新公式變?yōu)椋浩渲?，g返回的是在x的鄰居節(jié)點(diǎn)里出現(xiàn)的權(quán)值之和最大的label，若存在多個(gè)這樣的label，則隨機(jī)選擇一個(gè)作為x的label。這就在很大程度上限制了不同社區(qū)間label傳播的隨意性。也就是說(shuō)label的傳播被限定在與該節(jié)點(diǎn)距離最小的社區(qū)中，稱這種方法為基于相似性的標(biāo)簽傳播LPALS（Label Propagation Algorithm based on Local Similarity）。在這種情況下，圖2a中l(wèi)abel加了權(quán)，節(jié)點(diǎn)5的label不會(huì)變成4，如圖3所示。

圖3 加權(quán)后節(jié)點(diǎn)5的label的傳播

算法LPALS的具體步驟如下：

（1）初始化網(wǎng)絡(luò)中所有節(jié)點(diǎn)的label。

（2）計(jì)算所有連接的權(quán)值，即2個(gè)節(jié)點(diǎn)的局部相似度。

（3）迭代次數(shù)t＝1。

（4）隨機(jī)排列網(wǎng)絡(luò)中的節(jié)點(diǎn)，生成序列X。

（5）for（x∈X），

Cx（t）＝g（Cxi1（t），…，Cxim（t），Cxi（m＋1）（t－1），…，Cxik（t－1））。

（6）若所有節(jié)點(diǎn)的label都不再變化則結(jié)束；否則t＝t＋1并且返回步驟（4）。

易知該算法的時(shí)間復(fù)雜度為O（m＋n），其中，m為網(wǎng)絡(luò)中的邊數(shù)，n為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。

3 實(shí)驗(yàn)結(jié)果及分析

本節(jié)主要是LPA算法與LPALS算法在人工基準(zhǔn)網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果對(duì)比，由于這2種算法都具有一定的隨機(jī)性，所有實(shí)驗(yàn)結(jié)果都取10次實(shí)驗(yàn)的平均值。

3.1 LFR基準(zhǔn)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

LFR基準(zhǔn)網(wǎng)絡(luò)［12］被廣泛應(yīng)用于測(cè)試社區(qū)發(fā)現(xiàn)算法的性能。這種網(wǎng)絡(luò)能生成符合用戶指定分布的網(wǎng)絡(luò)，更接近真實(shí)的情況，這里的分布不僅包括網(wǎng)絡(luò)節(jié)點(diǎn)度的分布，而且包括各個(gè)社區(qū)中節(jié)點(diǎn)數(shù)的分布。本文中所使用的網(wǎng)絡(luò)節(jié)點(diǎn)度最大為50，最小為20，并且服從指數(shù)為2的冪律分布。在含有1 000和5 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，社區(qū)中的節(jié)點(diǎn)數(shù)最大為50，最小為10，并且服從指數(shù)為1的冪律分布。在含有10 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，社區(qū)中的節(jié)點(diǎn)數(shù)最大為100，最小為20，并且服從指數(shù)為1的冪律分布。參數(shù)μ表示社區(qū)的明顯程度，范圍從0到1，它表示網(wǎng)絡(luò)中處于社區(qū)之間的邊數(shù)與網(wǎng)絡(luò)總邊數(shù)的比值，所以μ值越大社區(qū)結(jié)構(gòu)越不明顯。

在節(jié)點(diǎn)數(shù)為1 000（小規(guī)模）、5 000（中等規(guī)模）、10 000（較大規(guī)模）的網(wǎng)絡(luò)上，測(cè)試了LPA算法與改進(jìn)的LPALS算法的性能。其中，μ值從0.1向0.9變化，步長(zhǎng)為0.1，對(duì)比結(jié)果如圖4～圖6所示。

圖4 1 000節(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

圖5 5 000節(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

圖6 10 000節(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

從圖4～圖6可以看出，當(dāng)社區(qū)結(jié)構(gòu)比較明顯時(shí)2種方法的準(zhǔn)確率都較高，但是當(dāng)社區(qū)結(jié)構(gòu)變得復(fù)雜時(shí)，LPALS算法的準(zhǔn)確率要明顯高于原始的LPA方法。

另外，在節(jié)點(diǎn)數(shù)為1 000、5 000、10 000的網(wǎng)絡(luò)上，在不同的μ值下測(cè)試了LPA算法與LPALS算法的執(zhí)行效率，結(jié)果見(jiàn)表1～表3所列。

從表1～表3中可以看出，LPALS算法的運(yùn)行時(shí)間和LPA算法相比并沒(méi)有太多增加，在提高了準(zhǔn)確率的前提下，運(yùn)算時(shí)間的增加是可以接受的。

表1 1 000節(jié)點(diǎn)運(yùn)行時(shí)間對(duì)比 s

表2 表2 5 000節(jié)點(diǎn)運(yùn)行時(shí)間對(duì)比 s

表3 表2 10 000節(jié)點(diǎn)運(yùn)行時(shí)間對(duì)比 s

3.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

選用常用的 Zachary Karate網(wǎng)絡(luò)［13］、College Football網(wǎng)絡(luò)對(duì)算法LPA及LPALS進(jìn)行測(cè)試分析。表4、表5分別為Zachary空手道俱樂(lè)部網(wǎng)絡(luò)、美國(guó)大學(xué)橄欖球聯(lián)盟網(wǎng)絡(luò)運(yùn)行2種算法的結(jié)果對(duì)比，結(jié)果用準(zhǔn)確率表示。

表4 Karate網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

表5 Football網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證算法的有效性，選擇較大的蛋白質(zhì)交互網(wǎng)絡(luò)［14］和 Email網(wǎng)絡(luò)［15］對(duì)算法 LPA及LPALS進(jìn)行測(cè)試分析。蛋白質(zhì)交互網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果見(jiàn)表6所列。由于Email網(wǎng)絡(luò)沒(méi)有標(biāo)準(zhǔn)的社區(qū)結(jié)構(gòu)，所以采用計(jì)算Q函數(shù)的方法來(lái)比較這2種算法，結(jié)果見(jiàn)表7所列。

表6 蛋白質(zhì)作用網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

表7 Email網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

從表4～表7的對(duì)比結(jié)果可以看出，LPALS在真實(shí)網(wǎng)絡(luò)上的準(zhǔn)確率或Q函數(shù)高于LPA。

4 結(jié)束語(yǔ)

本文基于網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)湎嗨菩?，給出了一種改進(jìn)的標(biāo)簽傳播算法LPALS，在有效繼承了LPA算法優(yōu)點(diǎn)的同時(shí)，提高了LPA算法的精度。該算法的精確度相比于適用于小規(guī)模網(wǎng)絡(luò)的、高復(fù)雜度的算法來(lái)說(shuō)，精確度還有待進(jìn)一步提高。

［1］ 楊 博，劉大有，Liu Jiming，等.復(fù)雜網(wǎng)絡(luò)聚類方法［J］.軟件學(xué)報(bào)，2009，20（1）：54－66.

［2］ Watts D J，Strogatz S H.Collective dynamics of Small－World networks［J］.Nature，1998，393（6638）：440－442.

［3］ Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509－512.

［4］ Newman M E J.Modularity and communities structure in networks［J］.Proceedings of the National Academy of Science，2006，103（23）：8577－8582.

［5］ Guimera R，Amaral L.Functional cartography of complex metabolic networks ［J］.Nature，2005，433 （7028）：895－900.

［6］ Flake G W，Lawrence S，Giles C L，et al.Self－organization and identification of Web communities［J］.IEEE Computer，2002，35（3）：66－71.

［7］ Kleinberg J M.Authoritative sources in a hyperlinked environment［J］.Journal of the ACM，1999，46（5）：604－632.

［8］ Palla G，Derenyi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structures of complex networks in nature and society［J］.Nature，2005，435（7043）：814－818.

［9］ Raghavan U N，Albert P，Kumara S.Near linear time algorithm to detect community structure in large－scale networks［J］.Physical review E，2007，76（3）：036106.

［10］ Pan Ying，Li Dehua，Liu Jianguo，et al.Detecting community structure in complex networks via node similarity［J］.Physical A：Statistical Mechanics and its Applications，2010，389（14）：2849－2857.

［11］ Xie J，Szymanski B K.Community detection using a neighborhood strength driven label propagation algorithm［C］／／Network Science Workshop，2011：188－195.

［12］ Lancichinetti A，F(xiàn)ourtunato S，Radicchi F.Benchmark graphs for testing community detection algorithm ［J］.Physical review E，2008，78（4）：046110.

［13］ Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452－473.

［14］ Jeong H，Mason S P，Barabasi A L，et al.Lethality and centrality in protein networks［J］.Nature，2001，411（6833）：41－42.

［15］ Guimera R，Danon L，Diaz－Guilera A，et al.The real communication networks behind the formal chart：Community structure in organizations［J］.Journal of Economic Behavior，2006，61（4）：663－667.