基于核心度和偏移量的社區(qū)檢測算法

辛慧英，劉向陽

(河海大學 理學院，江蘇 南京 211100)

0 引 言

在復雜網(wǎng)絡(luò)中，社區(qū)可以表示具有相似性、共同特點或關(guān)系的共同體，它具有“社區(qū)內(nèi)部節(jié)點之間連接比較緊密，與外部節(jié)點連接相對稀疏”的特點。對復雜網(wǎng)絡(luò)進行社區(qū)檢測可以清晰地認識到社區(qū)內(nèi)部的結(jié)構(gòu)及組織，明確網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，有助于獲得更多網(wǎng)絡(luò)未知區(qū)域的信息，在物理、生物、計算機科學等諸多領(lǐng)域應用廣泛。

Girvan和Newman在2002年提出了社區(qū)檢測第一算法：基于模塊度優(yōu)化的劃分算法[1](GN),該算法奠定了社區(qū)檢測研究領(lǐng)域的基石，但該算法需要多次計算節(jié)點之間的邊介數(shù)，大大增加了計算復雜度。而后，相繼提出的一些基于標簽傳播的社區(qū)檢測算法，基于信息流動的算法[2-3]，基于優(yōu)化塊模型的算法[4-5]，基于動態(tài)隨機游走的算法[6]以及基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的算法[7]都在社區(qū)檢測中得到了廣泛的應用。在一定意義上，社區(qū)檢測就是某種的聚類，這兩者的區(qū)別在于：社區(qū)檢測算法中可能存在孤立點，而聚類一般假設(shè)任意對象都是互相連接的，只是相似度不同，數(shù)據(jù)集可以表示為一張完全連通圖，如：層次，密度聚類等。但這兩個過程非常相似，因此產(chǎn)生許多將聚類算法的思想應用于社區(qū)檢測算法的例子。黃嵐等[8]通過網(wǎng)絡(luò)中節(jié)點的相似度來定義節(jié)點間的距離，將密度峰值聚類算法[9]應用于社區(qū)檢測中；文獻[10]引入箱線圖來確定核心節(jié)點，將密度峰值聚類算法應用于重疊社區(qū)檢測中；文獻[11]應用啟發(fā)式算法來劃分社區(qū)的自然結(jié)構(gòu)；郭玉全[12-13]等以兩階段盒子覆蓋法為基礎(chǔ)，進一步提出分形聚類檢測方法[14-15]，核心思想是通過兩階段盒子覆蓋法來完成分形聚類過程,并且在分形聚類過程中形成分形樹，最后通過對分形樹進行分割進而得到復雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。上述算法雖然成功將聚類算法引入到社區(qū)檢測中，但是卻由此引入一些新的參數(shù)，并且每個參數(shù)的選擇都需要大量的實驗數(shù)據(jù)來獲取，大大增加了算法的復雜度，通常只對一種或某幾種特定網(wǎng)絡(luò)的結(jié)果較好，無法適應性地對多種社區(qū)進行劃分，算法性能存在不足。

針對不依賴于大量實驗數(shù)據(jù)獲得參數(shù)的方法，文中提出一種基于偏移量和核心度的社區(qū)檢測算法。首先求出網(wǎng)絡(luò)中節(jié)點之間的距離矩陣，然后給出核心度、偏移量、核心社區(qū)的概念，并求出節(jié)點的核心度，來確定社區(qū)核心和核心社區(qū)，最后對其余節(jié)點進行分派，進而確定社區(qū)劃分結(jié)果。該方法的優(yōu)點在于，首先不需要過多的參數(shù)，不需要多次計算節(jié)點之間的邊介數(shù)，其次不僅可以給出社區(qū)劃分，而且可以很好地確定核心社區(qū)。實驗結(jié)果充分驗證了該方法的高效性和穩(wěn)定性。

1 算法思想

