孟 雪，許 英

(新疆財經(jīng)大學 統(tǒng)計與數(shù)據(jù)科學學院，烏魯木齊 830012)

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

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

1 算法架構

1.1 局部隨機游走距離

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

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

(1)

其中|E|是網(wǎng)絡的邊數(shù)。

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

(2)

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

(3)

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

1.2 輪廓系數(shù)

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

將網(wǎng)絡G劃分為{C1，C2，C3，…，Ck}，其中k是社團的數(shù)量。對于網(wǎng)絡中的任何節(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)選擇社團。 因此，了解網(wǎng)絡中每個節(jié)點的次優(yōu)選擇社團是非常重要的。

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

(7)

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

(8)

1.3 算法

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

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

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

輸出：網(wǎng)絡的社團結構

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

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

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

(9)

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

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

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

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

1.4 復雜度

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

2 應用

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

2.1 真實網(wǎng)絡檢測

A.空手道俱樂部網(wǎng)絡

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

(10)

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

圖1 空手道俱樂部網(wǎng)絡社團結構部分

B.海豚網(wǎng)絡

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

圖2 海豚網(wǎng)絡社團結構劃分

(11)

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

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

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

(12)

圖3 足球網(wǎng)絡社團結構劃分

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

表1 三個真實世界網(wǎng)絡在四種算法下的NMI值和社團數(shù)k

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

2.2 計算機生成網(wǎng)絡檢測

A.GN基準

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

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

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

B.LFR基準

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

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

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

3 結論

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