基于相似度的社團(tuán)劃分算法

吳蔚蔚，劉功申，黃 晨

（上海交通大學(xué)信息內(nèi)容分析技術(shù)國家工程實(shí)驗(yàn)室，上海，200240）

基于相似度的社團(tuán)劃分算法

吳蔚蔚，劉功申，黃 晨

（上海交通大學(xué)信息內(nèi)容分析技術(shù)國家工程實(shí)驗(yàn)室，上海，200240）

為對復(fù)雜網(wǎng)絡(luò)進(jìn)行合理劃分，找出真實(shí)存在的社團(tuán)結(jié)構(gòu)，提出一種基于局部模塊度和相似度的社團(tuán)劃分算法。計(jì)算網(wǎng)絡(luò)中相連節(jié)點(diǎn)之間的相似度，快速聚合關(guān)聯(lián)性最高的節(jié)點(diǎn)，從而實(shí)現(xiàn)社團(tuán)的初步劃分。以局部模塊度為閾值，根據(jù)社團(tuán)相似度聚合社團(tuán)，得到具有最佳模塊度的結(jié)果，避免模塊度缺陷，提高算法準(zhǔn)確度。算法進(jìn)行社團(tuán)劃分時(shí)只需要網(wǎng)絡(luò)局部信息，降低了時(shí)間復(fù)雜度。在實(shí)際網(wǎng)絡(luò)和計(jì)算機(jī)仿真網(wǎng)絡(luò)實(shí)驗(yàn)中的應(yīng)用結(jié)果表明，與NS1，CNM，LAP等算法相比，該算法具有較低的計(jì)算復(fù)雜度和較高的準(zhǔn)確率。

節(jié)點(diǎn)；相似度；社團(tuán)；復(fù)雜網(wǎng)絡(luò)；模塊度

1 概述

復(fù)雜網(wǎng)絡(luò)作為生物系統(tǒng)、社會系統(tǒng)、網(wǎng)絡(luò)、萬維網(wǎng)等一系列復(fù)雜系統(tǒng)的抽象代表，近年來已經(jīng)吸引來了來自眾多領(lǐng)域?qū)W者的研究［1-2］。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)預(yù)示著網(wǎng)絡(luò)中的節(jié)點(diǎn)聚合的趨勢，同一社團(tuán)列的節(jié)點(diǎn)之間的聯(lián)系會越發(fā)緊密，而社團(tuán)與社團(tuán)之間的節(jié)點(diǎn)聯(lián)系會越發(fā)稀疏，所以，社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)非常重要的屬性。對復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分同時(shí)也具有顯著的應(yīng)用意義，如收集具有相同話題的網(wǎng)頁、發(fā)現(xiàn)代謝網(wǎng)絡(luò)周期的功能單元等，此外，最近有很多研究結(jié)果顯示，社團(tuán)的屬性與整體網(wǎng)絡(luò)的屬性有很大不同，忽略對社團(tuán)結(jié)構(gòu)的研究很可能會錯(cuò)失很多有意義的屬性。

劃分社團(tuán)結(jié)構(gòu)的優(yōu)秀算法都需要滿足以下兩點(diǎn)要求：較高的社團(tuán)劃分準(zhǔn)確度和較低的計(jì)算復(fù)雜度。在過去幾年中，學(xué)者們就如何在復(fù)雜網(wǎng)絡(luò)中劃分社團(tuán)提出了許多算法，但是大多都很難同時(shí)達(dá)到以上兩點(diǎn)。

在目前已知的眾多算法中，主要有2類聚類算法，一類是劃分算法，另一類是層聚類算法。基于拉普拉斯矩陣譜圖的特征向量的譜平分算法，和基于盡量增大2個(gè)端點(diǎn)都在同一社團(tuán)的邊的數(shù)量的貪心算法的KL算法［3］是劃分算法中最經(jīng)典的2種。但這類算法需要預(yù)先給定社團(tuán)數(shù)量，不適合實(shí)際工作。層聚類算法在社會學(xué)領(lǐng)域中分為凝聚和分裂2種，這兩類算法都需要先計(jì)算每對節(jié)點(diǎn)對的連接強(qiáng)度。鏈接強(qiáng)度的計(jì)算方法有很多種，如邊界數(shù)、邊聚集系數(shù)、相異性指數(shù)、信息度、基于隨機(jī)游走的相似性等。凝聚算法會重復(fù)的聚合連接強(qiáng)度最高的節(jié)點(diǎn)對，分裂算法會重復(fù)的刪除連接強(qiáng)度最低的節(jié)點(diǎn)對之間的邊，從而獲得劃分網(wǎng)絡(luò)的結(jié)果。文獻(xiàn)［4］提出一種基于邊界數(shù)分裂方法，即GN算法。該算法在許多網(wǎng)絡(luò)都能成功應(yīng)用，但它的復(fù)雜度不太理想，對任意一個(gè)m條邊n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，GN算法的時(shí)間復(fù)雜度是O（m2n），而在稀疏網(wǎng)絡(luò)情況下，時(shí)間復(fù)雜度將達(dá)到O（n3）。文獻(xiàn)［5］提出了相類似的層聚類算法，即CNM算法，其計(jì)算復(fù)雜度為O（md lb（n）），d是聚類分析時(shí)群落結(jié)構(gòu)的深度，稀疏網(wǎng)絡(luò)情況下為接近線性的O（n lb2（n）），但準(zhǔn)確率都不是很高。其他小眾但卻有巨大影響力的算法有基于信息論的社團(tuán)發(fā)現(xiàn)算法和標(biāo)號轉(zhuǎn)播算法等。文獻(xiàn)［6］的信息論算法（InfoMap算法）以極高的計(jì)算復(fù)雜度O（n（n+m））為代價(jià)得到了極高的準(zhǔn)確度。該算法是目前非重疊社團(tuán)劃分的眾多算法中準(zhǔn)確度較高的一種算法。

