張海燕 梁 循 周小平

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

引 言

隨著Web 2.0的深入應(yīng)用，虛擬社會(huì)網(wǎng)絡(luò)已經(jīng)成為人們生活的重要組成部分，在不同的社會(huì)網(wǎng)絡(luò)中，人們發(fā)現(xiàn)個(gè)體之間往往存在某些共同特性，即網(wǎng)絡(luò)的群體特性［1，2］。一般情況下，把內(nèi)部聯(lián)系緊密、外部聯(lián)系稀疏的一群個(gè)體稱為社區(qū)，它反映了網(wǎng)絡(luò)元素之間的拓?fù)潢P(guān)系和功能實(shí)體，在不同的應(yīng)用領(lǐng)域，社區(qū)代表不同的實(shí)體關(guān)系群。從巨大的社會(huì)網(wǎng)絡(luò)中挖掘出社區(qū)的過程被稱為社區(qū)發(fā)現(xiàn)，是社會(huì)網(wǎng)絡(luò)分析的一個(gè)基本任務(wù)［1］。因此，發(fā)現(xiàn)并分析網(wǎng)絡(luò)所隱藏的社區(qū)結(jié)構(gòu)對(duì)了解現(xiàn)實(shí)生活中各種社會(huì)網(wǎng)絡(luò)具有重要的意義，在生物學(xué)、計(jì)算機(jī)科學(xué)以及社會(huì)學(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)可看作是硬分類，即每個(gè)結(jié)點(diǎn)有且僅能屬于一個(gè)社區(qū)；圖1下半部分表示重疊社區(qū)發(fā)現(xiàn)算法，重疊社區(qū)發(fā)現(xiàn)是軟分類，是指網(wǎng)絡(luò)中的結(jié)點(diǎn)可屬于多個(gè)社區(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ù)高的邊從而分裂得到整個(gè)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，但是，GN算法由于計(jì)算量大而很難適用于結(jié)點(diǎn)數(shù)目上萬級(jí)的大型復(fù)雜網(wǎng)絡(luò)［3］。同年Newman在PNAS會(huì)議上又提出了衡量社區(qū)劃分優(yōu)劣的模塊度Q概念［7］，之后，最大化模塊度的自下而上的合并算法和優(yōu)化模塊度的發(fā)現(xiàn)算法被研究者廣泛提出。盡管最大化模塊度Q一度成為衡量社區(qū)劃分優(yōu)劣的依據(jù)，但是由于其依賴于全局的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，會(huì)導(dǎo)致大的計(jì)算量［5］，而且，分辨率限制的問題也是模塊度優(yōu)化方法的癥結(jié)。隨著社會(huì)網(wǎng)絡(luò)的不斷發(fā)展以及研究工作的深入，研究者發(fā)現(xiàn)社區(qū)的重疊性是個(gè)顯而易見的網(wǎng)絡(luò)特性，忽略重疊性會(huì)降低所發(fā)現(xiàn)社區(qū)的質(zhì)量，也會(huì)掩蓋重疊結(jié)點(diǎn)所隱藏的重要信息而造成結(jié)點(diǎn)的誤判，但是，重疊性也是社區(qū)發(fā)現(xiàn)中難以量化的屬性，給社區(qū)發(fā)現(xiàn)算法帶來了新的難點(diǎn)［5，8］。2005年P(guān)alla等提出派系過濾（Clique percolation method，CPM）算法［9］，CPM算法的本質(zhì)是認(rèn)為典型的社區(qū)應(yīng)是全連通的完全子圖，全連通子圖之間共享的結(jié)點(diǎn)是重疊結(jié)點(diǎn)，其主要目的就是找到緊密相連的完全子圖，盡管CPM算法對(duì)重疊社區(qū)的發(fā)現(xiàn)一般來說很有效，但搜索完全子圖非常耗時(shí)，而且完全子圖的大小值k不易確定。2007年Gregory［10］在第11屆歐洲國(guó)際數(shù)據(jù)挖掘原理與發(fā)現(xiàn)會(huì)議上提出改進(jìn)GN算法的重疊社區(qū)發(fā)現(xiàn)算法（Clusteroverlap Newman Girvan algorithm，CONGA），但由于CONGA算法通過分裂結(jié)點(diǎn)為多個(gè)克隆結(jié)點(diǎn)來解決重疊結(jié)點(diǎn)的問題，因此，其仍然無法克服GN算法計(jì)算量大的問題。2009年Lancichinetti［11］提出局部測(cè)量擬合度的社區(qū)發(fā)現(xiàn)算法（Local fitness measure，LFM）從局部擬合構(gòu)造社區(qū)，局部性反映了社區(qū)的自然特性［12］，但隨機(jī)選擇初始節(jié)點(diǎn)會(huì)影響LFM算法的社區(qū)發(fā)現(xiàn)結(jié)果。盡管重疊社區(qū)發(fā)現(xiàn)算法受到了研究者的關(guān)注，但是重疊性的衡量標(biāo)準(zhǔn)仍然沒有得到有效解決，如何衡量結(jié)點(diǎn)與社區(qū)的重疊程度，還需進(jìn)一步研究。

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

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

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

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

