針對有向圖的局部擴展的重疊社區(qū)發(fā)現(xiàn)算法＊

張海燕 梁 循 周小平

（1.中國人民大學(xué)信息學(xué)院，北京，100872；2.寧夏大學(xué)數(shù)學(xué)計算機學(xué)院，銀川，750021）

引 言

隨著Web 2.0的深入應(yīng)用，虛擬社會網(wǎng)絡(luò)已經(jīng)成為人們生活的重要組成部分，在不同的社會網(wǎng)絡(luò)中，人們發(fā)現(xiàn)個體之間往往存在某些共同特性，即網(wǎng)絡(luò)的群體特性［1，2］。一般情況下，把內(nèi)部聯(lián)系緊密、外部聯(lián)系稀疏的一群個體稱為社區(qū)，它反映了網(wǎng)絡(luò)元素之間的拓撲關(guān)系和功能實體，在不同的應(yīng)用領(lǐng)域，社區(qū)代表不同的實體關(guān)系群。從巨大的社會網(wǎng)絡(luò)中挖掘出社區(qū)的過程被稱為社區(qū)發(fā)現(xiàn)，是社會網(wǎng)絡(luò)分析的一個基本任務(wù)［1］。因此，發(fā)現(xiàn)并分析網(wǎng)絡(luò)所隱藏的社區(qū)結(jié)構(gòu)對了解現(xiàn)實生活中各種社會網(wǎng)絡(luò)具有重要的意義，在生物學(xué)、計算機科學(xué)以及社會學(xué)等領(lǐng)域都有著廣泛的應(yīng)用［3］。

盡管社區(qū)發(fā)現(xiàn)已經(jīng)受到研究者們廣泛關(guān)注，但是，迄今為止大部分的研究成果都集中于無向圖的社區(qū)發(fā)現(xiàn)［4］。依據(jù)無向圖的社區(qū)發(fā)現(xiàn)算法的核心思想，本文將其劃分為非重疊和重疊社區(qū)發(fā)現(xiàn)兩類算法，算法劃分的結(jié)果如圖1所示。其中，圖1上半部分表示非重疊社區(qū)發(fā)現(xiàn)算法，非重疊社區(qū)發(fā)現(xiàn)可看作是硬分類，即每個結(jié)點有且僅能屬于一個社區(qū)；圖1下半部分表示重疊社區(qū)發(fā)現(xiàn)算法，重疊社區(qū)發(fā)現(xiàn)是軟分類，是指網(wǎng)絡(luò)中的結(jié)點可屬于多個社區(qū)。最早的非重疊社區(qū)發(fā)現(xiàn)算法應(yīng)追溯到基于圖論的圖分割算法［5］，其是解決社區(qū)發(fā)現(xiàn)問題的最直接方法，也是一種優(yōu)化方法，但其不足是需要事先指定社區(qū)數(shù)目。2004年Girvan和Newman提出了經(jīng)典的GN（Girvan-Newman）算法［6］，邊介數(shù)概念是GN算法的核心內(nèi)容，通過刪除邊介數(shù)高的邊從而分裂得到整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，但是，GN算法由于計算量大而很難適用于結(jié)點數(shù)目上萬級的大型復(fù)雜網(wǎng)絡(luò)［3］。同年Newman在PNAS會議上又提出了衡量社區(qū)劃分優(yōu)劣的模塊度Q概念［7］，之后，最大化模塊度的自下而上的合并算法和優(yōu)化模塊度的發(fā)現(xiàn)算法被研究者廣泛提出。盡管最大化模塊度Q一度成為衡量社區(qū)劃分優(yōu)劣的依據(jù)，但是由于其依賴于全局的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，會導(dǎo)致大的計算量［5］，而且，分辨率限制的問題也是模塊度優(yōu)化方法的癥結(jié)。隨著社會網(wǎng)絡(luò)的不斷發(fā)展以及研究工作的深入，研究者發(fā)現(xiàn)社區(qū)的重疊性是個顯而易見的網(wǎng)絡(luò)特性，忽略重疊性會降低所發(fā)現(xiàn)社區(qū)的質(zhì)量，也會掩蓋重疊結(jié)點所隱藏的重要信息而造成結(jié)點的誤判，但是，重疊性也是社區(qū)發(fā)現(xiàn)中難以量化的屬性，給社區(qū)發(fā)現(xiàn)算法帶來了新的難點［5，8］。2005年P(guān)alla等提出派系過濾（Clique percolation method，CPM）算法［9］，CPM算法的本質(zhì)是認為典型的社區(qū)應(yīng)是全連通的完全子圖，全連通子圖之間共享的結(jié)點是重疊結(jié)點，其主要目的就是找到緊密相連的完全子圖，盡管CPM算法對重疊社區(qū)的發(fā)現(xiàn)一般來說很有效，但搜索完全子圖非常耗時，而且完全子圖的大小值k不易確定。2007年Gregory［10］在第11屆歐洲國際數(shù)據(jù)挖掘原理與發(fā)現(xiàn)會議上提出改進GN算法的重疊社區(qū)發(fā)現(xiàn)算法（Clusteroverlap Newman Girvan algorithm，CONGA），但由于CONGA算法通過分裂結(jié)點為多個克隆結(jié)點來解決重疊結(jié)點的問題，因此，其仍然無法克服GN算法計算量大的問題。2009年Lancichinetti［11］提出局部測量擬合度的社區(qū)發(fā)現(xiàn)算法（Local fitness measure，LFM）從局部擬合構(gòu)造社區(qū)，局部性反映了社區(qū)的自然特性［12］，但隨機選擇初始節(jié)點會影響LFM算法的社區(qū)發(fā)現(xiàn)結(jié)果。盡管重疊社區(qū)發(fā)現(xiàn)算法受到了研究者的關(guān)注，但是重疊性的衡量標準仍然沒有得到有效解決，如何衡量結(jié)點與社區(qū)的重疊程度，還需進一步研究。

