基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法

劉 倩，劉 群

（重慶郵電大學 計算智能重慶市重點實驗室，重慶400065）

0 引 言

近年來，學者對復雜網(wǎng)絡社區(qū)結(jié)構(gòu)性質(zhì)的研究集中于重疊社區(qū)發(fā)現(xiàn)算法。目前，已經(jīng)出現(xiàn)了許多發(fā)現(xiàn)網(wǎng)絡重疊社區(qū)的算法。其中，Evans等［1］和Ahn等［2］分別發(fā)表了從邊的角度來研究社團劃分，文獻［3］還運用領導的思想來發(fā)現(xiàn)網(wǎng)絡重疊社區(qū)。其它算法有基于模糊聚類的發(fā)現(xiàn)算法［4］，基于非負矩陣分解的發(fā)現(xiàn)算法［5］，基于混合概率模型的方法［6］等。圖1是一個具有兩個社區(qū)并存在重疊節(jié)點的網(wǎng)絡結(jié)構(gòu)圖，其中每個圓圈虛線內(nèi)的節(jié)點集構(gòu)成一個社區(qū)，而三角形節(jié)點就是社區(qū)之間的重疊結(jié)點。

圖1 重疊社區(qū)網(wǎng)絡結(jié)構(gòu)

本文提出了基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法。該算法中的種子選取策略考慮了種子對網(wǎng)絡中其它節(jié)點的直接與間接影響力，這使算法選取的種子更加準確，從而使社區(qū)劃分的結(jié)果更加精確。

1 基本概念

1.1 結(jié)點的度

給定一個具有n個節(jié)點和m 條邊的網(wǎng)絡G（V，E），其中V 表示節(jié)點集合，E 表示邊集合。節(jié)點u與節(jié)點v之間連接的邊表示為euv，邊euv的權(quán)重為wuv；如果節(jié)點u與節(jié)點v有邊連接，則wuv＝1，相反，wuv＝0。節(jié)點u的度ku的定義如下

例如，在圖2所示的小網(wǎng)絡結(jié)構(gòu)中，節(jié)點5的度為1＋1＋1＋1＝4，節(jié)點9的度為1＋1＋1＝3，節(jié)點1的度為1＋1＋1＝3。網(wǎng)絡中一個節(jié)點的度等于與這個節(jié)點相連接的所有邊數(shù)的總和。

圖2 小網(wǎng)絡結(jié)構(gòu)

1.2 隸屬度

給定一個網(wǎng)絡G（V，E），以及G 中的一個社區(qū)c和一個節(jié)點u，則節(jié)點u 對社區(qū)c的隸屬度B（u，c）［7］的定義如下

式中：隸屬度函數(shù)B（u，c）反映了節(jié)點u與社區(qū)c聯(lián)系的緊密程度，B（u，c）的值越大，節(jié)點u與社區(qū)c的連接越密集，而B（u，c）的值越小，節(jié)點u與社區(qū)c的連接越松散。如果節(jié)點u的所有鄰居節(jié)點都被包含在社區(qū)c中，則B（u，c）＝1，即節(jié)點u只屬于c這一個社區(qū)；否則，B（u，c）＜1，即節(jié)點u屬于多個社區(qū)。

例如，在圖2中，假設社區(qū)c包含的節(jié)點集合為｛1，2，3，4，5｝，其中，節(jié)點6對社區(qū)c的隸屬度B（6，c）的值是1／（1＋1＋1）＝1／3，節(jié)點7對社區(qū)c的隸屬度B（7，c）的值是（1＋1）／（1＋1＋1＋1）＝1／2，節(jié)點5的所有鄰居節(jié)點都在社區(qū)c里，則它對社區(qū)c的隸屬度B（5，c）＝1。

1.3 引力度

牛頓萬有引力定律是解釋物體之間的相互作用的引力定律。且牛頓萬有引力定律認為，地球上的任何兩個物體之間都存在萬有引力，該引力的大小與它們的質(zhì)量乘積成正比，與它們距離的平方成反比，并且與兩物體的化學本質(zhì)或物理狀態(tài)以及中介物質(zhì)無關，公式表示如下

式中：F——兩個物體之間的引力，m1、m2——兩個相互存在引力的物體的質(zhì)量，r——兩個存在引力的物體之間的距離，G——引力常數(shù)。