本文提出一種新的社團(tuán)劃分算法，首先根據(jù)節(jié)點(diǎn)相似度，通過只合并最相似節(jié)點(diǎn)對的方式實(shí)現(xiàn)對網(wǎng)絡(luò)的初步社團(tuán)劃分，簡化網(wǎng)絡(luò)結(jié)構(gòu)。再以局部模塊度為閾值，根據(jù)社團(tuán)相似度進(jìn)一步聚合社團(tuán)，從而避免文獻(xiàn)［7］算法每次聚合都要計(jì)算模塊度的缺點(diǎn)，降低時(shí)間復(fù)雜度。

2 背景知識

復(fù)雜網(wǎng)絡(luò)是彼此錯(cuò)綜聯(lián)系在一起的節(jié)點(diǎn)組成集合，本節(jié)著重介紹社團(tuán)結(jié)構(gòu)的衡量標(biāo)準(zhǔn)和相似度衡量標(biāo)準(zhǔn)，這些是本文算法的知識基礎(chǔ)。

2.1 社團(tuán)結(jié)構(gòu)

用G=（V，E）表示一個(gè)無權(quán)重?zé)o方向的網(wǎng)絡(luò)，其中，V表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；E表示網(wǎng)絡(luò)中邊的集合。

社團(tuán)結(jié)構(gòu)是一個(gè)定性的定義，一般將網(wǎng)絡(luò)中具有相同屬性的節(jié)點(diǎn)劃分在一個(gè)社團(tuán)。學(xué)者們嘗試用不同的算法將其量化，其中以Newman根據(jù)社團(tuán)內(nèi)節(jié)點(diǎn)連接緊密、社團(tuán)間節(jié)點(diǎn)聯(lián)系稀疏而提出的模塊度Q最為著名，在無權(quán)重網(wǎng)絡(luò)中其定義如下：

其中，ai=∑jeij，eij表示網(wǎng)絡(luò)中橫跨社團(tuán)Ci和社團(tuán)Cj的邊的數(shù)量占所有邊數(shù)的比例。

模塊度Q越高代表社團(tuán)結(jié)構(gòu)劃分得越優(yōu)秀，由此產(chǎn)生了眾多基于模塊度的貪心思想的社團(tuán)劃分算法。由于模塊度Q的計(jì)算量很大，該類算法具有較高的計(jì)算復(fù)雜度，文獻(xiàn)［7］提出了局部模塊度Q′，只需計(jì)算局部信息而不用考慮全局，計(jì)算量得到大幅減少，其定義如下：

其中，Lin表示社團(tuán)內(nèi)的邊數(shù)；Lout表示該社團(tuán)與外界連接的邊數(shù)。

盡管使用模塊度來評價(jià)社團(tuán)劃分結(jié)果是業(yè)界比較流行的，但該方式仍有其局限性，如不能發(fā)現(xiàn)網(wǎng)絡(luò)中心的強(qiáng)連通小社區(qū)和當(dāng)網(wǎng)絡(luò)不具有社區(qū)結(jié)構(gòu)時(shí)，也有比較大的模塊度等。所以，本文使用NM I（Normalized M utual Information）來作為算法準(zhǔn)確度評價(jià)的指標(biāo)［8］。基于信息論的NM I用于量化衡量分區(qū)的相似性，已經(jīng)被證明是可靠的指標(biāo)，其被應(yīng)用于網(wǎng)絡(luò)社團(tuán)中的公式為：