在現(xiàn)實世界的復(fù)雜網(wǎng)絡(luò)中，鏈接關(guān)系并不總是對稱的或無方向的，針對這類具有非對稱的有方向關(guān)系所構(gòu)造的圖，無向圖中的社區(qū)發(fā)現(xiàn)算法不能直接適用，如果忽略了網(wǎng)絡(luò)中關(guān)系的方向性，會丟失一些隱藏的重要信息［13］?；谟邢驁D的社區(qū)發(fā)現(xiàn)是社會網(wǎng)絡(luò)研究中相對較新的發(fā)展點，目前也有了一些探索性的研究成果。2011年Satuluri［14］提出了對稱化有向圖的方法，基于結(jié)點之間的指向邊與被指向邊的相似性對稱化有向圖的鏈接矩陣，由此達到有向圖變無向圖的目的。然而，由于涉及到矩陣的各種運算，對于數(shù)據(jù)量很大的網(wǎng)絡(luò)結(jié)構(gòu)，該方法的計算性能受到限制。也有研究者演變無向圖社區(qū)發(fā)現(xiàn)中的模塊度、譜的概念到有向圖中，給出有向圖下相應(yīng)的定義和社區(qū)發(fā)現(xiàn)的目標函數(shù)，從優(yōu)化目標函數(shù)的角度出發(fā)進行社區(qū)發(fā)現(xiàn)。還有從實際應(yīng)用領(lǐng)域出發(fā)研究符合有向邊實際意義的有向圖社區(qū)發(fā)現(xiàn)算法。由于有方向關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu)中，方向往往表達一些重要的信息且無法像無向圖那樣對稱處理，方向意味著信息流動的走向以及信息傳播的趨勢，因此，有向圖的社區(qū)發(fā)現(xiàn)主要還應(yīng)從方向入手來解決問題。本文首先提出了基于k-Path的共社區(qū)鄰近相似性的概念和計算方法及局部擴展的重疊社區(qū)發(fā)現(xiàn)算法（Local and wave-like extension algorithm of detecting overlapping community，LWS-OCD）算法。

圖1 無向圖的社區(qū)發(fā)現(xiàn)算法分類Fig.1 Classification of community detection in undirected network

1 共社區(qū)鄰近相似性計算

為了衡量網(wǎng)絡(luò)中結(jié)點之間在關(guān)系網(wǎng)絡(luò)中的聚集程度，本文首先提出了共社區(qū)鄰近相似性的概念，共社區(qū)鄰近相似性描述了任意兩個結(jié)點在同一個社區(qū)的鄰近程度，同時給出了計算共社區(qū)鄰近相似性的計算方法，這個計算方法適用于無向圖也適用于有向圖。其次，為了解決有向圖的方向問題，本文提出轉(zhuǎn)換有向圖為帶權(quán)值的無向圖的方法，目的是將有向圖中的方向信息無損保留到無向圖中。

1.1 k-Path的共社區(qū)鄰近相似性

盡管在無向圖中，結(jié)點之間的鏈接關(guān)系無方向，然而，從實際網(wǎng)絡(luò)應(yīng)用中會發(fā)現(xiàn)，鏈接關(guān)系中隱藏著信息的走向，因此，結(jié)點之間的鏈接關(guān)系更多地是表現(xiàn)為信息在結(jié)點之間傳播。那么，若兩個結(jié)點之間有多條鏈接的通路，表明這兩個結(jié)點之間信息傳播的渠道更多，意味著兩個結(jié)點聯(lián)系得更緊密，或者說兩個結(jié)點信息交流得更便捷，因此，多通路特性反映出兩個結(jié)點在同一個社區(qū)的機率會增大。在有向圖上進行社區(qū)發(fā)現(xiàn)，不能直接延用無向圖中的方法，因為有向圖中的邊是非對稱的，方向性蘊含著有價值的信息。正像文獻［13］中所描述的那樣，很多在無向圖中常用的概念移植到有向圖中就不適用了，比如說：社區(qū)內(nèi)的邊密度和社區(qū)外的邊密度，當(dāng)把密度的概念直接用到有向圖時，有向邊的方向就會被忽略。對于有向圖來說，方向是個很關(guān)鍵的因素，并且方向代表著信息流動的可能性，與無向圖中信息傳播的原理一樣，結(jié)點之間的鏈接通路越多，結(jié)點之間信息流動得更頻繁，那么結(jié)點之間的聯(lián)系會更緊密，因此，多通路特性在有向圖中不僅衡量了方向性的強弱關(guān)系，同時也反映了結(jié)點在同一社區(qū)的可能性大小?？傊?，無論對于無向圖還是有向圖，多通路特性都可表明圖中結(jié)點之間在同一社區(qū)的鄰近相似性。為了說明方便，本文在有向圖上描述相應(yīng)的概念，但是，概念對于無向圖同樣適用。

