陳俊宇　周　剛　南　煜　曾　琦

(數(shù)學(xué)工程與先進計算國家重點實驗室　鄭州　450002)(junychen1107@gmail.com)

?

一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法

陳俊宇周剛南煜曾琦

(數(shù)學(xué)工程與先進計算國家重點實驗室鄭州450002)(junychen1107@gmail.com)

摘要重疊社區(qū)發(fā)現(xiàn)是近年來復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究熱點之一.提出一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法SLEM(semi-supervised local expansion method).該方法借鑒了帶約束的半監(jiān)督聚類的思想，不僅利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息，還充分地利用網(wǎng)絡(luò)節(jié)點的屬性信息.首先將網(wǎng)絡(luò)節(jié)點的屬性信息轉(zhuǎn)化為成對約束，并根據(jù)成對約束修正網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，使網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)更加明顯；然后基于網(wǎng)絡(luò)節(jié)點的度中心性選取種子節(jié)點，得到分散的、局部節(jié)點度大的種子作為初始社區(qū)；再采用貪心策略將初始社區(qū)向鄰居節(jié)點擴展，得到局部連接緊密的社區(qū)；最后檢測并合并冗余社區(qū)，得到高覆蓋率的社區(qū)發(fā)現(xiàn)結(jié)果.在模擬網(wǎng)絡(luò)數(shù)據(jù)和真實網(wǎng)絡(luò)數(shù)據(jù)上與當(dāng)前有代表性的基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法進行了對比實驗，結(jié)果表明SLEM方法在稀疏程度不同的網(wǎng)絡(luò)上均能發(fā)現(xiàn)較高質(zhì)量的重疊社區(qū)結(jié)構(gòu).

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)；重疊社區(qū)發(fā)現(xiàn)；半監(jiān)督聚類；局部擴展；SLEM方法

網(wǎng)絡(luò)是事物之間相互關(guān)聯(lián)的一種模式，現(xiàn)實世界的很多系統(tǒng)都是由相互聯(lián)系的實體組成的，自然地以網(wǎng)絡(luò)的形式存在或者可以用網(wǎng)絡(luò)來表示[1].復(fù)雜網(wǎng)絡(luò)一般指節(jié)點眾多、連接關(guān)系復(fù)雜的網(wǎng)絡(luò)，能夠廣泛應(yīng)用于各科學(xué)領(lǐng)域?qū)?fù)雜系統(tǒng)進行建模和分析.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特性是繼小世界特性和無標度特性被發(fā)現(xiàn)后的又一個重要結(jié)構(gòu)特性.社區(qū)結(jié)構(gòu)普遍存在于現(xiàn)實網(wǎng)絡(luò)中，一般由功能相近或性質(zhì)相似的網(wǎng)絡(luò)節(jié)點組成，刻畫了節(jié)點間關(guān)系的局部聚集特性，其內(nèi)部的節(jié)點連接相對緊密，不同社區(qū)間的連接則相對稀疏[2].近年來，復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究熱點之一.社區(qū)發(fā)現(xiàn)有助于理解網(wǎng)絡(luò)的拓撲結(jié)構(gòu)及功能結(jié)構(gòu)，從而為利用和改造網(wǎng)絡(luò)提供指導(dǎo)，對分析網(wǎng)絡(luò)特性具有極為重要的意義[3].

早期對于社區(qū)發(fā)現(xiàn)的研究主要關(guān)注網(wǎng)絡(luò)中非重疊社區(qū)結(jié)構(gòu)，即假設(shè)每個節(jié)點屬于單一的社區(qū)，而現(xiàn)實世界中的真實社區(qū)結(jié)構(gòu)往往會產(chǎn)生交叉重疊.為此，不少重疊社區(qū)算法被提出用于解決網(wǎng)絡(luò)中重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的問題.這些方法可歸納為基于網(wǎng)絡(luò)局部拓撲信息和基于網(wǎng)絡(luò)全局拓撲信息的方法.

基于網(wǎng)絡(luò)局部拓撲信息的方法，是從網(wǎng)絡(luò)中的節(jié)點開始，利用節(jié)點的局部連接結(jié)構(gòu)信息采用優(yōu)化某種局部目標函數(shù)的策略，達到發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的目的.基于網(wǎng)絡(luò)局部拓撲信息的方法包括局部擴展法[4-6]和標簽(tag)傳播法[7-8]：局部擴展法從不同種子節(jié)點開始，探索種子所在的局部社區(qū)結(jié)構(gòu)，各個局部社區(qū)結(jié)構(gòu)融合形成網(wǎng)絡(luò)整體的重疊社區(qū)結(jié)構(gòu)；標簽傳播法初始給各節(jié)點分配唯一標簽，然后根據(jù)鄰居節(jié)點信息更新標簽直到收斂，最終標簽相同的節(jié)點被劃分到相同社區(qū).該類方法的優(yōu)勢在于有較高的時間效率，不足之處是其社區(qū)發(fā)現(xiàn)的效果不夠好.

基于網(wǎng)絡(luò)全局拓撲信息的方法，利用網(wǎng)絡(luò)的全部拓撲結(jié)構(gòu)，對某種全局目標函數(shù)進行優(yōu)化，以發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).基于網(wǎng)絡(luò)全局拓撲信息的方法包括派系過濾法[9-10]、非負矩陣分解法[11-14]以及基于統(tǒng)計模型的方法[15-17]：派系過濾法將社區(qū)視為由一些團(全連通子圖)構(gòu)成的集合，團之間通過共享節(jié)點而緊密連接；非負矩陣分解法對鄰接矩陣或其他特征矩陣進行分解得到各節(jié)點對于不同社區(qū)的參與度，該方法能夠定性和定量地評價節(jié)點對于社區(qū)的隸屬關(guān)系；基于統(tǒng)計模型的方法將網(wǎng)絡(luò)拓撲結(jié)構(gòu)作為觀測量，通過假設(shè)概率分布參數(shù)(通常與社區(qū)結(jié)構(gòu)有關(guān))計算節(jié)點之間的連接概率，最后生成整個網(wǎng)絡(luò)，對應(yīng)的參數(shù)即為節(jié)點隸屬于不同社區(qū)的概率.基于網(wǎng)絡(luò)全局信息的方法能夠得到較好的社區(qū)發(fā)現(xiàn)結(jié)果，但其時間開銷較大，不容易擴展到大規(guī)模網(wǎng)絡(luò).

盡管當(dāng)前學(xué)術(shù)界對重疊社區(qū)發(fā)現(xiàn)這一問題的研究已經(jīng)取得不少成果，隨著信息時代數(shù)據(jù)爆炸式地增長，真實網(wǎng)絡(luò)的結(jié)構(gòu)變得更加復(fù)雜，網(wǎng)絡(luò)的規(guī)模日趨龐大，因此重疊社區(qū)發(fā)現(xiàn)的難度也隨之變大[18-19].重疊社區(qū)發(fā)現(xiàn)仍然是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中一個值得深入研究的課題.

本文提出一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法——SLEM(semi-supervised local expansion method)，包括基于成對約束的網(wǎng)絡(luò)結(jié)構(gòu)修正、基于節(jié)點度中心性的種子選取、局部擴展式的自然社區(qū)發(fā)現(xiàn)以及社區(qū)結(jié)果的對比與合并.SLEM方法的主要貢獻有3點：

