馮健 史丹丹 羅香玉 葉鷗

摘?要：社團發(fā)現(xiàn)能夠揭示復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)特性。針對現(xiàn)有社團發(fā)現(xiàn)算法社團初始節(jié)點選擇隨機、相似度計算過分依賴節(jié)點間共享鄰居以及需要事先設(shè)定社團個數(shù)等問題，依托層次聚類思想提出基于節(jié)點重要度和社團接近度的社團劃分算法。首先引入節(jié)點重要度的定義并給出重要節(jié)點的計算模型，根據(jù)該模型得到最重要節(jié)點作為社團的初始聚類中心;然后兼顧節(jié)點的共享關(guān)系和直接影響定義節(jié)點的社團接近度，依據(jù)社團接近度指標尋找與社團最接近的節(jié)點，根據(jù)該節(jié)點的加入為社團帶來的局部模塊度增量判斷是否將其加入到已有社團。首個社團劃分完畢后，重復(fù)選取初始聚類中心并構(gòu)造社團的過程，直到?jīng)]有可歸入社團的節(jié)點。在2個典型復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進行了測試，

并與Girvan-Newman算法和Newman快速算法從準確率和模塊度進行對比，實驗結(jié)果表明所提算法在社團數(shù)目未知的前提下能夠獲得更好的社團劃分結(jié)果。關(guān)鍵詞：社團發(fā)現(xiàn);層次聚類;節(jié)點重要性;社團接近度中圖分類號：TP 399

文獻標志碼：A

文章編號：1672-9315（2020）01-0181-06

DOI：10.13800/j.cnki.xakjdxxb.2020.0124開放科學(xué)（資源服務(wù)）標識碼（OSID）：

Discovering community structure using node importance

and community proximity

FENG Jian?1，SHI Dan-dan?2，LUO Xiang-yu?1，YE Ou?1

（1.College of Computer Science and Engineering，Xian University of Science and Technology，Xian 710054，China;

2.Chengdu Skysoft Information Technology Co.，Ltd.，Chengdu 610041，China）

Abstract：Community discovery can reveal the topological characteristics of complex networks.For the existing community discovery algorithms，selection of the initial node for a community is random，similarity calculation is over-reliant to the shared neighbors between nodes，and the numbers of communities needs to be set in advance.To overcome these problems，based on the idea of hierarchical clustering，a community discovery algorithm based on node importance and community proximity is proposed.Firstly，the definition of node importance is introduced and the calculation model of important nodes is given.According to the model，the most important node is taken as the initial cluster center of a community.Then，the concept of node-community proximity is defined by taking the sharing relationship and direct effect of nodes into account.The node closest to the community should be found according to the node-community proximity index，andwhether to add it to the existing community is decided according to the increment of partial modularity brought by the node.After the first community is divided，the process of selecting the initial cluster center and constructing the community is repeated until there are no nodes left.Experiments are carried out on two typical complex network datasets，

with a comparison of the accuracy and modularity made between the results by Girvan-Newman algorithm and Newman fast algorithm.The experimental results show that the proposed algorithm can get better result of community division under the premise that the number of communities is unknown.Key words：community discovery;hierarchical clustering;node importance;community proximity

0?引?言

大量研究表明，結(jié)構(gòu)性是復(fù)雜網(wǎng)絡(luò)的本質(zhì)特性。結(jié)構(gòu)性體現(xiàn)為社團，是指復(fù)雜網(wǎng)絡(luò)中的節(jié)點呈現(xiàn)出以簇為特征的聚集狀態(tài)，簇內(nèi)節(jié)點聯(lián)系緊密，簇間節(jié)點聯(lián)系松散[1]。發(fā)現(xiàn)網(wǎng)絡(luò)社團結(jié)構(gòu)也稱作社團劃分，有助于揭示網(wǎng)絡(luò)的組織原則和功能特性[2]，具有十分重要的理論和應(yīng)用價值。