由牛頓萬有引力定律可知，既然任意兩個物體之間都存在引力，那么網(wǎng)絡中的任意兩個節(jié)點之間也存在萬有引力。由于網(wǎng)絡具有自己的結(jié)構(gòu)特性，將網(wǎng)絡中任意兩個節(jié)點u與節(jié)點v之間的萬有引力重新定義為式（4）

式中：mu、mv——網(wǎng)絡中節(jié)點u和節(jié)點v的質(zhì)量。用節(jié)點的質(zhì)量來衡量節(jié)點自身的特性，則質(zhì)量越小，自身的重要性也越小；質(zhì)量越大，自身的重要性也越大。根據(jù)網(wǎng)絡自身的結(jié)構(gòu)性質(zhì)，對任意一個節(jié)點，只有節(jié)點的度能直接反應出該節(jié)點的相關信息，同時也體現(xiàn)了一個節(jié)點與網(wǎng)絡中其它節(jié)點的直接通信能力。因此，我們采用節(jié)點的度來衡量網(wǎng)絡節(jié)點的質(zhì)量，則對任意節(jié)點u，就有mu＝ku。

而距離d（u，v）的衡量，我們?nèi)匀粡木W(wǎng)絡的結(jié)構(gòu)特性出發(fā)，用節(jié)點u與節(jié)點v之間的最短路徑長度來具體度量d（u，v）。網(wǎng)絡中任意兩個節(jié)點u與節(jié)點v之間的最短路徑長度即是以節(jié)點u為起點，以v為終點的最短路徑中所含邊的數(shù)量，此長度值還可以反應出節(jié)點u最少能通過幾個節(jié)點就能與節(jié)點v取得聯(lián)系，即表明了一個節(jié)點與網(wǎng)絡中其它節(jié)點間接通信的最大能力。

既然，網(wǎng)絡中的任意節(jié)點u都與其它節(jié)點之間存在引力，那么網(wǎng)絡中每一個節(jié)點與其它節(jié)點的引力就存在一個和值，就將網(wǎng)絡中的節(jié)點u與其它節(jié)點的引力之和定義為節(jié)點u的引力度，其定義式如式（5）

2 基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法

給定一個網(wǎng)絡G（V，E），節(jié)點數(shù)｜V｜＝n，邊數(shù)｜E｜＝m；該算法主要由兩部分組成：①尋找初始社區(qū)；②對社區(qū)進行擴展。為了挖掘出網(wǎng)絡中的重疊社區(qū)，將網(wǎng)絡中未被劃分到任意一個社區(qū)中的節(jié)點標記為 ‘M’，這些被標記為 ‘M’的節(jié)點集合記為VM，而已經(jīng)被分配到至少一個社區(qū)中的節(jié)點標記為 ‘D’，這些被標記為 ‘D’的節(jié)點集合記為VD，且VM＝V－VD。首先，將網(wǎng)絡中所有節(jié)點的劃分狀態(tài)初始化為 ‘M’，即沒有任意一個節(jié)點已經(jīng)被劃分到某個社區(qū)。

2.1 尋找初始社區(qū)

步驟1 使用式（5），即用f（u）的定義公式來計算網(wǎng)絡中劃分狀態(tài)標記為 ‘M’的節(jié)點的引力度值；

步驟2 選取引力度值最大的節(jié)點作為發(fā)現(xiàn)一個社區(qū)的種子；

步驟3 查詢種子節(jié)點的劃分狀態(tài)為 ‘M’的鄰居節(jié)點集合，這些鄰居節(jié)點與種子節(jié)點便形成了一個初始社區(qū)c；

步驟4 對于社區(qū)c中的每一個節(jié)點u，計算其隸屬度B（u，c）的值，如果存在B（u，c）＜Bc（Bc表示節(jié)點u與社區(qū)c聯(lián)系緊密程度的門限值）的節(jié)點，則將這些節(jié)點從社區(qū)c中移除；

步驟5 返回步驟4，直到 u ∈c，B（u，c）≥Bc，則獲得了最終的初始社區(qū)c。

2.2 擴展社區(qū)

步驟1 找出社區(qū)c的鄰居節(jié)點集合，將其記為Nc，并計算鄰居節(jié)點集Nc中每個節(jié)點v的隸屬度B（v，c）的值；

步驟2 找出Nc中隸屬度B（v，c）≥Bv（Bv表示節(jié)點v與社區(qū)c聯(lián)系緊密程度的門限值）的所有節(jié)點，用Nv＝｛B（v，c）≥Bv｝表示這個節(jié)點集合；

