利用2-hop隨機(jī)游走進(jìn)行異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

楊海陸, 張健沛, 楊靜

(1.哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)博士后流動(dòng)站，黑龍江 哈爾濱150080； 2.哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150080； 3.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

利用2-hop隨機(jī)游走進(jìn)行異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

楊海陸1,2,3, 張健沛3, 楊靜3

(1.哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)博士后流動(dòng)站，黑龍江 哈爾濱150080； 2.哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150080； 3.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

摘要：針對(duì)異質(zhì)社交網(wǎng)絡(luò)社區(qū)識(shí)別問題，提出一種基于隨機(jī)游走層次社區(qū)識(shí)別算法。提出異質(zhì)網(wǎng)絡(luò)層級(jí)吸引力度量函數(shù)，構(gòu)建異質(zhì)網(wǎng)絡(luò)隨機(jī)游走模型；設(shè)計(jì)了一種基于2-hop互隨機(jī)游走的異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)相似性度量函數(shù)；通過將該相似性函數(shù)推廣到層次聚類并設(shè)計(jì)相應(yīng)的相似矩陣校準(zhǔn)方案，異質(zhì)社區(qū)識(shí)別任務(wù)可以在較短的時(shí)間內(nèi)迭代完成。人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上的仿真實(shí)驗(yàn)驗(yàn)證了算法的可行性和有效性。

關(guān)鍵詞：異質(zhì)社交網(wǎng)絡(luò)；社區(qū)識(shí)別；隨機(jī)游走；相似性度量；層次聚類

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151106.1328.018.html

張健沛(1956-)，男，教授，博士生導(dǎo)師.

社區(qū)識(shí)別是社會(huì)計(jì)算領(lǐng)域重要的研究內(nèi)容?？傮w上講，社區(qū)結(jié)構(gòu)是一種介于宏觀和微觀之間的特殊結(jié)構(gòu)[1]，它是網(wǎng)絡(luò)節(jié)點(diǎn)的一種聚集形式，使得社區(qū)內(nèi)部鏈接密度高于社區(qū)間的鏈接密度。社區(qū)的量化形式是模塊度函數(shù)[2]，以模塊度為優(yōu)化目標(biāo)的社區(qū)識(shí)別是當(dāng)前最熱門的方法之一，但精準(zhǔn)求解模塊度最大的社區(qū)劃分是NP-完全問題[3]，因此現(xiàn)有研究多采用啟發(fā)式方法[2-4]解決這一技術(shù)難點(diǎn)。除此之外，統(tǒng)計(jì)推理[5]、多目標(biāo)優(yōu)化[6]、圖分割[5]等方法同樣能夠有效的挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

傳統(tǒng)的社區(qū)識(shí)別研究通常假定社會(huì)網(wǎng)絡(luò)中只含有一種社會(huì)關(guān)系，然而在真實(shí)的網(wǎng)絡(luò)環(huán)境下，節(jié)點(diǎn)間通常是多種關(guān)系協(xié)同交互，由此構(gòu)成了維度更高的異質(zhì)社會(huì)網(wǎng)絡(luò)。異質(zhì)社會(huì)網(wǎng)絡(luò)社區(qū)識(shí)別旨在從多種社會(huì)關(guān)系中識(shí)別出隱含的社區(qū)結(jié)構(gòu)。目前這一領(lǐng)域的研究成果較少，并缺乏長期且系統(tǒng)化的研究體系。Mucha等[7]提出異質(zhì)社區(qū)模塊度函數(shù)，并將之用于分析美國東北部某大學(xué)在校學(xué)生以4種社會(huì)關(guān)系構(gòu)成的異質(zhì)關(guān)系網(wǎng)絡(luò)。Radicchi[8]證實(shí)了基于模塊度函數(shù)挖掘異質(zhì)社區(qū)的可行性，并給出基于模塊度優(yōu)化挖掘異質(zhì)社區(qū)的必要條件。文獻(xiàn)[9-10]選擇將傳統(tǒng)的數(shù)據(jù)挖掘方法推廣到異質(zhì)網(wǎng)絡(luò)，但由于異質(zhì)系統(tǒng)各子網(wǎng)通常波動(dòng)較大，因此這類方法識(shí)別的社區(qū)通常不具有現(xiàn)實(shí)意義。文獻(xiàn)[11-13]將異質(zhì)數(shù)據(jù)映射至低維空間進(jìn)行社區(qū)識(shí)別，但這種方法通常會(huì)造成信息損失。Tang等[14]將單質(zhì)網(wǎng)絡(luò)社區(qū)挖掘分為4個(gè)子目標(biāo)進(jìn)行優(yōu)化，設(shè)計(jì)了一種異構(gòu)目標(biāo)整合策略，并以新目標(biāo)作為優(yōu)化對(duì)象完成社區(qū)挖掘任務(wù)。