其中，A表示實(shí)際社團(tuán)；B表示通過算法劃分的社團(tuán)；CA表示A社團(tuán)數(shù)量；CB表示B社團(tuán)數(shù)量；在N矩陣中，Nij表示在記在A的社團(tuán)i又在B的社團(tuán)j的所有節(jié)點(diǎn)數(shù)量；Ni.表示N矩陣第i行的和；N.j表示N矩陣第j列的和。

2.2 相似度

2.2.1 節(jié)點(diǎn)相似度

節(jié)點(diǎn)相似度用來量化節(jié)點(diǎn)對的連接強(qiáng)度。節(jié)點(diǎn)相似度有很多種計(jì)算方式，如Jaccard指標(biāo)、Adam ic-Adar指標(biāo)、Leicht-Holme-Newman指標(biāo)等。據(jù)文獻(xiàn)［9］中對社團(tuán)劃分節(jié)點(diǎn)相似度的計(jì)算公式如式（4）所示。

其中，T（i）表示節(jié)點(diǎn)ni的鄰節(jié)點(diǎn)集；z∈T（i）∩T（j）表示節(jié)點(diǎn)ni和節(jié)點(diǎn)nj的公共鄰節(jié)點(diǎn)集；k（z）表示節(jié)點(diǎn)z的度。但是式（1）不能區(qū)分出直接相連的節(jié)點(diǎn)對與不直接相連的節(jié)點(diǎn)對的相似度。如在Zachary棒球俱樂部網(wǎng)絡(luò)中，通過式（4）計(jì)算，節(jié)點(diǎn)3與節(jié)點(diǎn)34的相似度極高。但事實(shí)上這2個(gè)節(jié)點(diǎn)分屬不同社團(tuán)，故進(jìn)一步修正式（4）為式（5）：

對于一些特殊情況：如當(dāng)z∈?時(shí)，即相鄰節(jié)點(diǎn)ni和節(jié)點(diǎn)nj沒有公共鄰節(jié)點(diǎn)時(shí)，如果ni的度為1，則Sij=1，否則Sij=0。如圖1所示，n8和n9沒有公共鄰節(jié)點(diǎn)，但顯然n9完全依賴n8，S98應(yīng)為一個(gè)極大值。

圖1 節(jié)點(diǎn)相似度計(jì)算示意圖

2.2.2 社團(tuán)相似度

將節(jié)點(diǎn)相似度推廣到社團(tuán)相似度，可得到下式：

其中，T（Ci）表示與社團(tuán)Ci有邊直接連接的社團(tuán)集合；K（Cz）表示社團(tuán)Cz中與其他社團(tuán)連接的邊數(shù)。當(dāng)Cz∈?時(shí)，即社團(tuán)Ci和社團(tuán)Cj沒有公共鄰社團(tuán)時(shí)，如果，則SCij=1，否則SCij=0。

2.3 基于節(jié)點(diǎn)相似度的聚類社團(tuán)發(fā)現(xiàn)算法

基于節(jié)點(diǎn)相似度的聚類社團(tuán)發(fā)現(xiàn)算法于近期提出，步驟如下：（1）隨機(jī)選取某未劃分社團(tuán)的節(jié)點(diǎn)；（2）聚合與該節(jié)點(diǎn)相似的鄰節(jié)點(diǎn)；（3）網(wǎng)絡(luò)中所有節(jié)點(diǎn)都劃分社團(tuán)，算法結(jié)束，反之重復(fù)步驟（1）。

該類算法的問題在于步驟（2）中，如何選定與指定節(jié)點(diǎn)相似的節(jié)點(diǎn)。目前衡量節(jié)點(diǎn)相似度的算法有很多，但相似度閾值的確認(rèn)問題還未能被有效的解決，從而影響了算法的準(zhǔn)確度。閾值過高，會使得最終社團(tuán)劃分得過于碎片零散；閾值過低，會使得最終社團(tuán)劃分得過于粗獷，將實(shí)際上應(yīng)屬于不同的社團(tuán)的節(jié)點(diǎn)合并在了一個(gè)社團(tuán)中。文獻(xiàn)［9］直接規(guī)避了這個(gè)問題，提出根據(jù)不同網(wǎng)絡(luò)，實(shí)時(shí)調(diào)整閾值，但具體如何調(diào)整閾值，沒有展開。文獻(xiàn)［7］提出以公共鄰節(jié)點(diǎn)數(shù)量作為節(jié)點(diǎn)相似度、用模塊度作為每一次合并節(jié)點(diǎn)的閾值的算法，記該算法為NS1，這樣做雖然保證了準(zhǔn)確度卻提高了計(jì)算復(fù)雜度；文獻(xiàn)［10］提出的算法，首先使用基于節(jié)點(diǎn)相似度和寬松的閾值聚類網(wǎng)絡(luò)中節(jié)點(diǎn)，再依次計(jì)算每個(gè)節(jié)點(diǎn)在其他社團(tuán)時(shí)的模塊度，從而以模塊度增大的方向?qū)Ξ?dāng)前社團(tuán)劃分做微調(diào)整，記該算法為NS2，這種做法僅適用于個(gè)別節(jié)點(diǎn)劃分錯(cuò)誤的情況，對于大規(guī)模節(jié)點(diǎn)劃分錯(cuò)誤無效（如前期閾值選擇過低，錯(cuò)誤的將不同社團(tuán)合并到一個(gè)社團(tuán)），而且增加了算法的復(fù)雜度。

