基于節(jié)點相似度的社團發(fā)現(xiàn)算法研究

張若昕　柴丹煒　熊小峰　劉建生　樂光學

摘要：社團發(fā)現(xiàn)算法是分析研究復雜網(wǎng)絡結(jié)構(gòu)的有效方法之一，針對該問題，在分析節(jié)點相似度和網(wǎng)絡拓撲結(jié)構(gòu)的基礎上，提出了一種基于節(jié)點相似度復雜網(wǎng)絡社團發(fā)現(xiàn)算法，算法以模塊密度函數(shù)和標準互信息作為社團的評價參數(shù)對復雜網(wǎng)絡實施有效劃分。人工網(wǎng)絡和真實網(wǎng)絡上的實驗結(jié)果表明，算法能夠準確的發(fā)現(xiàn)復雜網(wǎng)絡中的社區(qū)結(jié)構(gòu)。

關(guān)鍵詞： 社團發(fā)現(xiàn)； 節(jié)點相似； 模塊密度； 復雜網(wǎng)絡

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）08-0042-03

Abstract：Community detection is one of the effective methods for analyzing the structure of complex network. In this paper， the node similarity and topology of network is analyzed， a new community detection algorithm in complex network based on node similarity is proposed. The modularity density and normalized mutual information are chosen to be the evaluation parameters to detect the community structure. Experimental results on both artificial network and real world networks show the algorithm can detect the structure of community complex networks.

Key words：community detection； node similarity； modularity density； complex network

1 引言

社團結(jié)構(gòu)的發(fā)現(xiàn)已經(jīng)成為復雜網(wǎng)絡研究方向中重要的研究方向，社團結(jié)構(gòu)是復雜網(wǎng)絡具有共同性質(zhì)的節(jié)點的集合，在社團內(nèi)部節(jié)點連接較為緊密，節(jié)點之間的相似度較高，具有一些的共同屬性和相似的拓撲結(jié)構(gòu)；而不同社團之間的連接則較為稠密，節(jié)點之間的相似性較低[1]。目前對于復雜網(wǎng)絡的研究已經(jīng)廣泛的應用在社會網(wǎng)絡、生物網(wǎng)絡、通訊網(wǎng)絡等的網(wǎng)絡結(jié)構(gòu)研究問題中，針對其中的社團結(jié)構(gòu)的研究也已經(jīng)成為了熱點研究方向[2-6]。本文針對網(wǎng)絡中節(jié)點相似度，構(gòu)建了基于節(jié)點相似度的社團發(fā)現(xiàn)算法。

2 基于節(jié)點相似度的社團發(fā)現(xiàn)算法

2.1 相似度的定義

復雜網(wǎng)絡中的連通圖可以表示為G=（V，E），其中V是圖中節(jié)點的集合，定義為V={v1， v2，…，vn}， n為網(wǎng)絡中節(jié)點的數(shù)量，E是圖中邊的集合，表示為E={（vi，vj）| vi，vj∈V}，在一般的復雜網(wǎng)絡定義中，邊值定義為兩個節(jié)點之間的物理距離，若兩個節(jié)點之間沒有連接，則邊值定義為0，存在連接的話邊值為實際距離。而為了分析基于用戶相似度的網(wǎng)絡，將邊值設為兩個節(jié)點的相似度值，兩個節(jié)點的相似度越大，則連接這兩個節(jié)點的邊值也越大。

為了衡量兩個節(jié)點之間的相似度，根據(jù)復雜網(wǎng)絡的定義認為如果兩個節(jié)點擁有較多的共同鄰接節(jié)點，則它們的相似度應該較大；反之，而若它們之間的共同鄰接節(jié)點較少，則相似度較小。設節(jié)點vi的鄰接節(jié)點的集合為Ni，節(jié)點vj的鄰接節(jié)點的集合為Nj，則它們所擁有的共同鄰接節(jié)點的集合可以表示為Ni∩ Nj。則這兩個節(jié)點的相似度可以定義為：

但是由于在復雜網(wǎng)絡中存在著“富人俱樂部”特性，即在復雜網(wǎng)絡中的度分布呈現(xiàn)出長尾性質(zhì)，度較小的節(jié)點占據(jù)網(wǎng)絡中的大多數(shù)，而這些度較小的節(jié)點也傾向于網(wǎng)絡中少量存在的度較大的節(jié)點，這些度較大的節(jié)點會因為不斷的吸引導致度更大[7]?？紤]到這些“富人節(jié)點”的度較大，使得其他節(jié)點和它們的共同鄰接節(jié)點數(shù)量較多，導致它們的相似度很高，從而對其他非“富人節(jié)點”之間的相似度進行干擾。為了解決上述定義，相似度定義為：