歸納而言，挖掘異質(zhì)社區(qū)的難點(diǎn)主要在于各子網(wǎng)內(nèi)部鏈接模式不同且分布不均勻，因此需要一種新的節(jié)點(diǎn)局部相似性度量方法。此外，異質(zhì)社會(huì)網(wǎng)絡(luò)具有數(shù)據(jù)量大、數(shù)據(jù)維度高等特點(diǎn)，因此算法普遍時(shí)間開銷過高，挖掘效率較低。為解決上述問題，本文提出一種基于隨機(jī)游走的異質(zhì)社區(qū)識(shí)別方法，該方法模擬了社交節(jié)點(diǎn)在異質(zhì)系統(tǒng)中的自然選擇過程，不僅可以避免子系統(tǒng)鏈接的分布波動(dòng)，同時(shí)具有較高的運(yùn)行效率。

1隨機(jī)游走的基本概念

在統(tǒng)計(jì)學(xué)中，隨機(jī)游走的基本原理是從一個(gè)或多個(gè)節(jié)點(diǎn)開始遍歷全圖，對(duì)于任意節(jié)點(diǎn)而言，“游走者”將以轉(zhuǎn)移概率Pt隨機(jī)跳躍到圖中任何一個(gè)與其距離為t的節(jié)點(diǎn)。用di表示節(jié)點(diǎn)i的鄰居數(shù)，Aij為圖的鄰接矩陣，σ[u1～uk]={u1,u2},…,{uk-1,uk}?E表示一條從節(jié)點(diǎn)u1到節(jié)點(diǎn)uk的路徑，則“游走者”在任意節(jié)點(diǎn)的轉(zhuǎn)移概率為Puk,uk-1=Auk,uk-1/duk，進(jìn)而有節(jié)點(diǎn)u1到節(jié)點(diǎn)uk的游走概率為

(1)

(2)

這說明節(jié)點(diǎn)u1到節(jié)點(diǎn)uk和節(jié)點(diǎn)uk到節(jié)點(diǎn)u1的游走概率并不相同，與各自的出發(fā)節(jié)點(diǎn)度成正比。

對(duì)于任意具有強(qiáng)社區(qū)結(jié)構(gòu)的圖來講，由于社區(qū)內(nèi)部的鏈接較為稠密，因此當(dāng)“游走者”游走到社區(qū)邊緣時(shí)有極大的概率再次回到社區(qū)內(nèi)部。這說明社區(qū)內(nèi)部節(jié)點(diǎn)之間的游走可達(dá)概率相對(duì)較高，而分屬于不同社區(qū)的節(jié)點(diǎn)具有較低的游走概率。根據(jù)這一原理，通過度量節(jié)點(diǎn)或社區(qū)之間的游走可達(dá)概率，量化節(jié)點(diǎn)或社區(qū)之間的相似程度，進(jìn)而合并相似性較高的節(jié)點(diǎn)或社區(qū)為新社區(qū)。