社會學(xué)研究工作者Newman和Girvan等人的研究是復(fù)雜網(wǎng)絡(luò)中社團劃分的起源性研究[3]，在此基礎(chǔ)上人們提出了很多尋找社團結(jié)構(gòu)的算法，包括圖劃分方法，如早期提出的經(jīng)典Kernighan-Lin算法[4]和GN算法[5]，后來逐漸傾向于層次聚類法，具體又分為分裂算法[6-7]、凝聚算法[8-9]、譜平分法[10-11]等;以及隨機塊模型方法[12]、結(jié)合屬性和鏈接法[13-14]等。特別地，針對社團的重疊特性，提出了派系過濾算法[15]、極大團算法[16]、模糊算法[17]等。上述幾類算法根據(jù)不同的研究對象，又可以歸納為基于節(jié)點的和基于邊的社團劃分方法。雖然社團劃分算法已有大量研究，但仍存在一些問題，如圖劃分算法依據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)信息進行社團發(fā)現(xiàn)，往往需要事先設(shè)定社團的數(shù)目，對于社團數(shù)目未知的網(wǎng)絡(luò)效率較低[18];大多社團劃分算法將屬性相似或者角色相似的節(jié)點聚為一類，采用的主流相似度指標[19]如共同鄰居指標、Salton指標、Jaccard指標往往主要考慮節(jié)點之間的共同關(guān)系而忽視了節(jié)點對整個網(wǎng)絡(luò)的影響;已有算法常隨機選擇初始聚類中心，隨后再加以調(diào)整，這樣的策略易導(dǎo)致聚類效果不穩(wěn)定[20]。

為了解決上述問題，借鑒文獻[21]的思想，對層次聚類算法進行改進，提出基于節(jié)點重要度和社團接近度的社團劃分算法NICP（Node Importance and Community Proximity Based Community Discovery Algorithm）以探測網(wǎng)絡(luò)中的社團結(jié)構(gòu)。該算法迭代地選擇重要節(jié)點作為初始聚類中心，并將與社團最接近的節(jié)點有條件加入社團。文中其余部分組織如下，第1部分介紹NICP算法;第2部分進行實驗分析;第3部分總結(jié)全文并指出未來研究方向。

1?社團發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)可以建模為G=（V，E），其中V為節(jié)點集合;E為邊集合。n=|V|為G的節(jié)點總數(shù)，A是G的n×n維鄰接矩陣。要研究的問題是：對于網(wǎng)絡(luò)G，如何根據(jù)網(wǎng)絡(luò)中節(jié)點的相似性找到其社團集合CR.

1.1?評價指標

針對網(wǎng)絡(luò)的真實社團劃分未知和已知的情況，研究者們嘗試采用不同的社團劃分評價指標對社團結(jié)構(gòu)進行量化。主要的量化指標如下

1.1.1?準確率

準確率（Precision，P）指示了被正確劃分的節(jié)點數(shù)占總劃分規(guī)模的比例，其定義如下

P=|CR|∩|CRT||CR|

（1）

式中?|CR|T是網(wǎng)絡(luò)的實際社團結(jié)構(gòu)。

1.1.2?模塊度

模塊度Q是一種用于評價劃分結(jié)果的重要指標[5]，考量的是社區(qū)內(nèi)實際連邊和隨機連邊概率的差異。定義為

式中?m為網(wǎng)絡(luò)的總邊數(shù);u和v為網(wǎng)絡(luò)中的節(jié)點。auv為鄰接矩陣A中第uv個元素的值，即若u和v之間有連邊，則為1，否則為0.D（u）和D（v）分別為u和v的度;Cu和Cv分別是u和v所屬的社團，當(dāng)Cu=Cv時，δ（Cu，Cv）=1;否則，δ（Cu，Cv）=0.