1) 利用部分標注信息指導(dǎo)社區(qū)發(fā)現(xiàn)算法的執(zhí)行，避免了傳統(tǒng)非監(jiān)督類算法的盲目性問題；

2) 基于節(jié)點度中心性的種子選取規(guī)則能夠得到局部性好、結(jié)構(gòu)穩(wěn)定的社區(qū)發(fā)現(xiàn)結(jié)果，避免了結(jié)果的抖動性問題；

3) 對社區(qū)結(jié)果的對比與合并能夠在保證高社區(qū)覆蓋率的前提下盡量減少冗余的社區(qū).

本文分別在基準模擬網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上對SLEM方法的性能進行測試，并同當(dāng)前具有代表性的基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法進行了對比分析，結(jié)果表明該方法在稀疏程度不同的網(wǎng)絡(luò)上均能發(fā)現(xiàn)較高質(zhì)量的重疊社區(qū)結(jié)構(gòu).

1相關(guān)工作

1.1基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)通?？捎蓤DG=(V,E)來表示，其中V={v1,v2,…,vn}表示節(jié)點的集合，n為節(jié)點個數(shù)；E={e1,e2,…,em}表示邊的集合，m為邊的條數(shù).復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)發(fā)現(xiàn)問題可以描述為找到圖G的一個劃分P=(C1,C2,…,CK)，滿足條件：

基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法，通常從不同種子節(jié)點開始，根據(jù)設(shè)定的某優(yōu)化函數(shù)，探索種子所在的局部社區(qū)結(jié)構(gòu)，各個局部社區(qū)結(jié)構(gòu)融合形成網(wǎng)絡(luò)整體的重疊社區(qū)結(jié)構(gòu).代表算法有LFM算法[4]和GCE算法[5].

1) LFM算法

LFM算法的基本思路是每次在網(wǎng)絡(luò)中隨機選取一個尚無社區(qū)標簽的節(jié)點作為種子，然后采用一種貪心的策略將種子擴展為一個局部自然社區(qū)，直到網(wǎng)絡(luò)中所有節(jié)點都有社區(qū)標簽為止.

在局部擴展的過程中，LFM算法通過不斷對當(dāng)前子圖增加或者刪除節(jié)點使得適應(yīng)度函數(shù)值達到局部最大值，其設(shè)定的適應(yīng)度函數(shù)(fitness function)為

(1)

具體地， LFM算法每一次迭代都會對當(dāng)前社區(qū)C添加一個節(jié)點使得適應(yīng)度函數(shù)達到最大，得到社區(qū)C′，然后重新計算C′內(nèi)所有節(jié)點的適應(yīng)度，刪除適應(yīng)度為負的節(jié)點，得到社區(qū)C″.重復(fù)執(zhí)行直到適應(yīng)度函數(shù)不再增大時停止.其中節(jié)點v的適應(yīng)度定義為

(2)

LFM算法隨機選取種子節(jié)點導(dǎo)致其存在社區(qū)發(fā)現(xiàn)結(jié)果依賴所選種子質(zhì)量的問題.該算法擴展策略的刪除節(jié)點操作可能會導(dǎo)致最初的種子節(jié)點被刪除，使得擴展過程不再圍繞該種子進行，違背社區(qū)的“局部性”[6,18].

2) GCE算法

GCE算法在整個算法執(zhí)行的初始階段，在網(wǎng)絡(luò)中找出所有節(jié)點規(guī)模不小于k的最大團(全連通子圖)作為種子；然后同樣采用貪心的策略對種子進行擴展得到局部自然社區(qū)，其設(shè)定的適應(yīng)度函數(shù)與LFM算法相同.

該算法在擴展的每一次迭代中僅添加使得適應(yīng)度函數(shù)最大的節(jié)點，得到社區(qū)C′.重復(fù)執(zhí)行直到適應(yīng)度函數(shù)不再增大，然后將此時的社區(qū)Ct同之前已檢測到的所有社區(qū)C1,C2,…,Ct-1按照距離計算公式：

(3)

計算二者的距離，如果δ小于某個給定的閾值ε則判定為相似，舍去Ct，否則保留Ct.

GCE算法選取的種子存在相似性，導(dǎo)致不同種子擴展得到非常相似甚至冗余的社區(qū).該算法在種子擴展的過程中由于存在社區(qū)刪除操作，會使得最終得到的所有社區(qū)只能覆蓋到整個網(wǎng)絡(luò)的一部分節(jié)點，而非整個網(wǎng)絡(luò)，即在算法執(zhí)行結(jié)束后存在一部分社區(qū)標簽仍然未知的節(jié)點.

1.2帶約束的半監(jiān)督聚類

機器學(xué)習(xí)中的聚類問題通常意義上講屬于非監(jiān)督學(xué)習(xí)的范疇，因為一般認為沒有已知標簽的數(shù)據(jù)點.但是當(dāng)對數(shù)據(jù)引入成對約束(pairwise constraints)，或者已知部分數(shù)據(jù)點有明確的簇類標簽時，這些信息能夠給聚類過程提供指導(dǎo)，從而提高聚類的效果，此時聚類就變成一個半監(jiān)督的學(xué)習(xí)問題[20-21].

成對約束通常包括必然連接(must-link)和不可能連接(cannot-link).必然連接表示一對數(shù)據(jù)點屬于同一個簇類，不可能連接表示一對數(shù)據(jù)點屬于不同的簇類.

對于一些實際應(yīng)用中的聚類問題，事先準確得到某一個數(shù)據(jù)點的簇類標簽是不現(xiàn)實的，因為在得到聚類結(jié)果前無法獲知數(shù)據(jù)集由哪些具體的簇類組成.然而，某一對數(shù)據(jù)點是否屬于同一個簇類，則可通過人工對這一對數(shù)據(jù)點進行簡單比較獲知.因此，成對約束信息相比于明確的數(shù)據(jù)標簽信息更容易獲得.

類似地，復(fù)雜網(wǎng)絡(luò)中的某一個節(jié)點的社區(qū)屬性是不可能提前被獲知的，而一對節(jié)點是否同時屬于一個社區(qū)則可通過網(wǎng)絡(luò)結(jié)構(gòu)以及節(jié)點的某些屬性信息進行判斷.因此，在復(fù)雜網(wǎng)絡(luò)中進行社區(qū)發(fā)現(xiàn)前，事先抽取一定數(shù)量的節(jié)點對，并人工對其進行標注，作為成對約束信息指導(dǎo)社區(qū)發(fā)現(xiàn)過程的執(zhí)行，可以避免無監(jiān)督社區(qū)發(fā)現(xiàn)方法的盲目性，使社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量得到提升.

2半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法

本文提出一種半監(jiān)督的局部擴展式的重疊社區(qū)發(fā)現(xiàn)方法，該方法綜合利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息和網(wǎng)絡(luò)節(jié)點屬性信息，首先根據(jù)網(wǎng)絡(luò)中的部分節(jié)點屬性信息對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行修正，然后利用網(wǎng)絡(luò)節(jié)點的拓撲特征(度中心性)選取種子節(jié)點作為初始社區(qū)，再采用貪心策略將種子擴展為局部自然社區(qū)，最后將不同社區(qū)進行對比與合并得到最終的社區(qū)發(fā)現(xiàn)結(jié)果.

