王豫中，范 磊，李建華

（上海交通大學電子信息與電氣工程學院，上海200240）

基于廣度優(yōu)先搜索的局部社區(qū)發(fā)現(xiàn)算法

王豫中，范 磊，李建華

（上海交通大學電子信息與電氣工程學院，上海200240）

局部社區(qū)發(fā)現(xiàn)是網(wǎng)絡(luò)拓撲研究中的熱點，從起始節(jié)點的最大結(jié)合性節(jié)點出發(fā)，提出一個基于給定節(jié)點的局部社區(qū)發(fā)現(xiàn)算法。對整個社區(qū)進行廣度優(yōu)先搜索（BFS），從起始節(jié)點開始找到最大結(jié)合性節(jié)點，基于節(jié)點相似度（共同好友數(shù)目）并且利用BFS進行社區(qū)發(fā)現(xiàn)，對所發(fā)現(xiàn)的社區(qū)進行剪枝策略，從而得到起始節(jié)點所在的局部社團。實驗結(jié)果證明，該算法在不降低精度的前提下，時間復雜度為O（kd3）。

最大結(jié)合性；共同好友數(shù)；節(jié)點相似度；廣度優(yōu)先搜索；局部社區(qū)發(fā)現(xiàn)

DO I：10.3969/j.issn.1000-3428.2015.10.008

1 概述

隨著網(wǎng)絡(luò)的發(fā)展，越來越多的學者開始研究復雜網(wǎng)絡(luò)，如：社交網(wǎng)絡(luò)，蛋白質(zhì)網(wǎng)絡(luò)［1］，簽名網(wǎng)絡(luò)，微博社區(qū)網(wǎng)絡(luò)［2］，通信網(wǎng)絡(luò)，在線社會網(wǎng)絡(luò)［3］以及W eb網(wǎng)絡(luò)［4］。大量的研究表明，社區(qū)結(jié)構(gòu)普遍地存在于大型網(wǎng)絡(luò)中，并扮演著重要的角色。研究發(fā)現(xiàn)在社區(qū)結(jié)構(gòu)內(nèi)部的節(jié)點聯(lián)系相對比較緊密，而在社區(qū)結(jié)構(gòu)之間節(jié)點聯(lián)系相對比較稀疏［5］。發(fā)現(xiàn)社區(qū)結(jié)構(gòu)對于研究大型復雜網(wǎng)絡(luò)具有現(xiàn)實以及長遠意義。

目前網(wǎng)絡(luò)拓撲發(fā)現(xiàn)社區(qū)結(jié)構(gòu)主要有兩大方向：一個是全局社區(qū)發(fā)現(xiàn)；另一個是局部社區(qū)發(fā)現(xiàn)。全局社區(qū)發(fā)現(xiàn)以整個網(wǎng)絡(luò)為基準，發(fā)現(xiàn)網(wǎng)絡(luò)中存在的所有社區(qū)［6］。然而由于全局社區(qū)發(fā)現(xiàn)通常需要全局網(wǎng)絡(luò)信息，有時網(wǎng)絡(luò)是動態(tài)變化的或獲取全網(wǎng)信息難度較大等客觀因素的制約［7］，很多學者提出了局部社區(qū)發(fā)現(xiàn)方法［8-10］。與全局社區(qū)發(fā)現(xiàn)不同的是，局部社區(qū)發(fā)現(xiàn)從某個單一節(jié)點出發(fā)，進而發(fā)現(xiàn)該節(jié)點所在的社區(qū)結(jié)構(gòu)。因此，在局部社區(qū)發(fā)現(xiàn)算法中整個網(wǎng)絡(luò)被劃分為2個社區(qū)：該節(jié)點所在的社區(qū)CT以及剩余社區(qū)～CT。局部社區(qū)發(fā)現(xiàn)算法不需要知道整個網(wǎng)絡(luò)的信息，算法從一個起始節(jié)點出發(fā)，然后采用某種機制擴展社區(qū)直到達到某個預定義的條件。

