基于核心節點的復雜網絡社區劃分算法

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

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

0 引 言

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

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

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

1 算法的相關準備

1.1 網絡模型定義

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

其中，eii是所連接的兩個節點均在社區i內的邊占網絡總邊數的比例，ai是有一個節點在社區i的邊占網絡總邊數的比例。社區結構性越弱Q值越小，社區結構性越強Q值越大，目前大多數社區發現算法用模塊度作為標準來評價社區劃分的好壞。

1.2 相似性度量

相似性度量是對網絡圖中頂點之間相似或相異程度的度量，相當一部分的復雜網絡社區發現算法都利用到了相似性度量，目前對網絡中節點的相似性度量已經有了比較系統的研究，大部分的方法都是利用了網絡中節點的鄰接關系來計算節點之間的相似度，有的方法利用的是全局的鄰接關系，有的方法利用的是局部的鄰接關系。

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

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

圖1 空手道俱樂部成員間的相互關系

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

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

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

2 算法描述

2.1 探測網絡核心節點

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

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

圖2 網絡G社區關系

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

2.2 基于相似性傳遞的節點相似性度量方法

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

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

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

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

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

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

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

本文算法只需獲取網絡的鄰接關系矩陣即可給出一個較好的社區劃分結果，具體的算法步驟如下:

（1）根據網絡的鄰接矩陣統計出網絡中所有節點的度數，并根據節點的度數對節點進行排序，排序后構成集合Vd＝｛Vd1，…Vdn｝；

（2）挑選集合Vd中的大度數節點構成大度數節點集Vmaxd＝｛Vmaxd1，…Vmaxdn｝，本文中選取集合Vd的前0.1部分節點構成集合Vmaxd（實驗經驗所得）；

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

（4）用本文提出的基于相似性傳遞的節點相似性度量方法計算網絡中其他節點與集合Vcore內節點之間的相似度；

（5）根據步驟4的計算結果，將節點劃分到其最相似的核心節點所在的社區。

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

3 實驗分析

為了測試該算法的性能，在人人網的網絡數據和公共的網絡數據上進行了社區劃分實驗。

3.1 人人網數據中的算法應用

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

圖3 人人網數據網絡

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

3.2 公共網絡中的算法應用

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

表1 公共網絡上的實驗結果比較

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

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

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

4 結束語

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

[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）.[賴大榮.復雜網絡社區結構分析方法研究[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）.[程學旗，沈華偉.復雜網絡的社區結構[J].復雜系統與復雜性科學，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）.[劉旭，易東云.基于局部相似性的復雜網絡社區發現方法[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，Fortunato S，Kertész J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics，2009，11 （3）:1257－1276.