基于節(jié)點(diǎn)相似度的社團(tuán)劃分方法研究?

甘立強(qiáng) 王旭陽 燕 楠 王 嵐

（1.中國科學(xué)院深圳先進(jìn)技術(shù)研究院中國科學(xué)院人機(jī)智能協(xié)同系統(tǒng)重點(diǎn)實(shí)驗(yàn)室 深圳 518055）（2.蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院 蘭州 730050）

1 引言

近年來復(fù)雜網(wǎng)絡(luò)已經(jīng)得到了廣泛的應(yīng)用，如萬維網(wǎng)、社會網(wǎng)、蛋白質(zhì)交互網(wǎng)以及科學(xué)家合作關(guān)系網(wǎng)等。這些網(wǎng)絡(luò)具有較高的復(fù)雜性，因此被稱為“復(fù)雜網(wǎng)絡(luò)”［1］。復(fù)雜網(wǎng)絡(luò)已經(jīng)成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一［2］。隨著對復(fù)雜網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多復(fù)雜網(wǎng)絡(luò)都具有一個共同的性質(zhì)，即社團(tuán)結(jié)構(gòu)［3］。社團(tuán)內(nèi)部各節(jié)點(diǎn)之間連接緊密，而不同社團(tuán)節(jié)點(diǎn)之間連接稀疏。社團(tuán)結(jié)構(gòu)分析在生物學(xué)、物理學(xué)、計(jì)算機(jī)圖形學(xué)和社會學(xué)等領(lǐng)域內(nèi)有著廣泛的應(yīng)用。

目前，學(xué)者們已經(jīng)提出了很多有效的社團(tuán)檢測方法，比如基于分裂思想的GN算法［4］，自包含GN算法［5］、基于相異性的分裂算法［6］。該類算法劃分效果較好，但是時間復(fù)雜度太高，不適合在大型網(wǎng)絡(luò)中使用，隨后學(xué)者們根據(jù)上述缺點(diǎn)提出了基于凝聚 思 想 的 Newman 快 速 算 法［7］、CNM 算 法［8］、MSG-VM［9］，但是這些算法容易將過多的節(jié)點(diǎn)劃分到同一社團(tuán)，導(dǎo)致社團(tuán)過大，與真實(shí)網(wǎng)絡(luò)的劃分情況不相符。因此，針對這些缺點(diǎn)學(xué)者們又相繼提出了 LPAm 算法［10］、SYM［11］、CHM［12］、ILM［13］等，這些算法同樣存在很多問題，諸如LPAm算法的穩(wěn)定性不高，時間復(fù)雜度雖然較小，但是不容易得到最優(yōu)結(jié)果，CHM算法空間復(fù)雜度高，需要較大的內(nèi)存空間，不適合大型網(wǎng)絡(luò)，ILM算法參數(shù)選擇困難，算法穩(wěn)定性差等。

針對上述存在的問題，通過比較研究各種網(wǎng)絡(luò)節(jié)點(diǎn)相似度的構(gòu)造方法，通過綜合考慮網(wǎng)絡(luò)的局部信息和全局信息，設(shè)計(jì)了新的構(gòu)造節(jié)點(diǎn)相似度的方法，進(jìn)而提出了基于節(jié)點(diǎn)相似度的社團(tuán)劃分算法。該算法在不需要知道任何關(guān)于網(wǎng)絡(luò)的先驗(yàn)知識的情況下，仍然取得了較好的劃分結(jié)果。

2 基本概念

2.1 節(jié)點(diǎn)相似度

構(gòu)造節(jié)點(diǎn)相似度方法目前主要是基于網(wǎng)絡(luò)的局部信息［14］，比如 Salto［15］、Jaccard［16］、Hub Pr-omot?ed［17］、Leicht-Holme-Newman［18］、RA［19］等。其中 RA方法是目前效果最好的節(jié)點(diǎn)相似度的構(gòu)造方法［19］。

