張若昕　柴丹煒　熊小峰　劉建生　樂光學(xué)

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

2.1 相似度的定義

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

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

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

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

2.2 模塊密度定義

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

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

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

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

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

2.3 算法描述

算法流程描述如下：

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證及分析

3.1 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)

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

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

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

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

3.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)

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

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

4 結(jié)論

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

參考文獻(xiàn)：

[1] 劉大有，金弟，何東曉等.復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)算法綜述[J].計(jì)算機(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] 張健沛，李泓波，楊靜，等.基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)結(jié)點(diǎn)重要度排序算法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2012， 33（6）： 745-752.

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

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

[7] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].清華大學(xué)出版社有限公司，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.