本文算法從起始節(jié)點的最大結(jié)合性節(jié)點出發(fā)，用圖的廣度優(yōu)先搜索算法（BFS）進行社區(qū)發(fā)現(xiàn)。對于圖中的每一個節(jié)點，用該算法找到它所在的局部社區(qū)，并采用經(jīng)典的衡量標準來驗證算法的有效性和優(yōu)越性。

2 相關(guān)工作

用G=（V，E）來代表整個網(wǎng)絡(luò)，其中，V表示節(jié)點集合；E表示邊集合。n和 m分別代表節(jié)點的個數(shù)和邊的個數(shù)。和全局社區(qū)發(fā)現(xiàn)將整個網(wǎng)絡(luò)劃分為幾個社區(qū)不同的是，局部社區(qū)發(fā)現(xiàn)算法定義一個起始節(jié)點ν0，發(fā)現(xiàn)這個節(jié)點ν0所在的社區(qū)。

文獻［11］定義了局部社區(qū)發(fā)現(xiàn)問題，將局部社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)換為最優(yōu)化問題，在此將該算法簡記為M算法。

定義節(jié)點集合C為所探測到的社區(qū)（起始時C只包含一個起始節(jié)點ν0）。定義節(jié)點集合 U中的節(jié)點和C中的節(jié)點相連但是不屬于C。另外定義了C的的邊界節(jié)點集合B，B中的節(jié)點屬于C，但是這些節(jié)點又和U中節(jié)點相連。最優(yōu)化函數(shù)定義如下：

如果i，j∈E，節(jié)點νi和νj中至少有一個在B中，這時 Bij=1。否則 Bij=0。如果（i，j）∈E，δ（i，j）=1，否則δ（i，j）=0。算法通過貪心策略從U中選擇可以使R達到最大的節(jié)點，并將其加到C中，直到達到某個閾值為止。然而該算法顯著的缺點是需要指定社區(qū)的大小以及具有 O（k2d）的較高的時間復雜度。其中，d是節(jié)點的平均度數(shù)；k是最終發(fā)現(xiàn)的局部社區(qū)的節(jié)點個數(shù)。

文獻［12］提出另外一種最優(yōu)化算法來發(fā)現(xiàn)局部社區(qū)，簡記為R算法。最優(yōu)化函數(shù)定義為：

其中，Ein代表社區(qū)C內(nèi)部邊的個數(shù)；Eout代表社區(qū)C外部邊的個數(shù)。算法要實現(xiàn)M的最大化，分為2個階段：增加節(jié)點階段和刪除節(jié)點階段。使得M增大的節(jié)點被加入社區(qū)C中，同時如果從社區(qū)C中刪除一個節(jié)點也能使M增大，則刪除。這2個階段交替進行直到 M達到最大值。該算法的缺點是起始節(jié)點ν0可能被刪除。

文獻［13］定義另外一個度量函數(shù)：

文獻［14］為了提高算法的魯棒性，描述局部社區(qū)發(fā)現(xiàn)算法不是從起始節(jié)點出發(fā)進行社區(qū)發(fā)現(xiàn)，而是找到起始節(jié)點最近的局部最大中心點，從這個局部最大中心點出發(fā)進行社區(qū)發(fā)現(xiàn)，因此該算法可以有LMD-M，LMD-R，LMD-F等多種算法實現(xiàn)，簡記為LMD算法。

文獻［15］提出的局部社區(qū)發(fā)現(xiàn)算法不同于上述算法，該算法從一個團出發(fā)進行社區(qū)發(fā)現(xiàn)。此算法可挖掘出起始節(jié)點的重疊社區(qū)。本文將該算法簡記為LMD-MC算法。

3 本文算法

上述算法都有各自的缺點，文獻［11-12］提出的算法達到了O（k2d）的時間復雜度。文獻［14］提出的算法由于要發(fā)現(xiàn)局部最大中心點，這個過程可能具有較大的時間復雜度。文獻［15］提出的算法也有著時間復雜度過高的問題。