2基于隨機(jī)游走的節(jié)點(diǎn)相似性度量

2.1　多關(guān)系社會(huì)網(wǎng)絡(luò)隨機(jī)游走模型

(3)

(4)

(5)

進(jìn)而可知異質(zhì)社交網(wǎng)絡(luò)任意兩節(jié)點(diǎn)間的游走概率(即任意層任意節(jié)點(diǎn)間的游走的概率)為

(6)

圖1　異質(zhì)社會(huì)網(wǎng)絡(luò)上的隨機(jī)游走Fig.1　Random walks in heterogeneous social networks

(7)

2.2　節(jié)點(diǎn)相似性度量

在獲得異質(zhì)網(wǎng)絡(luò)隨機(jī)游走模型后，對(duì)游走路徑施以2-hop約束以度量節(jié)點(diǎn)間的相似程度。首先定義以下3種條件約束：

約束1：如果節(jié)點(diǎn)u和節(jié)點(diǎn)v在同一社區(qū)，則u到v的可達(dá)概率必定很高，但是u到v的可達(dá)概率很高并不意味著節(jié)點(diǎn)u和節(jié)點(diǎn)v必定在同一社區(qū)。

約束2：最小化社區(qū)內(nèi)部節(jié)點(diǎn)的互可達(dá)性差異，如果節(jié)點(diǎn)u和節(jié)點(diǎn)v在同一社區(qū)，則u到v的可達(dá)概率與v到u的可達(dá)概率彼此接近，即Puv≈Pvu。

約束3：同一社區(qū)內(nèi)的2個(gè)節(jié)點(diǎn)之間的最大可達(dá)路徑為2-hop路徑。

之所以將游走路徑約束在2-hop以內(nèi)，是由于1-hop路徑和2-hop路徑能夠捕獲節(jié)點(diǎn)間的直接相似性和結(jié)構(gòu)相似性。然后，設(shè)計(jì)了一種以直接相似性為主導(dǎo)的權(quán)衡式，當(dāng)節(jié)點(diǎn)間不具備1-hop路徑時(shí)，適當(dāng)?shù)臑槠涮砑?-hop可達(dá)概率，進(jìn)而可得x層節(jié)點(diǎn)i到節(jié)點(diǎn)j實(shí)際的可達(dá)概率為

(8)

(9)

如圖1所示，節(jié)點(diǎn)(d,L1)與節(jié)點(diǎn)(b,L1)不具有直接鏈接，因此(d,L1)到(b,L1)的1-hop可達(dá)性為0。通過觀察發(fā)現(xiàn)(d,L1)與(b,L1)之間存在2-hop路徑{(d,L1),(a,L1)},{(a,L1),(b,L1)}，根據(jù)式(8)可得節(jié)點(diǎn)實(shí)際的可達(dá)概率為δ(d,L1),(b,L1)=1/d(d,L1)d(a,L1)=1/9。

結(jié)合2.2節(jié)定義的3類隨機(jī)游走約束，設(shè)計(jì)了基于游走可達(dá)概率的節(jié)點(diǎn)相似性度量函數(shù)。在式(10)中，分子部分保證社區(qū)內(nèi)部節(jié)點(diǎn)具有較高的游走概率，而分母作為懲罰因素，降低了互可達(dá)差異過大的節(jié)點(diǎn)存在于相同社區(qū)的可能性。

(10)

2.3　社區(qū)相似性度量

通過簡單的擴(kuò)展即可將節(jié)點(diǎn)相似性度量擴(kuò)展至社區(qū)相似性度量。節(jié)點(diǎn)i與社區(qū)C之間的可達(dá)性定義為i與C內(nèi)部所有節(jié)點(diǎn)可達(dá)概率的平均值，即

(11)

(12)

同理可定義社區(qū)之間的可達(dá)性為

(13)

3異質(zhì)社區(qū)的層次聚類算法

