顏 燁 張學文 王立婧

1(重慶大學城市科技學院電氣信息學院 重慶 402167)

2(北華大學機械工程學院 吉林 吉林 132021)

0 引 言

近年來，通過觀察在這一交互作用下的網(wǎng)絡來分析真實世界的交互作用已經(jīng)變得很普遍。真實世界網(wǎng)絡通常表現(xiàn)出的一種有趣的特點就是社區(qū)結構特征，就是在網(wǎng)絡拓撲下組織而成的模塊，它們通常被稱作社區(qū)或者聚類[1-2]。

受最近出現(xiàn)的大數(shù)據(jù)的驅動，使用傳統(tǒng)方法和算法的真實世界網(wǎng)絡群已經(jīng)幾乎不可能在單獨的機器中被處理[3]。為了應對這種情況，需要一種分散的并行計算模型來處理大型數(shù)據(jù)集，將數(shù)據(jù)集擴展到集群中的多臺機器并進行處理[4-5]。

文獻[6]提出一種凝聚層次聚類方法，該算法收斂地去最大化模塊化功能，通過為網(wǎng)絡中的每個節(jié)點分配不同的社區(qū)來啟動該過程。通過不同級別的樹形圖切割為社區(qū)提供不同的分區(qū)，可以得到最佳的群落聚類。文獻[7]提出分層凝聚優(yōu)化方法，并且嘗試優(yōu)化網(wǎng)絡分區(qū)的模塊性。優(yōu)化分兩個步驟執(zhí)行，且兩個步驟迭代重復。該算法從屬于其自己的社區(qū)的網(wǎng)絡中的每個節(jié)點開始。這兩個步驟反復重復，并且在模塊增量時停止，因此可獲得最大模塊。此外，文獻[8]提出一種基于短步行的節(jié)點相似性度量來捕獲節(jié)點之間的結構相似性而不是模塊性通過分層聚集來識別社區(qū)。首先將每個節(jié)點分配給自己的社區(qū)，并且每對社區(qū)的距離是被計算好的。社區(qū)根據(jù)它們的最小距離進行合并，該過程重復進行，并給出一個稱為樹狀圖的社區(qū)層次結構。

然而，傳統(tǒng)的聚類算法是集中的(需要全局信息)，并且沒有能力以并行(或分布式)的方式跨多個服務器處理數(shù)據(jù)。因此，提出一種新穎且實用的算法來解決聚類問題以及在大量間接網(wǎng)絡中的社區(qū)檢測問題。這里所提出的方法都假設需要將給定的網(wǎng)絡結構劃分為社區(qū)，使得每個節(jié)點屬于一個社區(qū)，其主要創(chuàng)新點可總結如下：

(1) 提出一種基于網(wǎng)絡加權Voronoi圖的并行分散迭代社區(qū)聚類方法來提取大型網(wǎng)絡的有效社區(qū)結構。該方法能夠消除對網(wǎng)絡全局架構的依賴，能夠更有效地聚類網(wǎng)絡。

(2) 大多數(shù)現(xiàn)有的社區(qū)檢測算法不能在沒有涉及懲罰的情況下對大型網(wǎng)絡中的社區(qū)完成聚類，而結合網(wǎng)絡加權Voronoi圖的分散迭代社區(qū)聚類方法NWVD-DICCM可以通過聚合網(wǎng)絡中的節(jié)點來有效地聚類大規(guī)模數(shù)據(jù)集，以便問題簡化。

(3) 結合并行計算技術，將NWVD-DICCM方法的操作從串行過程轉換為并行方法。實現(xiàn)NWVD-PDICCM流水線并行，并維護保持NWVD-DICCM的整體結構。NWVD-PDICCM也因為利用分布式存儲器和在Spark框架下提取并行性的特性而具有更有效的聚類能力。

實驗結果表明，NWVD-PDICCM可以與一系列計算機架構平臺(例如PCs集群、多核分布存儲服務器、GPUs等)共同運行，可以在最流行的Spark平臺上實現(xiàn)并行操作，相比于文獻[6]和文獻[8]方法，大規(guī)模網(wǎng)絡數(shù)據(jù)處理速度和準確度得到了顯著提升。

