基于廣度優先搜索的局部社區發現算法

王豫中，范 磊，李建華

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

基于廣度優先搜索的局部社區發現算法

王豫中，范 磊，李建華

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

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

最大結合性；共同好友數；節點相似度；廣度優先搜索；局部社區發現

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

1 概述

隨著網絡的發展，越來越多的學者開始研究復雜網絡，如：社交網絡，蛋白質網絡［1］，簽名網絡，微博社區網絡［2］，通信網絡，在線社會網絡［3］以及W eb網絡［4］。大量的研究表明，社區結構普遍地存在于大型網絡中，并扮演著重要的角色。研究發現在社區結構內部的節點聯系相對比較緊密，而在社區結構之間節點聯系相對比較稀疏［5］。發現社區結構對于研究大型復雜網絡具有現實以及長遠意義。

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

本文算法從起始節點的最大結合性節點出發，用圖的廣度優先搜索算法（BFS）進行社區發現。對于圖中的每一個節點，用該算法找到它所在的局部社區，并采用經典的衡量標準來驗證算法的有效性和優越性。

2 相關工作

用G=（V，E）來代表整個網絡，其中，V表示節點集合；E表示邊集合。n和 m分別代表節點的個數和邊的個數。和全局社區發現將整個網絡劃分為幾個社區不同的是，局部社區發現算法定義一個起始節點ν0，發現這個節點ν0所在的社區。

文獻［11］定義了局部社區發現問題，將局部社區發現問題轉換為最優化問題，在此將該算法簡記為M算法。

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

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

文獻［12］提出另外一種最優化算法來發現局部社區，簡記為R算法。最優化函數定義為：

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

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

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

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

3 本文算法

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

本文提出一種新的局部社區發現算法，該算法從一個起始節點相對應的最大結合性節點出發，基于2個節點的共同好友數目，利用經典的廣度優先搜索算法來進行社區發現。發現起始節點相對應的最大結合性節點：一是可以提高算法的魯棒性，避免邊界節點找不到社區的情況；二是可以降低尋找局部最大中心點的時間復雜度。基于共同好友數目并且結合廣度優先搜索的算法將時間復雜度由原來的O（k2）降低到O（k）。

3.1 相似度

相似度用來衡量2個個體之間連接的緊密程度，如果2個個體的相似度越大，則它們屬于同一個社區的概率也就越大。基本的相似度度量有歐氏距離、Jaccard相似性［16］以及余弦函數［17］等。本文中用來衡量2個節點的相似度定義為：

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

3.2 節點的最大結合性

3.2.1 節點的結合性

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

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

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

3.3 社區的鄰居節點集合

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

3.4 節點社區的內度和外度

一個節點對于社區的內度定義為此節點的鄰居節點中在社區內部的節點的個數。

一個節點對于社區的外度定義為此節點的度數減去節點對于社區的內度。

節點ν對于社區C的內度定義為：

節點ν對于社區C的外度定義為：

3.5 算法過程

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

ν0：起始節點；

dν：節點ν的結合性；

w0：節點ν0對應的最大結合性節點；

C：被發現的局部社區；

Q：廣度優先搜索算法中用到的隊列；

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

sth：相似度閾值。

算法步驟如下：

（1）初始化社區 C為空，從起始節點 ν0出發找到它所對應的最大結合性節點 w0，將節點 w0加入C，并標記w0為已經訪問過的節點。

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

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

0.5 的正確性。

算法的偽代碼描述如下：

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

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

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

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

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

算法4main：尋找ν0的局部社區入口函數

代碼中BFS-Process（ν0）表示從起始節點ν0出發發現局部社區的過程，對應算法3的函數調用，函數返回被發現的局部社區。

3.6 算法復雜度分析

本文算法的時間復雜度分析主要包括兩部分。一部分是發現指定起始節點的最大結合性節點部分的時間復雜度，另外一部分是局部社區發現部分的時間復雜度。

（1）發現指定起始節點最大結合性節點部分的時間復雜度（算法1時間復雜度）

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

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

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

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

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

（3）局部社區發現過程的時間復雜度（算法3時間復雜度）

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

3.7 算法魯棒性分析

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

4 實驗結果分析

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

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

將此算法應用到經典的社區網絡中，分別是日本足球俱樂部網絡、海豚網絡、大學生足球賽網絡和美國政治書籍網絡。各個網絡的社區規模如表 1所示。

表1 經典數據集

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

算法）。在本文的算法中，對于getSimilarity（u，ν）≥sth中閾值sth的設置比較重要，sth的取值不同，所發現社區的精度區別很大。在此取sth=0.5。實驗結果如表2所示。

表2 對不同數據集的實驗結果

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

5 結束語

本文提出的局部社區發現算法從起始節點的最大結合性節點出發，對整個社區進行BFS搜索，基于共同好友數目考慮是否將一個節點加入到已經發現的社區中。將本文算法應用到各種經典社區中均取得了良好的效果。本文算法最大的優勢是將社區發現的時間復雜度由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］ 蔡波斯，陳 翔.基于行為相似度的微博社區發現算法研究［J］.計算機工程，2013，39（8）：55-59.

［3］ 熊正理，姜文君，王國軍.基于用戶緊密度的在線社會網絡社區發現算法［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］ 郭進時，湯紅波，葛國棟.一種聯合拓撲與屬性的社區模糊劃分算法［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，Fortunato 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，FAN 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

王豫中，范 磊，李建華.基于廣度優先搜索的局部社區發現算法［J］.計算機工程，2015，41（10）：37-41.

英文引用格式：Wang Yuzhong，Fan 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）；上海市科委基礎研究領域基金資助項目（13JC1403500）。

王豫中（1990-），男，碩士研究生，主研方向：社交網絡，數據挖掘；范 磊，副教授；李建華，教授。

2014-09-02

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