2.1算法描述

1) 網(wǎng)絡(luò)結(jié)構(gòu)修正

社區(qū)發(fā)現(xiàn)問題傳統(tǒng)的解決方案僅僅是針對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)設(shè)計和執(zhí)行的.在現(xiàn)實網(wǎng)絡(luò)中，研究人員不但能夠得到整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，還能夠獲取網(wǎng)絡(luò)中節(jié)點的某些屬性，僅針對網(wǎng)絡(luò)拓撲結(jié)構(gòu)設(shè)計的社區(qū)發(fā)現(xiàn)算法忽略了大量的節(jié)點屬性信息.

因此，本文提出一種基于成對約束的網(wǎng)絡(luò)結(jié)構(gòu)修正算法.該算法的核心思想是先隨機選取網(wǎng)絡(luò)中的一個節(jié)點對，再利用這2個節(jié)點的信息將此節(jié)點對進行標注為必然連接或不可能連接，然后將此成對約束通過同網(wǎng)絡(luò)結(jié)構(gòu)融合，對網(wǎng)絡(luò)的結(jié)構(gòu)進行修正.

該算法的核心步驟是節(jié)點對的人工標注和成對約束與網(wǎng)絡(luò)結(jié)構(gòu)的融合.網(wǎng)絡(luò)中任意節(jié)點的屬性信息可由一些標簽組成的集合來表示，對隨機選取的一個節(jié)點對，若二者的標簽集合的交不為空，則表明這2個節(jié)點在某些屬性上具有相似性，然后人工地對這些共有屬性進行判斷，確定此對節(jié)點是否應(yīng)當(dāng)屬于相同的社區(qū).

(4)

其中,Aij為鄰接矩陣第i行第j列的元素值，修正權(quán)重β≥1.通過這種方式，將成對約束融合到網(wǎng)絡(luò)結(jié)構(gòu)中，實現(xiàn)對網(wǎng)絡(luò)結(jié)構(gòu)的修正.

整個執(zhí)行過程的偽代碼如下：

算法1. 基于成對約束的網(wǎng)絡(luò)結(jié)構(gòu)修正算法.

輸入：網(wǎng)絡(luò)G=(V,E)、權(quán)重β、節(jié)點對數(shù)量n；

①VertexPairs←?,count←0;

② whilecount

③ 從V×V中隨機選取(u,v);

④ if (u,v)不在VertexPairs中 then

⑤ 人工標注(u,v);

⑥ if (u,v)是必然連接 then

⑦e.weight←β;

⑧ else if (u,v)是不可能連接 then

⑨ 刪除e;

⑩ end if

這種基于成對約束的網(wǎng)絡(luò)結(jié)構(gòu)修正算法將傳統(tǒng)的無監(jiān)督社區(qū)發(fā)現(xiàn)轉(zhuǎn)化為半監(jiān)督社區(qū)發(fā)現(xiàn)，能夠較顯著地提升社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量.

2) 種子選取

對于大部分局部擴展式的重疊社區(qū)發(fā)現(xiàn)算法，種子的選取會影響其社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量[18].文獻[4]提出的LFM算法采用隨機選取種子的方法，不可避免地存在社區(qū)發(fā)現(xiàn)結(jié)果的不穩(wěn)定性.文獻[5]中的GCE算法則選取網(wǎng)絡(luò)中的最大團作為種子，最大團表示網(wǎng)絡(luò)中的全連通子圖，即其包含的節(jié)點兩兩互相連接.如圖1所示，節(jié)點集合{A,B,C}表示一個3-團，節(jié)點集合{A,B,C,D}表示一個4-團.

Fig. 1　Demonstration of maximal cliques.圖1　最大團示例

在給定的某個圖中，相對于節(jié)點而言，最大團所處的位置是固定的，這使得種子選取的過程更遵循規(guī)則，避免了社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題.

然而這種種子選取方法卻存在新的問題：1)引入了參數(shù)k，用于限制最大團的大小.較小的k會導(dǎo)致種子規(guī)模過大，使得社區(qū)的個數(shù)變大，不可避免地存在冗余社區(qū);較大的k則會導(dǎo)致社區(qū)個數(shù)小，社區(qū)發(fā)現(xiàn)結(jié)果的覆蓋率低，即存在一部分節(jié)點的社區(qū)屬性未知.2)不同的最大團之間存在相似性.例如圖1中節(jié)點集合{A,B,C,D}以及{A,B,C,E}都為4-團，而二者都包含子集{A,B,C}，因此這2個種子是相似的，這種相似性導(dǎo)致通過不同種子擴展得到的社區(qū)是相似的，甚至是完全相同的冗余社區(qū).

針對以上問題，本文提出選取網(wǎng)絡(luò)中的核心節(jié)點作為社區(qū)種子.在現(xiàn)實網(wǎng)絡(luò)中，核心節(jié)點對信息傳播的貢獻較大，通常位于網(wǎng)絡(luò)中節(jié)點連接較緊密的區(qū)域.社區(qū)內(nèi)部節(jié)點連接緊密，不同社區(qū)間節(jié)點連接稀疏，故網(wǎng)絡(luò)中不同的社區(qū)恰好可同一部分互不鄰接的、分散的核心節(jié)點形成一一對應(yīng)，因而可選取網(wǎng)絡(luò)中的一部分核心節(jié)點作為種子.核心節(jié)點可通過多種節(jié)點中心性指標定義，本文考慮其中最簡單的節(jié)點度中心性作為核心節(jié)點的特征指標.整個種子選取過程的偽代碼如下：

算法2. 種子選取算法.

輸入：網(wǎng)絡(luò)G=(V,E)；

輸出：種子集合S.

①S←?;

②V中所有節(jié)點初始化為無標記;

③ whileV≠? do

⑤ forMaxDegreeSet中所有的vido

⑥ ifvi無標記 then

⑦ 設(shè)置vi的標記為i;

⑧S←S∪{vi};

⑨ end if

⑩ 設(shè)置vi的鄰居節(jié)點N(vi)標記為vi.label;

考慮到網(wǎng)絡(luò)中可能存在若干個節(jié)點同時滿足度最大的情況，算法2每輪迭代都會找出當(dāng)前節(jié)點集合V中所有度最大節(jié)點構(gòu)成的集合MaxDegreeSet，然后依次將點vi以及其鄰居節(jié)點N(vi)作標記，再將vi加入種子集合S中，最后從節(jié)點集合V中移除已標記的節(jié)點集{vi}∪N(vi).

對于一對節(jié)點vi和vj同時為度最大節(jié)點且相鄰接的情況，算法2在處理vi的過程中會用vi的索引值i對vj進行標記，在處理vj時vj是已被標注的節(jié)點，此時只用vj的標簽i對其鄰居節(jié)點進行標記，整個過程僅選取其中點vi作為種子加入到集合S中.