1 本文方法

1.1 整體框架

NWVD-PDICCM方法包括兩個工作方案：主工作者和從屬聚類的工作者。主工作者程序在讀取數(shù)據(jù)集時創(chuàng)建塊，并將它們傳遞給從屬聚類工作程序[9]。另一方面，從屬聚類工作者的功能就是通過遍歷自己的數(shù)據(jù)集并應用NWVD-PDICCM方法的第一階段來識別局部社區(qū)。NWVD-PDICCM方法的流程如圖1所示。

圖1 網(wǎng)絡加權Voronoi圖的并行分散迭代社區(qū)聚類算法流程

1.2 網(wǎng)絡加權Voronoi圖的分散迭代社區(qū)聚類方法

網(wǎng)絡加權Voronoi圖分散迭代社區(qū)聚類方法主要包括三部分：首先是初始化數(shù)據(jù)以及特征向量提取，主要負責數(shù)據(jù)導入以及提取特征向量并進行預處理；其次是聚類算法部分，它是基于網(wǎng)絡加權Voronoi圖改進的分散迭代社區(qū)聚類算法的主體部分；最后是聚類結果部分，可以從中提取特殊數(shù)組[10]。

Voronoi 圖是根據(jù)已知點集對平面施行的一種分割。其數(shù)學定義為：

給定平面上n個點構成的集合S={p1，p2，…，pn}，對每個生長點pi(i=1，2，…，n)，賦予非負實數(shù)權重λi，稱V(pi，λi)為點pi的權重為λi的V區(qū)域。V(pi，λi)表達式如下：

(1)

式中:d(p，pi)為p與pi之間的Euclid距離。

圖2給出了一個Voronoi圖的例子，圖中黑點為生長點，折線段為Voronoi邊。

圖2 Voronoi圖示例

圖3給出了一個加權Voronoi圖的例子。由定義可知，Voronoi圖是加權Voronoi圖當所有生長點的權重相等時的特例。

圖3 加權Voronoi圖示例

傳統(tǒng)DICCM是一種基于隨機游走和可達性的凝聚聚類算法，通過相鄰之間的消息傳播來實現(xiàn)。它有兩個階段，即局部聚類和網(wǎng)絡縮減，并且以迭代方式運行。前一階段用于為每個社區(qū)聚類定義起始節(jié)點[11]?？s減階段則用于重建網(wǎng)絡。網(wǎng)絡加權Voronoi圖的分散迭代社區(qū)聚類方法的流程如圖4所示。

圖4 網(wǎng)絡加權Voronoi圖的分散迭代社區(qū)聚類方法

每輪迭代過程包括隨機選擇一個節(jié)點作為起始點。 起始節(jié)點充當聚類頭并通過向網(wǎng)絡中的所有相鄰節(jié)點發(fā)送消息(Msg)來通告自己。此消息包含三個參數(shù)：起始節(jié)點ID(OnID)，消息權重(Message weight，WMsg)和TTL。OnID表示的是消息發(fā)起者的節(jié)點ID。WMsg是消息攜帶的權重，表示從起始節(jié)點開始到達網(wǎng)絡中任何節(jié)點的估計概率。TTL表示消息到期之前, 跳躍中的最大距離。值得注意的是，為了避免將起始點被分配給任何其他聚類，WMsg的起始點被設置為1。

考慮兩個節(jié)點，起始點Oi及其相鄰節(jié)點Vi，用于計算從起始點Oi發(fā)送到節(jié)點Vi的消息的權重的模型取決于Oi和Vi之間的邊緣的權重。定義如下：

(2)

式中：Nbr表示第i個節(jié)點的相鄰節(jié)點。

網(wǎng)絡中的每個節(jié)點維護了有關起始ID的信息和它為每個起始者收到的消息的總權重。這個信息被表示為總消息權重。 當節(jié)點收到了來自相鄰節(jié)點的信息后，它首先會更新消息總權重，并且隨后檢查TTL是否大于0。如果TTL大于0，則通過一個并行節(jié)點將消息轉發(fā)給除了發(fā)送者以外的所有節(jié)點，從而降低消息的TTL。