模塊度的取值范圍是[-1，1]，值越大表示網(wǎng)絡(luò)的社團化程度越高，相應(yīng)地，認為社團發(fā)現(xiàn)算法性能越好。

1.1.3?局部模塊度

Q通常也稱為全局模塊度，其計算時間復(fù)雜度高且需已知網(wǎng)絡(luò)整體結(jié)構(gòu)。為了解決這些問題，文獻[22]提出了局部模塊度Ql評價指標，其簡化定義如下

Ql=|Ei||Ei|+|Eo|（3）

式中?|Ei|為社團內(nèi)部的邊數(shù);|Eo|該社團對外連接的邊數(shù)。一個社團內(nèi)部邊越多，外部邊越少，則其Ql值越大，社團結(jié)構(gòu)越清晰。

1.2?NICP算法

NICP基于層次聚類的思想提出算法基本思路：從網(wǎng)絡(luò)G中找到最重要的節(jié)點u作為首個初始聚類中心以構(gòu)建初始社團。在剩余節(jié)點中尋找與該社團最接近的節(jié)點v，計算v與該社團合并后將為社團帶來的局部模塊度增量ΔQl;若ΔQl>0，即v的加入將使社團的內(nèi)聚力得到增強，則將v合并到u所在的社團，否則開始構(gòu)建新的社團。對合并后的小社團重復(fù)上述尋找并添加最接近節(jié)點的過程，直到某個接近節(jié)點的加入將導(dǎo)致ΔQl≤0，這時一個社團劃分完成。重新在剩余的節(jié)點中尋找最重要的節(jié)點作為下一個社團的初始聚類中心，并重復(fù)上述社團劃分過程，直到網(wǎng)絡(luò)中的所有節(jié)點都劃分完畢。算法的關(guān)鍵點是：①最重要節(jié)點的判定，即社團初始聚類中心的確定;②接近節(jié)點的度量，即節(jié)點及社團接近度的度量;③社團內(nèi)聚力的評判。

1.2.1?最重要節(jié)點的判定

在社團的聚類中，初始節(jié)點的選擇在很大程度上影響了社團的內(nèi)聚力和穩(wěn)定性。已有層次聚類算法常隨機選取初始聚類中心，后續(xù)再進行社團中心的調(diào)整，這樣的方法往往導(dǎo)致社團劃分質(zhì)量不高，也容易引起社團的動蕩。重要節(jié)點是網(wǎng)絡(luò)中能夠產(chǎn)生一定影響力并起到信息橋梁作用的節(jié)點，也即同時具有中心性和橋接能力[23]。據(jù)此引入節(jié)點重要度的概念，并選擇重要節(jié)點作為社團初始聚類中心。

定義1?（節(jié)點重要度）I（u），為節(jié)點u的K-shell值和結(jié)構(gòu)洞度的線性組合

I（u）=αKS（u）+βES（u），α+β=1（4）

式中KS（u）是u的K-shell值[24]，ES（u）是通過Burt提出的網(wǎng)絡(luò)有效規(guī)模計算得到的結(jié)構(gòu)洞度[25]。參數(shù)α和β為調(diào)節(jié)系數(shù)，其值根據(jù)實際網(wǎng)絡(luò)結(jié)構(gòu)與功能設(shè)定，實驗中設(shè)置α=0.1和β=0.9.

社團中最重要的節(jié)點即重要度最大的節(jié)點，概念如下

定義2?（重要節(jié)點）NCi，為社團Ci的重要節(jié)點

1.2.2?節(jié)點及社團接近度的度量

社團劃分實質(zhì)上是尋找結(jié)構(gòu)相似或性質(zhì)相似的節(jié)點并將其放入同一社團中的過程，其核心問題是如何不斷尋找與社團連接性最強的節(jié)點。這就要度量節(jié)點與社團中已有各節(jié)點的相似度。已有方法在評價節(jié)點間相似度時常依賴于2個節(jié)點的共同關(guān)系，如一般認為共享鄰居數(shù)量越多相似性越大;文中則認為節(jié)點的相似度不僅與節(jié)點間擁有的共同關(guān)系有關(guān)，還與節(jié)點對另一節(jié)點的直接影響有關(guān)，因此提出接近度的概念。

