Spark平臺(tái)上利用網(wǎng)絡(luò)加權(quán)Voronoi圖的分散迭代社區(qū)聚類并行化研究

顏 燁 張學(xué)文 王立婧

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

2(北華大學(xué)機(jī)械工程學(xué)院 吉林 吉林 132021)

0 引 言

近年來(lái)，通過(guò)觀察在這一交互作用下的網(wǎng)絡(luò)來(lái)分析真實(shí)世界的交互作用已經(jīng)變得很普遍。真實(shí)世界網(wǎng)絡(luò)通常表現(xiàn)出的一種有趣的特點(diǎn)就是社區(qū)結(jié)構(gòu)特征，就是在網(wǎng)絡(luò)拓?fù)湎陆M織而成的模塊，它們通常被稱作社區(qū)或者聚類[1-2]。

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

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

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

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

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

(3) 結(jié)合并行計(jì)算技術(shù)，將NWVD-DICCM方法的操作從串行過(guò)程轉(zhuǎn)換為并行方法。實(shí)現(xiàn)NWVD-PDICCM流水線并行，并維護(hù)保持NWVD-DICCM的整體結(jié)構(gòu)。NWVD-PDICCM也因?yàn)槔梅植际酱鎯?chǔ)器和在Spark框架下提取并行性的特性而具有更有效的聚類能力。

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

1 本文方法

1.1 整體框架

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

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

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

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

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

給定平面上n個(gè)點(diǎn)構(gòu)成的集合S={p1，p2，…，pn}，對(duì)每個(gè)生長(zhǎng)點(diǎn)pi(i=1，2，…，n)，賦予非負(fù)實(shí)數(shù)權(quán)重λi，稱V(pi，λi)為點(diǎn)pi的權(quán)重為λi的V區(qū)域。V(pi，λi)表達(dá)式如下：

(1)

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

圖2給出了一個(gè)Voronoi圖的例子，圖中黑點(diǎn)為生長(zhǎng)點(diǎn)，折線段為Voronoi邊。

圖2 Voronoi圖示例

圖3給出了一個(gè)加權(quán)Voronoi圖的例子。由定義可知，Voronoi圖是加權(quán)Voronoi圖當(dāng)所有生長(zhǎng)點(diǎn)的權(quán)重相等時(shí)的特例。

圖3 加權(quán)Voronoi圖示例

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

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

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

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

(2)

式中：Nbr表示第i個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。

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

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

(3)

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

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

1.3 并行化

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

算法1NWVD-PDICCM

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

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

重復(fù)

Outlier list all Nodes

//局部聚類階段

While outlier list≠{}

Oi← Rand select (outlier list)

//隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為發(fā)起人

OnId ← Oi

//發(fā)起人 ID

TTL ← time_to_live(time_to_live)

WMsg ← 1

Msg ← {OnId, TTL, WMsg}

While TTO≥0時(shí)

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

//Oi與其相鄰節(jié)點(diǎn)之間的總權(quán)重(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)

//無(wú)成員變更

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

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

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

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

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

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

(4)

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

通過(guò)計(jì)算這些C聚類中的Vm對(duì)其相鄰節(jié)點(diǎn)(Nbr Attraction)的吸引力之和，計(jì)算Vm所屬的所有聚類(C)的Vm強(qiáng)度值，如下：

(5)

真正的社區(qū)結(jié)構(gòu)(基本事實(shí))以基準(zhǔn)網(wǎng)絡(luò)而著稱，歸一化互信度(NMI)用于將實(shí)驗(yàn)中獲得的分區(qū)與LFR基準(zhǔn)的基本事實(shí)進(jìn)行比較，并以此來(lái)評(píng)估DICCM和PDICCM的性能。NMI指標(biāo)通過(guò)評(píng)估檢測(cè)到的和基本事實(shí)社區(qū)之間的對(duì)應(yīng)程度來(lái)量化所提方法的準(zhǔn)確性。

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

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

(6)

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

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

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

(7)

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

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

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

2.1 生存時(shí)間

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

2.2 閾 值

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

選擇合適的閾值是非常關(guān)鍵的，并且需要網(wǎng)絡(luò)結(jié)構(gòu)的先驗(yàn)知識(shí)。因此，提出一種自動(dòng)計(jì)算閾值的數(shù)學(xué)模型。該模型利用網(wǎng)絡(luò)的密度、大小和布局結(jié)構(gòu)來(lái)找到最佳閾值。

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

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

(8)

(9)

(10)

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

(11)

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

完全連接的網(wǎng)絡(luò)是n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中的簡(jiǎn)單無(wú)向圖，其中每對(duì)不同的節(jié)點(diǎn)通過(guò)唯一的邊連接?；趫D論，完全連通網(wǎng)絡(luò)的網(wǎng)絡(luò)聚類系數(shù)為1，每個(gè)節(jié)點(diǎn)的度數(shù)定義為：

Ki=n-1

(12)

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

(13)

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

(14)

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

2.3 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

3.1 環(huán)境設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

(a) n=600

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

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

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

3.2.2增長(zhǎng)的網(wǎng)絡(luò)大小的聚類結(jié)果

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

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

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

表1 與主機(jī)進(jìn)行本地交換的消息以及主機(jī)和主機(jī)之間交換的消息進(jìn)行比較 %

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

圖8 節(jié)點(diǎn)數(shù)量對(duì)聚類準(zhǔn)確性的影響

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

圖9 節(jié)點(diǎn)數(shù)量對(duì)標(biāo)準(zhǔn)偏差的影響

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

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

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

4 結(jié) 語(yǔ)

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

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