本文提出一種新的局部社區(qū)發(fā)現(xiàn)算法，該算法從一個起始節(jié)點相對應(yīng)的最大結(jié)合性節(jié)點出發(fā)，基于2個節(jié)點的共同好友數(shù)目，利用經(jīng)典的廣度優(yōu)先搜索算法來進行社區(qū)發(fā)現(xiàn)。發(fā)現(xiàn)起始節(jié)點相對應(yīng)的最大結(jié)合性節(jié)點：一是可以提高算法的魯棒性，避免邊界節(jié)點找不到社區(qū)的情況；二是可以降低尋找局部最大中心點的時間復雜度?；诠餐糜褦?shù)目并且結(jié)合廣度優(yōu)先搜索的算法將時間復雜度由原來的O（k2）降低到O（k）。

3.1 相似度

相似度用來衡量2個個體之間連接的緊密程度，如果2個個體的相似度越大，則它們屬于同一個社區(qū)的概率也就越大?；镜南嗨贫榷攘坑袣W氏距離、Jaccard相似性［16］以及余弦函數(shù)［17］等。本文中用來衡量2個節(jié)點的相似度定義為：

其中，S（νi，νj）表示節(jié)點 νi和節(jié)點 νj的相似度；N（νi）表示節(jié)點νi的鄰居節(jié)點集合；N（νj）表示節(jié)點νj的鄰居節(jié)點集合。所以分子表示節(jié)點νi和節(jié)點νj的共同鄰居節(jié)點數(shù)目。分母表示節(jié)點 νi和節(jié)點 νj鄰居節(jié)點數(shù)目的最小值。若某一個節(jié)點的鄰居數(shù)量為1，則將它和其鄰居節(jié)點的相似度定義為1，因此此節(jié)點始終可以歸為其鄰居節(jié)點所在的社區(qū)，其中0≤S（νi，νj）≤1。

3.2 節(jié)點的最大結(jié)合性

3.2.1 節(jié)點的結(jié)合性

一個節(jié)點的結(jié)合性定義為它的鄰居節(jié)點之間連接的邊數(shù)和它的鄰居節(jié)點之間可能存在的最大連接邊數(shù)的比值。節(jié)點ν的結(jié)合性dν定義為：

其中，eij表示節(jié)點i和節(jié)點j有邊相連；分子表示節(jié)點ν的鄰居節(jié)點集合中實際存在的邊數(shù)；分母表示節(jié)點ν的鄰居節(jié)點集合中可能存在的最多的邊數(shù)。3.2.2 節(jié)點最大結(jié)合性

考慮一個節(jié)點ν以及其鄰居節(jié)點集合N（ν），找出集合（ν，N（ν））中具有最大結(jié)合性 d的節(jié)點作為此節(jié)點ν的最大結(jié)合性節(jié)點。即節(jié)點 ν的最大結(jié)合性節(jié)點w定義為：

3.3 社區(qū)的鄰居節(jié)點集合

一個社區(qū)的鄰居節(jié)點集合定義為未被此社區(qū)包含的但有邊和此社區(qū)中的節(jié)點相連的節(jié)點的集合。對于社區(qū)C的鄰居節(jié)點集合B定義如下：

3.4 節(jié)點社區(qū)的內(nèi)度和外度

一個節(jié)點對于社區(qū)的內(nèi)度定義為此節(jié)點的鄰居節(jié)點中在社區(qū)內(nèi)部的節(jié)點的個數(shù)。

一個節(jié)點對于社區(qū)的外度定義為此節(jié)點的度數(shù)減去節(jié)點對于社區(qū)的內(nèi)度。

節(jié)點ν對于社區(qū)C的內(nèi)度定義為：

節(jié)點ν對于社區(qū)C的外度定義為：

3.5 算法過程

算法的主要符號說明如下：

ν0：起始節(jié)點；

dν：節(jié)點ν的結(jié)合性；

w0：節(jié)點ν0對應(yīng)的最大結(jié)合性節(jié)點；

C：被發(fā)現(xiàn)的局部社區(qū)；

Q：廣度優(yōu)先搜索算法中用到的隊列；

S（νi，νj）：節(jié)點νi和節(jié)點νj的相似度；

sth：相似度閾值。

算法步驟如下：

（1）初始化社區(qū) C為空，從起始節(jié)點 ν0出發(fā)找到它所對應(yīng)的最大結(jié)合性節(jié)點 w0，將節(jié)點 w0加入C，并標記w0為已經(jīng)訪問過的節(jié)點。