上節(jié)所討論的相似性度量方法使得具有較高互可達(dá)性的節(jié)點(diǎn)具有較高的相似程度。這種方式從全局的角度來看實(shí)際上保證了社區(qū)邊緣節(jié)點(diǎn)的入度大于出度。不同于Newman等[2]提出的基于割邊的層次社區(qū)檢測(cè)算法，本文采用了一種貪婪的層次化聚類策略。具體為：1)將每個(gè)節(jié)點(diǎn)視為獨(dú)立的劃分結(jié)果；2)迭代選擇相似性最大的2個(gè)劃分進(jìn)行合并，直至形成一個(gè)單一劃分，合并過程形成層次化樹；3)在層次化樹中，選取模塊度值最大的劃分方式作為最終的社區(qū)發(fā)現(xiàn)結(jié)果。

3.1　社區(qū)合并選擇

上述策略中，社區(qū)合并后相似矩陣必然發(fā)生變化。直觀上講，如果每次合并操作后都重新計(jì)算該矩陣，勢(shì)必造成過高的計(jì)算開銷。借鑒文獻(xiàn)[15]的思想，本文將“尋找相似矩陣最大元素”問題，轉(zhuǎn)化為“合并社區(qū)后，新社區(qū)內(nèi)部節(jié)點(diǎn)相似程度改變最小”問題。因此，通過對(duì)相似性改變矩陣進(jìn)行局部校準(zhǔn)，避免迭代過程中的冗余計(jì)算。

在聚類分析中，相似性的改變被描述為最小化新聚簇與中心點(diǎn)的平方距離，即

(14)

本文在合并社區(qū)的過程中遵循這樣一種啟發(fā)式思想：合并操作只發(fā)生在相鄰的社區(qū)之間(合并不相鄰的社區(qū)會(huì)使社區(qū)內(nèi)部鏈接過于稀疏)。因此如果社區(qū)C1和C2合并為新社區(qū)C3=C1∪C2，可得C3內(nèi)部節(jié)點(diǎn)的相似性改變程度為

(15)

(16)

將式(16)代入式(15)并參照式(12)可得新社區(qū)C3內(nèi)部節(jié)點(diǎn)最終的相似性改變量為

(17)

對(duì)式(17)進(jìn)行整理，可得C3與其鄰接社區(qū)C之間的相似性改變量為

(18)

因此，算法在迭代過程中采用式(18)對(duì)相似性改變矩陣進(jìn)行局部校準(zhǔn)，而無需對(duì)所有元素重新計(jì)算，可見這種局部選擇策略具有較高的效率。

3.2　輸出質(zhì)量最優(yōu)的社區(qū)劃分結(jié)果

算法的迭代過程最終會(huì)生成層次化樹，為了獲得最優(yōu)的社區(qū)結(jié)構(gòu)，本文采用Mucha等[7]提出的異質(zhì)模塊度函數(shù)度量社區(qū)質(zhì)量，具體為

(19)

由于篇幅限制，式中各參數(shù)不做過多介紹。需要說明的是，參數(shù)γs為層級(jí)Ls的分辨率參數(shù)，在實(shí)驗(yàn)中該值采用文獻(xiàn)[7]的默認(rèn)設(shè)置，即γs=1。

3.3　基于多層隨機(jī)游走的異構(gòu)社區(qū)挖掘算法

基于隨機(jī)游走的異構(gòu)社區(qū)挖掘算法MLW(multi-layerwalker)采用一種貪婪思想，偽代碼如算法1所示。

算法1異構(gòu)網(wǎng)絡(luò)社區(qū)挖掘算法MLW

1) 根據(jù)式(13)、(17)計(jì)算相似改變矩陣ξ;

4)選定Δζ最小的社區(qū)Ca,Cb∈C;

5)Ck←Ca∪Cb;

8)使用式(18)校準(zhǔn)矩陣Δζ;

9)刪除矩陣行列a,b并添加行列k;