步驟3 如果｜Nv｜＞0（｜Nv｜表示集合Nv中節(jié)點的個數(shù)），則添加Nv集合中的節(jié)點到社區(qū)c中，便形成了一個更大的社區(qū)c，返回步驟1；

步驟4 如果｜Nv｜＝0，則挖掘出了一個最終的社區(qū)c。

例如，在圖3中，假定初始社區(qū)c包含的節(jié)點集為｛1，2，3，4，5｝，它的鄰居節(jié)點集合為｛8，7，6｝，其中B（8，c）＝1／4，B（7，c）＝2／5，B（6，c）＝3／5，添加節(jié)點6到社區(qū)c中。添加節(jié)點6之后，社區(qū)c的鄰居節(jié)點集Nc中的任意節(jié)點v，都有B（v，c）＜Bv。此時，停止社區(qū)擴展過程并發(fā)現(xiàn)了一個最終的社區(qū)c＝｛1，2，3，4，5，6｝，即圖3中的三角形節(jié)點集。

圖3 社區(qū)擴展

2.3 算法流程圖

圖4表明了如何挖掘出一個網(wǎng)絡中的所有重疊社區(qū)。當作社區(qū)擴展時，查找鄰居節(jié)點集是不考慮鄰居節(jié)點是否已經(jīng)被劃分到了某個社區(qū)，因此就可以發(fā)現(xiàn)社區(qū)之間的重疊結(jié)點，即發(fā)現(xiàn)重疊社區(qū)。

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

為了測試本文算法的可行性，將算法運用在真實網(wǎng)絡上進行了測試，并與Lancichinetti［8］等提出的重疊社區(qū)發(fā)現(xiàn)算法 （LMF算法［9］）做了性能上的對比。

3.1 模塊度

圖4 算法流程

為了衡量一個網(wǎng)絡社區(qū)結(jié)構(gòu)劃分質(zhì)量的優(yōu)劣，New－man［10］提出了模塊度Q 這一衡量指標。雖然該模塊度已經(jīng)在復雜網(wǎng)絡中得到了廣泛的認可與運用，但是，仍然存在諸多問題，例如它不能解決衡量重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的限制性問題［11］。為了解決此問題，又有人提出了衡量重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的模塊度函數(shù)，本文采用文獻［12］中的擴展模塊度函數(shù)EQ（extend modularity）來衡量重疊社區(qū)結(jié)構(gòu)劃分的質(zhì)量。EQ 的定義如下

式中：m——網(wǎng)絡中節(jié)點之間連接的總邊數(shù)，Qu、Qv——節(jié)點u、節(jié)點v所屬的社區(qū)個數(shù)，Auv——網(wǎng)絡的鄰接矩陣里的元素，也反映了節(jié)點u與節(jié)點v的連接情況，如果節(jié)點u與節(jié)點v有連接，則Auv＝1，相反，Auv＝0，Ku、Kv分別表示節(jié)點u、節(jié)點v的度。

3.2 真實網(wǎng)絡

本文算法中Bc（Bc表示節(jié)點u與社區(qū)c聯(lián)系緊密程度的門限值）的取值影響著社區(qū)劃分的尺度與社區(qū)結(jié)構(gòu)的優(yōu)劣和明顯程度。下面主要從Bc取0.4與0.5來討論我們算法劃分的網(wǎng)絡社區(qū)結(jié)構(gòu)的結(jié)果。

3.2.1 Zachary’s karate club

Zachary社會網(wǎng)是復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)中經(jīng)常被用來進行測試的經(jīng)典小型網(wǎng)絡數(shù)據(jù)集，該網(wǎng)絡反映了美國一所大學空手道俱樂部成員之間的社會關系。網(wǎng)絡包含34個節(jié)點與78條邊，每一個節(jié)點表示一個俱樂部成員，每一條邊表示俱樂部成員之間除了具有俱樂部成員的關系外，他們私下還是朋友的關系。本文算法將Zachary社會網(wǎng)劃分的網(wǎng)絡社區(qū)結(jié)構(gòu)與真實網(wǎng)絡社區(qū)結(jié)構(gòu)如圖5所示。

圖5 社區(qū)劃分