定義1k-Path通路

假定G＝〈V，E〉表示有向圖，V是結(jié)點集，E是有向邊集，k是大于0的正數(shù)，k-Path通路指的是由邊序列e1，e2，…，ek所形成的通路，即經(jīng)過k條邊的單向通路。若G是無向圖，則表示結(jié)點之間經(jīng)過k條邊的通路。

定義2 共社區(qū)鄰近相似性

假定G＝〈V，E〉表示有向圖，V是結(jié)點集，E是有向邊集，L是大于0的正數(shù)，共社區(qū)鄰近相似性SL（a，b）指的是：?a，b∈V，結(jié)點a與結(jié)點b分別經(jīng)過1-Path，2-Path，…，L-Path通路的總數(shù)之和。換句話說，結(jié)點a到達結(jié)點b經(jīng)過1條邊、2條邊、直到L條邊的所有通路之和，定義如式（1）所示

1.2 有向轉(zhuǎn)換為無向的方法

在共社區(qū)鄰近相似性概念的基礎(chǔ)上，令G為初始的有向圖，G＝〈V，E〉，為轉(zhuǎn)換后的無向圖，其中W是邊的權(quán)值集合，有向圖G到無向圖的轉(zhuǎn)換策略為：（1）＝V；（2）若SL（a，b）＞0或SL（b，a）＞0，則e＝（a，b）∈；（3）若e＝（a，b）∈，則We＝SL（a，b）＋SL（b，a）。

轉(zhuǎn)換策略在不丟失有向圖的方向信息的情況下，將方向轉(zhuǎn)換為無向圖中邊的權(quán)值，即為帶權(quán)無向圖［15］，其中的權(quán)值代表結(jié)點之間在同一社區(qū)的鄰近相似性。

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

在現(xiàn)實生活中，社區(qū)的形成一般是從一些小群體開始的，每個人無論在真實生活中還是在虛擬世界中，往往都是先從熟悉的生活圈子或是個體出發(fā)，即從整個關(guān)系網(wǎng)絡(luò)中的局部形成規(guī)模，然后再不斷地擴張和延伸，因此，對于實際的復(fù)雜網(wǎng)絡(luò)，小群體和局部性就是社區(qū)的自然特性。本文提出的局部擴展的社區(qū)發(fā)現(xiàn)算法是先找出關(guān)系網(wǎng)絡(luò)中的聯(lián)系相對緊密的“小群體”，然后，再通過這些“小群體”之間的關(guān)系來判斷是否能構(gòu)成更大的“群體”，最終形成整個關(guān)系網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

文獻［11］中提出的LFM算法是從局部擬合構(gòu)造社區(qū)的發(fā)現(xiàn)算法，LFM算法通過試探當(dāng)前社區(qū)波及到的所有結(jié)點來判定結(jié)點是否屬于當(dāng)前的社區(qū)，然而，事實上，在圈定社區(qū)內(nèi)的結(jié)點時，沒有必要去試探所有的結(jié)點，因為按照六度分割原理，社區(qū)中的任意結(jié)點之間最多通過6個人就可達到聯(lián)系，因此，本文認為只需要判定某個范圍內(nèi)的結(jié)點是否屬于當(dāng)前社區(qū)即可，而且探測過程中，根據(jù)結(jié)點之間的相似性大小來優(yōu)先選擇結(jié)點，勢必會縮短社區(qū)形成的時間，本文將有限探測范圍所波及的結(jié)點確定為小社區(qū)，之后再以這些小社區(qū)為基礎(chǔ)，構(gòu)成更大社區(qū)。

2.1 概念定義

2.1.1 結(jié)點與社區(qū)的貼近度

式中：α是分辨率系數(shù)，用來控制社區(qū)的大小；C是社區(qū)，C＋｛u｝是指在社區(qū)C中加入結(jié)點u形成新社區(qū)，是指社區(qū)C內(nèi)的全部邊的權(quán)值之和，是指有且僅有一個結(jié)點在社區(qū)C內(nèi)的邊的權(quán)值之和。式（2）目的是用來判定結(jié)點是否能加入到社區(qū)中，意義是當(dāng)社區(qū)C中添加了結(jié)點u形成新的社區(qū)，若所形成的新社區(qū)內(nèi)部邊的權(quán)值之和增幅高于原先沒有添加結(jié)點u時的內(nèi)部權(quán)值之和的增幅，說明添加結(jié)點u不僅擴展了社區(qū)C，而且也增大了社區(qū)C內(nèi)部的緊密度，由此，可判斷結(jié)點u就應(yīng)加入到社區(qū)C中，否則，說明結(jié)點u與社區(qū)C之外的結(jié)點鏈接更緊密。

2.1.2 重疊結(jié)點與社區(qū)的重疊度

