基于LRWD輪廓系數的社團檢測新方法

孟 雪，許 英

(新疆財經大學 統計與數據科學學院，烏魯木齊 830012)

社團檢測技術廣泛應用于社會網絡、引用網絡、食品網絡、生物網絡等多個領域[1]。 在社團中，人們通常理解節(jié)點的子集與網絡的其余部分之間的互連更為緊密。利用生物學、物理學、社會科 學、應用數學和計算機科學等不同學科的技術和工具，開發(fā)了許多社團檢測算法[2]。 在文獻[3]中，Newman和Girvan引入了模塊度函數Q，通過模塊度函數Q，使我們找出網絡分解到社團的最佳方式社團。

本文提出了一種基于局部隨機游走距離輪廓系數的網絡社團檢測新算法(Silhouette算法，簡記為SIL算法)，并給出一個新的定量函數平均輪廓來評估質量網絡社團結構。 同時，通過四個現實世界網絡和計算機生成網絡(Girvan和Newman[3]提出的GN基準和Lancichineti Andrea等人[4]對GN Benchmark的缺陷提出的LFR基準)進行了測試。 實驗結果表明，SIL算法能夠以較高的NMI(Normalized Mutual Information)值、模塊度和平均輪廓值準確有效地檢測網絡的社團結構。

1 算法架構

1.1 局部隨機游走距離

給定無向無權網絡G=(V，E)，其中V是節(jié)點集合，E是邊集合。隨機游走是一個重要的隨機過程，它可以表示隨機游走者經過的一系列節(jié)點。轉移概率矩陣P，其中Pij=aij/kj代表在隨機游走者i在下一步步行到j的概率。其中A=(aij)是網絡的鄰接矩陣，ki表示節(jié)點的i的度，與其他基于隨機游走的距離度量相比，具有較低的時間復雜度。

給定隨機游走者i開始，在t步驟之后，該游走者到達j的概率可以用πij(t)表示。這個系統的演變方程可表示為πi(t)=PTπ(t-1)，其初始系統狀態(tài)為πi(0)=ei，第i個位置為1其他為0.隨機游走者訪問t步后，LRW(Local Random Walk)指數可以定義如下：

(1)

其中|E|是網絡的邊數。

SRW(Superposed Random Walk)度量是LRW在t步時間內的疊加，描述了隨機游走者從起始節(jié)點連續(xù)釋放，定義為：

(2)

節(jié)點i與節(jié)點j之間的局部隨機游走距離(LRWD)定義如下：

(3)

因此網絡的距離矩陣D=(dij)可以根據上述公式計算。以下實驗將網絡的直徑設置為隨機步長t，通常是小于n.

1.2 輪廓系數

基于上述局部隨機行走距離構造輪廓系數[4]，對于每個節(jié)點，將引入一個確定的值s(i)，稱為輪廓系數。

將網絡G劃分為{C1，C2，C3，…，Ck}，其中k是社團的數量。對于網絡中的任何節(jié)點i，并用gi表示它被分配到的社團。考慮a(i)為節(jié)點i和與i同一社團中的其他節(jié)點之間的平均距離，這是“內部”距離。

(4)

對于所有其他社團Cl，d(i，Cl)是i與Cl中其他節(jié)點之間的平均距離，即“之間”距離。

(5)

在計算了所有社團Cl≠gi的d(i，Cl)之后，選擇d(i，Cl)的最小值，通過：

(6)

是節(jié)點i與最近社團之間的距離。達到這個最小值的社團B(即d(i，B)=b(i))，稱之為節(jié)點i的次優(yōu)選擇社團。 因此，了解網絡中每個節(jié)點的次優(yōu)選擇社團是非常重要的。

輪廓系數s(i)定義為:

(7)

當社團gi只有一個不清楚如何定義的節(jié)點a(i)，簡單地設置s(i)等于零，-1≤s(i)≤1.

(8)

1.3 算法

從上述輪廓系數和平均輪廓的定義可以看出，對于網絡的任何社團結構，都可以用輪廓來判斷節(jié)點是否分類正確。如果一個節(jié)點被錯誤分類，那么可以將這個節(jié)點重新分類為次優(yōu)選擇社團，這將是一個新的網絡社團結構?；谶@一觀點，提出以下算法：

算法：基于LRWD輪廓的社團檢測算法

輸入：網絡G=(V，E)，|V|=n

輸出：網絡的社團結構

步驟1.根據局部隨機游走計算距離矩陣;

步驟2.使用密度峰值方法選擇社團中心;

節(jié)點i與密度較高的任何其他節(jié)點之間的最小距離

(9)

請注意，δi和ρi值異常大的節(jié)點為社團中心;

步驟3.計算除社團中心以外的每個節(jié)點V到社團中心的距離，將節(jié)點劃分給距離最小的社團;

步驟4.使用輪廓系數調整社團。對于網絡的點v，如果點v的輪廓系數s(v)滿足s(v)<0，則將點v分配給次優(yōu)選擇社團，否則，保持點v在原來的社團;