（2）從w0出發(fā)對圖進行廣度優(yōu)先搜索（BFS）。假如νi是當前從隊列中出隊的節(jié)點，將其鄰居節(jié)點中滿足S（νi，νj）≥sth的節(jié)點νj入隊并標記。將所有出隊的節(jié)點放入C中。

（3）對于C的鄰居節(jié)點集合B中的任何一個節(jié)點b∈B，若inward（b，C）?0.5，則將b加入到C中。在此步驟中由于起始節(jié)點或者是真正的起始節(jié)點ν0，或者是其對應(yīng)的最大結(jié)合性節(jié)點w0。所以起始節(jié)點ν0要么位于新發(fā)現(xiàn)的社區(qū)C中，要么位于社區(qū)C的鄰居節(jié)點集合B中。所以對B中每一個節(jié)點實施上述操作也就相當于判斷了inward（ν0，C）?

0.5 的正確性。

算法的偽代碼描述如下：

算法1FindMaχConnection（ν0）：尋找節(jié)點ν0的最大結(jié)合性節(jié)點

代碼中sort（result）表示對result集合中的數(shù)值按照從小到大的順序進行排序。maχ（result）表示提取出result集合中的最大值。

算法2getSimilarity（data1，data2）：計算節(jié)點data1和節(jié)點data2的相似度

算法3BFS-Process（ν0）：尋找ν0的局部社區(qū)C

代碼中enqueue（queue，w0）表示將w0放入隊列queue。dequeue（queue）表示從隊列queue中出隊一個元素。

算法4main：尋找ν0的局部社區(qū)入口函數(shù)

代碼中BFS-Process（ν0）表示從起始節(jié)點ν0出發(fā)發(fā)現(xiàn)局部社區(qū)的過程，對應(yīng)算法3的函數(shù)調(diào)用，函數(shù)返回被發(fā)現(xiàn)的局部社區(qū)。

3.6 算法復雜度分析

本文算法的時間復雜度分析主要包括兩部分。一部分是發(fā)現(xiàn)指定起始節(jié)點的最大結(jié)合性節(jié)點部分的時間復雜度，另外一部分是局部社區(qū)發(fā)現(xiàn)部分的時間復雜度。

（1）發(fā)現(xiàn)指定起始節(jié)點最大結(jié)合性節(jié)點部分的時間復雜度（算法1時間復雜度）

計算某個節(jié)點 νi結(jié)合性的時間復雜度為O（di

2），其中，di為節(jié)點 νi的度。為了計算節(jié)點 νi的最大結(jié)合性節(jié)點，需要計算此節(jié)點以及它的鄰居節(jié)點的結(jié)合性，并找出其最大值，所以總的時間復雜度為O（di

3）+O（di）=O（di3）。

（2）計算2個節(jié)點相似度的時間復雜度（算法2時間復雜度）

在廣度優(yōu)先搜索過程中，要計算當前節(jié)點 νi和它的鄰居節(jié)點νj（eij∈E）的相似度。要計算其共同好友數(shù)目，假設(shè)di和dj分別為節(jié)點νi和節(jié)點 νj對應(yīng)的度數(shù)，則計算兩者共同好友數(shù)目的時間復雜度為O（didj）。

（3）局部社區(qū)發(fā)現(xiàn)過程的時間復雜度（算法3時間復雜度）

對于廣度優(yōu)先搜索過程，要遍歷當前節(jié)點 νi的所有鄰居節(jié)點νj（eij∈E），并計算兩者的相似度，所以對于單個節(jié)點νi其時間復雜度為假設(shè)需要遍歷k個節(jié)點才能將整個局部社區(qū)發(fā)現(xiàn)出來，并假設(shè) d為整個社區(qū)的平均節(jié)點度數(shù)，所以局部社區(qū)發(fā)現(xiàn)過程的時間復雜度為O（kd3）。再加上算法1的時間復雜度，總的復雜度為由此可見，此算法將原來的具有O（k2）的時間復雜度降低為O（k）。

3.7 算法魯棒性分析

