基于網絡節(jié)點中心性度量的重疊社區(qū)發(fā)現算法

杜航原 王文劍 白 亮

1(山西大學計算機與信息技術學院 太原 030006)2 (計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006) (duhangyuan@sxu.edu.cn)

網絡結構作為一種靈活普適的抽象和描述方式，能夠對現實世界中大量復雜系統進行建模分析，例如，社會網絡、蛋白質互作用網絡、計算機因特網、生物疾病傳播網絡等都以網絡形式呈現[1].在這些網絡中，各個實體被抽象為網絡節(jié)點，實體間關系被抽象為節(jié)點間的連邊，這些網絡結構具有較高的復雜性，被稱為復雜網絡[2-3].隨著信息技術的快速發(fā)展，復雜網絡已經逐漸成為人類生產生活密不可分的重要組成部分，關于復雜網絡內部連接模式和結構特性的研究探索對人們深入了解和控制復雜系統具有重要意義.隨著研究的深入，人們發(fā)現復雜網絡的拓撲結構表現出一種社團化特征，即整個網絡由若干社區(qū)結構組成，這些社區(qū)內部連接相對緊密，社區(qū)之間連接相對稀疏.網絡社區(qū)結構是現實世界實體關系的一種映射，并廣泛存在于各種網絡中.有效發(fā)現網絡中的社區(qū)結構對于分析復雜系統組成結構、了解系統內部互作用機制、揭示系統發(fā)展規(guī)律以及預測復雜系統行為具有重要的理論意義和實用價值[3-8].

近年來，網絡社區(qū)發(fā)現問題不僅成為了計算機領域中一個極具挑戰(zhàn)的基礎研究課題，也吸引了大量來自物理、生物、醫(yī)學和社會學等諸多領域研究人員的目光，成為一個熱門的多學科交叉課題.發(fā)展至今，針對這一問題已經形成了大量具有代表性的算法，大致可分為4類：1)基于層次聚類的社區(qū)發(fā)現算法，通過度量網絡節(jié)點間的相似度，進而將相似度較大的節(jié)點歸為同一社區(qū)，將相似度較小的節(jié)點置于不同社區(qū)，根據其網絡節(jié)點的聚類規(guī)則可分為凝聚式[9-10]和分裂式2類方法[11-12];2)基于優(yōu)化模型的社區(qū)發(fā)現算法，模擬一個物理系統到達均衡狀態(tài)的過程，定義一個目標函數度量社區(qū)劃分結果的優(yōu)劣[13-14]，在搜索空間中尋找使目標函數取得最優(yōu)值的劃分結果，其中最典型的度量函數是模塊度[15];3)基于圖分割的社區(qū)發(fā)現算法，其基本思想是根據網絡Laplacian矩陣的特征向量分量對網絡節(jié)點間的相似性進行度量，并利用其可以在任意形狀樣本空間上實現聚類的優(yōu)點對網絡社區(qū)進行劃分[16-17];4)以直觀或經驗構造為基礎的啟發(fā)式方法也對社區(qū)發(fā)現問題的研究產生了積極意義，比較有代表性的方法主要包括標簽傳播算法[18-19]、基于距離或吸引力的算法[20-21]以及群智能算法[22-23]等.

在真實復雜網絡中，往往存在一些節(jié)點屬于多個社區(qū)的情況，即社區(qū)間存在彼此重疊的關系而非彼此獨立，這類社區(qū)結構被稱為重疊社區(qū)[1,7,24].例如，一個學者可能加入多個學術團體，一篇學術論文可能涉及多個主題，一個作者也可能參與多篇論文的發(fā)表，這些客觀現象都導致了重疊社區(qū)結構的出現.在這種情況下，從復雜網絡中發(fā)現具有重疊結構的社區(qū)往往具有更加重要的實際價值.

本文的主要貢獻有4方面:

1) 提出了網絡空間中節(jié)點的內聚度和分離度度量，用于描述網絡社區(qū)內部稠密以及外部稀疏的本質結構特征，并基于上述特征計算節(jié)點中心度，對節(jié)點關于其所屬社區(qū)的影響力進行分析;

2) 提出了基于節(jié)點中心度的網絡社區(qū)中心的快速選擇方法，能夠在缺乏先驗信息的情況下識別出網絡中潛在的社區(qū)中心;