定義3?（投入精力）ENuv，節(jié)點u對節(jié)點v投入的精力，表達節(jié)點的直接影響，定義為

ENuv= auv/D（u）（6）

定義4?（節(jié)點接近度）θuv，節(jié)點u與節(jié)點v的接近度，定義為

θuv= ENuv+sENus ENsv（7）

式中?s為u和v的共享鄰居。從上式可知接近度不僅表達了節(jié)點u對節(jié)點v的直接影響，也表達了2個節(jié)點間的共同關(guān)系。

以圖1的拓撲為例，節(jié)點a的鄰居集合為{b，c，d，g4，g5，g6，g7，g8}，根據(jù)公式（7）得到θab=0.250 0，

θac=0.125 0，

θad=0.312 5，

θag4=θag5=

θag6=θag7=

θag8=0.146 0

.根據(jù)計算結(jié)果可知，對于a來說，最接近的節(jié)點是d，這也和圖1中的實際情況是吻合的。

推而廣之，節(jié)點的社團接近度即為節(jié)點與社團內(nèi)部所有節(jié)點的接近度之和。

定義5?（社團接近度）θuC，節(jié)點u和社團C的接近度

1.2.3?社團內(nèi)聚力的評判

采用局部模塊度進行社團內(nèi)聚力的評判。若某個節(jié)點的加入導(dǎo)致當(dāng)前社團的局部模塊度增大，則將該節(jié)點加入社團，否則視為新社團起始的標志。

NICP算法的具體描述如下

輸入：G，α，β

輸出：CR

1）CR={}，Ql=0;

2）對V按節(jié)點重要度降序排序形成節(jié)點序列VI;

3）選擇VI中重要度最大的節(jié)點v作為社團初始聚類中心，VI=VI-{v}，Ct={v};

4）建立Ct社團：

①找到與Ct相連的所有節(jié)點，建立節(jié)點集合

VCt;

②通過計算θ值，從

VCt中查找與Ct社團最接近的節(jié)點u;

③若ΔQl>0，則將u加入社團Ct，Ct=Ct+{u}，

VI=VI-{u}，轉(zhuǎn)至①;

否則，CR=CR+Ct，若

VI={}，轉(zhuǎn)至⑤，否則轉(zhuǎn)至③，開始新社團的劃分;⑤算法結(jié)束，輸出CR.

算法引入了2個關(guān)鍵環(huán)節(jié)來保證其穩(wěn)定性和精度：根據(jù)節(jié)點的中心性和橋接性確定社團的初始聚類中心，提高社團劃分質(zhì)量并避免社團劃分過程中的動蕩;兼顧節(jié)點的共享關(guān)系和直接影響更準確地計算節(jié)點與社團的接近度，保證聚類的精度。另外，NICP算法利用局部模塊度增量自動確定一個社團是否結(jié)束，無需事先給定社團數(shù)量。

2?實驗分析

為了定量驗證NICP算法的可行性和有效性，在人工網(wǎng)絡(luò)—三社團網(wǎng)絡(luò)和真實網(wǎng)絡(luò)—足球隊俱樂部Football網(wǎng)絡(luò)數(shù)據(jù)集[3]上分別與有代表性的靜態(tài)社團發(fā)現(xiàn)算法GN和FN[8]進行了綜合評測。實驗在主頻為3.2 GHz，內(nèi)存大小為16 GB的Intel Core i5處理器上完成，程序運行環(huán)境為Python 2.7.

表1為2個測試網(wǎng)絡(luò)的基本信息。

2.1?三社團網(wǎng)絡(luò)