本文算法具有很強的魯棒性。為了避免起始節(jié)點位于邊界，采取算法1FindMaχConnection（ν0）來找出起始節(jié)點ν0相對應(yīng)的最大結(jié)合性節(jié)點，此最大結(jié)合性節(jié)點一般位于比較中心的位置，從此節(jié)點出發(fā)進行社區(qū)發(fā)現(xiàn)可以避免邊界起始節(jié)點魯棒性差的缺點。另外在函數(shù)getSimilarity（data1，data2）中分母為這樣節(jié)點度數(shù)較小的節(jié)點也可以發(fā)現(xiàn)節(jié)點度數(shù)較大的鄰居節(jié)點，提高了算法魯棒性。

4 實驗結(jié)果分析

為驗證算法的正確性，引入Precision，recall，F(xiàn)-measure3個指標，分別定義為：

從以上公式可以看出，Precision表示真實社區(qū)和算法挖掘出來的社區(qū)的交集占算法挖掘出來的社區(qū)的比例。recall表示真實社區(qū)和算法挖掘出來的社區(qū)的交集占真實社區(qū)的比例。F-measure表示Precision和recall的幾何平均數(shù)。

將此算法應(yīng)用到經(jīng)典的社區(qū)網(wǎng)絡(luò)中，分別是日本足球俱樂部網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)、大學生足球賽網(wǎng)絡(luò)和美國政治書籍網(wǎng)絡(luò)。各個網(wǎng)絡(luò)的社區(qū)規(guī)模如表 1所示。

表1 經(jīng)典數(shù)據(jù)集

為了驗證算法的有效性，將此算法和原來的經(jīng)典局部社區(qū)挖掘算法以及近幾年新提出的局部社區(qū)挖掘算法進行對比。包括Clauset算法（簡稱M算法）、Luo算法（簡稱R算法）、Lee算法（簡稱F算法）、Chen算法（簡稱LMD算法）、Zhu算法（簡稱LMD-CD

算法）。在本文的算法中，對于getSimilarity（u，ν）≥sth中閾值sth的設(shè)置比較重要，sth的取值不同，所發(fā)現(xiàn)社區(qū)的精度區(qū)別很大。在此取sth=0.5。實驗結(jié)果如表2所示。

表2 對不同數(shù)據(jù)集的實驗結(jié)果

從上面的顯示結(jié)果可以看出，對于日本足球俱樂部網(wǎng)絡(luò)，本文所采用的算法無論在準確率、召回率以及綜合值上面均是最優(yōu)的。對于海豚網(wǎng)絡(luò)和足球隊網(wǎng)絡(luò)，除了召回率本文算法低于LMD算法之外，其他2個指標均高于其他算法，尤其是綜合值。對于政治書籍網(wǎng)絡(luò)，本文算法在召回率和綜合值上面均是最優(yōu)的。由此可以得出，本文算法在將時間復雜度降低為社區(qū)規(guī)模的線性復雜度的前提下，仍然提高了算法精度，是一個可選算法。

5 結(jié)束語

本文提出的局部社區(qū)發(fā)現(xiàn)算法從起始節(jié)點的最大結(jié)合性節(jié)點出發(fā)，對整個社區(qū)進行BFS搜索，基于共同好友數(shù)目考慮是否將一個節(jié)點加入到已經(jīng)發(fā)現(xiàn)的社區(qū)中。將本文算法應(yīng)用到各種經(jīng)典社區(qū)中均取得了良好的效果。本文算法最大的優(yōu)勢是將社區(qū)發(fā)現(xiàn)的時間復雜度由O（k2）降低到O（k）。

［1］ Jonsson P F，Cavanna T，Zicha D，et al.Cluster Analysis of Networks Identification of Important Protein Communities Involved in Cancer Metastasis［J］.BMC Bioinformatics，2006，6（7）：2-9.

［2］ 蔡波斯，陳 翔.基于行為相似度的微博社區(qū)發(fā)現(xiàn)算法研究［J］.計算機工程，2013，39（8）：55-59.

［3］ 熊正理，姜文君，王國軍.基于用戶緊密度的在線社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法［J］.計算機工程，2013，39（8）：50-54.