3) 利用節(jié)點關于網絡社區(qū)的隸屬度表達社區(qū)結構間的重疊特性，設計了非中心節(jié)點的隸屬度迭代計算方法，將各節(jié)點分配到其可能隸屬的網絡社區(qū);

4) 在人工網絡和真實網絡上的實驗結果表明,本文提出的網絡社區(qū)發(fā)現算法能有效發(fā)現復雜網絡中存在的重疊社區(qū)結構.

1 相關工作

1.1 重疊社區(qū)發(fā)現

由于重疊社區(qū)結構中某些網絡節(jié)點關于社區(qū)的隸屬關系是重疊的，經典的面向獨立社區(qū)的硬劃分發(fā)現算法不再適用.因此，對重疊社區(qū)結構發(fā)現問題的研究逐步成為一個熱點，經過近幾年發(fā)展，在這一領域出現了大量相關研究成果.這些方法大體可分為：派系過濾(clique percolation method, CPM)算法、局部擴展算法、模糊發(fā)現算法、邊劃分發(fā)現算法和標簽傳播算法等5類[24].派系過濾算法最早由Palla等人[25]提出，其基本思想是構建由k個節(jié)點組成的完全連通子圖(即k-派系)，通過搜索具有k-1個相同節(jié)點的鄰接派系實現重疊社區(qū)的發(fā)現.文獻[26]將CPM算法拓展到有權網絡，在對k-派系進行搜索時引入了子圖密度的概念，通過設置閾值有選擇地將k-派系加入社區(qū).文獻[27]將網絡節(jié)點分為孤立節(jié)點、重疊節(jié)點和連接節(jié)點，首先基于深度和廣度搜索抽取網絡中的最大派系，接著利用指定規(guī)則將最大派系兩兩融合擴展為更大的子圖，再利用模塊度判定社區(qū)劃分的質量，該方法能成功地識別出網絡社區(qū)之間的重疊節(jié)點和連接節(jié)點.Zhang等人[28]依據耦合強度這一目標函數對網絡中搜索到的派系進行合并，再對得到的樹狀圖進行層次劃分獲得重疊社區(qū)結構.這類方法以派系為單位檢測社區(qū)的重疊性，在處理稀疏網絡社區(qū)發(fā)現問題時效果不夠理想，而且算法的時間復雜度相對較高.

局部擴展算法的基本思想是，依據某種策略在網絡中搜索種子節(jié)點，再通過一個局部優(yōu)化函數對種子節(jié)點進行擴展，最終獲得社區(qū)的最優(yōu)劃分[29].例如，LFM 算法[30]結合適應度函數將節(jié)點連接形成社區(qū)，再以迭代過程選取社區(qū)外的節(jié)點為種子節(jié)點進行社區(qū)擴展.對于這種使用種子節(jié)點發(fā)現重疊社區(qū)的局部優(yōu)化方法，如何選擇適當的種子節(jié)點尤為重要，為此，Yang等人[31]設計了一種種子節(jié)點選擇策略，首先利用節(jié)點連接密度將原始網絡轉換為一個有權網絡，接著利用Prim或Kruskal 算法找到節(jié)點間的強連接抽取最大生成樹，進而選取生成樹中權重較大的節(jié)點作為種子，并基于PageRank值和模塊度定義目標函數進行社區(qū)初始化，最后通過控制重疊率完成社區(qū)優(yōu)化.文獻[32]按照節(jié)點的度中心性從網絡中選取種子節(jié)點，并依次計算每個種子節(jié)點與其鄰居節(jié)點的局部簇系數，將這一系數作為對鄰居節(jié)點合并的依據，從而完成社區(qū)結構的發(fā)現.局部擴展社區(qū)發(fā)現算法對種子節(jié)點的選取具有較大隨機性，且對社區(qū)擴展的目標函數質量依賴較強，容易導致算法穩(wěn)定性下降.