圖2為三社團網(wǎng)絡(luò)示意圖，通過NICP算法的發(fā)現(xiàn)過程見表2.

從表2可以清晰地看到，NICP算法的社團發(fā)現(xiàn)過程：首先通過節(jié)點重要度找到社團的初始聚類中心（3個社團的初始聚類中心分別為6，7，18號節(jié)點），然后逐步尋找最接近節(jié)點，再通過局部模塊度的增大或減小決定將該節(jié)點加入社團或開始一個新的社團。通過對比圖2和表2可以看到，NICP算法的發(fā)現(xiàn)結(jié)果和原網(wǎng)絡(luò)完全一致。

表3給出各算法在三社團網(wǎng)絡(luò)中的發(fā)現(xiàn)結(jié)果。

從表3可以看出，NICP算法的準確率和模塊度與GN，F(xiàn)N算法一樣，3個算法均能準確地對三社團網(wǎng)絡(luò)進行劃分。

2.2?Football

Football是2000年美國大學(xué)橄欖球聯(lián)賽的網(wǎng)絡(luò)數(shù)據(jù)。其中，節(jié)點代表參賽球隊，若兩支球隊之間進行過一場比賽則形成連邊。該網(wǎng)絡(luò)共涉及115所大學(xué)的球隊，分為12個社團，對應(yīng)聯(lián)賽的12個聯(lián)盟。表4給出各算法的社團發(fā)現(xiàn)結(jié)果。

從表4可以看出，NICP算法無論是準確率還是模塊度都比傳統(tǒng)經(jīng)典算法高，說明NICP算法能更有效地劃分網(wǎng)絡(luò)社團結(jié)構(gòu)。

3?結(jié)?論

1）為解決復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)問題提出了一種改進的基于層次聚類的社團發(fā)現(xiàn)算法NICP.

2）針對已有社團發(fā)現(xiàn)算法中初始聚類中心選擇隨機的問題，考慮節(jié)點的中心性和橋接性提出節(jié)點重要度的概念，選擇最重要節(jié)點作為初始聚類中心，提高社團發(fā)現(xiàn)的效率和穩(wěn)定性;針對聚類過程中相似度計算過分依賴節(jié)點間共享鄰居的問題，結(jié)合節(jié)點間的共享關(guān)系和節(jié)點自身的影響提出節(jié)點接近度的概念，并擴展至節(jié)點-社團接近度，并以此作為節(jié)點與社團聚類相似度判定的依據(jù);針對已有算法常需要事先設(shè)定社團個數(shù)的問題，將局部模塊度的減小作為判定條件，自動發(fā)現(xiàn)新的社團。

3）將NICP算法和GN，F(xiàn)N算法應(yīng)用在經(jīng)典人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)中的結(jié)果表明，NICP算法社團發(fā)現(xiàn)結(jié)果的準確率和模塊度指標都更高，證實了該算法具有可行性和有效性。

參考文獻（References）：

[1]汪小帆，劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報，2009，38（5）：537-543.WANG Xiao-fan，LIU Ya-bing.Overview of algorithms for detecting community structure in complex networks[J].Journal of University of Electronic Science and Technology of China，2009，38（5）：537-543.

[2]朱慶生，蔣天弘，周明強.基于自然最近鄰居的社團檢測算法[J].計算機應(yīng)用研究，2014，31（12）：3560-3563.ZHU Qing-sheng，JIANG Tian-hong，ZHOU Ming-qiang.Community detection algorithm based on natural nearest neighbor[J].Application Research of Computers，2014，31（12）：3560-3563.

[3]Girvan M，Newman M E J.Community structure in social and biological networks[J].Proceedings of National Academy of Sciences of the United States of America，2002，99（12）：7821-7826.

[4]Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970（49）：291-307.

[5]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69（2）：026113.

[6]Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America，2004，101（9）：2658-2663.