此種子選取策略的好處是能夠在網(wǎng)絡(luò)中發(fā)掘彼此分散的、局部節(jié)點度數(shù)大(即節(jié)點的度數(shù)相對于其鄰居節(jié)點的度數(shù)較大)的節(jié)點，通過這些節(jié)點擴展得到的自然社區(qū)的局部性好，社區(qū)發(fā)現(xiàn)結(jié)果對全網(wǎng)絡(luò)的覆蓋率高.

3) 局部擴展發(fā)現(xiàn)自然社區(qū)

類似文獻[4-5]中的LFM和GCE算法，本文采用貪心的策略對種子進行擴展得到相應(yīng)的社區(qū).

在局部目標函數(shù)的構(gòu)造上，由于本文在整個算法第一階段對網(wǎng)絡(luò)中的連接進行修正，原始的無權(quán)網(wǎng)絡(luò)G=(V,E)轉(zhuǎn)變?yōu)榧訖?quán)網(wǎng)絡(luò)G=(V,E,W)，因此需要對式(1)進行修正.

定義2. 給定無向加權(quán)網(wǎng)絡(luò)G=(V,E,W)，?vi∈G，定義vi的加權(quán)節(jié)點度di為與vi所有連邊權(quán)重之和，即：

(5)

其中,N(vi)表示節(jié)點vi所有鄰居節(jié)點構(gòu)成的集合.容易得到對于無權(quán)網(wǎng)絡(luò)，連接的權(quán)重可視為1，此時式(5)等價于di=ki，即為vi的節(jié)點度.

定義3. 對于網(wǎng)絡(luò)G=(V,E)的某個子圖(即社區(qū))C?G，社區(qū)C的鄰居N(C)定義為

(6)

也可由節(jié)點鄰居的定義推廣得到：

(7)

即社區(qū)C中所有節(jié)點的不在C中的鄰居構(gòu)成的集合.

定義4. 對于加權(quán)網(wǎng)絡(luò)G=(V,E,W)中的某個社區(qū)C?G，社區(qū)C的適應(yīng)度f(C)定義為

(8)

(9)

由種子向局部擴展成為社區(qū)的策略與LFM算法類似，也是通過對當(dāng)前社區(qū)C增加或者刪除節(jié)點使得社區(qū)的適應(yīng)度函數(shù)f(C)達到最大值.對某個給定種子節(jié)點s，其擴展為社區(qū)的執(zhí)行過程的偽代碼如算法3所示：

算法3. 種子擴展成社區(qū).

輸入：網(wǎng)絡(luò)G=(V,E,W)、種子s、參數(shù)α；

輸出：社區(qū)C.

①C←{s};

②flag_1=0;

③ whileflag_1=0 do

④ for 對C的鄰居節(jié)點集N(C)中所有

neighbordo

⑤ 計算f(neighbor);

⑥ end for

⑧ iff(v)<0 then

⑨flag_1=1;

⑩ else iff(v)≥0 then

可以看出，在每一輪迭代中都涉及到社區(qū)的更新，考慮到重新計算所有社區(qū)內(nèi)節(jié)點以及社區(qū)鄰居節(jié)點的適應(yīng)度會增大計算開銷，本文在算法3的實現(xiàn)中，對社區(qū)的內(nèi)、外加權(quán)度數(shù)和進行更新為

(10)

(11)

然后再按照式(8)對社區(qū)適應(yīng)度進行計算.

另外，在此種擴展策略下，參數(shù)α實際上能夠控制社區(qū)C的大小，故稱α為分辨率參數(shù)：

4) 社區(qū)的對比與合并

非重疊社區(qū)發(fā)現(xiàn)問題要求不同社區(qū)的節(jié)點集是彼此互斥的，而重疊社區(qū)發(fā)現(xiàn)問題允許2個不同社區(qū)包含一些公共的節(jié)點，因此社區(qū)之間存在一定的相似性.當(dāng)相似性達到一定程度時，則會出現(xiàn)“過度重疊”的現(xiàn)象，產(chǎn)生冗余的社區(qū)[5-6].因此有必要對社區(qū)發(fā)現(xiàn)結(jié)果進行后處理，發(fā)現(xiàn)冗余社區(qū)，簡化社區(qū)結(jié)構(gòu).

類似GCE算法，本文采用式(3)計算不同社區(qū)間的距離.與其不同的是，本文在整個社區(qū)發(fā)現(xiàn)算法執(zhí)行結(jié)束后再對社區(qū)結(jié)果進行處理.

具體地，對2個不同社區(qū)C1和C2，將由式(3)計算得到的距離δ(C1,C2)同設(shè)定的參數(shù)閾值ε進行比較.若δ(C1,C2)<ε，則認為C1和C2是相似的，保留C1∪C2作為一個社區(qū)；若δ(C1,C2)≥ε，則保留C1和C2這2個社區(qū).

2.2方法時間復(fù)雜度分析

3實驗結(jié)果與分析

本文分別在模擬網(wǎng)絡(luò)數(shù)據(jù)和真實網(wǎng)絡(luò)數(shù)據(jù)上對SLEM方法的性能進行驗證，并同2種當(dāng)前有代表性的LFM算法[4]和GCE算法[5]進行對比，二者都是基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法.另外，為驗證基于成對約束的網(wǎng)絡(luò)結(jié)構(gòu)修正算法對傳統(tǒng)非監(jiān)督的局部擴展式方法的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的提升效果，本文還將SLEM方法同樸素局部擴展方法(naive local expansion method， NLEM)進行了對比實驗.

3.1在模擬網(wǎng)絡(luò)數(shù)據(jù)集上的實驗

1) LFR基準測試網(wǎng)絡(luò)介紹

通過對LFR模型參數(shù)的調(diào)節(jié)，可以得到不同的拓撲結(jié)構(gòu)性質(zhì)逼近真實網(wǎng)絡(luò)的模擬網(wǎng)絡(luò)數(shù)據(jù).此外，LFR模型還能夠生成網(wǎng)絡(luò)節(jié)點的社區(qū)劃分，便于算法發(fā)現(xiàn)的社區(qū)劃分結(jié)果同生成的社區(qū)結(jié)構(gòu)進行對比，驗證算法結(jié)果的準確性和算法的性能.

2) 社區(qū)發(fā)現(xiàn)結(jié)果評價指標

對于LFR基準測試網(wǎng)絡(luò)，由于其社區(qū)結(jié)構(gòu)已知，重點比較不同社區(qū)發(fā)現(xiàn)算法的結(jié)果與LFR網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)之間的相似程度.這種比較基于信息論的思想，采用規(guī)范互信息(normalized mutual information, NMI)指標[4]來度量.

(12)

X對Y的規(guī)范化條件熵為

(13)

類似可計算出Y對X的規(guī)范化條件熵H(Y|X)，則規(guī)范化互信息可計算為

(14)

此評價指標NMI(X|Y)的取值范圍為0～1，當(dāng)NMI(X|Y)=1時，X與Y完美匹配.

3) 實驗結(jié)果比較