步驟5.重復步驟4，直到網絡的社團結構不再改變。(當改變很小時，或者在最大的迭代次數之后，停止重復)

1.4 復雜度

SIL算法的時間復雜度O(n2)+O(nkt)，在第一部分中，選擇社團中心的時間復雜度為O(n2)；在第二部分中，根據距離將每個節(jié)點分配給社團的時間復雜度為O(nk)，O(nkt)是基于輪廓系數更新社團結構的后續(xù)迭代過程的時間復雜度，其中k是社團中心的數目，t是迭代時間。

2 應用

本節(jié)使用三個真實世界網絡和計算機生成網絡以評估所提出算法的性能。 使用的真實世界網絡包括空手道俱樂部網絡、海豚絡和NCAA足球網絡。

2.1 真實網絡檢測

A.空手道俱樂部網絡

空手道俱樂部網絡由34個節(jié)點和78條邊組成，該網絡被分成兩個社團。根據密度峰值方法選擇k=2,3,4個社團中心(圖1(b))，利用SIL算法對網絡進行劃分，不同k的平均輪廓值為:

(10)

根據平均輪廓的含義，空手道網絡分為2個社團是最佳選擇。在圖1(a)中，采用該算法檢測空手道網絡的社團結構與實際社團結構相同。

圖1 空手道俱樂部網絡社團結構部分

B.海豚網絡

海豚網絡由62個節(jié)點和159條邊組成，該網絡具有兩個社團。我們根據密度峰值方法選擇了k=2，3，4個社團中心(圖2(b))利用SIL算法進行網絡劃分，不同k的平均輪廓值是:

圖2 海豚網絡社團結構劃分

(11)

顯然，海豚網絡的最佳社團數量是k=2.圖2(b)中，實際社團數字1和2的數字，該算法識別了兩個顏色不同的社團，與實際的兩個社團是相同的。

C．NCAA足球網絡(National Collegiate Athletic Association)

D．NCAA足球網絡由115個節(jié)點和613條邊組成,該網絡被分成十二個社團。利用SIL算法對不同數量的社團k=8，9，10，11，12進行社團劃分，并計算平均輪廓系數

(12)

圖3 足球網絡社團結構劃分

根據表1和表2，在這三個現實世界的網絡中，模塊度函數的值并不是最大的，但是在實際社團劃分的歸一化互信息表明，本文的算法可以檢測到更真實的社團結構。所提出的算法，三個網絡的平均輪廓要比其他三個算法大，更接近網絡的真實社團結構。

表1 三個真實世界網絡在四種算法下的NMI值和社團數k

表2 三個真實世界網絡在四種算法下的Q值和平均輪廓值

2.2 計算機生成網絡檢測

A.GN基準

Girvan和Newman[3]給出128個節(jié)點計算機生成的網絡，稱為GN人工網絡。網絡由128個節(jié)點組成，分別屬于4個大小相等的社團，每個社團包含32個節(jié)點。每個節(jié)點的平均度〈k〉為16，并且邊被獨立隨機放置在節(jié)點對之間，其概率取決于兩個節(jié)點是否屬于同一個社團。每個節(jié)點都有與同一個社團中的其他節(jié)點連接的平均連接邊kin，以及社團之間的邊kout，并且kin+kout=16.隨著kout從零的增長，網絡中的社團變得越來越難以發(fā)現。

圖4(a)可以看到，四種算法的社團檢測結果NMI，當kout<8時，該算法有利于發(fā)現合理的社團。當kout=8時，注意到FG和LE算法不能發(fā)現合理的社團，本文的算法比LE和FG表現更好，但比SP差。當kout>8時，在GN網絡中，社團結構不合理，因此所有算法都無法發(fā)現社團結構。如圖4所示，當kout<8時，圖4(b)(c)，所提出的算法SIL的模塊度和平均輪廓是四種算法中最大的。

圖4 GN網絡中不同算法NMI、模塊度平均輪廓比較

B.LFR基準

根據LFR基準，通過設置不同的冪律分布規(guī)則來生成的網絡，這些網絡更接近現實的網絡。為了驗證LFR準則的SIL算法的效率，設置不同的參數，生成了五個不同規(guī)模的網絡，節(jié)點N=100～1 000.

根據表3，在某些LFR基準中，SIL算法得到的社團結果比FG，LE和SP算法得到的社團更準確，SIL算法可以有效地得到由LFR基準生成的不同規(guī)模測試網絡中的社團。

表3 LFR網絡在四種算法下的NMI值、模塊度值和平均輪廓

3 結論

本文提出了一種基于局部隨機游走輪廓系數的社團結構檢測算法(SIL算法。 將SIL算法在三個真實世界網絡中應用，并在計算機生成的網絡(GN基準和LFR基準)上進行了測試，與其他三種算法進行了比較。 實驗結果表明，該算法能夠有效地識別網絡的社團結構。