10)endwhile

11)Ctree={C1,C2,…,CH};

12)CP=argmaxCi∈CtreeQM(Ci);

13)returnCP.

算法在計(jì)算相似性改變矩陣時(shí)，最復(fù)雜的是計(jì)算2-hop路徑中轉(zhuǎn)節(jié)點(diǎn)。中轉(zhuǎn)節(jié)點(diǎn)的鄰接情況與平均節(jié)點(diǎn)度成正比，因此時(shí)間開銷為O(n2d)=O(mn)。循環(huán)次數(shù)為層次樹的高度H。由于合并操作的最小量級(jí)為節(jié)點(diǎn)，因此H≤N。算法選擇鄰接社區(qū)進(jìn)行合并，因此循環(huán)部分的復(fù)雜度為O(d)≤O(n)?？梢娝惴?最終的時(shí)間復(fù)雜度為O(mn+dH)=O(mn)。

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

本節(jié)將給出算法在人工合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的運(yùn)行結(jié)果。實(shí)驗(yàn)的運(yùn)行環(huán)境為IntelPentiumIV3.0GHz處理器，2GB內(nèi)存，WindowsXP操作系統(tǒng)，算法采用C++與MATLAB7.1混合編程。選擇Dong等[13]提出的SC-ML(spectralclusteringonmulti-layergraphs)算法以及Tang等[14]提出的LBSM(latentblockspectralmodularity)算法進(jìn)行比對(duì)。前者是1種新的多層級(jí)聚類算法，后者采用多目標(biāo)優(yōu)化并被認(rèn)為具有較高的社區(qū)識(shí)別精度。

4.1　人工合成網(wǎng)絡(luò)社區(qū)挖掘性能

人工合成網(wǎng)絡(luò)在生成時(shí)可根據(jù)相應(yīng)的規(guī)則生成一些“固有存在”的社區(qū)(Ground-truth)，因此與固有社區(qū)之間的差距越小則所提出的算法性能越優(yōu)。本文用歸一化互信息(normalizedmutualinformation，NMI)[16]度量2種劃分結(jié)果之間的差別，其定義為

(20)

當(dāng)劃分CA與CB完全一致時(shí)NMI(CA,CB)=1，當(dāng)劃分CA與劃分CB完全不同時(shí)NMI(CA,CB)=0。

實(shí)驗(yàn)1利用文獻(xiàn)[14]提供的MATLAB人工數(shù)據(jù)生成器，生成含有350個(gè)節(jié)點(diǎn)，4種不同社會(huì)關(guān)系的異質(zhì)社會(huì)網(wǎng)絡(luò)，其中內(nèi)含3個(gè)Ground-truth社區(qū)，每個(gè)社區(qū)約含50，100以及200個(gè)節(jié)點(diǎn)。

如圖2所示，在分別標(biāo)記為L1~L4的單質(zhì)網(wǎng)絡(luò)中，3種算法的NMI指數(shù)平均約為0.8(MLK)、0.74(LBSM)以及0.72(SC-ML)，可見本文算法所得的社區(qū)結(jié)果與Ground-truth社區(qū)更為接近，因此具有較高的性能。當(dāng)處理對(duì)象為異構(gòu)網(wǎng)絡(luò)時(shí)(在本文中被標(biāo)記為LM)，由于異質(zhì)關(guān)系的糾纏特性，3種算法普遍所得NMI值較低。在本情況中，MLW算法的NMI指數(shù)約為0.65，平均超出LBSM和SC-ML約24%，這說明本文提出的異構(gòu)隨機(jī)游走方案是有效的，能夠真實(shí)的挖掘異構(gòu)網(wǎng)絡(luò)潛在的社區(qū)結(jié)構(gòu)。

圖2　人工合成網(wǎng)絡(luò)性能比較(數(shù)據(jù)源自文獻(xiàn)[14])Fig.2　Performance comparison of synthetic datasets (data comes from [14])