模糊發(fā)現算法利用隸屬度表示節(jié)點和社區(qū)之間的隸屬關系，將社區(qū)發(fā)現問題轉化為確定節(jié)點隸屬度的過程.文獻[5]面向在線社交網絡提出了一種基于模糊自適應推理理論的重疊社區(qū)發(fā)現算法，包含比較和預測2個階段，在比較階段通過節(jié)點的邊介數和介中心度識別網絡中的獨立社區(qū)，在預測階段利用對偶介數和介中心度進行重疊社區(qū)的初始化，通過2個階段的循環(huán)迭代能較好地解決社區(qū)發(fā)現中產生的可塑性-穩(wěn)定性問題.文獻[7]提出了一種模糊模塊度最大化(fuzzy modularity maximization, FMM)方法，利用模塊度優(yōu)化模型確定節(jié)點的最優(yōu)隸屬度，并設計了2種求解方法.此外，一些學者以非負矩陣分解為工具，提出了一系列節(jié)點隸屬度的求解方法[6,24,33].模糊重疊社區(qū)發(fā)現算法的缺點在于，通常需要事先指定網絡中的社區(qū)數量，這對于結構復雜的網絡往往是不現實的.

以上算法在發(fā)現重疊社區(qū)結構時集中于對節(jié)點與社區(qū)關系的研究，與此不同，邊劃分發(fā)現算法從邊的角度構建社區(qū)結構.Li等人[34]設計了一種以線圖模型為基礎的加權模型，基于鏈路聚類構成具有相似結構的鏈路社區(qū)，對模塊密度函數進行優(yōu)化識別出線圖模型上連接稠密的鏈路組，并設計了一種新的基因表示模型將鏈路社區(qū)映射為節(jié)點社區(qū)，實現重疊社區(qū)的劃分.Ahn等人[35]認為社區(qū)是網絡中邊的聚合，當幾條邊隸屬不同社區(qū)時，它們的共有節(jié)點便成為了重疊節(jié)點，通過度量兩條邊之間的相似性對邊進行層次聚類，能有效表達社區(qū)內節(jié)點的層次關系和重疊關系.文獻[36]提出了一種社會網絡的多尺度重疊社區(qū)發(fā)現算法，該方法利用邊的局部集合對節(jié)點進行描述，分別在個體節(jié)點、個體連邊和整個網絡3個尺度上定義了社區(qū)結構應滿足的定量標準，并設計了一種基于原型的社區(qū)發(fā)現算法，能夠在大規(guī)模低密度網絡上產生較好效果.目前，邊劃分發(fā)現算法已經成為一類重要的重疊社區(qū)發(fā)現算法.

基于標簽傳播的方法為每個網絡節(jié)點分配包含重疊隸屬關系的標簽，通過這些標簽在鄰居節(jié)點之間的傳播使節(jié)點關于各社區(qū)的隸屬關系最終達到穩(wěn)定狀態(tài)，從而獲得社區(qū)發(fā)現結果.這類方法的典型代表是基于多標簽的COPRA算法和基于Speaker-listener模型的SLPA算法[24].Gaiter等人[18]于2015年提出了一種SpeakEasy聚類方法，利用自頂向下和自底向上2種策略識別社區(qū)，根據節(jié)點的局部連接性和網絡結構的全局信息將節(jié)點加入社區(qū)，該方法能對社區(qū)結構穩(wěn)定性做出定量評價，在10萬級節(jié)點數量的網絡中取得了較好效果.

1.2 密度峰值聚類

2014年Rodriguez等人[37]提出了密度峰值聚類算法，其基本思想是：簇中心被一些具有較低局部密度的節(jié)點圍繞，并且距離其他高密度節(jié)點的距離較遠.該方法依據節(jié)點間距離定義節(jié)點分布的局部密度，通過快速搜索和發(fā)現密度峰值進行聚類中心的選擇，實現簇的劃分.算法為每個節(jié)點定義了如式(1)所示的局部密度：

(1)

(2)

算法利用決策圖搜索δi值異常大的節(jié)點作為簇中心，再將非中心節(jié)點分配到比其密度高并且距離最近的節(jié)點所屬的簇中，實現對數據的聚類.