［4］ Dourisboure Y，Geraci F，Pellegrini F.Extraction and Classification of Dense Communities Int-the Web［C］// Proceedings of the 16th International Conference on World Wide Web.Washington D.C.，USA：IEEE Press，2007：461-470.

［5］ Girvan M，Newman M E.Comm unity Structure in Socialand Biological Networks［J］.Sciences of the United States of America，2002，99（12）：7821-7826.

［6］ 郭進時，湯紅波，葛國棟.一種聯(lián)合拓撲與屬性的社區(qū)模糊劃分算法［J］.計算機工程，2013，39（11）：35-40.

［7］ Li Xiang，Chen Guanrong.A Local-world Evolving Network Model［J］.Physical A：Statistical Mechanics and Its Applications，2003，328（1/2）：274-286.

［8］ Clauset A.Finding Local Comm unity Structure in Networks［J］.Physical Review E，2005，72（2）.

［9］ Luo Feng，Wang J Z，Promislow E.Exploring Local Community Structures in Large Networks［C］// Proceedings of 2006 IEEE/WIC/ACM International Conference on Web Intelligence.Washington D.C.，USA：IEEE Press，2006：233-239.

［10］ Lancichinetti A，F(xiàn)ortunato S，Kertesz J.Detecting the Overlapping and Hierarchical Comm unity Structure in Complex Networks［J］.New Journal of Physics，2009，11（3）.

［11］ Girvan M，Newman ME.Finding and Evaluating Community Structure in Networks［J］.Physical Review E，2004，69（2）.

［12］ Newman M E.Modularity and Comm unity Structure in Networks［J］.Sciences of the United States of America，2006，103（23）：8857-8882.

［13］ Acu?a M A，Dorso G.Detection of Community Structures in Networks via Global Optimization［J］. Physica A：Statistical Mechanics and Its Applications，2005，538（1）：593-604.

［14］ Jure L，Kevin J L，Anirban D，et al.Community Structure in Large Networks：Natural Cluster Sizes and the Absence of Large W ell-defined Clusters［EB/OL］.（2009-10-21）.http：//projecteuclid.org/euclid.im.

［15］ Newman M E.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E，2004，69（6）.

［16］ Gibson D，Kumar R，Tom kins A.Discovering Large Dense Subgraphs in Massive Graphs［C］//Proceedings of the 31st International Conference on Very Large Bases Databases.Washington D.C.，USA：IEEE Press，2005：721-732.

［17］ Fortunato S.Comm unity Detection in Graphs［J］.Physics Reports，2010，486（3）：75-174.

編輯 索書志

Local Community Discovery Algorithm Based on Bread th-first Search

WANG Yuzhong，F(xiàn)AN Lei，LI Jianhua
（School of Electronic Information and Electrical Engineering，Shanghai Jiaotong University，Shanghai200240，China）

Local community detection is a hot topic in network topology research recently，this paper proposes a local community detection algorithm based on a given node.This algorithm starts from original node，finds the max connective node relevant to the original node，uses Breadth-first Search（BFS）based on node similarity to find local community，and cuts off the found community and gets the entire community which contains the original node.Experimental result shows that this algorithm reduces the time complexity to O（kd3）with high accuracy.

max associativity；common number of friends；node similarity；Breadth-first Search（BFS）；local community detection

王豫中，范 磊，李建華.基于廣度優(yōu)先搜索的局部社區(qū)發(fā)現(xiàn)算法［J］.計算機工程，2015，41（10）：37-41.

英文引用格式：Wang Yuzhong，F(xiàn)an Lei，Li Jianhua.Local Community Discovery Algorithm Based on Breadth-first Search［J］.Computer Engineering，2015，41（10）：37-41.

1000-3428（2015）10-0037-05

A

TP391

國家“973”計劃基金資助項目（2013CB329603）；上海市科委基礎(chǔ)研究領(lǐng)域基金資助項目（13JC1403500）。

王豫中（1990-），男，碩士研究生，主研方向：社交網(wǎng)絡(luò)，數(shù)據(jù)挖掘；范 磊，副教授；李建華，教授。

2014-09-02

2014-10-15E-mail：wangyuzhong@sjtu.edu.cn