實(shí)驗(yàn)2人工合成數(shù)據(jù)集LFRBenchmark[16]。本實(shí)驗(yàn)考察子網(wǎng)絡(luò)鏈接關(guān)系波動(dòng)較大時(shí)各算法的表現(xiàn)。首先生成了2個(gè)具有5 000個(gè)節(jié)點(diǎn)的單質(zhì)網(wǎng)絡(luò)，然后以此為基礎(chǔ)，通過隨機(jī)添加或刪除鏈接來獲得4種不同的社會(huì)關(guān)系，其中各子網(wǎng)的鏈接改變量(networkrandomchange，NRC)分別為NRC=200和NRC=2 000。實(shí)驗(yàn)結(jié)果在圖3和圖4中給出。

通過分析發(fā)現(xiàn)，當(dāng)網(wǎng)絡(luò)改變量較小時(shí)(圖3)，各算法的性能與實(shí)驗(yàn)1類似；但網(wǎng)絡(luò)變化較大時(shí)(圖4)，MLW算法的優(yōu)勢(shì)逐漸變得明顯。這主要是由于：SC-ML算法和LBSN算法采用了模型生成的方法，因此當(dāng)網(wǎng)絡(luò)變化較大時(shí)，該方法使得構(gòu)建的新網(wǎng)絡(luò)與各子網(wǎng)之間的差距都很大，因此偏離了真實(shí)社區(qū)所具有的表現(xiàn)形式。

圖3　人工合成網(wǎng)絡(luò)性能比較(LFR Benchmark，NRC=200)Fig.3　Performance comparison of synthetic datasets (LFR Benchmark, NRC=200)

圖4　人工合成網(wǎng)絡(luò)性能比較(LFR Benchmark，NRC=2 000)Fig.4　Performance comparison of synthetic datasets (LFR Benchmark, NRC=2 000)

實(shí)驗(yàn)3LFRBenchmark運(yùn)行效率分析。本節(jié)考察MLW在不同規(guī)模網(wǎng)絡(luò)上的運(yùn)行效率，用LFRBenchmark生成了8個(gè)節(jié)點(diǎn)個(gè)數(shù)從1 000~8 000不等的網(wǎng)絡(luò)結(jié)構(gòu)。如圖5所示，MLW算法的運(yùn)行時(shí)間隨著數(shù)據(jù)集規(guī)模的增大近似呈線性增長，算法在節(jié)點(diǎn)數(shù)為8 000時(shí)運(yùn)行時(shí)間約為7.2s。實(shí)際上MLW算法在網(wǎng)絡(luò)規(guī)模不斷變大的情況下競(jìng)爭力更強(qiáng)，這是因?yàn)殡m然算法在計(jì)算初始相似改變矩陣時(shí)占據(jù)了部分時(shí)間，但后續(xù)的運(yùn)行僅需校準(zhǔn)原矩陣?？梢奙LW算法在規(guī)模較大的數(shù)據(jù)集上也可以令人滿意的時(shí)間開銷挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

圖5　各算法的運(yùn)行時(shí)間Fig.5　The runtime of the different algorithms

4.2　真實(shí)網(wǎng)絡(luò)社區(qū)挖掘性能

實(shí)驗(yàn)4DBLP數(shù)據(jù)集。來源于2000~2010年計(jì)算機(jī)科學(xué)權(quán)威會(huì)議網(wǎng)站，按會(huì)議等級(jí)從中抽取了13個(gè)不同的學(xué)科領(lǐng)域(如表1所示)，將其壓縮為約35個(gè)會(huì)議、18 000個(gè)學(xué)者和10 000篇文獻(xiàn)。本文將研究者作為網(wǎng)絡(luò)節(jié)點(diǎn)，將13種研究領(lǐng)域作為節(jié)點(diǎn)間的異構(gòu)鏈接，進(jìn)而生成了異構(gòu)關(guān)系圖。真實(shí)網(wǎng)絡(luò)不存在Ground-truth社區(qū)，因此本實(shí)驗(yàn)主要考察算法的模塊度(文獻(xiàn)[7])和運(yùn)行效率。