從節(jié)點Vi發(fā)送到其相鄰節(jié)點Oi的新消息(WMsg(Vi,Vk))的權重被定義為：

(3)

然而，如果TTL等于0或者WMsg值同預先定義的閾值相比減小的話，節(jié)點Vk處理消息并且停止下個階段。

如果來自起始點的消息總權重大于指定的閾值，則節(jié)點加入最近的發(fā)起者Oi。如果不是這樣的話，那些節(jié)點將保留為異常值并且不加入任何聚類[12]。

1.3 并行化

NWVD-PDICCM算法的核心思想是將數(shù)據(jù)集劃分為塊，然后迭代地重復以下三個階段：聚類，重新聚類,重建。聚類階段負責獨立和并行地為每個塊查找局部社區(qū)聚類。重新聚類階段，從各個別的塊中提取的局部聚類聚集起來，以找到整個網(wǎng)絡的初始社區(qū)聚類。重建階段涉及到基于初始社區(qū)聚類為每個數(shù)據(jù)塊構建一個新的但更小的網(wǎng)絡。通過上述三個階段的該過程的每一個循環(huán)被稱為迭代。這三個階段迭代到舊的和新的社區(qū)聚類列表不再收斂。具體算法如下：

算法1NWVD-PDICCM

輸入：底層網(wǎng)絡圖G、生存時間和閾值。

輸出：作為G的最終劃分的C社區(qū)。

重復

Outlier list all Nodes

//局部聚類階段

While outlier list≠{}

Oi← Rand select (outlier list)

//隨機選擇一個節(jié)點作為發(fā)起人

OnId ← Oi

//發(fā)起人 ID

TTL ← time_to_live(time_to_live)

WMsg ← 1

Msg ← {OnId, TTL, WMsg}

While TTO≥0時

Total_weight(Oi, Vi)= sendmessages(G, Oi, OnId, TTL, Msg )

//Oi與其相鄰節(jié)點之間的總權重(Vi)

TTL ← TTL-1

Oi← Vi

Msg ← {OnId, TTL, Total_weight(Oi, Vi)}

end while

for each Node Vi∈G

if Total_weight(Vi, OnID)≥ threshould then

C(Vi) Join the cluster lead by max onID

else

Remain outlier

end if

end

end

G = Aggregate(G, C)

if (C_current=C_previous)

//無成員變更

break；

return C

//返回C

end Algorithm

Function sendmessages (G, Oi, OnId, TTL, Msg)

for each Node Vi∈Nbr(Oi)

if Ni have seen message form onID before then

Total_weight(Vi,Oi) ← Total_weight(Vi,Oi)+WMsg

else

Total_weight(Vi, Oi) ← WMsg

end if

end

Return Total_weight(Vi, Oi)

end function

從屬聚類工作程序并行運行，并將社區(qū)群集列表存儲在其局部內(nèi)存中。然而，由于每個從屬聚類工作者有一部分數(shù)據(jù)并且不具有網(wǎng)絡的全局知識，從而不同的從屬聚類工作者可以將相同的節(jié)點聚類到不同的社區(qū)中。因此，當所有的塊都被聚類并且已經(jīng)識別了本地社區(qū)時，主工作者加載局部社區(qū)聚類列表以進行聚合。

重建階段使用NWVD-PDICCM方法，由每個從屬聚類工作者構建新網(wǎng)絡。該新網(wǎng)絡中兩個節(jié)點之間連接的權重就是原始網(wǎng)絡中兩個相對應社區(qū)節(jié)點之間連接的總權重。 同一社區(qū)的節(jié)點之間的連接變?yōu)樾戮W(wǎng)絡中相應節(jié)點的自循環(huán)。 然后重復迭代，直到獲得一組穩(wěn)定的社區(qū)聚類(滿足收斂條件)。

每個從屬聚類工作者都擁有各自不可共享內(nèi)存，并且在聚類階段工作者之間沒有通信。因此，每個從屬群集工作者操作獨立于其他操作，并且每個從屬聚類工作者的操作是可以并行執(zhí)行的[13]。對于聚類結果的評測指標，主要可定義為以下幾種：