社區(qū)檢測算法的一個基本假設(shè)是：社區(qū)內(nèi)部節(jié)點的相似度比較高，社區(qū)間節(jié)點相似度比較低；也可以理解為:社區(qū)內(nèi)部節(jié)點間的距離比較小，社區(qū)間節(jié)點的距離比較大。基于節(jié)點間的距離求出節(jié)點的核心度，基于核心度確定社區(qū)核心，假設(shè)：(1)社區(qū)核心的核心度比它周圍鄰居節(jié)點的核心度高；(2)社區(qū)核心比其他任意核心度更高節(jié)點的相對偏移量更大。該算法不需要重復大量的計算，只需要一次計算，即可得出復雜網(wǎng)絡(luò)的社區(qū)劃分。算法流程如圖1所示。

圖1 算法流程

2 社區(qū)檢測算法

社區(qū)檢測算法基于兩種基本的思想，一種是凝聚算法(agglomerative methods)，這類算法是從一個個孤立的節(jié)點開始，計算任意兩個節(jié)點的相似度，相似度高則這兩個節(jié)點在同一個社區(qū)。另一種社區(qū)檢測的思想是分裂算法(divisive methods)，原始的輸入是一個完整的網(wǎng)絡(luò)圖，要做得就是基于節(jié)點之間邊的某些特性來刪除圖中的一些邊。要刪除的邊是基于Newman[16]提出的刪除具有最大邊介數(shù)的邊。文中具體思路的靈感來自于此，并不是要去刪除節(jié)點之間的邊，但是在最初完整的網(wǎng)路中計算邊介數(shù)作為每條邊的權(quán)重，基于完整網(wǎng)絡(luò)中每條邊的權(quán)重，計算提出的加權(quán)鄰接矩陣。

2.1 計算加權(quán)鄰接矩陣

首先計算網(wǎng)絡(luò)中每個節(jié)點的權(quán)重w，節(jié)點權(quán)重為從源點s到該節(jié)點最短路徑的數(shù)目：

(1)將初始節(jié)點s的w值設(shè)為1；

(2)每個與s相鄰的節(jié)點i的權(quán)重w也設(shè)為1；

(3)對于每一個與(2)中節(jié)點i相鄰的節(jié)點j，有如下計算規(guī)則：

(a)若j的權(quán)重還未設(shè)置，令w(j)=w(i)；

(b)若w(j)已經(jīng)存在，則令w(j)=w(i)+w(j)。

計算得到每個節(jié)點的權(quán)重之后，計算每條邊的邊介數(shù)，自底向上，對邊界的節(jié)點：即與之直接相連的邊數(shù)為1，那么設(shè)該邊介數(shù)為1；對于一個節(jié)點有多條邊與之直接相連，則邊介數(shù)為w(i)/w(j)，其中i是上方的節(jié)點。對于上層節(jié)點：其與更高一層節(jié)點連接的邊介數(shù)等于所有與之直接相鄰的子邊介數(shù)之和加1，(如果該節(jié)點只有一個與之直接相連的上層節(jié)點)，或等于所有與之直接相鄰的子邊介數(shù)之和加1乘1/n(如果該節(jié)點有n個直接與之相連的上層節(jié)點)。計算完所有邊介數(shù)，將以此作為節(jié)點間邊的權(quán)重，計算得出網(wǎng)絡(luò)的加權(quán)鄰接矩陣。

2.2 全局距離矩陣

全局距離矩陣用來描述任意節(jié)點之間的最短距離，應用廣度優(yōu)先搜索算法求出復雜網(wǎng)絡(luò)中的邊介數(shù)作為邊的權(quán)值，基于邊的權(quán)值得到復雜網(wǎng)絡(luò)的加權(quán)鄰接矩陣，計算得到任意節(jié)點間的最短路徑和最短距離。全局距離矩陣的計算步驟如下：

(1) 基于加權(quán)鄰接矩陣生成網(wǎng)絡(luò)的無向圖；

(2) 基于加權(quán)無向圖，用函數(shù)計算任意兩點的最短路徑和最短距離；

(3) 由任意兩點的最短距離構(gòu)成網(wǎng)絡(luò)的全局距離矩陣。

2.3 節(jié)點的核心度和偏移量