[7]Sales-Pardo M，Guimera R，Moreira A A，et al.Extracting the hierarchical organization of complex systems[J].Proceedings of the National Academy of Sciences of the United States of America，2007，104（39）：15224-15229.

[8]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics，2003，69（6 Pt 2）：066133.

[9]Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of community hierarchies in large networks[J].Journal of Statistical Mechanics：Theory and Experiment，2008，10：10008.

[10]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.

[11]付立東.一種對分劃分的復(fù)雜網(wǎng)絡(luò)社團檢測方法[J].西安科技大學(xué)學(xué)報，2012，32（5）：648-651.FU Li-dong.Detecting of communities in complex networks with two partitioning approach[J].Journal of Xian University of Science and Technology，2012，32（5）：648-651.

[12]Zhang H，Qiu B，Giles C L，et al.An LDA-based community structure discovery approach for large-scale social networks[C]//Muresan G，Altiok T，Melamed B，Zeng D.Proceedings of 2007 IEEE Intelligence and Security Informatics，New Brunswick，NJ USA，2007：200-207.

[13]黃發(fā)良，肖南峰.基于線圖與PSO的網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)[J].自動化學(xué)報，2011，37（9）：1140-1144.HUANG Fa-liang，XIAO Nan-feng.Discovering overlapping communities based on line graph and PSO[J].Acta Automatica Sinica，2011，37（9）：1140-1144.

[14]李孝偉，陳福才，劉力雄.一種融合節(jié)點與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法[J].計算機應(yīng)用研究，2013，30（5）：1477-1480.LI Xiao-wei，CHEN Fu-cai，LIU Li-xiong.Combined node and link attributes of social network community detection algorithm[J].Application Research of Computers，2013，30（5）：1477-1480.

[15]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：814-818.

[16]Shen H W，Cheng X Q，Cai K，et al.Detect overlapping and hierarchical community structure in networks[J].Physica A Statistical Mechanics & Its Applications，2009，388（8）：1706-1712.

[17]Nepusz T，Petróczi A，N-gyessy L，et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E，2008，77（2）：016107.

[18]Fortunato S，Barthelemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America，2007，104（1）：36-41.

[19]姜雅文，賈彩燕，于?劍.基于節(jié)點相似度的網(wǎng)絡(luò)社團檢測算法研究[J].計算機科學(xué)，2011，38（7）：185-189.JIANG Ya-wen，JIA Cai-yan，YU Jian.Community detection in complex networks based on vertex similarities[J].Computer Science，2011，38（7）：185-189.

[20]閔?亮，邵良杉，趙永剛.基于節(jié)點相似度的社團檢測[J].計算機工程與應(yīng)用，2015，51（9）：77-81.MIN Liang，SHAO Liang-shan，ZHAO Yong-gang.Community detection based on node similarity[J].Computer Engineering and Applications，2015，51（9）：77-81.

[21]馮?健，丁媛媛.基于重疊社區(qū)和結(jié)構(gòu)洞度的社會網(wǎng)絡(luò)結(jié)構(gòu)洞識別算法[J].計算機工程與科學(xué)，2016，38（5）：898-904.FENG Jian，DING Yuan-yuan.A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree[J].Computer Engineering & Science，2016，38（5）：898-904.

[22]Clauset A.Finding local community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics，2005，72（2）：026132.

[23]Feng J，Shi D D，Luo X Y.An identification method for important nodes based on K-shell[J].Journal of Complex Networks，2018，6（3）：342-352.

[24]任卓明，劉建國，邵?鳳，等.復(fù)雜網(wǎng)絡(luò)中最小K-核節(jié)點的傳播能力分析[J].物理學(xué)報，2013，62（10）：466-471.REN Zhuo-ming，LIU Jian-guo，SHAO Feng，et al.Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J].Acta Physica Sinica，2013，62（10）：466-471.

[25]Burt R.Structural holes and good ideas[J].American Journal of Sociology，2004，110（2）：349-399.