3 本文算法

3.1 算法描述

對網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，是為了將具有相同屬性的節(jié)點(diǎn)聚合在一起，從而讓人們更進(jìn)一步研究網(wǎng)絡(luò)子結(jié)構(gòu)屬性。由此可以推論出相似度越大的2個(gè)節(jié)點(diǎn)，越有可能屬于同一個(gè)社團(tuán)。

對于網(wǎng)絡(luò)G=（V，E），計(jì)算出節(jié)點(diǎn)相似度矩陣S，首先不斷合并具有最大相似度的節(jié)點(diǎn)對，完成社團(tuán)初步劃分。再根據(jù)局部模塊度的增量進(jìn)步一合并社團(tuán)，直到獲取最大的模塊度。

算法具體描述如下：

輸入 一個(gè)無向無權(quán)重網(wǎng)絡(luò)G=（V，E）

輸出 網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)

步驟1 如果V=?，算法結(jié)束。否則，根據(jù)2.3節(jié)知識獲得nxn的節(jié)點(diǎn)相似度矩陣S=｛Sij｝，其中，n為G的節(jié)點(diǎn)數(shù)，即n=|V|。新建V′=V。

步驟2 在V中任意選取節(jié)點(diǎn)ni，根據(jù)相似度矩陣S，選取其最相似節(jié)點(diǎn)集N。V′=V′-ni。

步驟3 如果節(jié)點(diǎn)ni和節(jié)點(diǎn)集N不屬于任何社團(tuán)，新建社團(tuán)Ci，Ci=ni+N。如果節(jié)點(diǎn)ni或節(jié)點(diǎn)集N中的任意節(jié)點(diǎn)有社團(tuán)屬性，分別屬于為Cx，Cy等，則合并這些社團(tuán)為Cz，使ni∈Cz，N∈Cz。

步驟4 當(dāng)V′≠?時(shí)，跳轉(zhuǎn)步驟2。

步驟5 定義局部模塊度Q′=0。

步驟6 新建社團(tuán)集C，集合中包含網(wǎng)絡(luò)當(dāng)前劃分的社團(tuán)。新建Qmax=Q′。

步驟7 根據(jù)2.2節(jié)知識獲得社團(tuán)相似度矩陣SC=｛SCij｝。

步驟8 在C中任取一社團(tuán)Ci，根據(jù)社團(tuán)相似度矩陣SC，選取其最相似社團(tuán)集CN。C=C-Ci。

步驟9 合并社團(tuán)Ci和最相似社團(tuán)集CN組成新的社團(tuán)C′i。計(jì)算局部模塊度Q′i，如果Q′i＞Qmax，則Qmax=Q′i；反之，退回步驟8。

步驟10 當(dāng)C≠?時(shí)，跳轉(zhuǎn)步驟8；當(dāng)C=?時(shí)，如果Qmax＞Q′，Q′=Qmax，跳轉(zhuǎn)步驟6。

步驟11 輸出結(jié)果

3.2 可行性分析

基于相似度的聚類算法和依據(jù)模塊度的聚類算法如CNM算法思維類似，都是以局部最優(yōu)獲取最終結(jié)果，這就不可避免地造成結(jié)局不是最優(yōu)，所以該類貪心算法準(zhǔn)確度很難達(dá)到100%，但目前已有算法中，沒有能達(dá)到完全準(zhǔn)確的算法。所以，本文提出的這種依據(jù)相似度的貪心算法，若能實(shí)現(xiàn)比已知同類算法時(shí)間復(fù)雜度低且準(zhǔn)確度高，就是一個(gè)優(yōu)秀的社團(tuán)發(fā)現(xiàn)算法。本節(jié)將著重分析本文提出的算法如何降低了時(shí)間復(fù)雜度和提高了準(zhǔn)確性。

3.2.1 時(shí)間復(fù)雜度分析