密度峰值聚類思想很適合用來描述網絡社區(qū)內部稠密、外部稀疏的結構特征，因此一些學者[38-39]將密度峰值的概念用于重疊社區(qū)發(fā)現，為這一問題的研究開辟了新的方向.但這些方法存在一些共性問題，例如需要事先指定社區(qū)數量、需要設置節(jié)點間的截斷距離、在度量節(jié)點間距離時將整個網絡作為搜索空間引入了過高的計算量、難以應用于大規(guī)模網絡等.為了解決這些問題，本文基于密度峰值聚類思想提出了一種面向重疊社區(qū)結構的自適應發(fā)現算法，利用網絡節(jié)點的內聚度和分離度度量描述社區(qū)內部稠密、外部稀疏的結構特征，通過節(jié)點中心度反映節(jié)點對所屬社區(qū)結構的影響力，在此基礎上設計了社區(qū)中心的快速選取策略，最終確定各非中心節(jié)點的隸屬度實現重疊社區(qū)結構的劃分.該方法能獲得接近真實社區(qū)劃分的發(fā)現結果，無需事先指定社區(qū)數量，具有較低的計算復雜度.人工網絡和真實網絡上的仿真實驗結果驗證了該方法的有效性.

2 基于節(jié)點中心度的重疊社區(qū)發(fā)現算法

在聚類問題中，節(jié)點的局部密度基于節(jié)點間距離進行定義，而網絡中的節(jié)點并非定義在幾何特征空間中，我們能獲得的僅僅是網絡節(jié)點間的連接關系，基于距離對節(jié)點局部密度進行定義不再適用，并且對于重疊社區(qū)，節(jié)點與社區(qū)的隸屬關系相比獨立社區(qū)更加復雜.為此，本文利用節(jié)點間的連接關系定義了節(jié)點的內聚度和分離度分別用于描述社區(qū)內部連接的緊密性以及社區(qū)外部連接的稀疏性，在此基礎上計算節(jié)點中心度替代局部密度，作為度量節(jié)點對社區(qū)結構影響力的重要性指標.

2.1 節(jié)點內聚度

為敘述簡便，本文算法以無權網絡為例進行闡述，對有權網絡同樣適用.對于一個以圖G=V,E表示的復雜網絡，其中V={v1,v2,…vn}為由網絡中全部節(jié)點構成的集合，E={e1,e2,…,em}為節(jié)點間連邊構成的集合.令NGi={vj|vi,vj∈E}表示節(jié)點vi的鄰居節(jié)點構成的集合，則節(jié)點vi的度可表示為di=|NGi|.An×n=(ai j)為網絡的鄰接矩陣，若節(jié)點vi與節(jié)點vj存在連邊，則ai j=1，否則ai j=0.

對于一個網絡社區(qū)，其中心節(jié)點作為社區(qū)的組織和領導者，應該與其他節(jié)點保持比較密切的連接關系，因此中心節(jié)點通常具有較高的度.同時，社區(qū)內部的連接關系應該具有較高的相似性，即由中心節(jié)點關聯的節(jié)點間具有較為相似的連接關系.基于這一假設，我們?yōu)榫W絡節(jié)點的內聚度進行如下定義：

定義1. 網絡節(jié)點內聚度.網絡中節(jié)點vi的內聚度是該節(jié)點的度及其與鄰居節(jié)點的最大相似度的乘積，可形式化表示為

(3)

其中Ii為節(jié)點vi的內聚度;simi,j=|NGi∩NGj|為節(jié)點vi與其鄰居節(jié)點vj的相似度，即兩節(jié)點共有的鄰居節(jié)點數量.由這一定義可以看出，節(jié)點內聚度同時考慮了節(jié)點的連接數量和連接相似性2個因素，節(jié)點的內聚度越高，該節(jié)點對于社區(qū)內其他節(jié)點的聚合能力越強，這反映了社區(qū)結構內部連接的稠密性.

2.2 節(jié)點分離度

依據網絡社區(qū)的定義，社區(qū)外部的連接是相對稀疏的，也就是說作為社區(qū)領導者的中心節(jié)點之間應該具有較低的相似性和連接密切性.根據節(jié)點內聚度定義可知，社區(qū)中心具有較高的內聚度，那么社區(qū)中心與其他內聚度較高的節(jié)點(潛在的社區(qū)中心)應該具有較低的相似性.基于這一思想，我們定義節(jié)點的分離度如下：

定義2. 網絡節(jié)點分離度.網絡中節(jié)點vi的分離度是內聚度比該節(jié)點高的節(jié)點與該節(jié)點間的最大相似度的倒數，可形式化表示為

(4)