RA方法是通過模擬網(wǎng)絡(luò)中資源的分配過程來衡量兩個節(jié)點(diǎn)的相似度。假設(shè)有一個節(jié)點(diǎn)對（i，j），節(jié)點(diǎn) j通過它們的共同鄰居節(jié)點(diǎn)作為中介間接地向節(jié)點(diǎn)i發(fā)送一定資源。同時規(guī)定每個中介能擁有的資源是一定的。因此每個中介發(fā)送給節(jié)點(diǎn)i的資源取決于它的度。資源分配過程如圖1，我們可以把節(jié)點(diǎn)i收到節(jié)點(diǎn) j發(fā)送的資源的多少定義為節(jié)點(diǎn)i和節(jié)點(diǎn) j的相似度：

其中，Γ(i)代表節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的集合，z∈Γ(i)∩Γ(j)代表節(jié)點(diǎn)i和節(jié)點(diǎn) j共同鄰居節(jié)點(diǎn)的集合，k(z)代表節(jié)點(diǎn)z的度。

但是這種只是依靠網(wǎng)絡(luò)的局部信息作為衡量相似度的標(biāo)準(zhǔn)容易過度追求局部最優(yōu)，忽視了網(wǎng)絡(luò)整體的結(jié)構(gòu)，造成與實(shí)際網(wǎng)絡(luò)不符的情況，例如將RA算法應(yīng)用在經(jīng)典的Zachary空手道俱樂部網(wǎng)絡(luò)中，按照式（1）計(jì)算節(jié)點(diǎn)之間的相似度，發(fā)現(xiàn)節(jié)點(diǎn)3對應(yīng)的最大相似度節(jié)點(diǎn)是節(jié)點(diǎn)34，應(yīng)該被分到同一個社團(tuán)中，但是現(xiàn)實(shí)網(wǎng)絡(luò)中它們被分到了以教練和主管為首的兩個社團(tuán)中。所以劃分社團(tuán)中應(yīng)該考慮網(wǎng)絡(luò)的全局拓?fù)湫畔ⅰＨ绻麅蓚€節(jié)點(diǎn)的距離越近，即它們之間的最短路徑越短，這兩個節(jié)點(diǎn)同屬于一個社團(tuán)的機(jī)會就越大，反之，則它們屬于一個社團(tuán)的機(jī)會就越?。?0］。因此綜合兩個節(jié)點(diǎn)間共同鄰居的網(wǎng)絡(luò)局部信息和節(jié)點(diǎn)間最短路徑的網(wǎng)絡(luò)全局信息，本文重新定義了節(jié)點(diǎn)相似度Sim(i，j)：

其中d(i，j)表示節(jié)點(diǎn)i和節(jié)點(diǎn) j之間最短路徑長度，n代表網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目，節(jié)點(diǎn)i，j可達(dá)是指節(jié)點(diǎn)i，j之間存在路徑將其連通。當(dāng)d(i，j)越小時，1 d(i，j)越大，則 Sim(i，j)就越大，兩個節(jié)點(diǎn)越相似。同時如果兩個節(jié)點(diǎn)之間沒有可以到達(dá)的路徑，這說明這兩個節(jié)點(diǎn)之間的資源交換主要依靠鄰居節(jié)點(diǎn)，相對于直接相連的節(jié)點(diǎn)，交換的資源較少，可以忽略。因此我們把相似度設(shè)置為0。因?yàn)镾i，j本身很小，再除以d(i，j)結(jié)果可能小到超出計(jì)算機(jī)的表示范圍，就會出現(xiàn)浮點(diǎn)數(shù)下溢出的情況，將該運(yùn)算結(jié)果處理成機(jī)器零，這時就無法對相似度進(jìn)行比較。所以乘以n對結(jié)果進(jìn)行適當(dāng)?shù)姆糯?，防止這種情況發(fā)生。

圖1 網(wǎng)絡(luò)資源流動過程圖

2.2 模塊度和準(zhǔn)確率