在圖5的圖（a）、圖（b）、圖（c）中，實心圓節(jié)點集表示一個社區(qū)，實心正方形節(jié)點集表示另一個社區(qū)，三角形節(jié)點集表示社區(qū)之間的重疊節(jié)點。圖5 （a）是真實社區(qū)結(jié)構(gòu)圖，節(jié)點3是兩個社區(qū)之間的重疊節(jié)點。在圖5（b）中，Bc取值為0.4，網(wǎng)絡被本文算法劃分為兩個社區(qū)，節(jié)點3、9、10、14、31是兩個社區(qū)之間的重疊節(jié)點。在圖5（c）中，Bc取值為0.5，此時本文算法仍然將網(wǎng)絡劃分為2個社區(qū)，但重疊節(jié)點是3、10。將圖5中的圖（b）、圖（c）與圖（a）作對比，可以得出Bc＝0.5時，我們算法所劃分的社區(qū)結(jié)構(gòu)與真實社區(qū)結(jié)構(gòu)更相符合。

3.2.2 American College football

College football網(wǎng)通常也是社區(qū)發(fā)現(xiàn)中算法運用的網(wǎng)絡數(shù)據(jù)集對象，該網(wǎng)絡描述了美國一所大學里各學院之間玩足球游戲的社會關系。網(wǎng)絡包含了115個結(jié)點和615條邊，節(jié)點表示足球隊，節(jié)點之間的邊則表示足球隊之間有足球比賽的社會關系。當Bc取值為0.4時，我們算法將網(wǎng)絡劃分為11個非重疊社區(qū)；當Bc取值為0.5 時，算法將網(wǎng)絡劃分為14個非重疊社區(qū)。

3.2.3 Email

Email網(wǎng)是Rovira i Virgeili大學的一個郵件網(wǎng)絡，該網(wǎng)絡包含1133個節(jié)點和5451條邊。我們算法在Bc取值為0.4時將網(wǎng)絡劃分為232個社區(qū)，社區(qū)之間有101個重疊節(jié)點，在Bc取值為0.5時將網(wǎng)絡劃分為261個社區(qū)，社區(qū)之間有107個重疊節(jié)點。

本文算法與LMF算法在3個真實網(wǎng)絡上進行測試的算法性能結(jié)果見表1。

表1 算法性能對比

從3個網(wǎng)絡的描述與表1可以得出，當網(wǎng)絡數(shù)據(jù)集不同，網(wǎng)絡節(jié)點數(shù)也不相同，隨著節(jié)點數(shù)的增多，我們算法的運行時間與LMF算法的運行時間都在增加，尤其是本文算法的運行時間增加更快。對表1作進一步分析，在karate網(wǎng)絡中，Bc取0.4與0.5時，我們算法的EQ 值都比LMF算法的EQ 值略低，說明本文算法劃分的社區(qū)結(jié)構(gòu)不如LMF算法劃分的社區(qū)結(jié)構(gòu)明顯，且我們算法在Bc取0.5比Bc取0.4時的EQ 值高，即Bc取0.5時的社區(qū)劃分結(jié)果更好。在football網(wǎng)絡中，Bc取0.4與0.5時，我們算法的EQ 值都比LMF算法的EQ 值高，表明我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)更優(yōu)。而在email網(wǎng)絡中，Bc取0.4時，我們算法的EQ 值比LMF算法的EQ 值高，即我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)更好，但Bc取0.5 時，我們算法的EQ 值卻比LMF 算法的EQ 值低，即我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)稍差。

3.2.4 KDD Cup2012

KDD Cup2012是2012年在中國舉行的國際性數(shù)據(jù)挖掘大賽，大賽任務一是好友推薦，其數(shù)據(jù)集是由騰訊微博提供的大量微博數(shù)據(jù)。騰訊微博也是一個社會關系網(wǎng)絡，每一個微博用戶就是網(wǎng)絡中的一個節(jié)點，用戶在微博上與其他用戶取得的聯(lián)系就是網(wǎng)絡中的邊。該微博數(shù)據(jù)集分為很多項目文件，其中的user＿profile.txt文件描述的是每個騰訊微博用戶的一些基本信息，如用戶的編號、出身日期、興趣愛好等，user＿sns.txt文件描述的是微博用戶之間在微博上有聯(lián)系的社會關系。我們從user＿profile.txt文件中提取了不同規(guī)模的節(jié)點數(shù)（節(jié)點數(shù)以100作為起點），并從user＿sns.txt文件中提取了不同規(guī)模節(jié)點對應的邊關系。將本文算法與LMF算法在提取的數(shù)據(jù)集上做了測試，然后對測試的結(jié)果做了對比分析。如圖所示，其中圖6是算法的運行時間與節(jié)點數(shù)的關系圖，橫坐標為節(jié)點數(shù)，縱坐標為運行時間；圖7 是EQ 與節(jié)點數(shù)的關系圖，橫坐標為節(jié)點數(shù)，縱坐標為EQ 值。

