牛冬冬，陳鴻昶，金 鑫，劉力雄

（1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州450002；2.國家計算機網(wǎng)絡與信息安全管理中心，北京100031）

0 引 言

復雜網(wǎng)絡的網(wǎng)絡結(jié)構(gòu)存在著小世界特性、無標度特性以及網(wǎng)絡節(jié)點的冪律分布等特性[1－3]。研究發(fā)現(xiàn)，實際的復雜網(wǎng)絡并不是隨機網(wǎng)絡，而是具有一定的組織結(jié)構(gòu)，絕大多數(shù)復雜網(wǎng)絡的拓撲結(jié)構(gòu)都呈現(xiàn)總體分散局部聚集的特征，即整個網(wǎng)絡是由若干個 “群”或 “團”構(gòu)成的，群內(nèi)部的節(jié)點鏈接相對較緊密，但是各個群之間的鏈接相對而言卻比較稀疏，研究者把這稱為復雜網(wǎng)絡的社區(qū)結(jié)構(gòu)特性。復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)對于復雜網(wǎng)絡的拓撲結(jié)構(gòu)分析、群體行為分析以及行為預測等具有重要的研究意義。

目前存在很多種社區(qū)發(fā)現(xiàn)方法，可以分類為全局社區(qū)發(fā)現(xiàn)方法和局部社區(qū)發(fā)現(xiàn)方法[4]。全局社區(qū)發(fā)現(xiàn)方法有圖分割方法、層次聚類算法、分裂算法等等，由于全局社區(qū)發(fā)現(xiàn)方法進行社區(qū)發(fā)現(xiàn)時利用全局的網(wǎng)絡信息，所以該類算法計算復雜度往往過高，而復雜網(wǎng)絡的規(guī)模愈來愈大，所以該類算法的應用范圍比較有限。局部社區(qū)發(fā)現(xiàn)方法是從點到面的信息挖掘，使用網(wǎng)絡中的部分信息進行社區(qū)分析，因此有著全局社區(qū)發(fā)現(xiàn)方法不可比的效率，該類方法一般是選取網(wǎng)絡中的一個起始節(jié)點進行社區(qū)結(jié)構(gòu)的探測，通過發(fā)現(xiàn)不同的起始節(jié)點所在的社區(qū)達到發(fā)現(xiàn)全網(wǎng)社區(qū)的目的。但是該類社區(qū)發(fā)現(xiàn)方法的社區(qū)發(fā)現(xiàn)結(jié)果準確度往往較低，因為該類社區(qū)發(fā)現(xiàn)方法受限于起始節(jié)點，當起始節(jié)點為邊界節(jié)點時發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)并不一定是網(wǎng)絡中真實的社區(qū)結(jié)構(gòu)。局部社區(qū)發(fā)現(xiàn)方法雖然降低了計算復雜度，但卻是以社區(qū)發(fā)現(xiàn)質(zhì)量降低為代價的，因此該類方法的應用也比較有限。

針對上述社區(qū)發(fā)現(xiàn)方法存在的不足，本文提出一種基于核心節(jié)點的社區(qū)劃分方法。本方法借鑒了從中心節(jié)點出發(fā)進行社區(qū)發(fā)現(xiàn)可以保證社區(qū)發(fā)現(xiàn)質(zhì)量思想[5]，提出了直接探測出目標網(wǎng)絡中存在的屬于不同社區(qū)的核心節(jié)點作為社區(qū)劃分的種子節(jié)點，然后采用相似性傳遞的節(jié)點相似性度量方法計算網(wǎng)絡中其他節(jié)點與核心節(jié)點的相似度，根據(jù)相似性度量結(jié)果對網(wǎng)絡進行劃分。本方法在算法復雜度較低的條件下保證了社區(qū)發(fā)現(xiàn)的質(zhì)量。

1 算法的相關(guān)準備

1.1 網(wǎng)絡模型定義