社團(tuán)模塊度［20］是Newman等引進(jìn)的一個衡量網(wǎng)絡(luò)劃分質(zhì)量的度量標(biāo)準(zhǔn)。假設(shè)有某種劃分形式，將網(wǎng)絡(luò)劃分為k個社團(tuán)，定義一個k×k維的對稱矩陣E=(eij)，其中eij表示網(wǎng)絡(luò)中連接兩個不同社團(tuán)的節(jié)點(diǎn)的邊在所有邊中所占的比例，這兩個節(jié)點(diǎn)分別位于第i和第 j個社團(tuán)。模塊度Q可表示為

3 基于節(jié)點(diǎn)相似度的社團(tuán)劃分方法

3.1 基本思想

兩個節(jié)點(diǎn)的相似度越大，屬于同一個社團(tuán)的概率越大［21］，根據(jù)這一思想，本算法利用節(jié)點(diǎn)之間的相似性，判斷兩個節(jié)點(diǎn)是否屬于同一個社團(tuán)。

對于一個含有n個節(jié)點(diǎn)的網(wǎng)絡(luò)，首先根據(jù)式（2）計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)對的相似度。由此我們可以得到一個 n×n的矩陣 Sim(n，n)=[ ]Sim(i，j) 。Sim(i，j)代表的是兩個節(jié)點(diǎn)之間的相似度。為了方便處理數(shù)據(jù)，我們把這個矩陣的每一行用鏈表存起來，頭節(jié)點(diǎn)保存節(jié)點(diǎn)i，頭節(jié)點(diǎn)的next節(jié)點(diǎn)保存節(jié)點(diǎn)i對應(yīng)的相似度最大的節(jié)點(diǎn) j。如果有多個相似度相同的節(jié)點(diǎn)，則把它們都保存起來。算法具體步驟：

1）首先將每個節(jié)點(diǎn)看作是一個社團(tuán)，選擇任意一個節(jié)點(diǎn)作為初始節(jié)點(diǎn)；

2）然后從剩余的節(jié)點(diǎn)中選擇和這個節(jié)點(diǎn)相似度最大的節(jié)點(diǎn)，將它們合并成一個新的社團(tuán)；

3）最后再將新加入的節(jié)點(diǎn)作為初始節(jié)點(diǎn)，尋找和它相似度最大的節(jié)點(diǎn)。如果找到的這個節(jié)點(diǎn)不在當(dāng)前的社團(tuán)中，則把這個節(jié)點(diǎn)合并到當(dāng)前社團(tuán)，如果在的話，就隨機(jī)從剩余未處理的節(jié)點(diǎn)中選擇一個作為初始節(jié)點(diǎn)，回到2）；

4）重復(fù)執(zhí)行步驟2）和3），直到處理完所有的節(jié)點(diǎn)。

為了更清楚地表達(dá)本文算法的思想，我們構(gòu)建了一個含有8個節(jié)點(diǎn)的小網(wǎng)絡(luò)（如圖2）。

首先計(jì)算每個節(jié)點(diǎn)和它鄰居節(jié)點(diǎn)的節(jié)點(diǎn)相似度，然后找出每個節(jié)點(diǎn)以及它對應(yīng)的相似度最大的節(jié)點(diǎn)（結(jié)果如表1）。

圖2 示例網(wǎng)絡(luò)

表1 對應(yīng)的最大相似度節(jié)點(diǎn)列表

然后隨機(jī)地選擇一個節(jié)點(diǎn)，用帶箭頭的線段將當(dāng)前節(jié)點(diǎn)和對應(yīng)的相似度最大的節(jié)點(diǎn)連接起來，箭頭指向的是對應(yīng)的相似度最大的節(jié)點(diǎn)。同時，線段兩端的節(jié)點(diǎn)合并到同一個網(wǎng)絡(luò)。等到標(biāo)記完網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，劃分過程結(jié)束，得到最后的劃分結(jié)果（如圖3）。

圖3 本文算法劃分結(jié)果