實驗根據(jù)N∈{1 000,5 000}和μ∈{0.1,0.3}生成4組不同節(jié)點規(guī)模和混合參數(shù)的LFR基準測試網(wǎng)絡(luò)，其中每組LFR網(wǎng)絡(luò)的參數(shù)Om∈[2,8]，即每組包含7個重疊程度不同的網(wǎng)絡(luò)數(shù)據(jù)集.其他參數(shù)設(shè)置相同的值：平均節(jié)點度k=10；最大節(jié)點度kmax=50；冪律分布指數(shù)τ1=-2,τ2=-1；重疊節(jié)點個數(shù)On=0.1N；社區(qū)大小的上下界cmin=20,cmax=100.

由于LFR模型能夠生成網(wǎng)絡(luò)節(jié)點的社區(qū)劃分，本實驗將LFR網(wǎng)絡(luò)中節(jié)點的屬性信息對應(yīng)的標簽集合抽象為該節(jié)點所屬社區(qū)的ID編號組成的集合，對從網(wǎng)絡(luò)中隨機選取的2個節(jié)點，若二者標簽集合的交不為空，則表明這2個節(jié)點屬于相同社區(qū)，從而標注該節(jié)點對為必然連接，否則標注為不可能連接.

實驗對于不同算法設(shè)置不同的參數(shù)，并選取各參數(shù)下NMI值中的最大值作為最終結(jié)果進行對比.具體地，對于LFM算法，與文獻[4]相同，設(shè)置其參數(shù)α∈[0.8,1.6]，取值間隔為0.1，運行次數(shù)r=3；對于GCE算法，與文獻[5]相同，設(shè)置其參數(shù)k∈{3,4}，參數(shù)α∈[0.8,1.6]，取值間隔為0.1，參數(shù)ε=0.6；SLEM方法中，設(shè)置參數(shù)n=0.05N(N-1)2，設(shè)置β=1，參數(shù)α∈[0.6,1.2]，ε∈[0,0.9]，取值間隔均為0.1；NLEM算法不需要設(shè)置參數(shù)n和β，其他參數(shù)設(shè)置與SLEM方法相同.

各種算法在4組不同LFR基準測試網(wǎng)絡(luò)下社區(qū)發(fā)現(xiàn)結(jié)果的NMI值如圖2所示，其中橫軸坐標表示重疊節(jié)點所屬社區(qū)個數(shù)Om，縱軸坐標表示相應(yīng)的NMI值.

Fig. 2　Experimental results on LFR networks.圖2　LFR網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果

整體上看，隨著重疊節(jié)點所屬社區(qū)個數(shù)Om的增加，社區(qū)發(fā)現(xiàn)的難度越來越大，導(dǎo)致4種算法的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量逐漸降低，因此在所有網(wǎng)絡(luò)上這4種算法得到的NMI值呈現(xiàn)下降的趨勢.

當(dāng)固定混合參數(shù)為μ時，隨著節(jié)點數(shù)N從1 000增加到5 000，4種算法得到的NMI值基本保持穩(wěn)定.這是因為基于局部擴展的方法僅從網(wǎng)絡(luò)中的某個種子出發(fā)，探索其局部自然社區(qū)，并且探索的策略和過程僅與包含該種子的某個子圖有關(guān)，與整個網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)無關(guān).這表明基于局部擴展的重疊社區(qū)發(fā)現(xiàn)方法對網(wǎng)絡(luò)的規(guī)模表現(xiàn)出一定的魯棒性.

當(dāng)固定節(jié)點數(shù)為N時，隨著混合參數(shù)μ從0.1增加到0.3，網(wǎng)絡(luò)中社區(qū)的內(nèi)部節(jié)點連接社區(qū)外部節(jié)點的機會增大，導(dǎo)致社區(qū)的結(jié)構(gòu)變得模糊，因此4種算法得到的NMI值都有不同程度的下降.其中NLEM和LFM算法相對于GCE算法的降幅更大.這表明在社區(qū)結(jié)構(gòu)較不明顯的網(wǎng)絡(luò)中，基于團的種子選取表現(xiàn)出一定優(yōu)勢.

比較圖2中NLEM算法與LFM算法的曲線可以看出，NLEM算法在絕大多數(shù)網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果較明顯地好于LFM算法.這是因為NLEM算法選取網(wǎng)絡(luò)中的核心節(jié)點作為種子，擴展得到的社區(qū)具有更好的局部性；而LFM算法隨機選取種子，其在擴展過程中可能因為某些種子的適應(yīng)度函數(shù)值為負而被刪除，導(dǎo)致社區(qū)的擴展過程不再圍繞該種子進行，最終得到局部性較差的社區(qū)[6,18].

比較圖2中SLEM方法與GCE算法的曲線可以看出，SLEM方法的社區(qū)發(fā)現(xiàn)結(jié)果略好于GCE算法，特別在重疊節(jié)點所屬社區(qū)個數(shù)2≤Om≤5時，SLEM方法社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量表現(xiàn)出一定優(yōu)勢.這是因為SLEM方法對社區(qū)發(fā)現(xiàn)結(jié)果進行了后處理，將冗余的社區(qū)合并而不是直接舍棄，保持網(wǎng)絡(luò)社區(qū)高覆蓋率，更符合社區(qū)的真實情況;而GCE算法則會存在一部分社區(qū)標簽仍然未知的節(jié)點，導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量較低.

比較圖2中SLEM方法與NLEM算法的曲線可以看出，在網(wǎng)絡(luò)的混合參數(shù)較低(μ=0.1)時，二者得到的NMI值非常接近.這是因為此時網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)較為明顯，非監(jiān)督的NLEM重疊社區(qū)發(fā)現(xiàn)方法能夠較準確地發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū).當(dāng)網(wǎng)絡(luò)的混合參數(shù)較高(μ=0.3)時，NLEM算法得到的NMI值大幅下降，這時網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)不明顯，非監(jiān)督的方法又存在一定盲目性，故得到的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量降低；而此時半監(jiān)督的SLEM方法則表現(xiàn)出明顯優(yōu)勢，這是因為其利用少量的成對約束對網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行了修正，使整個社區(qū)發(fā)現(xiàn)過程在這些約束信息的指導(dǎo)下完成，因而能夠發(fā)現(xiàn)更高質(zhì)量的社區(qū).另外，可以觀察到隨著網(wǎng)絡(luò)中重疊節(jié)點所屬社區(qū)個數(shù)Om逐漸增大，SLEM方法和NLEM算法的NMI值差距逐漸縮小.這表明當(dāng)社區(qū)結(jié)構(gòu)的重疊程度變大時，社區(qū)發(fā)現(xiàn)的難度變大，需要增加成對約束的數(shù)量才能保持社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的顯著提升.

綜上，SLEM方法相對于NLEM算法、LFM算法和GCE算法在LFR基準測試網(wǎng)絡(luò)上能夠得到較高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果.

3.2在真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗

1) 真實網(wǎng)絡(luò)數(shù)據(jù)介紹

實驗在8個不同規(guī)模、不同類型的真實網(wǎng)絡(luò)數(shù)據(jù)集上對算法的性能進行了對比驗證.這些真實網(wǎng)絡(luò)數(shù)據(jù)包括人物關(guān)系網(wǎng)絡(luò)(Zachary，Lesmis，F(xiàn)ootball，PGP)、動物關(guān)系網(wǎng)絡(luò)(Dolphins)、論文合作網(wǎng)絡(luò)(CA-GrQc)、文件共享網(wǎng)絡(luò)(P2P)以及產(chǎn)品銷售記錄網(wǎng)絡(luò)(Amazon)，基本信息如表1所示.更多信息可在http:www-personal.umich.edu～mejnnetdata以及 http:snap.stanford.edudata上找到.