圖6的橫坐標(biāo)標(biāo)記各領(lǐng)域的類別，合成后的異構(gòu)網(wǎng)絡(luò)用NM加以標(biāo)識(shí)。MLW算法具有最高的模塊度指標(biāo)，而LBSM和SC-ML算法則模塊度相對(duì)較低。這主要是由于這2種算法在社區(qū)識(shí)別的過程中忽略了各子網(wǎng)間節(jié)點(diǎn)的吸引力。LBSM采用了模塊度優(yōu)化，因此略勝于SC-ML。此外SC-ML算法將相似程度較低的領(lǐng)域整合為同一網(wǎng)絡(luò)也是其模塊度較低的原因。在運(yùn)行時(shí)間方面，LBSM和SCML需要大量的準(zhǔn)備工作，因此時(shí)間開銷較大。相比之下，MLW除在算法初期需要計(jì)算相似改變矩陣外，其他過程均為校準(zhǔn)操作，因此具有較高的效率。

表1　13種會(huì)議領(lǐng)域清單Table 1　The details of 13 conferences

(a) 模塊度

(b)運(yùn)行時(shí)間圖6　DBLP網(wǎng)絡(luò)各算法性能比較Fig.6　Performance comparison on DBLP networks

如圖7所示，由于該數(shù)據(jù)集的社區(qū)結(jié)構(gòu)不是十分明顯，因此3種算法模塊度均較低。相比之下MLW算法約超出LBSM算法和SC-ML算法12.3%和22.1%。在社區(qū)個(gè)數(shù)方面，由于MLW算法充分考慮了各子網(wǎng)間的吸引程度，因此穩(wěn)定性較強(qiáng)，從圖7(b)中可以看出，MLW始終能夠保持識(shí)別的社區(qū)個(gè)數(shù)為3，而LBSM和SC-ML則波動(dòng)較大。不同的是LBSM在單質(zhì)網(wǎng)絡(luò)上較為穩(wěn)定，但網(wǎng)絡(luò)合成為異構(gòu)網(wǎng)絡(luò)時(shí)，由于其多目標(biāo)的優(yōu)化策略，因此識(shí)別出的社區(qū)數(shù)大于Ground-truth社區(qū)數(shù)。與之相反，SC-ML選擇在合成后的網(wǎng)絡(luò)上進(jìn)行社區(qū)識(shí)別，因此當(dāng)處理對(duì)象為異構(gòu)網(wǎng)絡(luò)時(shí)，準(zhǔn)確率提高。

(a)模塊度

(b)社區(qū)個(gè)數(shù)圖7　Iris數(shù)據(jù)網(wǎng)絡(luò)各算法性能比較Fig.7　Performance comparison on Iris data networks

5結(jié)束語

本文提出一種基于隨機(jī)游走的異質(zhì)社區(qū)識(shí)別算法，重要研究了隨機(jī)游走在異質(zhì)網(wǎng)絡(luò)中的跨層級(jí)游走特性。首先設(shè)計(jì)了節(jié)點(diǎn)的同社區(qū)互可達(dá)游走約束，進(jìn)而提出異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)相似性度量函數(shù)；然后基于貪婪的層次化聚類算法將相似性較高的節(jié)點(diǎn)合并為同一社區(qū)。由于算法在迭代過程中采用了局部化的校準(zhǔn)策略，因此具有較低的時(shí)間開銷。在今后的工作中，將重點(diǎn)研究動(dòng)態(tài)社交網(wǎng)絡(luò)中的異質(zhì)社區(qū)識(shí)別方法，實(shí)現(xiàn)對(duì)真實(shí)世界的精準(zhǔn)感知。

參考文獻(xiàn)：