復雜網(wǎng)絡可以建模為圖G＝（V，E），設網(wǎng)絡G具有n個節(jié)點和m條邊，其頂點集為V＝｛V1，…，Vn｝，邊集合為E＝｛Ej｜Ej∈V×V，j＝1，…，m｝。本文中只考慮無向、無權(quán)的網(wǎng)絡，網(wǎng)絡的鄰接矩陣A的取值為0或1，若Vi與Vj之間有邊相連時Aij＝1，否則Aij＝0。Newman等提出了網(wǎng)絡模塊性評價函數(shù) （又稱Q函數(shù)），Q函數(shù)定義如下

其中，eii是所連接的兩個節(jié)點均在社區(qū)i內(nèi)的邊占網(wǎng)絡總邊數(shù)的比例，ai是有一個節(jié)點在社區(qū)i的邊占網(wǎng)絡總邊數(shù)的比例。社區(qū)結(jié)構(gòu)性越弱Q值越小，社區(qū)結(jié)構(gòu)性越強Q值越大，目前大多數(shù)社區(qū)發(fā)現(xiàn)算法用模塊度作為標準來評價社區(qū)劃分的好壞。

1.2 相似性度量

相似性度量是對網(wǎng)絡圖中頂點之間相似或相異程度的度量，相當一部分的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法都利用到了相似性度量，目前對網(wǎng)絡中節(jié)點的相似性度量已經(jīng)有了比較系統(tǒng)的研究，大部分的方法都是利用了網(wǎng)絡中節(jié)點的鄰接關(guān)系來計算節(jié)點之間的相似度，有的方法利用的是全局的鄰接關(guān)系，有的方法利用的是局部的鄰接關(guān)系。

一種利用全局鄰接關(guān)系的節(jié)點相似性度量[6]將節(jié)點之間的距離定義為

這是一種基于結(jié)構(gòu)同等概念的度量頂點相異度的方法。結(jié)構(gòu)同等是指兩個節(jié)點的鏈接關(guān)系相同，即兩個節(jié)點有著相同的鄰居節(jié)點，若節(jié)點i和j結(jié)構(gòu)同等，則dij＝0。這種方法可以計算出網(wǎng)絡中任意節(jié)點之間的相異度，但是計算的結(jié)果有時并不能正確的反映節(jié)點之間的相異程度，如圖1所示。

圖1 空手道俱樂部成員間的相互關(guān)系

采用式 （2）計算出V12與V1的相異度為3.873，而V12與V33的相異度為3.6056，根據(jù)計算結(jié)果得到V12與V33更加近似，但是圖中顯然可以看出V12僅與V1有邊連接，計算結(jié)果顯然得出了錯誤的相異性度量。但是當利用式 （2）計算V33，V1與V34的相異度時，計算結(jié)果正確的反映出了節(jié)點之間的相異程度?？梢园l(fā)現(xiàn)V12處于網(wǎng)絡的邊界位置，與該節(jié)點的鄰居節(jié)點個數(shù)很少，而V33，V1與V34都是大度數(shù)節(jié)點，所以發(fā)現(xiàn)采用式 （2）往往不能正確得到低度數(shù)節(jié)點與其他節(jié)點的相似度，但可以用于計算大度數(shù)節(jié)點之間的相似度。

局部相似性度量方法共同特點是利用節(jié)點的鄰域子圖，該類方法認為兩個節(jié)點共有的鄰居節(jié)點越多，則兩個節(jié)點之間就更加相似[7]。節(jié)點Vi的鄰居節(jié)點集記為N（i），即N（i）＝｛Vj｜Aij＝1｝。Vi的星型鄰域子圖記為St（i），它是由Vi及其鄰居點集構(gòu)成，即St（i）＝｛Vi｝∪N（i）。如圖1所示，V6的星型鄰域子圖St（6）包括5個節(jié)點St（6）＝｛V1，V6，V7，V11，V17｝，V6和V7的 星 型 鄰 域 子 圖 的 交 集St（6）∩St（7）＝｛V1，V6，V7，V17｝。集合St（6）∩St（7）反映了節(jié)點之間聯(lián)系的緊密程度，綜上定義Vi與Vj的局部相似性度量[8]為

式中，ke為Ve的度數(shù)，該方法能夠正確的反映兩個節(jié)點之間的相似程度，但是當兩個節(jié)點之間的距離大于2的時候，兩個節(jié)點之間不存在公共的鄰居節(jié)點，此時采用局部相似性度量方法不能度量這兩個節(jié)點之間的相似程度。