Table 1　Real World Network Datasets

2) 社區(qū)發(fā)現(xiàn)結(jié)果評價指標

對于真實網(wǎng)絡(luò)數(shù)據(jù)，由于其實際社區(qū)結(jié)構(gòu)是未知的，無法直接將社區(qū)發(fā)現(xiàn)結(jié)果與真實社區(qū)進行對比.實驗采用重疊模塊度(overlapping modularity，記為Qov)、社區(qū)連接密度(community link density, 記為Dav)和網(wǎng)絡(luò)覆蓋率(network cover rate, 記為Rcv)這3種指標對算法的性能進行驗證.

重疊模塊度[18]是將模塊度[23](modularity，記為Q)的概念推廣到重疊社區(qū)發(fā)現(xiàn)問題的一種被普遍用于驗證重疊社區(qū)發(fā)現(xiàn)算法性能的指標.模塊度能夠度量劃分得到的社區(qū)結(jié)構(gòu)的穩(wěn)定性，其定義如下：

(15)

(16)

其中,m為網(wǎng)絡(luò)中總邊數(shù)，K為社區(qū)個數(shù)，Aij為鄰接矩陣第i行第j列的元素值，di為節(jié)點vi的度，Oi為節(jié)點vi所屬社區(qū)的個數(shù).可以看出對于非重疊社區(qū)劃分，?vi∈V有Oi=1，此時Q=Qov.

根據(jù)社區(qū)的定義，社區(qū)內(nèi)部節(jié)點之間的連接較緊密，不同社區(qū)間的連接相對稀疏[2].社區(qū)內(nèi)部的連接密度越大，表明社區(qū)的結(jié)構(gòu)越明顯.社區(qū)連接密度定義為

(17)

社區(qū)發(fā)現(xiàn)的目標是找出網(wǎng)絡(luò)中每個節(jié)點所屬的一個或多個社區(qū).這對于基于局部擴展的重疊社區(qū)發(fā)現(xiàn)方法是一種比較理想的目標，在實際情況中此類算法在執(zhí)行結(jié)束后會存在一部分社區(qū)標簽仍然未知的節(jié)點，算法的實際目標是使發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)覆蓋到網(wǎng)絡(luò)中盡可能多的節(jié)點.因此針對基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法性能的驗證，本文還引入網(wǎng)絡(luò)覆蓋率作為驗證社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的指標.其定義為

(18)

其中,N為網(wǎng)絡(luò)中節(jié)點總數(shù)，K為社區(qū)個數(shù)，Ck表示第k個社區(qū).

以上3種評價指標的取值范圍均為0～1，值越大表明社區(qū)發(fā)現(xiàn)的結(jié)果質(zhì)量越好.

3) 實驗結(jié)果比較

對于需要設(shè)置參數(shù)的算法，其參數(shù)的設(shè)置與3.1節(jié)相同，并選取各參數(shù)下的最好結(jié)果進行對比.

特別地，對于SLEM方法，由于所選數(shù)據(jù)集僅包含網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息，無法直接對節(jié)點對進行標注.實驗采用Infomap算法[24]對網(wǎng)絡(luò)數(shù)據(jù)進行社區(qū)發(fā)現(xiàn)，再以此結(jié)果為依據(jù)選取5%的節(jié)點對作為成對約束.Infomap算法是一種非重疊社區(qū)發(fā)現(xiàn)算法，Lancichinetti等人[25]對比了多種非重疊社區(qū)發(fā)現(xiàn)算法，指出Infomap算法在時間效率和結(jié)果質(zhì)量上均優(yōu)于其他算法.類似1.3節(jié)中在虛擬網(wǎng)絡(luò)上實驗的標注方式，將網(wǎng)絡(luò)中各節(jié)點的屬性信息對應(yīng)的標簽抽象成該節(jié)點在Infomap算法下所屬社區(qū)的ID編號，對隨機選取的一個節(jié)點對，若二者在Infomap算法結(jié)果中屬于同一社區(qū)，則將其標注為必然連接，否則標注為不可能連接.

各種算法在8個真實網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的評價值如圖3所示，其中橫軸表示節(jié)點規(guī)模隨坐標遞增的真實網(wǎng)絡(luò)數(shù)據(jù)集，縱軸表示不同算法在對應(yīng)數(shù)據(jù)集上社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的評價值.

不同算法在真實網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)結(jié)果對應(yīng)的重疊模塊度如圖3(a)所示.可以看出SLEM方法在大部分真實網(wǎng)絡(luò)上得到的重疊模塊度是最好的，或與LFM算法的結(jié)果相當(dāng)，二者較NLEM算法和GCE算法表現(xiàn)出一定優(yōu)勢，表明SLEM方法能夠得到質(zhì)量較高的重疊社區(qū)結(jié)構(gòu).這是由于SLEM方法根據(jù)成對約束對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行了修正，使得網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)更加明顯，進而使算法結(jié)果的質(zhì)量得到有效提高.

Fig. 3　Experimental results on real world networks.圖3　真實網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果

從圖3(b)可看出，SLEM方法在所有真實數(shù)據(jù)集上都取得最高的社區(qū)連接密度，NLEM算法次之，LFM算法得到的社區(qū)連接密度最低.這是由于SLEM方法和NLEM算法的種子節(jié)點選取方法好于LFM算法隨機選取的方法，使得社區(qū)擴展的過程圍繞所選取的種子進行，從而得到局部性較好的社區(qū)，即種子所在社區(qū)的內(nèi)部節(jié)點連接相對于不同社區(qū)之間的節(jié)點連接更加稠密，這更符合社區(qū)的一般定義.

圖3(c)展示出SLEM方法、NLEM算法和LFM算法在不同網(wǎng)絡(luò)上均能夠得到較高、較穩(wěn)定的網(wǎng)絡(luò)覆蓋率，而GCE算法的結(jié)果較差且波動性大.LFM算法每一個社區(qū)的種子總是從尚無社區(qū)標簽的節(jié)點中隨機選取，故在算法結(jié)束時僅剩余極小部分社區(qū)標簽不明確的節(jié)點(文獻[4]稱之為homeless node)，因此LFM算法得到的社區(qū)覆蓋率最高.SLEM方法和NLEM算法選取的種子之間的相似性相對于GCE算法更低，在網(wǎng)絡(luò)中的分布更加分散，因此擴展得到的社區(qū)能夠覆蓋到網(wǎng)絡(luò)中較多的節(jié)點，即便出現(xiàn)冗余社區(qū)的情況，SLEM方法和NLEM算法也是將二者合并，以保持網(wǎng)絡(luò)的高覆蓋率.實驗進一步對3種評價指標對應(yīng)的社區(qū)發(fā)現(xiàn)結(jié)果進行融合，以綜合評價4種方法和算法的性能.具體地，先對各方法、算法在每個網(wǎng)絡(luò)得到的每個指標的評價值進行規(guī)范化，即賦每組數(shù)據(jù)的最大值為1，其余賦值為原始值占最大值的比值；再將不同指標的規(guī)范化評價值相加得到最終的綜合評價值，綜合評價值的取值范圍是0～3.不同方法、算法在稀疏程度不同的網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的綜合評價值如圖3(d)所示.