其中，Pi為節(jié)點vi的分離度，其取值越大表明vi與內聚度更大的節(jié)點之間的相似性越低，這反映了社區(qū)結構外部連接的稀疏性.為了確保式(4)是有意義的，對分母進行修正，如式(5)所示：

(5)

2.3 社區(qū)中心的快速選擇方法

基于密度峰值聚類方法的思想，我們認為社區(qū)中心是這樣一些節(jié)點：1)在局部范圍內具有較高的內聚度；2)與其他內聚度較高的節(jié)點間相似性較低.節(jié)點對這2個條件的滿足程度越高，表明它對社區(qū)結構的影響力越大，也就越有可能成為社區(qū)中心.為此，我們利用節(jié)點的中心度描述其影響力.

定義3. 網絡節(jié)點中心度.網絡中節(jié)點vi的中心度是該節(jié)點內聚度與分離度的乘積，可形式化地表示為

Ri=Ii×Pi，

(6)

其中，Ri為節(jié)點vi的中心度，反映了節(jié)點對社區(qū)結構的影響力，中心度越高，則該節(jié)點越可能成為社區(qū)中心.

這樣，我們可以獲得每個網絡節(jié)點的內聚度、分離度以及中心度.如果已知網絡中社區(qū)數量K，則可直接選取中心度最大的K個節(jié)點作為社區(qū)中心.然而在很多實際網絡中，我們很難預先獲得準確的社區(qū)數量，針對這一問題，本文提出了一種能夠快速確定社區(qū)中心的方法.

首先，利用式(7)求取各節(jié)點中心度的Z分數(Z-scores)：

(7)

其中，

(8)

(9)

算法1. 社區(qū)中心自適應選擇算法.

輸入：復雜網絡G=V,E、鄰接矩陣An×n；

輸出：社區(qū)中心節(jié)點集合C.

① for each nodevi∈V

② 通過式(3),(5),(6)分別計算節(jié)點vi的內聚度Ii、分離度Pi以及中心度Ri；

④ end for

⑦ returnC={ck}.

2.4 節(jié)點的社區(qū)分配

本文通過隸屬度向量表示節(jié)點關于各社區(qū)的隸屬情況，假設網絡中包含K個社區(qū)，則節(jié)點vi的隸屬度向量可表示為ωi=(ωi,1,ωi,2,…,ωi,K)，其中ωi,k為vi關于第k個社區(qū)的隸屬度.通常情況下社區(qū)中心不會成為重疊節(jié)點，因此社區(qū)中心ck關于第k個社區(qū)的隸屬度設置如下：

ωcj,k=Δcj,k，

(10)

其中，

(11)

非社區(qū)中心節(jié)點的隸屬度向量依賴于比其內聚度更高的節(jié)點，并且二者之間的相似度越高，這種依賴關系越強烈.為便于計算，我們將網絡中所有節(jié)點按照內聚度進行降序排列，得到的節(jié)點列表V中任意2個節(jié)點vp和vq滿足若pvq.此外，依據節(jié)點中心度定義可知R1=maxRi.各非中心節(jié)點的隸屬度向量可通過式(12)依次計算：

(12)

其中，

(13)

算法2. 節(jié)點社區(qū)分配算法.

輸入：社區(qū)中心節(jié)點集合C、按內聚度降序排列的節(jié)點列表V、節(jié)點中心度Ri、閾值θ；

輸出：節(jié)點隸屬度向量ωi.

① for each core nodeci∈C

② for each communityk=1,2,…,K

③ ifci是第k個社區(qū)的中心；

④ωi,k=1;

⑤ else

⑥ωi,k=0;

⑦ end if

⑧ end for

⑨ end for

⑩ for each non-core nodevi∈V-C

3 實驗與結果分析

為驗證算法有效性，我們選取LFM[29],LINK[35],COPRA[24],OCDDP[39]以及CFinder[40]等重疊社區(qū)發(fā)現算法與本文提出方法進行實驗比較.實驗環(huán)境為：處理器Inter Core i7 4790 3.60 GHz，內存8 GB，操作系統Windows10 64 bit.

3.1 實驗數據集

本文分別利用人工網絡數據集和真實網絡數據集對多種算法開展實驗分析與比較，其中真實數據集選取如表1所示的8個常見網絡數據集，人工數據集由LFR基準生成.