2 算法描述

2.1 探測網(wǎng)絡核心節(jié)點

研究發(fā)現(xiàn)從中心節(jié)點出發(fā)可以提高社區(qū)發(fā)現(xiàn)的質(zhì)量，通過選取更加合適的起始節(jié)點可以提高局部社區(qū)發(fā)現(xiàn)結(jié)果的準確度。通常情況下，在每個社區(qū)中往往會有一部分節(jié)點處于社區(qū)的中心位置，本文定義這部分節(jié)點為社區(qū)的核心節(jié)點，如果在進行社區(qū)劃分之前可以探測出存在于不同社區(qū)的全部核心節(jié)點，對接下來的社區(qū)劃分具有重要意義。

圖2是網(wǎng)絡G的簡單示意圖，設網(wǎng)絡G中存在著3個社區(qū)，不同社區(qū)之間用虛線連接。

圖2 網(wǎng)絡G社區(qū)關(guān)系

如圖2所示，不同的社區(qū)內(nèi)部都會存在著一小部分節(jié)點處于社區(qū)的中心位置，并且會與網(wǎng)絡中的其他節(jié)點連接關(guān)系緊密，該類節(jié)點可認為是網(wǎng)絡中的核心節(jié)點，本文所要探測的核心節(jié)點首先是大度數(shù)節(jié)點。定義網(wǎng)絡中節(jié)點的集合為V＝｛V1，…，Vn｝，根據(jù)網(wǎng)絡中節(jié)點之間的鏈接關(guān)系計算網(wǎng)絡中所有節(jié)點的度數(shù)，然后根據(jù)度數(shù)進行排序，定義排序后的節(jié)點集合為，然后取出集合中的前一部分節(jié)點即大度數(shù)節(jié)點構(gòu)成集合，則網(wǎng)絡中不同社區(qū)內(nèi)的核心節(jié)點一定處于集合中。在本文社區(qū)劃分算法中需要獲取的是每個社區(qū)內(nèi)部唯一的核心節(jié)點，然而同一個社區(qū)可能有多個大度數(shù)節(jié)點存在于集合中，所以需要對集合中的節(jié)點進行篩選。結(jié)合圖2進行分析不難得出由于不同社區(qū)的核心節(jié)點在網(wǎng)絡中相距較遠，所以對節(jié)點進行相似性度量時，同一社區(qū)內(nèi)部的大度數(shù)節(jié)點相似度一定遠大于不同社區(qū)內(nèi)部大度數(shù)節(jié)點之間的相似度。利用文中式 （2）度量集合中節(jié)點兩兩之間的相似度，將相似度過高的節(jié)點從集合中剔除，余下的節(jié)點則組成新的集合，該集合即為本文探測出的核心節(jié)點集。

2.2 基于相似性傳遞的節(jié)點相似性度量方法

本文進行社區(qū)劃分時涉及到計算網(wǎng)絡中核心節(jié)點與網(wǎng)絡中其他節(jié)點的相似性計算，但是利用式 （2）無法得出正確的相似性度量結(jié)果，而利用式 （3）只能度量與核心節(jié)點距離小于3的節(jié)點之間的相似性，無法度量網(wǎng)絡中所有非核心節(jié)點與核心節(jié)點的相似度。因此需要一種新的相似性度量方法來計算度量網(wǎng)絡中核心節(jié)點與其他所有非核心節(jié)點之間的相似度。本文在局部相似性度量方法的基礎上加以改進，提出了基于相似性傳遞的節(jié)點相似性度量方法，具體步驟如下:

步驟1 利用式 （3）計算核心節(jié)點與核心節(jié)點的鄰居節(jié)點之間的相似度；

步驟2 采用式 （4）計算核心節(jié)點與距離核心節(jié)點超過2的節(jié)點之間的的相似度