圖6 時間與節(jié)點數(shù)的關系

圖7 EQ 與節(jié)點數(shù)的關系

由圖6可以得出，當網(wǎng)絡節(jié)點規(guī)模增大時，我們算法的運行時間仍然比LMF算法的運行時間增加得更多。由圖7可以看出，我們算法的EQ 值與LMF 算法的EQ 值在節(jié)點數(shù)增加時都有所下降，但我們算法在Bc取0.4 與0.5時，其EQ 值都比LMF算法的EQ 值高，這說明我們算法劃分的社區(qū)結(jié)構(gòu)更加精確與明顯。而節(jié)點規(guī)模為1000 時，我們算法在Bc取0.4時的社區(qū)劃分結(jié)果比Bc取0.5時的社區(qū)劃分結(jié)果更準確。

4 結(jié)束語

本文提出了基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法。算法以引力度最大的節(jié)點為種子來尋找初始社區(qū)，再進行擴展得到最終社區(qū)。將算法在真實網(wǎng)絡上進行了測試，實驗結(jié)果顯示我們算法的時間復雜度比LMF算法的時間復雜度高。我們算法劃分的社區(qū)結(jié)構(gòu)的結(jié)果雖然受Bc取值的影響，但總體上獲得的EQ 值比LMF算法的EQ 值更高，即我們算法劃分的網(wǎng)絡社區(qū)結(jié)構(gòu)比LFM 算法劃分的社區(qū)結(jié)構(gòu)更精確，這說明我們算法在發(fā)現(xiàn)網(wǎng)絡重疊社區(qū)上是可行與有效的。我們后續(xù)工作將提高算法的時間效率，并提高我們算法在大數(shù)據(jù)網(wǎng)絡上劃分的社區(qū)結(jié)構(gòu)質(zhì)量。

［1］Evans T，Lambiotte R.Line graphs，link partitions，and overlapping communities ［J］.Physical Review E，2009，80（1）：1－8.

［2］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multiscale complexity in networks ［J］.Nature，2010，466：761－764.

［3］Li H J，Zhang J H，Liu Z P，et al.Identifying overlapping communities in social networks using multi－scale local information expansion ［J］.The European Physical Journal B，2012，85 （6）：1－9.

［4］Zhang S，Wang R S，Zhang X.Identification of overlapping community structure in complex networks using fuzzy C－means clustering ［J］.Physica A：Statistical Mechanics and its Applications，2007，374 （1）：483－490.

［5］Zarei M，Izadi D，Samani K A.Detecting overlapping community structure of networks based on vertex－vertex correlations［J］.Journal of Statistical Mechanics：Theory and Experiment，2009 （11）：11013.

［6］Ball B，Karrer B，Newman M E J.An efficient and principled method for detecting communities in networks ［J］.Physical Review E，2011，84 （3）：1－14.

［7］Chen D，Shang M，Lv Z，et al.Detecting overlapping communities of weighted networks via a local algorithm ［J］.Physica A：Statistical Mechanics and its Applications，2010，389（19）：4177－4187.

［8］Lancichinetti A，F(xiàn)ortunato S，Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks［J］.New Journal of Physics，2009，11 （3）：1－18.

［9］LUO Zhigang，DING Fan，JIANG Xiaozhou，et al.New progress on community detection in complex networks ［J］.Journal of National University of Defense Technology，2011，33（1）：47－51 （in Chinese）.［駱志剛，丁凡，蔣曉舟，等.復雜網(wǎng)絡社團發(fā)現(xiàn)算法研究新進展 ［J］.國防科技大學學報，2011，33 （1）：47－51.］

［10］Newman M E J.Modularity and community structure in networks［J］.Proceeding of the National Academy of Sciences of the United States of America，2006，103 （23）：8577－8582.

［11］Fortunato S，Barthélemy M.Resolution limit in community detection ［J］.Proceeding of the National Academy of Sciences of the United States of America，2007，104 （1）：36－41.

［12］Shen Hawei，Cheng Xueqi，Cai Kai，et al.Detect overlapping and hierarchical community structure in networks ［J］.Physica A，2009，388 （8）：1706－1712.