趙寶峰，趙菊敏，李燈熬

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

現(xiàn)實世界紛繁復(fù)雜，各種事物之間存在著普遍的聯(lián)系和彼此的依賴。許多這樣的復(fù)雜系統(tǒng)可以用復(fù)雜網(wǎng)絡(luò)來建模表示，并通過網(wǎng)絡(luò)分析與挖掘方法對系統(tǒng)進(jìn)行深入的研究。20世紀(jì)末，人類對復(fù)雜網(wǎng)絡(luò)的認(rèn)識有了突破性進(jìn)展，除了眾所周知的小世界特性［1］和無標(biāo)度特性［2］外，科學(xué)家們還發(fā)現(xiàn)各類復(fù)雜網(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ò)中的組織團(tuán)體、生物蛋白質(zhì)相互作用網(wǎng)絡(luò)中的蛋白復(fù)合體以及電路網(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等人提出，它通過割斷中介度指標(biāo)大的邊將網(wǎng)絡(luò)進(jìn)行分裂從而發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。BGLL算法［5］是一種基于模塊度指標(biāo)的貪心優(yōu)化算法，可以發(fā)現(xiàn)有層次的社區(qū)結(jié)構(gòu)。Infomap算法［6］是一種利用隨機(jī)游走和信息論的算法，是目前公認(rèn)的準(zhǔn)確率較高的一種算法。此外，在各種算法當(dāng)中，有一類具有接近線性時間復(fù)雜度的算法，稱為標(biāo)簽傳播算法［7］（Label Propagation Algorithm，LPA）。該算法的優(yōu)點是計算過程非常簡單，計算速度非常之快，但缺點是算法的穩(wěn)定性較差，連續(xù)幾次運行結(jié)果可能會很不相同。針對此問題，提出一種穩(wěn)定的標(biāo)簽傳播算法。該算法主要改進(jìn)了LPA算法的初始化過程，從而使算法結(jié)果更加穩(wěn)定。

1 算法

1．1 標(biāo)簽傳播算法介紹

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

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

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

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

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

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

1．2 非重疊最小極大團(tuán)提取算法

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

完全子圖是網(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ū)。因此，提出一種非重疊最小極大團(tuán)提取算法（DMMCA：Disjoint Minimal Maximal Clique Algorithm）來作為標(biāo)簽傳播的初始。算法描述如下：

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

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

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

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

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

2 實驗

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

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

實驗中，使用6個真實不同大小的網(wǎng)絡(luò)來測試改進(jìn)了初始化過程的標(biāo)簽傳播算法，實驗中記為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é)果的標(biāo)準(zhǔn)差，并給出了平均運行時間。從結(jié)果中可以看到，通過對標(biāo)簽初始化的改進(jìn)，LPAs算法的結(jié)果穩(wěn)定性明顯好于LPA算法（平均方差更?。?，更意想不到的是在許多情況下算法發(fā)現(xiàn)的社區(qū)質(zhì)量也得到了一定程度的提升。而從時間消耗來看，LPAs算法的初始化過程也并沒有帶來太大的時間開銷，結(jié)果與原始LPA算法時間消耗相當(dāng)。

表2 實驗結(jié)果

3 總論

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

本文的改進(jìn)主要針對標(biāo)簽傳播的初始化問題，從實驗結(jié)果看，雖然算法的穩(wěn)定性得到了明顯提升，但在特殊情況下結(jié)果仍然具有不穩(wěn)定性。因此，如何從具體的傳播過程入手來進(jìn)一步增強(qiáng)算法的穩(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．