式中，N（i）是Vi的鄰居節(jié)點，首先采用局部相似性度量方法即式 （3）計算Vi與其鄰居節(jié)點之間的相似度，將Vi的鄰居節(jié)點與核心節(jié)點的相似度Sj，core作為權(quán)值與Si，j相乘，然后求和結(jié)果作為Vi與核心節(jié)點的相似度。例如圖1中定義V6與V1的相似度為S1，6，V7與V1的相似度為S1，7，則V17與V1的相似度即為S1，17＝S1，6×S6，17＋S1，7×S7，17。計算過程中Vi的鄰居節(jié)點會有一部分距離目標節(jié)點更遠，這部分節(jié)點與目標節(jié)點的初始相似度會設置為零，相似性傳遞過程中這部分節(jié)點的貢獻也為零。

步驟3 逐層向外計算更外圍節(jié)點與核心節(jié)點的相似度，直到網(wǎng)絡中所有節(jié)點都計算完畢。

本文提出的這種基于相似性傳遞的節(jié)點相似性度量方法可以正確的度量節(jié)點之間的相似性，從式 （4）可以很容易看出與核心節(jié)點距離越遠的節(jié)點與核心節(jié)點的相似性會越低，所以該方法不存上述基于全局鄰接關(guān)系的相似性度量方法錯誤計算節(jié)點之間相似性的缺陷，并且彌補了局部相似性距離不能計算距離大于等于3的節(jié)點之間的相似度的不足。

2.3 算法的具體步驟及算法分析

本文算法只需獲取網(wǎng)絡的鄰接關(guān)系矩陣即可給出一個較好的社區(qū)劃分結(jié)果，具體的算法步驟如下:

（1）根據(jù)網(wǎng)絡的鄰接矩陣統(tǒng)計出網(wǎng)絡中所有節(jié)點的度數(shù)，并根據(jù)節(jié)點的度數(shù)對節(jié)點進行排序，排序后構(gòu)成集合Vd＝｛Vd1，…Vdn｝；

（2）挑選集合Vd中的大度數(shù)節(jié)點構(gòu)成大度數(shù)節(jié)點集Vmaxd＝｛Vmaxd1，…Vmaxdn｝，本文中選取集合Vd的前0.1部分節(jié)點構(gòu)成集合Vmaxd（實驗經(jīng)驗所得）；

（3）利用式 （2）計算集合Vmaxd內(nèi)節(jié)點兩兩之間的相異性，挑選出相異度大的節(jié)點構(gòu)成集合Vcore＝｛Vcore1，…Vcorek｝，該集合即為核心節(jié)點集；

（4）用本文提出的基于相似性傳遞的節(jié)點相似性度量方法計算網(wǎng)絡中其他節(jié)點與集合Vcore內(nèi)節(jié)點之間的相似度；

（5）根據(jù)步驟4的計算結(jié)果，將節(jié)點劃分到其最相似的核心節(jié)點所在的社區(qū)。

由于復雜網(wǎng)絡中節(jié)點度數(shù)的冪律分布，所以網(wǎng)絡中的大度數(shù)節(jié)點僅占網(wǎng)絡規(guī)模的很小的一個部分，在探測核心節(jié)點的過程中所導致的時間開銷應該占算法總時間的很小的一個部分，算法的時間開銷大部分耗在了網(wǎng)絡中非核心節(jié)點與核心節(jié)點的相似性度量這一步驟，設網(wǎng)絡中存在有n個節(jié)點，而探測的核心節(jié)點的數(shù)目為k，則本方法的時間復雜度應該近似于O（kn），由于k相對于n來說是一個非常小的數(shù)值，可以認定為一個常數(shù)，因此本方法的時間復雜度近似與n呈線性關(guān)系。采用本方法可以對網(wǎng)絡中的社區(qū)進行比較好的劃分，尤其是對于核心節(jié)點比較凸顯的網(wǎng)絡劃分效果更好。

3 實驗分析

為了測試該算法的性能，在人人網(wǎng)的網(wǎng)絡數(shù)據(jù)和公共的網(wǎng)絡數(shù)據(jù)上進行了社區(qū)劃分實驗。

3.1 人人網(wǎng)數(shù)據(jù)中的算法應用