在公式（3）中使用對數(shù)函數(shù)對復雜網(wǎng)絡中的“富人節(jié)點”與其他節(jié)點進行相似度計算后相似度值要明顯大于其他普通節(jié)點之間的相似度值的現(xiàn)象進行抑制。而由于當|Ni∩ Nj|<1時，相似度值為負的情況，公式（3）在對數(shù)函數(shù)內(nèi)部進行加一，這樣保證了相似度的值為正的完備性。

2.2 模塊密度定義

Newman等人在文獻[8]中提出了模塊度Q作為網(wǎng)絡社區(qū)劃分質(zhì)量的評價參數(shù)，其公式定義為：

在公式中， eii是邊所連接的兩個節(jié)點均在社區(qū)Gi內(nèi)的邊占網(wǎng)絡中所有邊的比例，ai是邊所連接的節(jié)點中至少有一個在社區(qū)Gi內(nèi)的邊占網(wǎng)絡中所有邊的比例。模塊度函數(shù)可以反映社區(qū)結(jié)構(gòu)的明顯程度，社區(qū)結(jié)構(gòu)越明顯，則模塊度函數(shù)值越大，反之社區(qū)結(jié)構(gòu)越弱，模塊度函數(shù)值越小。

使用模塊度作為社團劃分的評價參數(shù)存在著對于小社團結(jié)構(gòu)無法正確發(fā)現(xiàn)的分辨率極限問題，所以目前也有很多對于模塊度進行改進的研究。Fortunato等人在文獻[9]中提出了使用模塊密度作為社區(qū)劃分的評價函數(shù)，其定義為：

其中L（Vi， Vi）表示某個社團內(nèi)部的連接數(shù)量，而表示該社團與其他社團的連接數(shù)量，基于復雜網(wǎng)絡的鄰接矩陣A，它們分別可以表示為：

模塊密度定義了所有子圖平均內(nèi)部連接率和所有子圖與子圖之間的平均外部連接率的差，反映了模塊內(nèi)部和模塊之間的連接緊密程度。對于網(wǎng)絡中的社團結(jié)構(gòu)，其基礎定義就是社團內(nèi)部連接較為緊密而不同社團之間的連接較為稀疏。

2.3 算法描述

算法流程描述如下：

輸入：無向網(wǎng)絡圖G=（V，E）

輸出：網(wǎng)絡G的社團結(jié)構(gòu)

Step1：初始化網(wǎng)絡社團結(jié)構(gòu)，使得整個網(wǎng)絡構(gòu)成一個大型社團結(jié)構(gòu)；

Step2：若網(wǎng)絡中||V||=0或者||E||=0，則退出算法，否則計算每個節(jié)點對的相似度，并存于節(jié)點相似度矩陣中；

Step3：遍歷節(jié)點相似度矩陣中的值，刪除其中相似度最小的社團連接；

Step4：重復Step3直到社團連接數(shù)量小于閾值，形成一個終止的社團劃分結(jié)果。

3 實驗驗證及分析

3.1 人工合成網(wǎng)絡實驗

為了驗證算法的有效性，先使用Lancichinetti提出的基準網(wǎng)絡對算法進行驗證。Lancichinetti網(wǎng)絡由128個節(jié)點組成，這些節(jié)點被劃分為4個社團，每個社團包含32個節(jié)點，節(jié)點的平均度為16。該網(wǎng)絡的構(gòu)成可以通過混合參數(shù)γ進行調(diào)整，γ表示節(jié)點與該節(jié)點所屬社區(qū)之外的所有社區(qū)之間的邊數(shù)占該節(jié)點所有連接的百分數(shù)，所以γ越小則社團內(nèi)部連接數(shù)較多，連接更為緊密，社區(qū)結(jié)構(gòu)也就更加明顯。隨著混合參數(shù)的γ的增大，與其他社團的連接數(shù)量越多，社團結(jié)構(gòu)也變得不明顯，通常認為當γ=0.5時，社團結(jié)構(gòu)已經(jīng)較難進行識別。

實驗根據(jù)Lancichinetti網(wǎng)絡的規(guī)則，構(gòu)造了γ取值范圍為0到0.5的11個測試網(wǎng)絡，對于每個測試網(wǎng)絡運行算法20次，并記錄社團劃分結(jié)果。對于社團劃分結(jié)果，使用標準互信息（Normalized Mutual Information）作為評價參數(shù)，標準互信息可以表示由算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)和真實社區(qū)結(jié)構(gòu)之間的相似性，若兩者完全一致，則標準互信息的值為1，反之，若完全不相似則為0。標準互信息公式定義為：

其中A代表真實網(wǎng)絡的社團劃分情況，CA表示真實網(wǎng)絡中社團的數(shù)量，B表示算法得出的網(wǎng)絡社團劃分情況，CB表示由算法的得到的社團數(shù)量，Ci?表示鄰接矩陣中第i行元素的和，C?j表示鄰接矩陣中第j列元素的和。若使用算法得到的社團結(jié)構(gòu)與真實網(wǎng)絡的社團結(jié)構(gòu)完全一致，則NMI（A，B）=1；反之若完全不一致則NMI（A，B）=0。實驗結(jié)果如圖1所示。