Table 1 The Real Network Dataset表1 真實網絡數據集

LFR基準網絡能對真實網絡的特性進行較好的模擬，例如節(jié)點度和社區(qū)大小的無標度性等，且其社區(qū)結構特性通過參數指定，便于對社區(qū)發(fā)現質量進行客觀評價，是當前網絡社區(qū)發(fā)現研究中常用的人工數據集.LFR基準網絡的結構特性由表2所示參數指定：

Table 2 Parameters of LFR Network表2 LFR網絡參數

3.2 評價準則

1) 人工網絡評價準則

對于由LFR基準生成的人工網絡，其網絡特性通過多個參數進行指定，社區(qū)結構真值已知，可利用標準化互信息(normalized mutual information,NMI)[16]作為各社區(qū)發(fā)現算法的評價指標.NMI指數通過信息熵定義，用于反映社區(qū)發(fā)現結果與真實社區(qū)劃分之間的相似程度，取值范圍為0≤NMI≤1，其取值越高，表明社區(qū)發(fā)現結果越接近真實值.

2) 真實網絡評價準則

對于真實網絡，由于缺乏社區(qū)結構的先驗真值，一般利用模塊度將社區(qū)劃分后的網絡與相應一階零模型網絡進行比較，以此評價社區(qū)發(fā)現結果的質量.由于模塊度函數Q假設各社區(qū)之間相互獨立，只適用于獨立社區(qū)評價，為此本文選取2類重疊模塊度函數Qov[24]和EQ[41]作為算法發(fā)現結果的評價指標.這2種模塊度函數是在重疊社區(qū)結構下對模塊度函數Q進行擴展，其取值越大，表明社區(qū)發(fā)現結果的質量越高.

3.3 人工網絡實驗結果

1)算法時間效率比較

我們利用LFR基準生成10個人工網絡，用于測試和比較各種社區(qū)發(fā)現算法的運行時間，在這些網絡中，節(jié)點數量依次設置為N=10 000～100 000，其他參數取相同值，d=15，dmax=50，γ=-2，β=-1，minc=10，maxc=500，mu=0.1，On=100，Om=3.

各社區(qū)發(fā)現算法在不同規(guī)模的人工網絡上運行時間如圖1所示.由圖1可以看出，CFinder算法運行時間顯著高于其他算法，當網絡節(jié)點數量超過50 000后算法失效，這是由于算法以派系為單位檢測社區(qū)的重疊性，派系的產生過程計算量較大；其他算法的運行時間與網絡節(jié)點數量基本呈線性關系；LFM算法基于適應度函數局部最優(yōu)化思想，在實驗中取得了最高的計算效率；COPRA算法的計算量與迭代次數相關，因此當網絡規(guī)模較大時，其算法計算效率有所下降； OCDDP算法基于節(jié)點間連接強度定義節(jié)點密度和距離，由于考慮到兩節(jié)點間的間接連接方式，需要在整個網絡上進行全局搜索，算法計算量對網絡規(guī)模比較敏感；LINK算法在處理規(guī)模不大的網絡時具有較高的計算效率，但由于其將所有的邊都劃分到特定的鏈接社區(qū)中，需要耗費較多的存儲時間，當網絡規(guī)模較大時，其計算量有明顯增加；本文算法是對數據集的“一次性”掃描，計算量與網絡規(guī)模呈線性關系，計算效率較高，且非常穩(wěn)定.綜上，本文算法在這些人工網絡中的計算效率略低于LFM算法，但相比COPRA,LINK,CFinder和OCDDP等算法具有一定優(yōu)勢.

Fig. 1 Execution time comparison for different algorithms圖1 各算法運行時間比較

2) 參數δ和θ的影響