重疊度的概念是衡量重疊結(jié)點與其每個所屬的社區(qū)之間的重疊程度。式（3）中，當(dāng)結(jié)點u是重疊結(jié)點時，它屬于多個社區(qū)，假定社區(qū)發(fā)現(xiàn)算法劃定的社區(qū)個數(shù)為n個，式（3）中的分母表示結(jié)點u所屬于的每個社區(qū)的貼近度總和，式（3）的分子表示結(jié)點u屬于當(dāng)前社區(qū)C的貼近度，因此，式（3）表明結(jié)點u屬于當(dāng)前社區(qū)C的貼近度占其所屬的所有社區(qū)的貼近度的比重。由此，OD（u，C）值越大，說明結(jié)點u與當(dāng)前社區(qū)C的重疊度越高，反之，表明結(jié)點u與當(dāng)前社區(qū)C的重疊度低。OD（u，C）是動態(tài)變化的，它與社區(qū)當(dāng)前的狀態(tài)有關(guān)，因此，在整個復(fù)雜網(wǎng)絡(luò)的社區(qū)沒有固定時，重疊結(jié)點與社區(qū)的重疊度會隨著社區(qū)大小而改變。

2.1.3 相鄰社區(qū)

一旦“小群體”（或稱之為小社區(qū)）形成，整個網(wǎng)絡(luò)的狀態(tài)就變成“小群體”與“小群體”之間的交互，如果“小群體”之間有頻繁的聯(lián)系或是緊密性，那么這兩個“小群體”就會在未來組合成更大的群體，反之，這些“小群體”就會以獨立的群體成為網(wǎng)絡(luò)中的社區(qū)。對于復(fù)雜網(wǎng)絡(luò)，組合為更大社區(qū)的最直接辦法就是兩兩小社區(qū)互相判斷組合，然而，根據(jù)現(xiàn)實生活中實際社區(qū)的觀察，兩個社區(qū)之間能組合的可能性是社區(qū)之間或多或少都會有聯(lián)系。因此，本文把具備組合條件的兩個社區(qū)稱之為相鄰社區(qū)，即相鄰社區(qū)應(yīng)該滿足如下條件之一：（1）兩個社區(qū)之間有公共的結(jié)點，即重疊結(jié)點；（2）兩個社區(qū)之間有多條鏈接邊。只有符合這些條件的兩個社區(qū)，才有組合為更大社區(qū)的基礎(chǔ)。相鄰社區(qū)的定義意味著并不需要所有的小社區(qū)互相判定，而只需要在相鄰社區(qū)之間判定組合，這實際是對小社區(qū)在組合之前進行了篩選。

2.1.4 相鄰社區(qū)之間的貼近度

2.2 LWS-OCD算法

局部擴展的重疊社區(qū)發(fā)現(xiàn)算法分為兩部分，（1）局部波動擴展小社區(qū)算法（Local and wave-like extension algorithm of detecting small communities，LWS），目的是以L為最大波長從起始點波動擴展局部小社區(qū)；（2）歸并小社區(qū)的重疊社區(qū)發(fā)現(xiàn)算法（Overlapping community detection algorithm of merging small communities，OCD），合并局部小社區(qū)構(gòu)造網(wǎng)絡(luò)的全局重疊社區(qū)結(jié)構(gòu)。

2.2.1 局部波動擴展小社區(qū)

文獻［11］中提出的LFM算法也是局部擴展的算法，然而，LFM算法是隨機選擇初始結(jié)點，并且在局部區(qū)域選擇結(jié)點時并不考慮結(jié)點之間的不同，結(jié)點與結(jié)點之間是沒有關(guān)系強弱之分，隨機選擇結(jié)點的所有鄰接結(jié)點判斷并選擇其中擬合度最大的結(jié)點，當(dāng)結(jié)點的鄰接數(shù)目很多時，探測的過程很費時。本文認為結(jié)點之間的關(guān)系應(yīng)有強弱之分，強關(guān)系的結(jié)點應(yīng)比弱關(guān)系的結(jié)點更早地被選入社區(qū)。

LWS算法首先選擇結(jié)點度數(shù)最高的結(jié)點作為社區(qū)的起始點，這樣的結(jié)點鏈接其他結(jié)點的數(shù)目多，更有可能是小社區(qū)中的中心結(jié)點，也是與周圍結(jié)點聯(lián)系頻繁的結(jié)點。其次，根據(jù)式（2）從波長1直到最大波長范圍L逐圈選擇并判斷結(jié)點是否要加入社區(qū)，最大波長范圍L可根據(jù)具體問題來設(shè)定。當(dāng)然，按照六度分割原理，網(wǎng)絡(luò)的波長上界為6。在選擇結(jié)點時，本文按照表達強弱關(guān)系的共社區(qū)鄰近相似性權(quán)值對結(jié)點進行篩選，優(yōu)先選擇與中心結(jié)點在同一社區(qū)相似性最高的結(jié)點，由此可減少結(jié)點的選擇時間和誤判。最后，局部構(gòu)造小社區(qū)的過程在最大波長范圍下停止。LWS算法的具體過程如下所示。

輸入：L：最大波長；G（V，E，W）：帶相似性w的無向圖；閾值θ；

輸出：LC＝（C1，C2，…，CI）：小社區(qū)集合。