本文提出的算法計(jì)算花費(fèi)主要由2個(gè)部分構(gòu)成：一是通過節(jié)點(diǎn)相似度初步劃分網(wǎng)絡(luò)，二是通過局部模塊度和社團(tuán)相似度對進(jìn)一步聚合社團(tuán)。初步依據(jù)最相似聚類節(jié)點(diǎn)，所有節(jié)點(diǎn)需遍歷一次，且每個(gè)節(jié)點(diǎn)都要需要在其鄰節(jié)點(diǎn)中找出最相似的節(jié)點(diǎn)，故時(shí)間復(fù)雜度為O（kn），k為節(jié)點(diǎn)度數(shù)。進(jìn)一步聚合網(wǎng)絡(luò)階段，依據(jù)模塊度和社團(tuán)相似度，至多需要合并O（lg m）次，m為網(wǎng)絡(luò)中邊的數(shù)目，每次合并計(jì)算社團(tuán)相似度和模塊度增量的時(shí)間復(fù)雜度為O（n），故該部分的時(shí)間復(fù)雜度為O（n lg m）。綜上所示，本文提出的算法時(shí)間復(fù)雜度為O（n lg m）。而NS1算法的時(shí)間復(fù)雜度為O（mn），NS2算法復(fù)雜度為O（n2m）。因此，本文算法的時(shí)間復(fù)雜度遠(yuǎn)高于同類基于節(jié)點(diǎn)相似度的聚類算法，在一定程度上提高了運(yùn)行效率。

3.2.2 準(zhǔn)確度分析

社團(tuán)劃分的目的是社團(tuán)內(nèi)節(jié)點(diǎn)連接緊密、社團(tuán)間節(jié)點(diǎn)聯(lián)系稀疏，依據(jù)此提出模塊度Q是目前對社團(tuán)劃分算法的評價(jià)標(biāo)準(zhǔn)，但其存在自身局限，Q值越高不代表越接近真實(shí)情況。下面通過一個(gè)簡單的例子來說明。考慮2個(gè)社團(tuán)構(gòu)成的網(wǎng)絡(luò)，社團(tuán)S1為100個(gè)節(jié)點(diǎn)的完全圖（任意節(jié)點(diǎn)之間都存在邊），社團(tuán)S2為4個(gè)節(jié)點(diǎn)的完全圖，社團(tuán)S1與社團(tuán)S2之間以一條邊連接，如圖2（a）所示。很明顯的這個(gè)網(wǎng)絡(luò)應(yīng)該被劃分為S1和S2兩個(gè)社團(tuán)，但對于指著這種劃分，模塊度Q才為0.002 417 38，而對于圖2（b）這種劃分方式，模塊度Q為0.002 564 459，比前者要高，但劃分結(jié)果卻遠(yuǎn)離社團(tuán)實(shí)際真實(shí)情況。

圖2 社團(tuán)S1和社團(tuán)S2組成的網(wǎng)絡(luò)及其劃分

所以，以模塊度最大化作為每一步節(jié)點(diǎn)合并的標(biāo)準(zhǔn)，對個(gè)別情況（如上文舉例的社團(tuán)大小差異過大）中的部分節(jié)點(diǎn)的社團(tuán)歸類不適用，即模塊度不適用于單個(gè)節(jié)點(diǎn)對聚類。但是用節(jié)點(diǎn)相似度就避免了這類情況，再次考慮圖2（a）所示網(wǎng)絡(luò)，連接S1和S2的2個(gè)節(jié)點(diǎn)沒有公共鄰節(jié)點(diǎn)，故兩個(gè)點(diǎn)的相似度為0，從而自然將2個(gè)社團(tuán)劃分開。

本文嘗試用比較粗獷的方式定義算法評價(jià)標(biāo)準(zhǔn)：使社團(tuán)間的邊數(shù)最小化。即如式（7）所示，i，j表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，eij當(dāng)且僅當(dāng)節(jié)點(diǎn)i，j相連是為1，否則為0。

如果節(jié)點(diǎn)i，j被劃分到不同社團(tuán)，則社團(tuán)間的邊數(shù)至少為公共鄰節(jié)點(diǎn)數(shù)量。即：

其中，T（i）表示節(jié)點(diǎn)i的鄰節(jié)點(diǎn)。所以可以通過以公共鄰節(jié)點(diǎn)數(shù)量作為相似度，將公共鄰節(jié)點(diǎn)多的節(jié)點(diǎn)對劃分在一個(gè)社團(tuán)，從而實(shí)現(xiàn)社團(tuán)間的邊數(shù)最小。文獻(xiàn)［6］根據(jù)實(shí)驗(yàn)表明，增加考慮公共鄰節(jié)點(diǎn)的度數(shù)，可以提高算法的準(zhǔn)確度。因此，本文算法采用包含公共鄰節(jié)點(diǎn)和其度數(shù)的RA指標(biāo)作為衡量兩相鄰節(jié)點(diǎn)相似度的標(biāo)準(zhǔn)，以最相似作為閾值聚合節(jié)點(diǎn)保證初步快速社團(tuán)劃分的準(zhǔn)確度。