整體上看，SLEM方法的綜合評價值最高，NLEM算法和LFM算法的結(jié)果相當(dāng)，GCE算法的結(jié)果相對較低.4種算法的綜合結(jié)果存在不同程度的波動性，其中SLEM方法的結(jié)果波動程度相對較小，LFM算法和GCE算法的結(jié)果隨網(wǎng)絡(luò)稀疏程度的增加呈上升趨勢.這表明SLEM方法在稀疏程度不同的網(wǎng)絡(luò)上均能夠取得高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果；而LFM算法和GCE算法僅能夠在較稠密的網(wǎng)絡(luò)上取得較高質(zhì)量的社區(qū)結(jié)構(gòu)，而在較稀疏網(wǎng)絡(luò)上結(jié)果較差.例如GCE算法在平均節(jié)點度為2.4的P2P網(wǎng)絡(luò)數(shù)據(jù)上僅發(fā)現(xiàn)到1個規(guī)模為310個節(jié)點的社區(qū)，其余節(jié)點的所屬社區(qū)標簽均未知，其重疊模塊度為0，社區(qū)連接密度為0.48，網(wǎng)絡(luò)覆蓋率不足0.005.

綜上，SLEM方法在稀疏程度不同的真實網(wǎng)絡(luò)數(shù)據(jù)上均能取得較高質(zhì)量社區(qū)發(fā)現(xiàn)結(jié)果.

3.3SLEM方法參數(shù)的選取

與LFM，GCE算法相同，SLEM方法的社區(qū)發(fā)現(xiàn)結(jié)果依賴于參數(shù)的選取.SLEM方法需要設(shè)置的參數(shù)包括節(jié)點對數(shù)目n、社區(qū)結(jié)構(gòu)修正權(quán)重β、分辨率參數(shù)α以及社區(qū)距離閾值ε.本節(jié)通過理論證明和實驗分析，討論這些參數(shù)的選取規(guī)則.

參數(shù)n和β的設(shè)置是依賴于數(shù)據(jù)的，即需要根據(jù)網(wǎng)絡(luò)數(shù)據(jù)集的具體實際情況選取.設(shè)置這2個參數(shù)的目的是利用有限的成對約束盡可能大程度地修正網(wǎng)絡(luò)的結(jié)構(gòu)，從而提升社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量.為度量網(wǎng)絡(luò)結(jié)構(gòu)的修正效果，定義修正貢獻的概念：

(19)

由上述定義可知，當(dāng)|Con(i,j)|>0時，成對約束(i,j)對網(wǎng)絡(luò)結(jié)構(gòu)產(chǎn)生修正的效果.

給定參數(shù)n和β，所有成對約束對網(wǎng)絡(luò)結(jié)構(gòu)的修正貢獻的總和為

s×|β|+t×|β-1|+p×0+q×|-1|=

(20)

其中,s=|SML-E|，t=|SML∩E|，p=|SCL-E|，q=|SCL∩E|，滿足n=s+t+p+q.

通過式(20)可知，當(dāng)成對約束集合SML和SCL固定時，式(20)中β的系數(shù)s+t固定，修正貢獻總和Con隨β線性遞增.因此當(dāng)網(wǎng)絡(luò)數(shù)據(jù)集僅包含小部分(如不足1%)節(jié)點的屬性信息時，參數(shù)n只能取較小的值(n<10-4N(N-1)2)，此種情況下，為盡可能大地修正網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，修正權(quán)重β就應(yīng)當(dāng)設(shè)置較大的值(如β≥2)，否則整個修正過程對最終的社區(qū)結(jié)果的質(zhì)量提升不明顯；當(dāng)網(wǎng)絡(luò)數(shù)據(jù)集包含較多節(jié)點的屬性信息時，這些節(jié)點自然能夠組合更多的節(jié)點對，參數(shù)n可取較大的值，此時選取β=1即可顯著提升社區(qū)結(jié)果的質(zhì)量，否則會增加不必要的計算開銷.對于LFR基準測試網(wǎng)絡(luò)，其節(jié)點社區(qū)屬性已知，本實驗選取n=0.05N(N-1)2，β=1，相對于NLEM算法，社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量提升是顯著的,如圖2所示.

參數(shù)α和ε的選取則是依賴于結(jié)果的，即可以通過人工調(diào)節(jié)，選取評價值最好的社區(qū)發(fā)現(xiàn)結(jié)果對應(yīng)的參數(shù)值.本實驗設(shè)置參數(shù)α∈[0.6,1.2]，ε∈[0,0.9]，取值間隔均為0.1，圖4以4組參數(shù)不同的LFR網(wǎng)絡(luò)數(shù)據(jù)中Om=2的數(shù)據(jù)集為例，展示出各參數(shù)值對應(yīng)的社區(qū)發(fā)現(xiàn)結(jié)果的NMI值.

圖4(a)(b)分別展示了最高NMI值隨參數(shù)α和ε值的變化曲線.從圖4(a)可以看出，社區(qū)發(fā)現(xiàn)結(jié)果的NMI值隨參數(shù)α的增大呈先增后減的趨勢，在區(qū)間α∈[0.7,0.8]取到極大值.對于混合參數(shù)較小的網(wǎng)絡(luò)(μ=0.1)，NMI在α=0.7處達到極大值；對于混合參數(shù)較大的網(wǎng)絡(luò)(μ=0.3)，NMI在α=0.8處達到極大值.從圖4(b)可看出，在混合參數(shù)μ=0.1的網(wǎng)絡(luò)上，社區(qū)發(fā)現(xiàn)結(jié)果的NMI值在整個區(qū)間ε∈[0,0.9]上保持平穩(wěn)，在ε=0.6處取極大值；在混合參數(shù)μ=0.3的網(wǎng)絡(luò)上，除去區(qū)間的2個端點外，NMI值基本保持不變，在ε=0處和ε=0.9處分別取極大值和極小值.

Fig. 4　NMI value with different parameters on LFR benchmarks.圖4　LFR網(wǎng)絡(luò)上不同參數(shù)對應(yīng)的NMI值

綜上，對于LFR基準測試網(wǎng)絡(luò)中Om=2的4個網(wǎng)絡(luò)數(shù)據(jù)集，當(dāng)μ=0.1時，選取參數(shù)α=0.7，ε=0.6；當(dāng)μ=0.3時，選取參數(shù)α=0.8，ε=0.在實際應(yīng)用中，對于參數(shù)α，可先求出SLEM方法在α=α0∈[0.7,0.8]的結(jié)果，再求出算法在α0附近的結(jié)果，進行比較得到最優(yōu)的參數(shù)值；對于參數(shù)ε，可先求出SLEM方法在區(qū)間[0,0.9]兩端點的結(jié)果，比較二者的差異，若差值較大，則在較大結(jié)果對應(yīng)的點附近繼續(xù)計算再作比較，反之則在二者的中值點附近繼續(xù)查找最優(yōu)參數(shù)值.