定義1聚類強度。這里給定一個網(wǎng)絡集G=(V,E)，節(jié)點n=|V|，邊m=|E|。在聚類階段時，每個從屬聚類工作者將這些節(jié)點聚集為C聚類，并將Vm節(jié)點分配給不同的社區(qū)。為了能找到適合Vm節(jié)點的最佳社區(qū)，提出的方案按照下面的兩個步驟實施。

首先節(jié)點Vm從其每個相鄰節(jié)點獲得兩組信息，即相鄰節(jié)點的程度和它所屬的集群，然后計算Vm與其相鄰Vi之間的相鄰吸引力，并且定義為：

(4)

式中：W(Vm,Vi)表示Vm與Vi之間的邊緣的權重。

通過計算這些C聚類中的Vm對其相鄰節(jié)點(Nbr Attraction)的吸引力之和，計算Vm所屬的所有聚類(C)的Vm強度值，如下：

(5)

真正的社區(qū)結構(基本事實)以基準網(wǎng)絡而著稱，歸一化互信度(NMI)用于將實驗中獲得的分區(qū)與LFR基準的基本事實進行比較，并以此來評估DICCM和PDICCM的性能。NMI指標通過評估檢測到的和基本事實社區(qū)之間的對應程度來量化所提方法的準確性。

定義2歸一化互信度。歸一化互信度(NMI)是用信息理論概念比較兩個分區(qū)的相似性度量，被廣泛用于評估社區(qū)檢測算法的準確性。

對于一個擁有兩個分區(qū)n個節(jié)點網(wǎng)絡，其劃分分別為X={X1,X2,…,Xk}和Y={Y1,Y2,…,Yk}，其中X和Y分別代表了真實社區(qū)和查找社區(qū)，并且一個網(wǎng)絡中兩個劃分X和Y的歸一化互信度定義如下：

(6)

如果通過算法得到的查找分區(qū)與真實社區(qū)相同，則NMI取最大值1；如果找到的分區(qū)完全獨立于真實分區(qū)，則NMI取0。

定義3模塊化(Q)。模塊化(Q)是衡量社區(qū)結構質量的重要指標，已成為社區(qū)檢測的一種廣泛接受的衡量標準。模塊化表明，良好的聚類應該在模塊內(nèi)的節(jié)點之間具有大于預期的連接數(shù)，并且在不同模塊中的節(jié)點之間的連接數(shù)量小于預期。模塊化的價值越高，其社區(qū)力量就越好。

模塊化優(yōu)化算法的一般概念是通過搜索具有高模塊性的網(wǎng)絡的可能劃分來檢測模塊化方面的最佳社區(qū)結構。模塊化定義如下：

(7)

式中：Aij是相鄰的基地元素；Ki是節(jié)點i的程度；δcicj是Kronecker三角洲符號，且其值為1。

2 參數(shù)設置與數(shù)據(jù)集

使用兩個參數(shù)來評估本文方法：1) 生存時間(Time To Live,TTL)，允許消息在被丟棄之前傳播的跳躍；2) 閾值，用于確定合并社區(qū)的難度。

2.1 生存時間

每條消息都有一個TTL區(qū)間，該區(qū)間以某個值T>0時啟動，該值限制了消息轉發(fā)的次數(shù)。實際上，需要謹慎選擇合適的TTL值，因為TTL值小意味著消息在到達網(wǎng)絡中的所有相關節(jié)點之前可能過期；TTL大意味著訪問的節(jié)點多于所需的節(jié)點，從而增加了網(wǎng)絡上的消息負載和算法的運行時間。因此，在這項工作中，建議在開始新的迭代之前重建網(wǎng)絡。此外，基于現(xiàn)實世界的網(wǎng)絡屬性，據(jù)說來自應用的網(wǎng)絡通常是小世界網(wǎng)絡。簡單來說，小世界概念描述了這樣一個事實，也就是即使網(wǎng)絡有許多節(jié)點，也存在連接網(wǎng)絡中任何一對節(jié)點的相對少量的中間步驟。