針對上述步驟，有一種特殊情況需要說明，如果一個節(jié)點(diǎn)和它所有的鄰居節(jié)點(diǎn)都沒有共同的鄰居節(jié)點(diǎn)，則這個節(jié)點(diǎn)和其它所有節(jié)點(diǎn)的相似度都等于0，因此按照上述算法無法完成劃分，這種情況下我們把這個節(jié)點(diǎn)劃分到它鄰居節(jié)點(diǎn)中度最大的那個節(jié)點(diǎn)所在的社團(tuán)中。因?yàn)橐粋€節(jié)點(diǎn)的度越大，它就越重要，新來的節(jié)點(diǎn)就傾向于和這個節(jié)點(diǎn)靠攏［22］。同時為了進(jìn)一步提高劃分社團(tuán)的準(zhǔn)確率，我們引進(jìn)一個相似度閾值ε，當(dāng)一個節(jié)點(diǎn)和它所有鄰居節(jié)點(diǎn)的最大相似度小于ε時，我們就把這個具有最大相似度的節(jié)點(diǎn)劃分到它所有鄰居節(jié)點(diǎn)中度最大節(jié)點(diǎn)所在的社團(tuán)中，因?yàn)槿绻嗨贫群苄?，依然使用?jié)點(diǎn)的這個屬性作為劃分標(biāo)準(zhǔn)的話，容易過擬合。針對不同的網(wǎng)絡(luò)這個ε也不同，我們可以通過調(diào)整ε的值來獲得更好的劃分效果。

3.2 算法性能分析

本算法需要時間的步驟主要包括三部分：計(jì)算節(jié)點(diǎn)相似度，尋找下一個需要處理的節(jié)點(diǎn)，合并社團(tuán)。由于下一個要處理的節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)對應(yīng)的相似度最大的節(jié)點(diǎn)，并且之前我們已經(jīng)把這兩個節(jié)點(diǎn)存在一個以當(dāng)前節(jié)點(diǎn)為頭節(jié)點(diǎn)的鏈表中，因此可以直接獲取到下一個需要處理的節(jié)點(diǎn)，因此這部分的計(jì)算時間可以忽略。計(jì)算節(jié)點(diǎn)相似度只需要知道它最近的鄰居節(jié)點(diǎn)的信息，因此計(jì)算量非常小。計(jì)算式（2）的時間復(fù)雜度是O()1，計(jì)算一個節(jié)點(diǎn)和它的k個鄰居節(jié)點(diǎn)相似度的時間復(fù)雜度就是O(k)，k是網(wǎng)絡(luò)中節(jié)點(diǎn)的平均的度。因此計(jì)算有n個節(jié)點(diǎn)的網(wǎng)絡(luò)所需要的時間復(fù)雜度為O(kn)。合并一個節(jié)點(diǎn)和它相似度的節(jié)點(diǎn)所需要的時間復(fù)雜度明顯的是O(1)。所以將網(wǎng)絡(luò)中所有n個節(jié)點(diǎn)都合并花費(fèi)的時間復(fù)雜度是O(n)。使用Dijkstra算法計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最短路徑的時間復(fù)雜度為O(n2)，所以算法時間復(fù)雜度為O(k+n)n≈O(n2)(k＜＜n)。而CHM、ILM算法的時間復(fù)雜度也同樣為O(n2)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 Zachary空手道俱樂部網(wǎng)絡(luò)

空手道俱樂部網(wǎng)絡(luò)是描述美國一所大學(xué)里空手道俱樂部里俱樂部成員之間關(guān)系的網(wǎng)絡(luò)［23］，該網(wǎng)絡(luò)由Zachary耗時兩年研究出來的。此網(wǎng)絡(luò)含有34個節(jié)點(diǎn)和78條邊，節(jié)點(diǎn)表示俱樂部中的成員，邊表示俱樂部成員之間的關(guān)系。通過研究發(fā)現(xiàn)，由于俱樂部主管JohnA（node 34）和俱樂部教練員Mr.Hi（node 1）之間產(chǎn)生分歧，俱樂部被劃分成了以主管和教練為首的兩個團(tuán)體。首先通過式（2）計(jì)算每個節(jié)點(diǎn)的和鄰居節(jié)點(diǎn)的相似度，然后找出最大相似度的節(jié)點(diǎn)，結(jié)果如表2。然后用本文算法對其進(jìn)行劃分，圖4描述了此次劃分的過程（ε=0.88）。由結(jié)果可以看出本文算法劃分的結(jié)果與現(xiàn)實(shí)中的劃分結(jié)果一致。