本文中采用的網(wǎng)絡數(shù)據(jù)采集于社交網(wǎng)站人人網(wǎng)，其中共有39個個體，已知該網(wǎng)絡分為3個小組，其中每個小組內(nèi)部都會有一到兩個 “核心”個體，該個體與其小組內(nèi)的成員關(guān)系密切，如圖3所示。

圖3 人人網(wǎng)數(shù)據(jù)網(wǎng)絡

該網(wǎng)絡是一個核心節(jié)點比較明顯，且小組之間差異較大的一個網(wǎng)絡，本文算法首先根據(jù)節(jié)點度數(shù)對節(jié)點進行排序，挑選出V6，V10，V19，V20，V33組成集合Vmaxd，然后計算集合Vmaxd內(nèi)節(jié)點兩兩之間的相異度，根據(jù)計算結(jié)果得出V6與V10以及V19與V20之間相異度過低，所以挑選出了V6，V19和V33構(gòu)成核心節(jié)點集Vcore。從圖3可以看出，本文算法所挑選的節(jié)點正好分別處于3個不同的小組內(nèi)。在得出核心節(jié)點集之后，利用本文提出的相似性度量方法度量網(wǎng)絡中其他節(jié)點與核心節(jié)點之間的相似度，最終對網(wǎng)絡進行社區(qū)劃分得出3個社區(qū)，利用Q公式計算社區(qū)劃分之后的模塊度，得到Q＝0.9，將劃分的結(jié)果與實際的情況進行比較發(fā)現(xiàn)所得社區(qū)與原來分組情況完全一致。實驗結(jié)果表明本文算法在核心節(jié)點比較明顯的網(wǎng)絡中可以得到比較理想的社區(qū)發(fā)現(xiàn)結(jié)果。

3.2 公共網(wǎng)絡中的算法應用

為了進一步驗證算法的有效性和可行性，本文將提出的算法應用在了經(jīng)典的網(wǎng)絡數(shù)據(jù)集Karate Club網(wǎng)絡和Dolphin Social Network中，并且與GN算法和LFM算法[10]進行比較。Karate Club網(wǎng)絡是美國20世紀70年代一所大學的一個空手道俱樂部里34名成員之間的友誼關(guān)系網(wǎng)絡，這是一個存在34個節(jié)點和78條邊的無向拓撲結(jié)構(gòu)網(wǎng)絡。Dolphin Social Network數(shù)據(jù)集是居住在Doubtful Sound外的一個由62頭海豚組成的群落里成員間的頻繁交流形成的一個無向網(wǎng)絡，這個網(wǎng)絡包含62個節(jié)點和159條邊。GN算法是一種典型的全局社區(qū)發(fā)現(xiàn)方法，它是通過不斷的去除最大邊介數(shù)的邊來達到社區(qū)發(fā)現(xiàn)的目的；LFM算法是一種典型的局部社區(qū)發(fā)現(xiàn)方法，它從不同的節(jié)點出發(fā)基于局部模塊度進行信息凝聚來發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。實驗結(jié)果如表1所示。

表1 公共網(wǎng)絡上的實驗結(jié)果比較

本文利用模塊度Q值這一指標來評判社區(qū)劃分的質(zhì)量。從Karate網(wǎng)絡的實驗結(jié)果看來本文算法進行社區(qū)劃分后得到的Q是0.8389，這一結(jié)果與GN算法得到的劃分結(jié)果一樣，而LFM算法得到的Q值為0.7451，本文算法明顯優(yōu)于LFM算法。從表1中可以發(fā)現(xiàn)本文算法進行社區(qū)劃分耗時僅用66ms，而LFM算法用時為166ms，GN算法耗時更是高達1597ms，這一結(jié)果說明本文算法復雜度是最低的。分析Dolphin網(wǎng)絡的實驗結(jié)果發(fā)現(xiàn)本文算法雖然社區(qū)劃分質(zhì)量略低于GN算法得到的結(jié)果，但是明顯優(yōu)于LFM算法，并且算法用時仍是最少的。