圖1顯示了γ取值不同時使用算法得出的NMI平均值的變化情況。隨著混合參數(shù)γ的增加，NMI平均值逐漸減小，當γ=0.5時NMI平均值達到最小，而在γ≤0.35時NMI平均值均為1，即說明與真實網(wǎng)絡的社團劃分結(jié)果一致。從圖1中可以看出，本文算法在混合參數(shù)γ增大的變化趨勢中，相比于其他算法NMI平均值下降速度較慢，當γ≤0.35的情況下始終可以保持與真實社團結(jié)構(gòu)一致。

3.2 真實網(wǎng)絡數(shù)據(jù)實驗

為了進一步驗證算法的有效性，使用其他三個真實網(wǎng)絡數(shù)據(jù)集來對算法進行評價：Zachery空手道俱樂部網(wǎng)絡、美國大學橄欖球網(wǎng)絡和球鼻海豚網(wǎng)絡。Zachery空手道俱樂部網(wǎng)絡是Zachery對一個空手道俱樂部觀測得到的，網(wǎng)絡中的節(jié)點代表俱樂部的成員，網(wǎng)絡中的邊數(shù)代表俱樂部成員之間的交流。網(wǎng)絡的社區(qū)劃分是分別由俱樂部管理者和俱樂部教練為核心的兩個子網(wǎng)絡。美國大學橄欖球網(wǎng)絡表示美國大學橄欖球比賽2000年賽季第一分區(qū)的比賽日程安排表，網(wǎng)絡中頂點表示球隊，連接兩個頂點的邊表示這兩個球隊之間有比賽。這些球隊被分為多個聯(lián)盟，每一個球隊平均和聯(lián)盟內(nèi)的球隊進行了7場比賽，和聯(lián)盟外的球隊進行了4場比賽，因此具有較為明顯的社區(qū)劃分結(jié)構(gòu)。球鼻海豚網(wǎng)絡是由Lusseau通過7年時間觀察生活在新西蘭Doubtful Sound的62頭海豚的行為編輯而成的社會網(wǎng)絡，該網(wǎng)絡之間的連接基于統(tǒng)計海豚之間有意義的頻繁交往而建立起來的，62個節(jié)點根據(jù)交往的頻繁程度被分為2組，即劃分為2個社區(qū)。

對于每個真實網(wǎng)絡，運行算法20次并保存社團劃分結(jié)果，表1記錄了每個真實網(wǎng)絡的社團劃分的社團數(shù)量和NMI平均值，圖2-圖4表示了社團劃分結(jié)果的圖形：

4 結(jié)論

本文針對復雜網(wǎng)絡中的社團發(fā)現(xiàn)問題，基于節(jié)點的相似度構(gòu)建了社團發(fā)現(xiàn)模型算法，通過使用人工合成網(wǎng)絡進行實驗并與其他算法進行對比，本文算法在社團結(jié)構(gòu)不明顯的情況下，仍然對社團結(jié)構(gòu)具有一定的發(fā)現(xiàn)能力，證明了算法具有一定的優(yōu)勢。而通過真實網(wǎng)絡數(shù)據(jù)的實驗驗證，證明了算法在真實的網(wǎng)絡中的有效性。

參考文獻：

[1] 劉大有，金弟，何東曉等.復雜網(wǎng)絡中的社區(qū)結(jié)構(gòu)算法綜述[J].計算機研究與發(fā)展， 2013，50（10）： 2140-2154.

[2] Watts D J，Strogatz S H.Collective dynamics of ‘small-world networks[J].nature，1998， 393（6684）： 440-442.

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

[4] 張健沛，李泓波，楊靜，等.基于拓撲勢的網(wǎng)絡社區(qū)結(jié)點重要度排序算法[J].哈爾濱工程大學學報，2012， 33（6）： 745-752.

[5] 程學旗，沈華偉.復雜網(wǎng)絡的社區(qū)結(jié)構(gòu)[J].復雜系統(tǒng)與復雜性科學，2011，8（1）： 57-70.

[6] 張健沛，李泓波，楊靜.基于歸屬不確定性的變規(guī)模網(wǎng)絡重疊社區(qū)識別[J].電子學報，2012， 40（12）： 2512.2518.

[7] 汪小帆，李翔，陳關(guān)榮.復雜網(wǎng)絡理論及其應用[M].清華大學出版社有限公司，2006.

[8] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical review E，2004，69（2）： 26-113.

[9] Fortunato S，Barthélemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences，2007，104（1）： 36-41.

[10] Lancichinetti，Andrea，Santo Fortunato，F(xiàn)ilippo Radicchi.Benchmark graphs for testing community detection algorithms[J].Physical review E，2008（4）： 46-110.