由此可以得出，本文提出的算法比以依據(jù)模塊度增量的聚類算法（如CNM算法）和以模塊度增量作為每次聚類單個(gè)節(jié)點(diǎn)的閾值的算法（如NS1算法）準(zhǔn)確度高。后續(xù)實(shí)驗(yàn)數(shù)據(jù)也證明了本文算法比同類聚類算法具有更高的準(zhǔn)確度。

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

為了評估本文提出算法的效果，本節(jié)將該算法應(yīng)用于一些實(shí)際網(wǎng)絡(luò)，如海豚社團(tuán)網(wǎng)、Zachary空手道俱樂部網(wǎng)絡(luò)、足球隊(duì)網(wǎng)絡(luò)和計(jì)算機(jī)仿真網(wǎng)絡(luò)。所有實(shí)驗(yàn)均在2.3 GH的處理器和3 GB內(nèi)存的筆記本上運(yùn)行。

4.1 現(xiàn)實(shí)網(wǎng)絡(luò)

4.1.1 海豚社團(tuán)網(wǎng)絡(luò)

Lusseau通過7年的觀察，總結(jié)了生活在新西蘭附近海域的62只海豚的社團(tuán)網(wǎng)絡(luò)，這個(gè)網(wǎng)絡(luò)也是如今復(fù)雜網(wǎng)絡(luò)領(lǐng)域中重要的測試用例［11］。海豚群漸漸分化為成年海豚群和年幼海豚群，成年海豚群又進(jìn)一步分化成更小的海豚群。

使用本文算法劃分海豚社團(tuán)，過程如圖3所示。其中，圖3（a）為Lusseau觀察總結(jié)出的海豚網(wǎng)絡(luò)；圖3（b）為基于節(jié)點(diǎn)相似度快速聚合社團(tuán)的結(jié)果，該過程將網(wǎng)絡(luò)初步劃分出10個(gè)社團(tuán)。圖中節(jié)點(diǎn)代表海豚個(gè)體，點(diǎn)與點(diǎn)之間的連線代表這2個(gè)海豚相似度最高。圖3（c）為基于社團(tuán)相似度和局部模塊度進(jìn)一步聚合社團(tuán)結(jié)果，圖中4中顏色代表本算法劃分出的4個(gè)不同社團(tuán)。

圖3 本文算法處理海豚網(wǎng)絡(luò)過程

本文算法與其他算法的準(zhǔn)確度及時(shí)間復(fù)雜度對比結(jié)果如表1表示，本文算法運(yùn)算時(shí)間最低，可近似于忽略不計(jì)，準(zhǔn)確度NM I為0.580 1，比InfoM ap算法高2.4%，比NS1算法高1.0%。同時(shí)本文算法在時(shí)間和NM I上相比于CNM算法、LAP算法和M ultiLevel算法都有一定優(yōu)勢。

表1 海豚網(wǎng)絡(luò)社團(tuán)劃分算法對比

4.1.2 大學(xué)足球隊(duì)網(wǎng)絡(luò)

大學(xué)足球隊(duì)網(wǎng)絡(luò)［12］代表的是某個(gè)賽季中大學(xué)足球隊(duì)的比賽情況。該網(wǎng)絡(luò)由115個(gè)節(jié)點(diǎn)組成，代表了115個(gè)參賽足球隊(duì)，節(jié)點(diǎn)之間用邊相連，表示2個(gè)足球隊(duì)之間有比賽。由于比賽將115個(gè)足球隊(duì)劃分為12個(gè)小組，因此小組內(nèi)的球賽會比與組間球賽數(shù)量更多。使用本文算法劃分結(jié)果如表2所示。本文算法與其他算法的準(zhǔn)確度及時(shí)間復(fù)雜度對比結(jié)果如表3所示。與CNM算法、InfoM ap算法和LAP算法相比，本文算法的運(yùn)算時(shí)間最短，為0.000 8 s，準(zhǔn)確度NM I為0.954 5，與InfoM ap差距4.7%，但是卻高出NS1算法8.2%，高出LAP算法1.3%，高出CNM算法25.7%，雖和M ultiLevel算法準(zhǔn)確度持平，但用時(shí)僅為MultiLevel算法的40%?？梢?，相比于一些常見的算法，本文算法在現(xiàn)實(shí)網(wǎng)絡(luò)具有一定的優(yōu)勢。

表2 本文算法處理足球隊(duì)網(wǎng)絡(luò)的社團(tuán)劃分結(jié)果

表3 足球隊(duì)網(wǎng)絡(luò)社團(tuán)劃分算法對比