本文算法將Karate網(wǎng)絡劃分為2個社區(qū)，而將Dolphin網(wǎng)絡劃分為3個社區(qū)，說明在進行核心節(jié)點探測時在Karate網(wǎng)絡中探測到2個核心節(jié)點，而在Dolphin網(wǎng)絡中得到3個核心節(jié)點。Karate網(wǎng)絡中有34個節(jié)點，算法用時66ms，Dolphin網(wǎng)絡中有62個節(jié)點，算法用時為170ms，對這些數(shù)據(jù)進行分析得到這一式子是算法用時除節(jié)點數(shù)，再除劃分社區(qū)個數(shù)，這一結(jié)果這好驗證了本文算法復雜度和網(wǎng)絡節(jié)點個數(shù)以及核心節(jié)點個數(shù)相關(guān)，成線性關(guān)系。

由于GN算法在不斷的計算網(wǎng)絡中最大邊介數(shù)的邊耗費了大量的時間，該算法計算復雜度極高，而LFM算法隨機選取初始節(jié)點進行社區(qū)發(fā)現(xiàn)無法保證社區(qū)發(fā)現(xiàn)質(zhì)量，本文提出的算法在探測出網(wǎng)絡中不同社區(qū)的核心節(jié)點的條件下進行社區(qū)劃分，保證了社區(qū)發(fā)現(xiàn)的質(zhì)量，并且社區(qū)劃分過程中僅需計算網(wǎng)絡中節(jié)點與核心節(jié)點之間的相似性，算法復雜度近似與網(wǎng)絡中節(jié)點個數(shù)成線性關(guān)系，算法復雜度低。因此理論和實驗結(jié)果證實利用本文提出的算法進行社區(qū)劃分是準確并高效的。

4 結(jié)束語

本文針對當前節(jié)點相似性度量存在的不足，提出了一種基于相似性傳遞的節(jié)點相似性度量方法，可以準確的度量網(wǎng)絡中的節(jié)點與核心節(jié)點之間的相似性，并且應用于本文提出的基于網(wǎng)絡核心節(jié)點的社區(qū)劃分方法中。通過多類數(shù)據(jù)下的實驗比較，表明本文提出的算法社區(qū)發(fā)現(xiàn)質(zhì)量高，效率高，是一種有效的算法。但是如何更加準確的找出網(wǎng)絡中分散在不同社區(qū)的核心節(jié)點仍是接下來需要重要研究和改進的地方。

[1]Scheffer M.Complex systems:Foreseeing tipping points[J].Nature，2010，467（7314）:411－412.

[2]Van der Leij M J，Goyal S.Strong ties in a small world[J].Review of Network Economics，2011，10 （2）:1－21.

[3]LAI Darong.Reseach of complex network community structure analysis method[D].Shanghai:Shanghai Jiaotong University，2011:4－9 （in Chinese）.[賴大榮.復雜網(wǎng)絡社區(qū)結(jié)構(gòu)分析方法研究[D].上海:上海交通大學，2011:4－9.]

[4]CHENG Xueqi，SHEN Huawei.Community structure of complex networks[J].Complex Systems and Complex Science，2011，8（1）:57－70 （in Chinese）.[程學旗，沈華偉.復雜網(wǎng)絡的社區(qū)結(jié)構(gòu)[J].復雜系統(tǒng)與復雜性科學，2011，8 （1）:57－70.]

[5]Chen Q，Wu T T.A method for local community detection by finding maximal－degree nodes[C]／／International Conference on Machine Learning and Cybernetics，2010:8－13.

[6]Fortunato S.Community detection in graphs[J].Physics Reports，2010，486 （3）:75－174.

[7]LüL，Zhou T.Link prediction in complex networks:A survey[J].Physica A:Statistical Mechanics and its Applications，2011，390 （6）:1150－1170.

[8]LIU Xu，YI Dongyun.Complex network community detection by local similarity[J].Acta Automatica Sinica，2011，37（12）:1520－1529 （in Chinese）.[劉旭，易東云.基于局部相似性的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[J].自動化學報，2011，37（12）:1520－1529.]

[9]Leskovec J，Lang K J，Mahoney M.Empirical comparison of algorithms for network community detection[C]／／Proceedings of the 19th International Conference on World Wide Web.ACM，2010:631－640.

[10]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）:1257－1276.