2014年Alex Rodriguez[9]在新聚類算法中提出了局部密度和“距離”的概念，基于此，文中提出將網(wǎng)絡(luò)中節(jié)點的核心度以及偏移量應用于復雜網(wǎng)絡(luò)的社區(qū)檢測。核心度和偏移量定義了任意節(jié)點作為社區(qū)核心的程度。

采用高斯核函數(shù)計算核心度，這樣計算不同的節(jié)點具有相同的核心度的概率更小。計算公式為：

(1)

其中，exp(.)為指數(shù)函數(shù)，dc為截斷距離，是算法中的可變參數(shù)，實驗時取網(wǎng)絡(luò)中所有節(jié)點間距離的1%～2%，dij為網(wǎng)絡(luò)中節(jié)點之間的距離。當計算得到核心度ci后，讓核心度按從大到小的順序進行排列，即{c1,c2,…,cm}。

節(jié)點的偏移量計算公式為：

(2)

即當xi的核心度最大時，δi表示網(wǎng)絡(luò)中與xi距離最大的節(jié)點到xi之間的距離；否則，δi表示在所有核心度大于xi的節(jié)點中，與xi距離最小的那個節(jié)點到xi之間的距離。

2.4 社區(qū)檢測

2.4.1 確定社區(qū)核心和核心社區(qū)

根據(jù)假設(shè)，社區(qū)核心為核心度比它周圍鄰居節(jié)點的核心度高且與任意其他核心度更高節(jié)點的偏移量相對更大的節(jié)點，由公式(1)和公式(2)，可以計算得出網(wǎng)絡(luò)中節(jié)點的核心度和偏移量，從而確定社區(qū)核心。核心社區(qū)“C”為社區(qū)中距離社區(qū)核心的距離相對比較小的節(jié)點集，確定核心社區(qū)的計算公式為：

(3)

其中，dz是核心社區(qū)內(nèi)節(jié)點距離社區(qū)核心的距離閾值，實驗中取網(wǎng)絡(luò)中所有節(jié)點間距離的50%～60%，dhi為網(wǎng)絡(luò)中節(jié)點與社區(qū)核心的距離。

2.4.2 對其他節(jié)點的處理

將其余節(jié)點按照核心度大小依次歸類到比它們核心度更大，節(jié)點之間相似性更大的節(jié)點所屬的類別。對社區(qū)邊界的節(jié)點，首先定義社區(qū)邊界區(qū)域，即分配到該社區(qū)又與其他社區(qū)節(jié)點的距離小于截斷距離的節(jié)點的集合，然后為每個社區(qū)找到其邊界區(qū)域中平均核心度的最大值，并以這個核心度作為閾值來篩選節(jié)點，對不滿足該閾值的節(jié)點，排除在該社區(qū)之外。至此，即可完成社區(qū)劃分。

3 實驗與分析

為了驗證算法的有效性、可行性和穩(wěn)定性，選取了數(shù)據(jù)集Karate、Dolphins、Football進行實驗。

3.1 實驗數(shù)據(jù)集描述

選取三個真實數(shù)據(jù)集進行實驗，數(shù)據(jù)集中的節(jié)點之間有一定的社會關(guān)系，所以這三個數(shù)據(jù)集都具有已知的社區(qū)結(jié)構(gòu)，分別為空手道數(shù)據(jù)集(Karate)、海豚數(shù)據(jù)集(Dolphins)、美國大學橄欖球數(shù)據(jù)集(Football)。Karate數(shù)據(jù)集是由34個節(jié)點和78條邊組成，其中每個空手道俱樂部成員代表一個節(jié)點，如果兩個節(jié)點之間存在邊，則表示相對應的成員之間聯(lián)系交往密切，俱樂部會長和俱樂部的教練由于一些個人原因，他們之間存在一些分歧，所以最終俱樂部成員們形成了兩個小團體(俱樂部)。Dolphins數(shù)據(jù)集是由62個節(jié)點和159條邊組成，每只生活在新西蘭Doubtful Sound海峽的寬吻海豚代表一個節(jié)點，如果兩個節(jié)點之間存在邊，那么代表對應的兩只海豚有非常多的交流，經(jīng)過很長一段時間的跟蹤觀察及記錄，發(fā)現(xiàn)可以將這些海豚分為兩個社區(qū)，但是更仔細觀察分類，它們可以被分為5個社區(qū)。Football數(shù)據(jù)集是由115個節(jié)點和609條邊組成，每支參加2000年美國大學秋季學期橄欖球賽的球隊代表一個節(jié)點，如果兩支球隊曾經(jīng)有過一場比賽，則表示兩個節(jié)點之間存在邊。這些球隊隸屬于12個不同的球會，且在球會內(nèi)部進行的比賽比較多。