（1）選擇結(jié)點中度數(shù)最大的結(jié)點u作為起始點并加入社區(qū)CI（初始I＝1），推進的步長T為1；

（2）For（T＜L）Do

以起始點u為波動中心點，結(jié)點u的鄰接邊數(shù)為T的結(jié)點構(gòu)成備選結(jié)點集合；

（3）For（備選結(jié)點集合不空）Do

依次選擇備選結(jié)點集合中的鄰近相似性最高結(jié)點v；

計算結(jié)點v與社區(qū)CI的貼近度F（CI，v）；

IF（貼近度F（CI，v））＞閾值θThen結(jié)點v加入社區(qū)CI中構(gòu)成新的社區(qū)CI。

While（社區(qū)CI有變化）Do

重新計算社區(qū)CI中每個結(jié)點w與社區(qū)的貼近度；

若結(jié)點w與社區(qū)CI貼近度為負，則將結(jié)點w移出社區(qū)CI；

End while（社區(qū)CI有變化）

End For（備選結(jié)點集合不空）

步長T增加1，返回到（2）

End For（T＜L）

（4）若存在未分區(qū)的結(jié)點，社區(qū)數(shù)目I＋1，則選擇下一個結(jié)點度最大的結(jié)點作為起始點u，返回（1）。

2.2.2 小社區(qū)組合

算法LWS結(jié)束后會獲得局部穩(wěn)定的小社區(qū)，這些小社區(qū)是聯(lián)系緊密的“小群體”，但還不是最終的社區(qū)結(jié)構(gòu)，因為“小群體”是整個網(wǎng)絡(luò)的初始劃分，還需要進一步探究“小群體”之間的關(guān)系，以此判斷是否達到整個網(wǎng)絡(luò)結(jié)構(gòu)劃分的穩(wěn)定態(tài)，所以，算法OCD的目的是合并小社區(qū)形成整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

首先，依據(jù)相鄰社區(qū)的定義來判定社區(qū)之間是否是相鄰社區(qū)，然后，在判定為相鄰社區(qū)的兩個社區(qū)之間測量社區(qū)之間的貼近度，若兩社區(qū)之間的貼近度大于事先設(shè)定的閾值，則合并相鄰社區(qū)為一個社區(qū)，最后，不斷迭代此過程，直到社區(qū)之間無合并，則迭代結(jié)束時的社區(qū)結(jié)構(gòu)就是整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

OCD算法的具體過程如下所示。

輸入：LC＝（C1，C2，…，CI）：小社區(qū)（算法LWS的結(jié)果）；閾值δ；

輸出：C＝（C1，C2，…，CK）：社區(qū)。

（1）小社區(qū)集合作為社區(qū)的初始集合C＝LC，K＝I，即C＝｛C1，C2，……，CK｝；

（2）While（i＜K）Do

從社區(qū)向量C中Ci之后找出社區(qū)Ci的相鄰社區(qū)Ct；

計算社區(qū)Ci與社區(qū)Ct之間的貼近度F（Ci，Ct）；

IFF（Ci，Ct）＞閾值δThen

合并社區(qū)Ci，Ct加入社區(qū)C中形成新社區(qū)Ci；

K＝K-1；

重新計算新社區(qū)Ci中每個結(jié)點與新社區(qū)Ci的貼近度。

End IF

變換下一個小社區(qū)i＝i＋1；

End While（i＜K）

（3）循環(huán)結(jié)束，全局社區(qū)C構(gòu)造完成，所形成的C即為網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)；

（4）確定社區(qū)C中的重疊結(jié)點；

（5）計算重疊結(jié)點與每個所屬社區(qū)的重疊度。

2.2.3 LWS-OCD算法的計算復(fù)雜性分析

重疊社區(qū)發(fā)現(xiàn)算法的復(fù)雜性是很難精確估計的，因為它和網(wǎng)絡(luò)的大小、重疊結(jié)點的個數(shù)以及網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)等因素相關(guān)，同時，在實踐中，算法的效率與數(shù)據(jù)所采用的數(shù)據(jù)結(jié)構(gòu)以及機器性能等因素也有關(guān)。但是，本文從理論上粗略地分析LWS-OCD社區(qū)發(fā)現(xiàn)算法的計算復(fù)雜性。