2.2 閾 值

閾值是在過程開始時設置的參數(shù)，范圍在0到1之間。如果節(jié)點從起始者Oi接收的消息的總權重等于或大于閾值，則節(jié)點能夠加入由Oi主導的聚類。這就意味著閾值越高，節(jié)點合并到社區(qū)的可能性就越小。例如，將閾值設置為接近零時，將生成包含網(wǎng)絡中所有節(jié)點的單個社區(qū)聚類。另一方面，將閾值設置為接近1時，將使每個節(jié)點位于其自己的聚類中。即低閾值產(chǎn)生大量小尺寸聚類；高閾值將產(chǎn)生較少數(shù)量的較大規(guī)模的聚類。因此，閾值對聚類精度以及檢測到的聚類的大小具有重要影響。很顯然，調(diào)整閾值可被視為控制所需社區(qū)的大小和數(shù)量的一種可能的實際補救措施。

選擇合適的閾值是非常關鍵的，并且需要網(wǎng)絡結構的先驗知識。因此，提出一種自動計算閾值的數(shù)學模型。該模型利用網(wǎng)絡的密度、大小和布局結構來找到最佳閾值。

式(8)-式(14)定義了為無向網(wǎng)絡設置閾值的數(shù)學模型：

Thresholdvalue=avg_t+(t-1)×((1-C)×avg_t)

(8)

(9)

(10)

式中：i是主節(jié)點；j代表所有其他節(jié)點；A是鄰接矩陣，若主節(jié)點i與其他節(jié)點j之間具有連通性，則Aij的值為1，否則，值為0；n是網(wǎng)絡中節(jié)點的總數(shù)；t是迭代次數(shù)；Ki是節(jié)點i的度數(shù)；C是網(wǎng)絡聚類系數(shù)。

(11)

式中：Li表示臨近的節(jié)點i的邊數(shù)。

完全連接的網(wǎng)絡是n個節(jié)點的網(wǎng)絡中的簡單無向圖，其中每對不同的節(jié)點通過唯一的邊連接。基于圖論，完全連通網(wǎng)絡的網(wǎng)絡聚類系數(shù)為1，每個節(jié)點的度數(shù)定義為：

Ki=n-1

(12)

因此，擁有n個節(jié)點的完整網(wǎng)絡的總邊數(shù)為：

(13)

計算得到完整的網(wǎng)絡閾值：

(14)

值得一提的是，在每次迭代中，給定網(wǎng)絡的閾值通過(t-1)×((1-C)×avg_t)逐步增加，如式(8)所示，使得密度較小的聚類彼此連接變得越來越困難。只有強關聯(lián)的才能合并。 另外，最大閾值不能大于1。

2.3 實驗數(shù)據(jù)集

為了分析社區(qū)檢測算法在一系列網(wǎng)絡規(guī)模上的效率，并且由于具有地面實況社區(qū)的真實網(wǎng)絡的稀缺可用性，LFR基準被用于生成合成數(shù)據(jù)集。LFR基準模型是由Lancichinetti等為了生成與社區(qū)結構的現(xiàn)實世界網(wǎng)絡非常相似的無向和未加權網(wǎng)絡而提出的。LFR模型已成為評估社區(qū)檢測算法性能的受歡迎的選擇。

大多數(shù)現(xiàn)實生活網(wǎng)絡已被定義和建模為無向和未加權/加權網(wǎng)絡。提出LFR模型以解決實際網(wǎng)絡的大多數(shù)特征，例如網(wǎng)絡的大小和異構度分布。在LFR基準測試中，網(wǎng)絡的節(jié)點度和每個社區(qū)的大小分別由具有指數(shù)γ和β的冪律分布控制[14]。然而，已經(jīng)觀察到真實世界圖具有典型值為：2≤γ≤3,1≤β≤2這樣的冪律度分布。