3.2 實驗結(jié)果和分析

將文中算法在三個真實數(shù)據(jù)集上進行實驗，圖2～圖5為文中算法在Karate、Dolphins數(shù)據(jù)集上的劃分結(jié)果以及帶有核心社區(qū)的社區(qū)劃分結(jié)果，此時都取dz為網(wǎng)絡(luò)中所有節(jié)點間距離的59%。圖6為Dolphins數(shù)據(jù)集更仔細地被劃分為5個社區(qū)的情況。圖7為文中算法在Football數(shù)據(jù)集上的劃分結(jié)果。

圖2、圖3表明，文中算法幾乎完美地將Karate數(shù)據(jù)集的34個節(jié)點分為兩個社區(qū)，只有一個節(jié)點(Karate數(shù)據(jù)集中的3號節(jié)點)被錯誤地分類，但該節(jié)點是在群體之間的邊界上，所以可能是一個模糊的情況，是可以理解的。文中算法可以找出核心社區(qū)，在圖3中，標簽為3的節(jié)點和標簽為4的節(jié)點分別為兩個社區(qū)的核心社區(qū)，這些節(jié)點在網(wǎng)絡(luò)中占據(jù)重要的地位，發(fā)現(xiàn)并準確定位這些節(jié)點將有很大的現(xiàn)實意義。

圖2 Karate數(shù)據(jù)集社區(qū)劃分結(jié)果

圖3 Karate數(shù)據(jù)集帶有核心社區(qū)的社區(qū)劃分結(jié)果

圖4～圖6表明，文中算法可以準確將Dolphins數(shù)據(jù)集劃分為2個社區(qū)，社區(qū)間有明顯的界限，并且進一步劃分，Dolphins數(shù)據(jù)集可以被劃分為5個社區(qū)。文中算法可以找出核心社區(qū)，在圖5中，標簽為3的節(jié)點和標簽為4的節(jié)點分別為兩個社區(qū)的核心社區(qū)。

圖4 Dolphins數(shù)據(jù)集社區(qū)劃分結(jié)果

圖5 Dolphins數(shù)據(jù)集帶有核心社區(qū)的社區(qū)劃分結(jié)果

圖6 Dolphins數(shù)據(jù)集社區(qū)劃分結(jié)果

圖7 Football數(shù)據(jù)集社區(qū)劃分結(jié)果

圖7表明，文中算法將Football數(shù)據(jù)集中115個節(jié)點分為12個社區(qū)，圖7中不同的節(jié)點標簽分別代表不同的社區(qū)?？梢钥闯?，文中算法發(fā)現(xiàn)的社區(qū)數(shù)目與真實的社區(qū)數(shù)目相同，并且可視化效果良好，只有少數(shù)幾個節(jié)點游離在社區(qū)之間。

4 結(jié)束語

提出一種基于節(jié)點核心度和偏移量進行社區(qū)檢測的算法，在三個真實數(shù)據(jù)集上的實驗結(jié)果表明，該算法簡潔、高效、準確，算法運行良好，不僅可以準確地對數(shù)據(jù)集Karate、Dolphins、Football進行社區(qū)檢測，而且可以找到核心社區(qū)。相比于一般的社區(qū)發(fā)現(xiàn)算法只能發(fā)現(xiàn)社區(qū)的一般整體劃分，該算法可以檢測出社區(qū)核心和核心社區(qū)，基于大多數(shù)網(wǎng)絡(luò)具有拓撲結(jié)構(gòu)的特性，核心社區(qū)的發(fā)現(xiàn)具有很好的現(xiàn)實意義，未來將嘗試應用于更加復雜的網(wǎng)絡(luò)。