4結(jié)束語

本文提出一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法——SLEM.該方法除利用網(wǎng)絡(luò)數(shù)據(jù)的拓撲結(jié)構(gòu)信息外，還根據(jù)部分節(jié)點屬性信息對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行修正，相對于傳統(tǒng)的非監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法，其社區(qū)發(fā)現(xiàn)過程是在成對約束的監(jiān)督下執(zhí)行的.此外，該方法采用更規(guī)則化的種子選取方式，使種子擴展得到的社區(qū)結(jié)構(gòu)質(zhì)量更好.對社區(qū)發(fā)現(xiàn)結(jié)果的后處理能夠減少冗余社區(qū)，同時保持社區(qū)的高覆蓋率.通過在LFR基準測試網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗，結(jié)果表明SLEM方法相對于當(dāng)前有代表性的LFM，GCE算法能夠在稀疏程度不同的網(wǎng)絡(luò)上取得較好社區(qū)發(fā)現(xiàn)結(jié)果.最后對SLEM方法參數(shù)的選取進行了討論分析，并總結(jié)出較合理的、可行的參數(shù)選取經(jīng)驗和方法.

此外，實驗發(fā)現(xiàn)在原始網(wǎng)絡(luò)中不相鄰接的且被標注為不可能連接的節(jié)點對數(shù)量占全部所選節(jié)點對的比例達到90%以上，而這類成對約束對網(wǎng)絡(luò)結(jié)構(gòu)沒有修正作用，導(dǎo)致人工標注的效率較低.下一步工作將對節(jié)點對的選取規(guī)則以及節(jié)點對的標注方法進行深入研究，在提升社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的同時提高人工標注的效率，避免人力的浪費.

參考文獻

[1]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256

[2]Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174

[3]Liu Dayou, Jin Di, He Dongxiao, et al. Community mining in complex networks[J]. Journal of Computer Research and Development, 2013, 50(10): 2140-2154 (in Chinese)(劉大有, 金弟, 何東曉, 等. 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J]. 計算機研究與發(fā)展, 2013, 50(10): 2140-2154)

[4]Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3): 033015

[5]Lee C, Reid F, McDaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[EB/OL]. 2010 [2014-11-10]. http://arXiv.org/abs/1002.1827

s[6]Havemann F, Heinz M, Struck A, et al. Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels[J]. Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011(1): P01023

[7]Gregory S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10): 103018

[8]Xie J, Szymanski B K. Towards Linear Time Overlapping Community Detection in Social Networks[M]. Berlin: Springer, 2012: 25-36

[9]Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818

[11]Psorakis I, Roberts S, Ebden M, et al. Overlapping community detection using Bayesian non-negative matrix factorization[J]. Physical Review E, 2011, 83(6): 066114

[12]Zhang Y, Yeung D Y. Overlapping community detection via bounded nonnegative matrix tri-factorization[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining (SIGKDD’12). New York: ACM, 2012: 606-614

[13]Yang J, Leskovec J. Overlapping community detection at scale: A nonnegative matrix factorization approach[C] //Proc of the 6th Int Conf on Web Search and Data Mining (WSDM’13). New York: ACM, 2013: 587-596

[14]Zhang Z Y, Wang Y, Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87(6): 062803

[15]Ball B, Karrer B, Newman M E J. Efficient and principled method for detecting communities in networks[J]. Physical Review E, 2011, 84(3): 036103

[16]Yang J, Leskovec J. Community-affiliation graph model for overlapping network community detection[C] //Proc of the 12th IEEE Int Conf on Data Mining (ICDM’12). Piscataway, NJ: IEEE, 2012: 1170-1175

[17]Wang Z, Hu Y, Xiao W, et al. Overlapping community detection using a generative model for networks[J]. Physica A: Statistical Mechanics and Its Applications, 2013, 392(20): 5218-5230

[18]Xie J, Kelley S, Szymanski B K. Overlapping community detection in networks: The state-of-the-art and comparative study[J]. ACM Computing Surveys, 2013, 45(4): 43

[19]Zhu Mu, Meng Fanrong, Zhou Yong. Density-based link clustering algorithm for overlapping community detection[J]. Journal of Computer Research and Development, 2013, 50(12): 2520-2530 (in Chinese)(朱牧, 孟凡榮, 周勇. 基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機研究與發(fā)展, 2013, 50(12): 2520-2530)

[20]Chapelle O, Sch?lkopf B, Zien A. Semi-Supervised Learning[M]. Cambridge, MA: MIT Press, 2006

[21]Zhang Z Y. Community structure detection in complex networks with partial background information[J]. Europhysics Letters, 2013, 101(4): 48005

[22]Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1): 016118

[23]Newman M E J. Modularity and community structure in networks[J]. Proceedings of National Academy of Sciences, 2006, 103(23): 8577-8582

[24]Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of National Academy of Sciences, 2008, 105(4): 1118-1123

[25]Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis[J]. Physical Review E, 2009, 80(5): 056117

Chen Junyu, born in 1989. Master. Student member of China Computer Federation. His research interests include complexsocial network and machine learning.

Zhou Gang, born in 1974. Associate professor. Member of China Computer Federation. His research interests include data mining, complexsocial network and machine learning (gzhougzhou@gmail.com).

Nan Yu, born in 1978. Lecturer. Member of China Computer Federation. Her research interests include data mining and machine learning (ddapple2011@163.com).

Zeng Qi, born in 1992. Master candidate. Student member of China Computer Federation. His research interests include machine learning and natural language processing (windddk@163.com).

Semi-Supervised Local Expansion Method for Overlapping Community Detection

Chen Junyu, Zhou Gang, Nan Yu, and Zeng Qi

(StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Zhengzhou450002)

AbstractOverlapping community detection has become one of the hottest research issues in the field of network science, as well as attracted the attention of researchers with different backgrounds. A novel semi-supervised local expansion method (SLEM) is proposed for detecting overlapping communities more effectively in real world networks. The proposed method makes use of not only the topology information of the network but also the attribute information of partial vertices. Inspired by the idea of semi-supervised clustering with constraints in the field of machine learning, SLEM starts from utilizing the attribute information of partial vertices to get pairwise constraints which can be used to modify the topology structure of the original network. Afterward, a vertex degree centrality-based seeding method is proposed for selecting seeds as initial communities. Then these seeds expand into local communities by a greedy strategy, after which partial connected close-knit communities are formed. Finally, similarities between different communities are computed on the basis of a community distance measurement, and then near-duplicated communities are combined. Taking more advantage of network information than traditional unsupervised community detection methods, SLEM can produce communities with higher structure quality. Experimental results on both synthetic benchmark networks and real world networks show that SLEM can achieve better effect than the state-of-the-art local expansion methods on the networks of different sparsity degrees.

Key wordscomplex network; overlapping community detection; semi-supervised clustering; local expansion; semi-supervised local expansion method (SLEM)

收稿日期：2014-12-09；修回日期：2015-03-19

基金項目：數(shù)學(xué)工程與先進計算國家重點實驗室開放基金項目(2013A02)

中圖法分類號TP391

This work was supported by the Open Program of State Key Laboratory of Mathematical Engineering and Advanced Computing (2013A02).