LWS算法的時間主要消耗在挑選結(jié)點的過程，最耗時的過程有兩個：（1）在當(dāng)前波長T所涉及的范圍圈內(nèi)結(jié)點的貼近度計算，假設(shè)此時圈定范圍的結(jié)點數(shù)目為NT，那么計算時間就是O（NT）。（2）一旦有新結(jié)點加入社區(qū)，就需重新調(diào)整當(dāng)前社區(qū)內(nèi)已有結(jié)點與社區(qū)貼近度的變化，若有某些結(jié)點的貼近度減少以致低于閾值或為負值，則需要將這些結(jié)點移出當(dāng)前社區(qū)，這個過程會不斷重復(fù)，直到社區(qū)內(nèi)的結(jié)點的貼近度都超出閾值。那么，假設(shè)此時社區(qū)內(nèi)的結(jié)點個數(shù)為NC，這個過程的最壞情況是所有結(jié)點都被依次移出，時間復(fù)雜度為O（N2C），然而，本文提出的LWS-OCD算法為了避免這種情況，每次選擇共社區(qū)鄰近相似性最高的結(jié)點判斷，大大減少了與社區(qū)弱相關(guān)結(jié)點的誤移入而造成結(jié)點移出操作，故此部分的時間復(fù)雜度可近似為O（NC）。最終，整個LWS算法的時間復(fù)雜度近似為O（L×NT×NC），其中的NT，NC都是小于結(jié)點個數(shù)N的，L是波長。而對于LFM算法，因為其要遍歷所有當(dāng)前社區(qū)的鄰接點，這個鄰接點數(shù)目遠遠大于離中心點步長為T的NT，所以其計算貼近度的時間是大于O（NT），且LFM算法的初始結(jié)點隨機選擇，結(jié)點選擇的不合適會增加結(jié)點的移出操作，所以其復(fù)雜性高于本文的LWS算法。對于OCD算法而言，它是在小社區(qū)的基礎(chǔ)上的兩兩合并，小社區(qū)的數(shù)目是遠遠低于網(wǎng)絡(luò)結(jié)點數(shù)目N，假設(shè)小社區(qū)的數(shù)目為Cn，那么這個過程最壞的情況下的時間復(fù)雜度O（），然而，大多數(shù)網(wǎng)絡(luò)結(jié)構(gòu)在LWS算法結(jié)束時刻會達到初始穩(wěn)定態(tài)，因此，此部分的時間復(fù)雜度近乎為線性O(shè)（Cn）。綜合算法LWS和算法OCD兩部分，LWS-OCD算法的時間復(fù)雜度為O（L×NT×NC＋），即好的情況下可近似為O（n2）的量級。

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

3.1 測試數(shù)據(jù)集

本文所采用的兩組真實數(shù)據(jù)集網(wǎng)絡(luò)如下：第1組數(shù)據(jù)是有向圖的數(shù)據(jù)集，來源于最大的社會網(wǎng)絡(luò)研究組織。選擇了其中的數(shù)據(jù)集Wiki-Vote。Wiki-Vote數(shù)據(jù)集是維基百科（Wikipedia）網(wǎng)站中2008年百科版塊中的投票數(shù)據(jù)，包括7 115個結(jié)點和103 689條邊。第2組數(shù)據(jù)是無向圖的數(shù)據(jù)集，選擇海豚關(guān)系網(wǎng)Dolphins數(shù)據(jù)集［16］，包括62個結(jié)點和159條邊；另外一個是科學(xué)家合作網(wǎng)Netscience數(shù)據(jù)集，包括1 589個結(jié)點和2742條邊。

本文的實驗環(huán)境是在CPU為Intel i5 3.2GHz，內(nèi)存為4GB的64位Win7機器上，共社區(qū)鄰近相似性的計算以及有向圖轉(zhuǎn)換為帶權(quán)無向圖分別采用Visual C和Matlab7.0的編譯環(huán)境。為了充分說明算法的有效性，本文選擇文獻［11］中提出的局部擬合的LFM重疊社區(qū)發(fā)現(xiàn)算法進行實驗對比，LWSOCD算法和對比算法LFM采用Visual C的編譯環(huán)境完成實驗的測試和驗證任務(wù)。

3.2 共社區(qū)鄰近相似性的實驗結(jié)果和分析

3.2.1 時間效率的對比

無論是無向圖還是有向圖，共社區(qū)鄰近相似性是社區(qū)發(fā)現(xiàn)算法的基礎(chǔ)，也是圖中結(jié)點相似性的一種有效測量方法。本文采用了Matlab的編譯環(huán)境，運用矩陣運算的優(yōu)勢來完成共社區(qū)鄰近相似性的計算過程，針對有向圖數(shù)據(jù)集Wiki-Vote和無向圖的數(shù)據(jù)集Netscience，完成在不同的路徑長度下計算共社區(qū)鄰近相似性所需時間的對比實驗，實驗結(jié)果如圖2所示。在圖2中，Netscience的網(wǎng)絡(luò)結(jié)點數(shù)目少，因此所用時間就短，而Wiki-Vote的網(wǎng)絡(luò)結(jié)點數(shù)目是Netscience的4倍多，因此其所用時間明顯比Netscience多。此外，隨著鏈接路徑的長度增大，共社區(qū)鄰近相似性的計算時間也會呈線性增加。由此可知，共社區(qū)鄰近相似性的計算時間主要還是取決于網(wǎng)絡(luò)的結(jié)點數(shù)目和鏈接情況，若鏈接相對密集且結(jié)點數(shù)目很多，則共社區(qū)鄰近相似性的計算時間就長，若鏈接相對稀疏則鄰近相似性的計算時間短。事實上，根據(jù)小世界網(wǎng)絡(luò)的特性可知，任何兩個結(jié)點之間最多通過6個人就可達到彼此的聯(lián)系，而且，從現(xiàn)實生活中觀察也可看到，若兩個結(jié)點屬于共同社區(qū)，通常這樣的結(jié)點聯(lián)系會更頻繁些，意味著這樣的結(jié)點之間的鏈接通路都不會太長，否則，它們之間的交互可能性就會很低，表明它們之間在同一社區(qū)的可能性也會降低。由以上原因和實驗效率的觀察，本文認為鏈接通路長為3是共社區(qū)鄰近相似性的最佳選擇。