LFR模型提供一些其他參數(shù)來控制網(wǎng)絡拓撲，其中包括節(jié)點數(shù)、最大度數(shù)和混合參數(shù)μ。 混合參數(shù)μ∈[0,1]，用于控制網(wǎng)絡上的聚類內(nèi)和聚類間邊緣的分數(shù)。對于較小的μ值，將有少量邊緣到達社區(qū)之外，這表明網(wǎng)絡中有可用的清晰聚類。μ值越大，檢測網(wǎng)絡中的社區(qū)就越具有挑戰(zhàn)性。LFR模式的代碼已由作者公開[15-16]。

3 仿真實驗與結果分析

3.1 環(huán)境設置

基于MATLAB平臺實現(xiàn)NWVD-DICCM和NWVD-PDICCM，實驗運行環(huán)境為4核CoreTMi5 7500 K CPU 4.00 GHz的Linux系統(tǒng)，可用運行內(nèi)存為32 GB RAM。因為這些方法是隨機初始化發(fā)起者，并且為了忽略本文方法中隨機性的影響，每個結果的平均值超過200次運行。

使用LFR網(wǎng)絡生成一組無向網(wǎng)絡。默認基準參數(shù)值用作度分布和社區(qū)大小的指數(shù)的基準參數(shù)，即：γ=2，β=1。平均度和最大度分別為25和50?；旌蠀?shù)在0.10到0.75之間變化，節(jié)點數(shù)從500增加到5 000。

3.2 實驗結果

3.2.1與并行核心數(shù)量相關的水平可伸縮性

為了驗證當更多工作者可用時，所提出的方法處理數(shù)據(jù)集的程度如何，實驗中使用的網(wǎng)絡中的節(jié)點數(shù)保持不變，工作者的數(shù)量從1到4不等。值得一提的是，如果工作者數(shù)量是1，算法只代表MLDICCM。圖5所示為當節(jié)點數(shù)量恒定時，不同工作者數(shù)量對應的聚類準確性，n∈{600,1 200}。

(a) n=600

(1) 質量。由圖5可知，所提方法顯示出接近最佳值的良好可擴展性，其由平均模塊性和NMI值表示。此外，使用多個工作程序來并行化算法不會對結果的準確性產(chǎn)生不利影響。因此，結果證明該算法是有效的并且能夠以并行方式得到非常高質量的結果。具體地說，NWVD-PDICCM能夠有效地利用多核架構。

(2) 消息復雜性?？紤]到每個工作者交換消息的數(shù)量，圖6所示為每個工作者處理器在每次迭代時交換消息的百分比。 正如在每次迭代中可以看到的，每個工作者生成幾乎相同數(shù)量的消息，這可以通過以下事實來澄清：數(shù)據(jù)已在工作者中平均分配，因此每個工作者必須處理相同大小的數(shù)據(jù)。在每次迭代時，主工作者必須等到所有從屬工作者完成他們的過程。 因此，將數(shù)據(jù)平均分配給工作者可以顯著減少等待最慢的機器的工作者返回數(shù)據(jù)所需的預期時間。

圖6 節(jié)點數(shù)量為1 200時，工作者從2到4變化過程中，每次迭代交換的消息數(shù)量

3.2.2增長的網(wǎng)絡大小的聚類結果

為了證明被可擴展性影響的性能，節(jié)點數(shù)量從500線性增加到5 000，工作者數(shù)量保持恒定在1和3。所有其他參數(shù)和因素保持與先前評估相同。

對于更深入的分析，圖7顯示了每次迭代過程中消息交換的平均百分比。從數(shù)據(jù)中可以很容易地看出，當每個節(jié)點在其自己的聚類中時，算法的數(shù)據(jù)交換在迭代的第一階段要大得多。在2到3次初始迭代之后，大多數(shù)節(jié)點都有其聚類標簽，并且算法已將屬于同一聚類的節(jié)點合并為一個節(jié)點。從表1中的主工作者(主工)和從屬工作者(從工)之間交換消息的百分比也可以清楚地看到，通信成本可以忽略不計。然而，相比主工與從工之間信息交換成本，從工中局部信息交換的成本明顯較高，這部分是算法的時間消耗主體。

圖7 對于網(wǎng)絡規(guī)模1 200，每次迭代交換的消息的平均百分比與核心數(shù)量從1到4個工作者的變化