[1]XIE J, KELLEY S, SZYMANSKI B K. Overlapping community detection in networks: the state of the art and comparative study[J]. ACM Computing Surveys, 2013, 45(4): 43.

[2]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.

[3]BRANDES U, DELLING D, GAERTLER M, et al. On modularity clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(2): 172-188.

[4]鄧琨, 張健沛, 楊靜. 利用改進(jìn)遺傳算法進(jìn)行復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 2013, 34(11): 1438-1444.DENG Kun, ZHANG Jianpei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University, 2013, 34(11): 1438-1444.

[5]DUAN Lian, STREET W N, LIU Yanchi, et al. Community detection in graphs through correlation[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,USA, 2014: 1376-1385.

[6]LIU Chenlong, LIU Jing, JIANG Zhongzhou. A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks[J]. IEEE Transactions on Cybernetics, 2014, 44(12): 2274-2287.

[7]MUCHA P J, RICHARDSON T, MACON K, et al. Community structure in time-dependent, multiscale, and multiplex networks[J]. Science, 2010, 328(5980): 876-878.

[8]RADICCHI F. Detectability of communities in heterogeneous networks[J]. Physical Review E, 2013, 88(1): 010801.

[9]DONG Xiaowen, FROSSARD P, VANDERGHEYNST P, et al. Clustering with multi-layer graphs: A spectral perspective[J]. IEEE Transactions on Signal Processing, 2012, 60(11): 5820-5831.

[10]BERLINGERIO M, PINELLI F, CALABRESE F. ABACUS: frequent pattern mining-based community discovery in multidimensional networks[J]. Data Mining and Knowledge Discovery, 2013, 27(3): 294-320.

[11]YIN Qiyue, WU Shu, HE Ran, et al. Multi-view clustering via pairwise sparse subspace presentation[J]. Neurocomputing, 2015, 156: 12-21.

[12]FIORI S, KANEKO T, TANAKA T. Tangent-bundle maps on the Grassmann manifold: Application to empirical arithmetic averaging[J]. IEEE Transactions on Signal Processing, 2015, 63(1): 155-168.

[13]DONG Xiaowen, FROSSARD P, VANDERGHEYNST P, et al. Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds[J]. IEEE Transactions on Signal Processing, 2014, 62(4): 905-918.

[14]TANG Lei, WANG Xufei, LIU Huan. Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery, 2012, 25(1): 1-33.

[15]PONS P, LATAPY M. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms and Applications, 2006, 10(2): 191-218.

[16]LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80: 016118.

Community detection in heterogeneous

social networks using 2-hop random walks

YANG Hailu1,2,3, ZHANG Jianpei3, YANG Jing3

(1. Computer Science and Technology Postdoctoral Workstation, Harbin University of Science and Technology, Harbin 150080; 2. College

of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China; 3. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Abstract：In order to solve the problem of identifying community structures in heterogeneous social networks, a hierarchical community detection algorithm was proposed based on random walks. A heterogeneous random walk model was built by measuring the attraction between network layers and the transition probability between nodes in homogeneous networks. Then, a heterogeneous network node similarity function was proposed based on 2-hop mutual random walks. Finally, the similarity function was extended to hierarchical clustering so the multi-relational community structure could be obtained iteratively in a relatively short period of time. Competitive experiments on both synthesized and real-world social networks demonstrate the effectiveness and feasibility of the proposed algorithm.

Keywords：heterogeneous social networks; community detection; random walks; similarity measurement; hierarchical clustering

通信作者：張健沛,E-mail:zhangjianpei@hrbeu.edu.cn.

作者簡介：楊海陸(1985-)，男，講師；

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61202274，61370083，61402126)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20112304110011，20122304110012).

收稿日期：2014-11-03.網(wǎng)絡(luò)出版日期：2015-11-06.

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-7043(2015)12-1626-06

doi:10.11990/jheu.201411008