圖2 共社區(qū)鄰近相似性的計算復(fù)雜性Fig.2 Computational complexity of co-community similarity

3.2.2 對社區(qū)發(fā)現(xiàn)算法的影響

共社區(qū)鄰近相似性對社區(qū)發(fā)現(xiàn)算法所起的效果也不容忽視，為了說明共社區(qū)鄰近相似性所起的作用，圖3中分別列出了LFM算法在未加和加上共社區(qū)鄰近相似性的Dolphins數(shù)據(jù)集網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)結(jié)果。從圖3（a）中可以看到，當(dāng)在原始Dolphins無向圖上實現(xiàn)LFM算法時，網(wǎng)絡(luò)形成了唯一的社區(qū)，而在圖3（b）中，首先為原始的無向圖構(gòu)造最大鏈接通路長為3的共社區(qū)鄰近相似性的帶權(quán)值無向圖，然后在帶相似性權(quán)值的圖上完成LFM社區(qū)發(fā)現(xiàn)算法，可以看到，此時的網(wǎng)絡(luò)被清楚地分為左下部和右上部黑色結(jié)點組成的兩個密集社區(qū)，而其中的灰色結(jié)點為網(wǎng)絡(luò)的重疊結(jié)點，這個社區(qū)劃分結(jié)果與GN算法在Dolphins數(shù)據(jù)集上所進行的社區(qū)劃分結(jié)果相一致。由此可見，共社區(qū)鄰近相似性加權(quán)會起到對網(wǎng)絡(luò)中同一社區(qū)結(jié)點聚集的作用，有助于社區(qū)發(fā)現(xiàn)算法實現(xiàn)密集社區(qū)劃分的效果。

3.3 LWS-OCD算法的實驗結(jié)果和分析

3.3.1 LWS-OCD算法的有效性對比

為了對比本文所提出的LWS-OCD算法的有效性，分別在Dolphins和Netscience兩個無向圖數(shù)據(jù)集中構(gòu)造各自對應(yīng)的鏈接通路長2，3，…，6的共社區(qū)鄰近相似性的帶權(quán)無向圖，然后，在所構(gòu)造的帶權(quán)無向圖上完成LWS-OCD算法和LFM算法。圖4中給出了LFM算法和LWS-OCD算法所挖掘出的重疊結(jié)點個數(shù)占總結(jié)點的比例。圖5中給出了LFM算法和LWS-OCD算法在Netscience數(shù)據(jù)集上所劃分出的社區(qū)的個數(shù)。Dolphins in 3-Path和5-Path分別對應(yīng)Dolphins網(wǎng)絡(luò)在鏈接通路最長為3和5所構(gòu)造的共社區(qū)鄰近相似性的帶權(quán)無向圖，同理，Netscience in 3-Path和5-Path分別對應(yīng)的是Netscience的帶權(quán)無向圖。在不同的帶權(quán)無向圖中，分別在社區(qū)分辨系數(shù)α從0.6，0.65，0.70，……，1.6的每隔0.05的條件下實現(xiàn)LFM和LWS-OCD算法。

圖3 LFM算法的社區(qū)發(fā)現(xiàn)結(jié)果Fig.3 Result of community detection by LFM algorithm

從圖4中可看出，本文提出的LWS-OCD算法除了在Dolphins in 5-Path的帶權(quán)無向圖下的后部出現(xiàn)凸起外，在其他的帶權(quán)無向圖下都比LFM算法的重疊結(jié)點的比例平穩(wěn)，即重疊結(jié)點的數(shù)目不會隨社區(qū)大小的變化而劇烈變化。事實上，在現(xiàn)實網(wǎng)絡(luò)中，對于在某一時刻相對靜止的網(wǎng)絡(luò)來說，一旦社區(qū)結(jié)構(gòu)穩(wěn)定后，社區(qū)是相對清晰的，那么，重疊結(jié)點也會是一定的，不會出現(xiàn)突然的變化。

在圖5中，不論是在3-Path的帶權(quán)無向圖還是在5-Path的帶權(quán)無向圖中，LWS-OCD算法與LFM算法所挖掘的社區(qū)個數(shù)相差不大，由此說明，本文提出的LWS-OCD算法有效。

圖4 重疊結(jié)點在帶權(quán)無向圖上所占的比重Fig.4 Ratio of overlapping node on weighted undirected networks

3.3.2 波長對LWS-OCD算法的影響

為了分析本文提出的LWS-OCD算法受波長范圍的影響，在Netscience無向圖數(shù)據(jù)集的鏈路通路長為3的共社區(qū)鄰近相似性所構(gòu)造的帶權(quán)無向圖上，完成波長范圍2，3，…，6依次變換且社區(qū)分辨率系數(shù)α從0.8變化到1.8，步長0.1的本文提出的LWS-OCD算法。圖6給出了LWS-OCD算法在不同波長范圍下所產(chǎn)生的總社區(qū)個數(shù)和所挖掘出的重疊結(jié)點個數(shù)占總結(jié)點的比例。

圖5 LFM算法與LWS-OCD算法劃分Netscience無向圖的社區(qū)個數(shù)Fig.5 Number of community detected by LFM and LWS-OCD algorithms on Netscience network

