一種穩(wěn)定的標簽傳播社區(qū)發(fā)現(xiàn)算法

趙寶峰，趙菊敏，李燈熬

（太原理工大學a．礦業(yè)工程學院；b．信息工程學院，太原030024）

現(xiàn)實世界紛繁復雜，各種事物之間存在著普遍的聯(lián)系和彼此的依賴。許多這樣的復雜系統(tǒng)可以用復雜網(wǎng)絡(luò)來建模表示，并通過網(wǎng)絡(luò)分析與挖掘方法對系統(tǒng)進行深入的研究。20世紀末，人類對復雜網(wǎng)絡(luò)的認識有了突破性進展，除了眾所周知的小世界特性［1］和無標度特性［2］外，科學家們還發(fā)現(xiàn)各類復雜網(wǎng)絡(luò)中普遍存在著社區(qū)結(jié)構(gòu)［3］。所謂社區(qū)結(jié)構(gòu)是指網(wǎng)絡(luò)中內(nèi)部連接較為緊密而彼此連接較為松散的子結(jié)構(gòu)。在現(xiàn)實世界中，社區(qū)結(jié)構(gòu)往往對應(yīng)著各類系統(tǒng)中不同的功能與結(jié)構(gòu)。例如社會網(wǎng)絡(luò)中的組織團體、生物蛋白質(zhì)相互作用網(wǎng)絡(luò)中的蛋白復合體以及電路網(wǎng)絡(luò)中的各個功能模塊等。因此，發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)對深入了解系統(tǒng)的功能和結(jié)構(gòu)有著非常重要的意義。

經(jīng)過近十年的發(fā)展，已經(jīng)有許多種社區(qū)發(fā)現(xiàn)算法被提出。GN算法［4］由Newman等人提出，它通過割斷中介度指標大的邊將網(wǎng)絡(luò)進行分裂從而發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。BGLL算法［5］是一種基于模塊度指標的貪心優(yōu)化算法，可以發(fā)現(xiàn)有層次的社區(qū)結(jié)構(gòu)。Infomap算法［6］是一種利用隨機游走和信息論的算法，是目前公認的準確率較高的一種算法。此外，在各種算法當中，有一類具有接近線性時間復雜度的算法，稱為標簽傳播算法［7］（Label Propagation Algorithm，LPA）。該算法的優(yōu)點是計算過程非常簡單，計算速度非常之快，但缺點是算法的穩(wěn)定性較差，連續(xù)幾次運行結(jié)果可能會很不相同。針對此問題，提出一種穩(wěn)定的標簽傳播算法。該算法主要改進了LPA算法的初始化過程，從而使算法結(jié)果更加穩(wěn)定。

1 算法

1．1 標簽傳播算法介紹

標簽傳播算法的核心思想是使用鄰居節(jié)點的標簽中數(shù)量最多的標簽作為每個節(jié)點自身的標簽，其基本計算步驟如下：

1）初始時，給每個節(jié)點一個唯一的標簽；

2）每個節(jié)點使用其鄰居節(jié)點的標簽中最多的標簽來更新自身的標簽。如果存在多個標簽數(shù)量最多時，隨機選擇其中一個即可；

3）反復執(zhí)行步驟2），直到每個節(jié)點的標簽都不再發(fā)生變化或達到最大迭代次數(shù)為止；

4）相同標簽的節(jié)點即形成各個社區(qū)。

由于第2）步中存在的隨機性導致算法結(jié)果非常不穩(wěn)定，而這種不穩(wěn)定性對于標簽傳播算法的應(yīng)用將產(chǎn)生非常重要的影響。例如在進行社區(qū)的動態(tài)計算或演化分析時，這種不穩(wěn)定性將導致社區(qū)匹配與跟蹤存在較大困難。

1．2 非重疊最小極大團提取算法

LPA算法的步驟2）要求，如果在鄰居標簽中存在數(shù)量最多的多個標簽時，算法從中隨機選擇一個，這里帶來的隨機性在算法運行最開始的時候影響最大。因為在LPA算法的初始時，每個節(jié)點都有一個唯一的標簽，因此，在最開始的情況下，每個節(jié)點都是從其鄰居節(jié)點的標簽中隨機選擇一個。為了降低算法的不穩(wěn)定性，首先提取一些較為緊密的子結(jié)構(gòu)來作為標簽傳播的初始標簽。

完全子圖是網(wǎng)絡(luò)中連接最緊密的子結(jié)構(gòu)。在完全子圖中，所有節(jié)點之間都彼此相連。CPM算法［8］通過提取并合并所有k－clique來發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)，但是k－clique數(shù)量太龐大，因此計算效率較低。而提取所有極大完全子圖后，存在一個節(jié)點屬于多個完全子圖的情況，而LPA算法要求每個節(jié)點只能最多屬于一個社區(qū)。因此，提出一種非重疊最小極大團提取算法（DMMCA：Disjoint Minimal Maximal Clique Algorithm）來作為標簽傳播的初始。算法描述如下：

1）所有節(jié)點按度數(shù)排序；

2）選擇當前未處理過的度數(shù)最大的節(jié)點，并從鄰接節(jié)點中選擇未處理過的度數(shù)最大的第二個節(jié)點；

3）從步驟2）中選擇出的兩個節(jié)點出發(fā)找出最小的極大團，要求團中每個節(jié)點都是未被處理過的；

4）重復步驟2）和3）直到?jīng)]有符合條件的節(jié)點為止。