表2 Zachary網(wǎng)絡(luò)中對應(yīng)的最大相似度節(jié)點(diǎn)列表

圖4 Zachary網(wǎng)絡(luò)的劃分過程

表3表示將本文算法與Newman快速算法和CNM算法進(jìn)行比較，通過結(jié)果可以看出本文算法模塊度更大，準(zhǔn)確率更高，因此本文算法更適合劃分Zachary空手道俱樂部網(wǎng)絡(luò)。

表3 不同算法的性能比較

4.2 美國大學(xué)足球賽網(wǎng)絡(luò)

美國大學(xué)足球賽網(wǎng)絡(luò)［24］由115個節(jié)點(diǎn)613條邊組成。每個節(jié)點(diǎn)代表一支球隊(duì)，每條邊代表端點(diǎn)上的兩支隊(duì)伍進(jìn)行過比賽。這些球隊(duì)被劃分成若干個小組，每個小組有8～12名球員，同組內(nèi)球隊(duì)進(jìn)行比賽的次數(shù)要比組間球隊(duì)之間比賽的次數(shù)多。如圖5（ε=0.7）所示本文算法將網(wǎng)絡(luò)劃分11個社團(tuán)，其中7個社團(tuán)和現(xiàn)實(shí)網(wǎng)絡(luò)中的社團(tuán)一致，但是CNM算法只劃分出7個社團(tuán)，其中劃分完全正確的社團(tuán)只有4個。所以本文提出的算法劃分社團(tuán)的準(zhǔn)確率更高。表4表示的是本文算法與Newman快速和CNM算法的從模塊度和準(zhǔn)確率上對比的結(jié)果，從數(shù)據(jù)上看，本文算法要優(yōu)于Newman快速算法和CNM算法。

圖5 美國大學(xué)足球賽網(wǎng)絡(luò)

表4 不同算法性能比較

4.3 海豚社會網(wǎng)絡(luò)

Lusseau等在新西蘭對62只寬吻海豚的生活習(xí)性進(jìn)行了長時間的觀察，他們研究發(fā)現(xiàn)這些海豚的交往呈現(xiàn)出特定的模式，并構(gòu)造了包含有62個結(jié)點(diǎn)的社會網(wǎng)絡(luò)［25］。如果某兩只海豚經(jīng)常一起頻繁活動，那么網(wǎng)絡(luò)中相應(yīng)的兩個結(jié)點(diǎn)之間就會有一條邊存在。利用本算法劃分的結(jié)果如圖6（ε=0.75）所示。從圖6可以看出，本文算法劃分的結(jié)果與現(xiàn)實(shí)中的劃分較為符合。

圖6 海豚社會網(wǎng)絡(luò)

5 結(jié)語

目前節(jié)點(diǎn)相似度的構(gòu)造方法大多數(shù)是基于網(wǎng)絡(luò)的局部信息，使用這種構(gòu)造方法的節(jié)點(diǎn)相似度容易使算法陷入局部最優(yōu)，使得劃分結(jié)果和真實(shí)網(wǎng)絡(luò)差異較大，針對這一缺點(diǎn)，本文綜合網(wǎng)絡(luò)局部信息和全局信息，重新定義了節(jié)點(diǎn)相似度，并設(shè)計(jì)了基于凝聚思想的劃分算法，通過與CHM算法、ILM算法的對比，在時間復(fù)雜度相當(dāng)?shù)那闆r下，經(jīng)過仿真實(shí)驗(yàn)證明，本文算法可以更好地對復(fù)雜網(wǎng)絡(luò)進(jìn)行劃分。因此，可以將本文算法用于復(fù)雜網(wǎng)絡(luò)中的社團(tuán)劃分。