定義1k-Path通路

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

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

假定G＝〈V，E〉表示有向圖，V是結(jié)點(diǎn)集，E是有向邊集，L是大于0的正數(shù)，共社區(qū)鄰近相似性SL（a，b）指的是：?a，b∈V，結(jié)點(diǎn)a與結(jié)點(diǎn)b分別經(jīng)過1-Path，2-Path，…，L-Path通路的總數(shù)之和。換句話說，結(jié)點(diǎn)a到達(dá)結(jié)點(diǎn)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é)點(diǎn)之間在同一社區(qū)的鄰近相似性。

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

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

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

2.1 概念定義

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

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

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

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

2.1.3 相鄰社區(qū)

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

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

2.2 LWS-OCD算法

局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法分為兩部分，（1）局部波動(dòng)擴(kuò)展小社區(qū)算法（Local and wave-like extension algorithm of detecting small communities，LWS），目的是以L為最大波長(zhǎng)從起始點(diǎn)波動(dòng)擴(kuò)展局部小社區(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 局部波動(dòng)擴(kuò)展小社區(qū)

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

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

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

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

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

（2）For（T＜L）Do

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

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

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

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

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

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

重新計(jì)算社區(qū)CI中每個(gè)結(jié)點(diǎn)w與社區(qū)的貼近度；

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

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

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

步長(zhǎng)T增加1，返回到（2）

End For（T＜L）

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

2.2.2 小社區(qū)組合

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

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

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

IFF（Ci，Ct）＞閾值δThen

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

K＝K-1；

重新計(jì)算新社區(qū)Ci中每個(gè)結(jié)點(diǎn)與新社區(qū)Ci的貼近度。

End IF

變換下一個(gè)小社區(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é)點(diǎn)；

（5）計(jì)算重疊結(jié)點(diǎn)與每個(gè)所屬社區(qū)的重疊度。

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

3.2.1 時(shí)間效率的對(duì)比

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

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

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

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

3.3 LWS-OCD算法的實(shí)驗(yàn)結(jié)果和分析

3.3.1 LWS-OCD算法的有效性對(duì)比

為了對(duì)比本文所提出的LWS-OCD算法的有效性，分別在Dolphins和Netscience兩個(gè)無向圖數(shù)據(jù)集中構(gòu)造各自對(duì)應(yīng)的鏈接通路長(zhǎng)2，3，…，6的共社區(qū)鄰近相似性的帶權(quán)無向圖，然后，在所構(gòu)造的帶權(quán)無向圖上完成LWS-OCD算法和LFM算法。圖4中給出了LFM算法和LWS-OCD算法所挖掘出的重疊結(jié)點(diǎn)個(gè)數(shù)占總結(jié)點(diǎn)的比例。圖5中給出了LFM算法和LWS-OCD算法在Netscience數(shù)據(jù)集上所劃分出的社區(qū)的個(gè)數(shù)。Dolphins in 3-Path和5-Path分別對(duì)應(yīng)Dolphins網(wǎng)絡(luò)在鏈接通路最長(zhǎng)為3和5所構(gòu)造的共社區(qū)鄰近相似性的帶權(quán)無向圖，同理，Netscience in 3-Path和5-Path分別對(duì)應(yīng)的是Netscience的帶權(quán)無向圖。在不同的帶權(quán)無向圖中，分別在社區(qū)分辨系數(shù)α從0.6，0.65，0.70，……，1.6的每隔0.05的條件下實(shí)現(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é)點(diǎn)的比例平穩(wěn)，即重疊結(jié)點(diǎn)的數(shù)目不會(huì)隨社區(qū)大小的變化而劇烈變化。事實(shí)上，在現(xiàn)實(shí)網(wǎng)絡(luò)中，對(duì)于在某一時(shí)刻相對(duì)靜止的網(wǎng)絡(luò)來說，一旦社區(qū)結(jié)構(gòu)穩(wěn)定后，社區(qū)是相對(duì)清晰的，那么，重疊結(jié)點(diǎn)也會(huì)是一定的，不會(huì)出現(xiàn)突然的變化。

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

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

3.3.2 波長(zhǎng)對(duì)LWS-OCD算法的影響

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

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

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

圖6 波長(zhǎng)范圍對(duì)LWS-OCD算法的影響Fig.6 Result of wave influencing LWS-OCD algorithm range

4 結(jié)束語

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