DMMC算法中，提取非重疊完全子圖是為了滿足發(fā)現(xiàn)非重疊社區(qū)的要求，即每個節(jié)點最多只有一個標簽，而提取最小的極大團則是為了避免巨型社區(qū)的出現(xiàn)。因為標簽傳播算法具有較強的傳染性，如果初始標簽中某些標簽勢力過大而標簽之間數(shù)量嚴重不均衡，則會導致大勢力標簽吞并其他標簽的結(jié)果，最終只發(fā)現(xiàn)很少的包含絕大多數(shù)節(jié)點的巨型社區(qū)，這樣的結(jié)果將失去社區(qū)發(fā)現(xiàn)的意義。算法中，“未處理過”是指沒有存在于已經(jīng)被找出的極大團中。

2 實驗

對社區(qū)發(fā)現(xiàn)結(jié)果的評價，最常用的是Newman等人提出的Q函數(shù)［9］，其表達式如下：

式中：A表示鄰接矩陣；di和dj分別表示節(jié)點i和j的度數(shù)；m表示網(wǎng)絡(luò)的總邊數(shù)；Ci和Cj分別表示i和j所屬的社區(qū)。當i和j屬于同一個社團時，δ函數(shù)等于1，否則等于0。雖然Q函數(shù)也存在一些缺陷［10］，它仍是目前最常用的一種社區(qū)質(zhì)量評價指標。

實驗中，使用6個真實不同大小的網(wǎng)絡(luò)來測試改進了初始化過程的標簽傳播算法，實驗中記為LPAs（LPA stable）算法。6個網(wǎng)絡(luò)分別是Karate、Dolphins、Books、Jazz、Netsci和 HepPh。所使用的網(wǎng)絡(luò)數(shù)據(jù)如表1所示。

表1 實驗所使用的網(wǎng)絡(luò)數(shù)據(jù)

實驗中，將每個算法在每個網(wǎng)絡(luò)上運行了100次，表2給出了實驗的結(jié)果，其中Qavg表示結(jié)果Q函數(shù)值的平均值，Qstd表示結(jié)果的標準差，并給出了平均運行時間。從結(jié)果中可以看到，通過對標簽初始化的改進，LPAs算法的結(jié)果穩(wěn)定性明顯好于LPA算法（平均方差更小），更意想不到的是在許多情況下算法發(fā)現(xiàn)的社區(qū)質(zhì)量也得到了一定程度的提升。而從時間消耗來看，LPAs算法的初始化過程也并沒有帶來太大的時間開銷，結(jié)果與原始LPA算法時間消耗相當。

表2 實驗結(jié)果

3 總論

通過改進標簽傳播算法的初始化過程，提出了一種更加穩(wěn)定的標簽傳播算法。在真實網(wǎng)絡(luò)上的實驗結(jié)果表明，提取的非重疊最小極大團可以很好地作為標簽傳播算法的初始標簽，不僅可以顯著提升算法的穩(wěn)定性，在許多情況下還能夠提高算法所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)的質(zhì)量。同時，算法也沒有帶來太多額外的時間開銷。

本文的改進主要針對標簽傳播的初始化問題，從實驗結(jié)果看，雖然算法的穩(wěn)定性得到了明顯提升，但在特殊情況下結(jié)果仍然具有不穩(wěn)定性。因此，如何從具體的傳播過程入手來進一步增強算法的穩(wěn)定性也是未來工作中一個具有研究價值和挑戰(zhàn)性的問題。

［1］ Watts D，Strogatz S．Collective dynamics of‘small－world’networks［J］．Nature，1998，393（6684）：440－442．

［2］ Barabasi A L，Albert R．Emergence of scaling in random networks［J］．Science，1999，286（5439）：509－512．

［3］ Newman M E J．Detecting community structure in networks［J］．The European Physical Journal B－Condensed Matter，2004，38（2）：321－330．

［4］ Girvan M，Newman M E J．Community structure in social and biological networks［J］．Proceedings of the National Academy of Sciences of the United States of America（PNAS），2002，99（12）：7821．

［5］ Blondel V D，Guillaume J L，Lambiotte R，et al．Fast unfolding of communities in large networks［J］．Journal of Statistical Mechanics：Theory and Experiment，2008，2008（10）：10008．

［6］ Rosvall M，Bergstrom C T．Maps of random walks on complex networks reveal community structure［J］．Proceedings of the National Academy of Sciences of the United States of America（PNAS），2008，105（4）：1118－1123．

［7］ Raghavan U，Albert R，Kumara S．Near linear time algorithm to detect community structures in large－scale networks．Physical Review E，2007，76（3）：036106．

［8］ Palla G，Derényi I，F(xiàn)arkas I，et al．Uncovering the overlapping community structure of complex networks in nature and society［J］．Nature，2005，435：814－818．

［9］ Newman M E J，Girvan M．Finding and evaluating community structure in networks．Physical Review E，2004，69（2）：026113．

［10］ Fortunato S，Barth？lemy M．Resolution limit in community detection［J］．．Proceedings of the National Academy of Sciences of the United States of America（PNAS），2007，104（1）：36－41．

［11］ Subelj L，Bajec M．Unfolding communities in large complex networks：Combining defensive and offensive label propagation for core extraction．Physical Review E，2011，83（3）：036103．

［12］ Leskovec J，Kleinberg J，F(xiàn)aloutsos C．Graph Evolution：Densification and Shrinking Diameters［J］．ACM Transactions on Knowledge Discovery from Data（ACM TKDD），2007，1（1）：242．