［1］駱志剛，丁凡，蔣曉舟.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展［J］.國防科技大學(xué)學(xué)報，2011，33（1）：47-52.

LUO Zhigang，DING Fan，JANG Xiaozhou.New Progress on Community Detection in Complex Networks［J］.Journal of National University of Defense Technology，2011，33（1）：47-52.

XIE Zhou，WANG Xiaofan.An Overview of Algorithm for Analyzing Community Structure in Complex Networks［J］.Complex Systems and Complexity Science，2005，2（3）：1-12.

［3］Chen Y，Wang X，Bu J，et al.Network structure explora?tion in networks with node attributes［J］.Physica A：Sta?tistical Mechanics and its Applications，2016，449：240-253.

［4］Guimera R，Danon L，Diaz-Guilera A，et al.Self-similar community structure in a network of human interactions［J］.Physical review E，2003，68（6）：065103.

［5］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.

［6］Zhou H.Distance，dissimilarity index，and network com?munity structure［J］.Physical review e，2003，67（6）：061901.

［7］Newman M E J.Detecting community structure in networks［J］.European Physical Journal B，2004，38（2）：321-330.

［8］Clauset A.Finding local community structure in networks［J］.Physical Review E，2005，72（2）：26-132.

［9］Schuetz P，Caflisch A.Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement［J］.Physical Review E，2008，77（4）：046112.

［10］Frey B J，Dueck D.Clustering by passing messages be?tween data points［J］.Science，2007，315：972-976.

［11］Symeonidis P，Tiakas E，Manolopoulos Y.Transitive node similarity for link prediction in social networks with positive and negative links［C］//Pro-cedings of the fourth ACM conference on Recommendersystems.ACM，2010：183-190.

［12］H.Chen，L.Guo，X.L.Zhang，C.L.Giles，Proceedings of the 27th Annual ACM Symposium on Applied Comput?ing［J］.2012，1：138-143.

［13］Li Y，Luo P，Wu C.Information loss method to measure node similarity in networks［J］.Physica A：Statistical Mechanics and its Applications，2014，410：439-449.

［14］Chen Z，Xie Z，Zhang Q.Community detection based on local topological information and its application in power grid［J］.Neurocomputing，2015，170：384-392.

［15］Salton G，McGill M J.Introduction to modern informa?tion retrieval［J］.1986.

［16］Jaccard P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura［M］.Impr.Corbaz，1901.

［17］Ravasz E，Somera A L，Mongru D A，et al.Hierarchical organization of modularity in metabolic networks［J］.sci?ence，2002，297（5586）：1551-1555.

［18］Leicht E A，Holme P，Newman M E J.Vertex similarity in networks［J］.Physical Review E，2006，73（2）：026120.

［19］Zhou T，Lü L，Zhang Y C.Predicting missing links via local information［J］.The European Physical Journal B-Condensed Matter and Complex Systems，2009，71（4）：623-630.

［20］Liu J G，Zhou T，Che H A，et al.Effects of high-order correlations on personalized recommendations for bipar?tite networks［J］.Physica A：Statistical Mechanics and its Applications，2010，389（4）：881-886.

［21］Symeonidis P，Tiakas E，Manolopoulos Y.Transitive node similarity for link prediction in social networks with positive and negative links［C］//Proceedings of the fourth ACM conference on Recommender systems.ACM，2010：183-190.

［22］Barabási A L，Albert R.Emergence of scalling in ran?dom networks［J］.Science，1999，286（5439）：509-512.

［23］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of anthropological re?search，1977，33（4）：452-473.

［24］Girvan M，Newman M E J.Community structure in so?cial and biological networks［J］.Proceedings of the na?tional academy of sciences，2002，99（12）：7821-7826.

［25］Barabási A L，Albert R.Emergence of scaling in random networks［J］.science，1999，286（5439）：509-512.