為分析參數δ和θ對本文算法社區(qū)發(fā)現結果產生的影響，我們令δ的取值分別為2,3,4,5,6，以及θ的取值分別為0.5,0.6,0.7,0.8,0.9,1，在前述10個LFR人工網絡上進行實驗，取每一組參數設置下算法社區(qū)發(fā)現結果的NMI均值作為最終結果.這2個參數取不同值時算法獲得的NMI值如圖2所示，其中每條折線表示了給定δ取值算法社區(qū)發(fā)現結果隨δ取值的變化情況.由圖2可以看出，δ取3和4時，本文算法能獲得較好的社區(qū)發(fā)現結果，而該參數取值為5和6時社區(qū)發(fā)現準確度較差，這主要是由于參數δ用于控制內聚度和分離度的相對關系，確保選擇出內聚度和分離度都較大的節(jié)點作為社區(qū)中心，參數取值過小或過大都無法實現這一目的.參數θ的取值為0.8和0.9時，算法能獲得較高的NMI值，這是由于算法首先考慮將非中心節(jié)點分配到使節(jié)點隸屬度最大的社區(qū)，若節(jié)點同時作為2個社區(qū)的重疊節(jié)點，則節(jié)點關于這2個社區(qū)的隸屬度應當較為接近；而參數θ的取值較小時，算法會將一些獨立節(jié)點誤判為重疊節(jié)點，導致識別出的社區(qū)結構過度重疊.

Fig. 2 Comparison results for parameters δ and θ圖2 參數δ和θ取不同值時的結果比較

3) 各算法社區(qū)發(fā)現結果比較

為比較各算法在人工數據集上獲得的社區(qū)發(fā)現精度，我們利用LFR基準生成8組網絡數據，每組數據由8個網絡構成，這些網絡的Om參數取值分別為2～9，其余參數在每一組數據中使用相同的設置，如表3所示.用于對比實驗的算法中LINK算法無需設置參數，其余算法的參數設置如表4所示.其中，LFM算法的參數α用于控制社區(qū)規(guī)模，COPRA算法的參數v表示節(jié)點攜帶的最大標簽數，CFinder算法的參數k表示完全連通子圖規(guī)模，OCDDP算法中的參數t和σ分別表示節(jié)點連接強度中絕對連接的權重以及節(jié)點關于重疊社區(qū)的分配閾值，本文算法中參數δ和θ分別用于控制節(jié)點內聚度與分離度的相對關系以及節(jié)點重疊程度.每種算法選取不同參數設置下的最大NMI值作為該算法運行結果，在各組網絡中算法的社區(qū)發(fā)現結果如圖3所示，其中橫坐標為LFR基準的參數Om，縱坐標表示算法獲得的NMI值.

Table 3 Parameter Settings of LFR Benchmarks表3 LFR基準網絡參數設置

Table 4 Parameter Settings of Different Algorithms表4 各算法參數設置參數

Fig. 3 Community detection results of different algorithms on synthetic networks圖3 人工網絡上各算法的社區(qū)發(fā)現結果

與LFM算法相比，本文算法在混合度較低的網絡上獲得了與LFM算法相近的社區(qū)發(fā)現質量，2種算法的社區(qū)發(fā)現結果質量都較高，而對于混合度較高的網絡，本文算法在大多數情況下能獲得優(yōu)于LFM的發(fā)現結果，表明本文算法在復雜網絡結構中的重疊社區(qū)識別能力優(yōu)于LFM.此外，重疊節(jié)點數量的變化對2種算法社區(qū)發(fā)現結果影響都不大，說明二者都具有一定的發(fā)現重疊度較高的網絡社區(qū)的能力.

與LINK算法相比，本文算法在各個網絡上都獲得了更高的NMI值，這主要是由于LINK算法將所有邊都視為重疊社區(qū)的一部分，容易導致社區(qū)結構過度重疊，使得社區(qū)發(fā)現質量降低；而本文算法對重疊節(jié)點的處理更加合理，僅選擇相對隸屬度較大的有效節(jié)點轉化為重疊節(jié)點.

與COPRA算法相比，本文算法在所有混合度較低(mu=0.1)的網絡中能夠獲得NMI值更高的社區(qū)發(fā)現結果，并且對于混合度較高的(mu=0.3)網絡，算法在大部分時候仍然取得了更好的結果.而COPRA僅在個別網絡中，如G4的Om=7和G6的Om=2時獲得優(yōu)于本文算法的結果.此外，隨著Om取值的增大，在各組網絡中社區(qū)發(fā)現的難度也隨之增大，本文算法獲得的NMI值整體呈現出較為平穩(wěn)的下降趨勢；而COPRA獲得的結果出現了多次震蕩，尤其是對于高混合網絡，算法的穩(wěn)定性較差.這主要是由于COPRA算法中存在較多隨機因素，尤其是在更新標簽和隸屬系數時，往往需要對多余標簽做隨機刪除，導致 COPRA算法得到的結果不夠穩(wěn)定.