從圖6清楚地看到算法當(dāng)波長范圍達到3之后，社區(qū)數(shù)目和重疊結(jié)點的個數(shù)并不以波長的增大而任意擴張，即波長從4到6時社區(qū)數(shù)目的個數(shù)持平，重疊結(jié)點的個數(shù)也是重合的，社區(qū)結(jié)構(gòu)一方面表現(xiàn)出小世界特性，即局部特性，另一方面也反映出社區(qū)結(jié)構(gòu)實際在某一時刻是處于一種穩(wěn)定態(tài)。

圖6 波長范圍對LWS-OCD算法的影響Fig.6 Result of wave influencing LWS-OCD algorithm range

4 結(jié)束語

本文從信息在網(wǎng)絡(luò)中的傳播規(guī)律和流動的方向性出發(fā)，提出了共社區(qū)鄰近相似性的概念，共社區(qū)鄰近相似性是測量結(jié)點在同一社區(qū)的可能性，此概念在無向圖和有向圖中都適用于測量結(jié)點之間的相似性。并基于此概念，給出了有向圖轉(zhuǎn)換成帶權(quán)無向圖的方法，為有向圖的社區(qū)發(fā)現(xiàn)算法提供了不丟失方向性的有效策略。本文針對帶權(quán)無向圖提出了LWS-OCD局部擴展的重疊社區(qū)發(fā)現(xiàn)算法，算法的優(yōu)勢在于從社區(qū)的“小群體”的自然狀態(tài)出發(fā)，然后由“小群體”不斷擴展合并形成更大的社區(qū)。LWS-OCD算法不僅避免了分辨率問題，而且與現(xiàn)實生活中社區(qū)的發(fā)展規(guī)律相一致，同時還能為層次型的社區(qū)發(fā)現(xiàn)做些鋪墊工作。本文下一步的工作是擴展算法到并行環(huán)境，以此來提高LWS-OCD算法在大數(shù)據(jù)復(fù)雜網(wǎng)絡(luò)中的可擴展性。另外，針對有向圖的社區(qū)發(fā)現(xiàn)算法是當(dāng)前社區(qū)發(fā)現(xiàn)算法的研究熱點，本文將提出直接在有向圖上進行社區(qū)發(fā)現(xiàn)的算法，即不經(jīng)過有向到無向的轉(zhuǎn)換，由于有向圖中方向性的存在，這必然是個有挑戰(zhàn)性的工作。

［1］ Easley D，Kleinberg J.Networks，crowds，and markets：Reasoning about a highly connected world［M］.Cambridge：Cambridge University Press，2010.

［2］ 周耀明，李弼程.一種自適應(yīng)網(wǎng)絡(luò)輿情演化建模方法 ［J］.數(shù)據(jù)采集與處理，2013，28（1）：69-76.

Zhou Yaoming，Li Bicheng.Adaptive evolution modeling method of internet public opinions［J］.Journal of Data Acquisition and Processing，2013，28（1）：69-76.

［3］ Tang Lei，Liu huan.社會計算：社區(qū)發(fā)現(xiàn)和社會化媒體挖掘 ［M］.文益民，閉應(yīng)洲，譯.北京：機械工業(yè)出版社，2012.Tang Lei，Liu Huan.Community detection and mining in social media［M］.Beijing：China Machine Press，2012.

［4］ Fortunato S.Community detection in graphs［J］.Physics Reports，2010，486（3）：75-174.

［5］ 程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu) ［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（1）：57-70.

Cheng Xueqi，Shen Huawei.Community structure of complex networks［J］.Complex Systems and Complexity Science，2011，8（1）：57-70.

［6］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical review E，2004，69（2），026113.

［7］ Newman M E J.Detecting community structure in networks［J］.The European Physical Journal B-Condensed Matter and Complex Systems，2004，38（2）：321-330.

［8］ Xie J，Kelley S，Szymanski B.Overlapping community detection in Networks：the state-of-the-art and comparative study［J］.ACM Computing Surveys，2013，45（4）.43：1-35.

［9］ 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（7043）：814-818.

［10］Gregory S.An algorithm to find overlapping community structure in networks［C］／／Proceedings of Knowledge Discovery in Databases：PKDD 2007，11th European Conference on Principles and Practice of Knowledge Discovery in Databases.Warsaw，Poland：Lecture Notes in Computer Science，2007：91-102.

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

［12］Chen D，Shang M，LV Z，et al.Detecting overlapping communities of weighted networks via a local algorithm［J］.Physica A，2010，389（19）：4177-4187

［13］Malliaros F D，Vazirgiannis M.Clustering and community detection in directed networks：A survey［J］.Physics Reports，2013，533（4）：95-142.

［14］Satuluri V，Parthasarathy S.Symmetrizations for clustering directed graphs［C］／／Proceedings of the 14th International Conference on Extending Database Technology.［S.l.］：ACM，2011：343-354.

［15］De M P，F(xiàn)errara E，F(xiàn)iumara G，et al.Enhancing community detection using a network weighting strategy［J］.Information Sciences，2013，222：648-668.

［16］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations［J］.Behavioral Ecology and Sociobiology，2003，54（4）：396-405.