通過將本文算法運(yùn)用于海豚等3個(gè)現(xiàn)實(shí)網(wǎng)絡(luò)，可以很容易的發(fā)現(xiàn)本文提出的算法準(zhǔn)確率可以達(dá)到InfoMap算法的水平，同時(shí)算法用時(shí)略低于LAP標(biāo)簽算法。由此可見，本文算法在現(xiàn)實(shí)網(wǎng)絡(luò)中具有很高的準(zhǔn)確度和較低的時(shí)間復(fù)雜度，是一種優(yōu)秀的算法。

4.1.3 微博網(wǎng)絡(luò)

以上通過小規(guī)模實(shí)際網(wǎng)絡(luò)方面說明了本文算法的有效性。本節(jié)將選用大規(guī)模實(shí)際網(wǎng)絡(luò)來驗(yàn)證本文算法。通過調(diào)用新浪微博API接口，下載存儲新浪用戶網(wǎng)絡(luò)信息。這里以用戶為節(jié)點(diǎn)，用戶之間相互關(guān)注為邊，從而截取構(gòu)建出10萬個(gè)節(jié)點(diǎn)、100萬條邊的微博網(wǎng)絡(luò)。由于不知該網(wǎng)絡(luò)的正確社團(tuán)劃分結(jié)果，所以這里以模塊度Q作為標(biāo)準(zhǔn)比較各類算法的準(zhǔn)確度，一般認(rèn)為，模塊度Q值越高，社團(tuán)劃分效果越理想。本文算法與其他算法處理該網(wǎng)絡(luò)結(jié)果如表4所示。NS1算法獲得最高的Q值，但由于該算法每一步都需計(jì)算一次模塊度Q導(dǎo)致用時(shí)過多，本文算法取得與NS1差不多的模塊度（Q值相差2.4%），但用時(shí)僅為其用時(shí)的4.2%。

表4 微博網(wǎng)絡(luò)社團(tuán)劃分算法對比

4.2 模擬網(wǎng)絡(luò)

基準(zhǔn)圖［13］是由Lancichinetti等人提出的計(jì)算機(jī)模擬網(wǎng)絡(luò)，它的網(wǎng)絡(luò)擁有與現(xiàn)實(shí)網(wǎng)絡(luò)相類似的社團(tuán)規(guī)模和節(jié)點(diǎn)度的異構(gòu)分布，適合作為評估社團(tuán)發(fā)現(xiàn)算法的測試用例。在基準(zhǔn)圖中節(jié)點(diǎn)度分布和社團(tuán)大小按照冪律分布。節(jié)點(diǎn)度冪律分布的指數(shù)為γ，社團(tuán)規(guī)模冪律分布指數(shù)為β，μ稱為拌和參數(shù)，1-μ表示節(jié)點(diǎn)與所在社團(tuán)內(nèi)的節(jié)點(diǎn)連接的概率。

將本文提出的算法應(yīng)用在平均節(jié)點(diǎn)度k=20、節(jié)點(diǎn)度分布指數(shù)γ=2.5、社團(tuán)規(guī)模分布指數(shù)β=1.5、拌和參數(shù)μ從0.1到0.6的基準(zhǔn)圖中。社團(tuán)劃分結(jié)果如圖4所示。其中的3個(gè)圖分別代表節(jié)點(diǎn)數(shù)為1 000，50 000，10 000的基準(zhǔn)圖。隨著拌合參數(shù)μ的增大，社團(tuán)之間的區(qū)分越發(fā)模糊，即劃分社團(tuán)難度越大。在圖4中可以看出，除了InfoMap算法一直以極高的時(shí)間復(fù)雜度為代價(jià)保持著NM I接近1的準(zhǔn)確度，其他算法都隨著μ值增大，用時(shí)增加而準(zhǔn)確率在下降。本文提出的算法無論在用時(shí)還是準(zhǔn)確度上，都遠(yuǎn)遠(yuǎn)高于CNM算法。與MultiLevel算法相比，本文算法準(zhǔn)確率與其持平，但用時(shí)略低于M ultiLevel算法。當(dāng)μ≤0.6時(shí)，本文提出的算法的準(zhǔn)確度NM I始終保持在0.8以上。雖然本文算法應(yīng)用于計(jì)算機(jī)模擬網(wǎng)絡(luò)的優(yōu)勢沒有應(yīng)用于現(xiàn)實(shí)網(wǎng)絡(luò)那么明顯，但它能在極短的用時(shí)下，達(dá)到較高的準(zhǔn)確度，實(shí)驗(yàn)效果優(yōu)于CNM算法，時(shí)間也略優(yōu)于M ultiLevel算法。

圖4 基準(zhǔn)圖

5 結(jié)束語