表1 與主機進行本地交換的消息以及主機和主機之間交換的消息進行比較 %

(1) 質量。由NWVD-DICCM和NWVD-PDICCM獲得的解的模塊性值如圖8所示?？梢钥闯?，NWVD-DICCM和NWVD-PDICCM的性能始終良好且接近最佳值，NMI平均大于0.90。

圖8 節(jié)點數(shù)量對聚類準確性的影響

(2) 性能的可重復性評估。為了進一步研究NWVD-DICCM和NWVD-PDICCM在隨機數(shù)據(jù)分區(qū)和初始化中隨機啟動時產(chǎn)生一致結果的能力，聚類結果的標準偏差被測量了，其中NWVD-DICCM和NWVD-PDICCM每次運行100次，使用不同的隨機數(shù)據(jù)分區(qū)和算法初始化。在不同節(jié)點數(shù)量情況下，記錄NMI與網(wǎng)絡模塊的標準偏差，如圖9所示。

圖9 節(jié)點數(shù)量對標準偏差的影響

3.2.3使用混合參數(shù)的聚類性能評估

當社區(qū)結構被高度增長的社區(qū)內(nèi)部連接(LFR基準的μ值具有較高值時發(fā)生)削弱時，為了研究NWVD-DICCM和NWVD-PDICCM的社區(qū)聚類能力，將混合參數(shù)設定在0至0.8之間，并保持節(jié)點數(shù)恒定，n∈{1 000}，記錄混合參數(shù)μ對幾種算法聚類準確性的影響，如圖10所示?？梢郧宄乜吹剑敾旌暇W(wǎng)絡參數(shù)低于0.7時，NWVD-DICCM和NWVD-PDICCM獲得的準確性均高于其他2種對比方法，然而，當混合網(wǎng)絡參數(shù)繼續(xù)增大時，NWVD-DICCM的準確性低于文獻[6]方法。分析原因可知，當混合網(wǎng)絡參數(shù)值較低時，網(wǎng)絡中明確定義的社區(qū)結構，大部分邊緣節(jié)點可落在社區(qū)內(nèi)，因此NWVD-DICCM和NWVD-PDICCM具有較高的聚類準確性。當網(wǎng)絡參數(shù)值較大時，邊緣節(jié)點很難落在社區(qū)內(nèi)，一定程度上影響NWVD-DICCM的聚類效果。通過引入網(wǎng)絡加權Voronoi圖可以有效解決該問題，因此，改進后的NWVD-PDICCM方法可以一直保持較高的聚類準確性。

圖10 混合參數(shù)μ對聚類準確性的影響

4 結 語

本文提出一種基于網(wǎng)絡加權Voronoi圖的并行分散迭代社區(qū)聚類方法(NWVD-DICCM)及其并行版本(NWVD-PDICCM)，以提取大型網(wǎng)絡的有效社區(qū)結構。本文方法的一個重要特性是它們能夠在沒有全局網(wǎng)絡拓撲知識的情況下從整個網(wǎng)絡中識別最佳社區(qū)聚類。本文方法解決了圍繞處理大數(shù)據(jù)集的計算需求的問題。它們通過以并行方式處理多個塊，最佳地利用現(xiàn)代多核系統(tǒng)的硬件功能，從而加快執(zhí)行速度。此外，當數(shù)據(jù)大小超出單個機器的處理能力時出現(xiàn)可擴展性問題時，基于Spark計算平臺的建議分布式方法將有助于解決這個問題。最后，使用具有基本事實的社區(qū)的合成網(wǎng)絡來測試和分析這些方法的有效性和復雜性。

現(xiàn)實世界的網(wǎng)絡通常不包含完美的社區(qū)，實際上節(jié)點可能同時屬于多個社區(qū)。識別這種重疊社區(qū)對于理解現(xiàn)實世界網(wǎng)絡的結構和功能至關重要。因此，未來主要方向是擴展所提出的方法以能夠檢測出這種模糊社區(qū)。此外，本文只考慮了無向網(wǎng)絡，對于有向網(wǎng)絡則需要進一步深化研究。