與CFinder算法相比，本文算法在各個網絡中獲得的社區(qū)發(fā)現結果都優(yōu)于CFinder，尤其是當網絡mu參數較大時，本文算法能獲得比CFinder更加穩(wěn)定的社區(qū)發(fā)現結果.這主要是由于CFinder對mu參數容忍度較差，基本無法處理較為稠密的網絡.

與OCDDP算法相比，本文算法同樣基于密度峰值聚類思想，二者不同之處在于：OCDDP算法僅考慮節(jié)點的連接強度作為距離和密度度量，忽略了節(jié)點間連接關系的相似性對社區(qū)構成的影響因素，而本文算法通過內聚度和分離度能較好地反映社區(qū)內部稠密、外部稀疏的本質屬性，因此在大部分網絡中能夠獲得更好的社區(qū)發(fā)現結果.

綜上，在不同人工網絡中本文算法獲得了優(yōu)于其他算法的重疊社區(qū)結構發(fā)現結果.

3.4 真實網絡實驗結果

在表1所示的真實網絡上，我們對各種重疊社區(qū)發(fā)現算法的結果進行比較，各算法仍采用表4所示的參數設置.對于LINK算法，我們設置參數c作為其將鏈接社區(qū)轉化為節(jié)點社區(qū)時的最小邊數量，令c的取值范圍為2～15.各算法分別選取不同參數下最優(yōu)Qov和EQ作為最終結果，表5給出了各算法在真實網絡上的社區(qū)發(fā)現結果及最優(yōu)參數值，并且將每個網絡中社區(qū)發(fā)現結果的最大Qov值進行標黑.通過對比這些結果可以發(fā)現，LINK算法的社區(qū)發(fā)現Qov值是最低的，且這一算法的最大Qov值都是在參數c>0的不同值時獲得的，說明算法構造的較小的鏈路社區(qū)影響了社區(qū)發(fā)現結果，簡單地舍去這些小規(guī)模鏈路社區(qū)仍然無法顯著改善算法有效性.在這些真實網絡中，本文算法在大部分情況下都取得了最高的Qov值，并在Netscience和PGP網絡中獲得了非常接近最優(yōu)值的次優(yōu)結果.總體上來看，本文算法能夠在各種真實網絡中獲得優(yōu)于其他算法的重疊社區(qū)發(fā)現結果.此外，本文算法在不同網絡上獲得最大Qov值時對應的參數δ和θ取值變化不大，表明這2個參數的最優(yōu)值具有較高的普遍適用性.

Table 5 Community Detection Results of Different Algorithms on Real Networks表5 網絡上各算法的社區(qū)發(fā)現結果

4 總 結

本文設計了一種網絡節(jié)點的中心性度量模型，基于網絡社區(qū)內部連接稠密和外部連接稀疏的結構特征評價網絡節(jié)點對所屬社區(qū)的影響力，為網絡節(jié)點中心性定量分析提供了有效途徑.在此基礎上，給出了社區(qū)中心節(jié)點的快速選擇方法以及非中心節(jié)點的社區(qū)分配策略，提出一種基于節(jié)點中心性度量的重疊社區(qū)結構發(fā)現算法.在仿真實驗中，利用人工網絡和真實網絡對算法的有效性進行了驗證，實驗結果表明，本文提出的重疊社區(qū)發(fā)現算法在社區(qū)發(fā)現質量和計算效率方面優(yōu)于許多已有算法.在未來工作中，我們將在時空軌跡網絡上對節(jié)點中心性度量模型及重疊社區(qū)發(fā)現算法開展探索應用，針對行人、車輛、飛機及船只等移動物體產生的大規(guī)模時空網絡數據進行模式發(fā)現和異常檢測分析.

DuHangyuan, born in 1985. PhD, master supervisor. Member of CCF. His main research interests include clustering analysis and complex network theory.

WangWenjian, born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include computational intelligence, machine learning, and machine vision.

BaiLiang, born in 1982. PhD, associate professor, master supervisor. Member of CCF. His main research interests include clustering ensemble and complex network theory.