本文提出的基于相似度和局部模塊度的算法，是一種能夠在網(wǎng)絡(luò)中快速劃分社團(tuán)結(jié)構(gòu)的算法。該算法不需要事先確定社團(tuán)數(shù)目和網(wǎng)絡(luò)的全局信息，只需要節(jié)點(diǎn)局部信息就能夠得到較好的結(jié)果，大幅降低了算法的時(shí)間復(fù)雜度。在具體實(shí)驗(yàn)中以不同節(jié)點(diǎn)作為算法入口，發(fā)現(xiàn)最后的社團(tuán)劃分結(jié)果都一致，即說明本文算法具有很好的穩(wěn)定性。進(jìn)一步通過與其他算法的對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果也證明了本文算法不僅具有著較高的準(zhǔn)確率，同時(shí)時(shí)間復(fù)雜度也較低。不過目前對本文算法的分析還局限于社團(tuán)非重疊網(wǎng)絡(luò)，后續(xù)工作是研究如何將該算法應(yīng)用于重疊社團(tuán)網(wǎng)絡(luò)中。

［1］ Newman M E J.The Structure and Function of Complex Networks［J］.SIAM Review，2003，45（2）：167-256.

［2］ Albert R，Barabasi A L.Statistical Mechanics of Complex Networks［J］.Reviews of Modern Physics，2002，74：47-97.

［3］ Kernighan B W，Lin S.An Efficient Heuristic Procedure for Partitioning Graphs［J］.Bell System Technical Journal，1970，49（2）：291-307.

［4］ Girvan M，Newman M E J.Community Structure in Social and Biological Networks［J］.PNAS Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826

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

［6］ Rosvall M，Bergstrom C T.Maps of Radom Walks on Complex Networks［J］.Proceedings of the National Academy of Science，2008，105（4）：1118-1123.

［7］ 劉 微.基于共享鄰居數(shù)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法［J］.計(jì)算機(jī)工程，2011，37（6）：172-174.

［8］ Xuan V N，Julien E，James B.Information Theoretic Measures for Clusterings Comparison：Variants，Properties，Normalization and Correction for Chance［J］.The Journal of Machine Learning Research，2011，11（10）：2837-2854.

［9］ Ying Pan.Detecting Community Structure in Complex Networks via Node Similarity［J］.Physica A，2010，389：2849-2857.

［10］ 胡 瓊.社會網(wǎng)絡(luò)結(jié)構(gòu)劃分算法研究［D］.上海：上海交通大學(xué)，2014.

［11］ Lusseau D.The Emergent Properties of a Dolphin Social Network［J］.Proceedings of the Royal Society of London，Series B，2003，270（Suppl.）：186-188.

［12］ Sun PG，Gao L，Han Shanshan.Identification of Overlapping and Non-overlapping Community Structure by Fuzzy Clustering in Complex Networks［J］.Information Sciences，2011，181（6）：1060-1071.

［13］ Andrea L，Santo F，F(xiàn)ilippo R.Benchmark Graphs for Testing Comm unity Detection Algorithm s［J］.Physical Review E，2008，78（4）.

編輯 金胡考

Comm unity Partition Algorithm Based on Similarity

WU Weiwei，LIU Gongshen，HUANG Chen
（National Engineering Laboratory of Information Content Analysis Technology，Shanghai Jiaotong University，Shanghai 200240，China）

The partition of complex network is useful to find the real community structure and help people research the real world，so this paper proposes a new algorithm of communities partition in network based on the local module degree and similarities.The algorithm calculates the similarities between the nodes in the network and aggregates the nodes which have the highest correlation.It aggregates the communities based on the local module degree and community similarity. Then the results is gotten which has the best local module degree.To verify the validity of the algorithm，this paper applies it in the real network and computer simulation network，and com pares the algorithm with other algorithm s.The result shows that the proposed algorithm has lower computational complexity and higher accuracy compared with NS1，CNM，LAP algorithm s，etc..

nodes；similarity；community；complex network；module degree

吳蔚蔚，劉功申，黃 晨.基于相似度的社團(tuán)劃分算法［J］.計(jì)算機(jī)工程，2015，41（11）：67-72，83.

英文引用格式：Wu Weiwei，Liu Gongshen，Huang Chen.Community Partition Algorithm Based on Similarity［J］. Computer Engineering，2015，41（11）：67-72，83.

1000-3428（2015）11-0067-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.012

國家“973”計(jì)劃基金資助項(xiàng)目（2013CB329603）；國家自然科學(xué)基金資助項(xiàng)目（61171173）。

吳蔚蔚（1990-），女，碩士，主研方向：復(fù)雜網(wǎng)絡(luò)；劉功申，副教授；黃 晨，碩士。

2014-10-09

2014-12-02 E-m ail：vivibear@sjtu.edu.cn