楊海陸, 張健沛, 楊靜

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

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

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

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

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

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

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

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

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

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

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

1隨機游走的基本概念

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

(1)

(2)

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

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

2基于隨機游走的節(jié)點相似性度量

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

(3)

(4)

(5)

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

(6)

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

(7)

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

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

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

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

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

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

(8)

(9)

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

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

(10)

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

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

(11)

(12)

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

(13)

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

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

3.1　社區(qū)合并選擇

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

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

(14)

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

(15)

(16)

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

(17)

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

(18)

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

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

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

(19)

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

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

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

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

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

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.

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

4實驗結(jié)果與分析

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

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

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

(20)

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

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

如圖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)處理對象為異構(gòu)網(wǎng)絡(luò)時(在本文中被標(biāo)記為LM)，由于異質(zhì)關(guān)系的糾纏特性，3種算法普遍所得NMI值較低。在本情況中，MLW算法的NMI指數(shù)約為0.65，平均超出LBSM和SC-ML約24%，這說明本文提出的異構(gòu)隨機游走方案是有效的，能夠真實的挖掘異構(gòu)網(wǎng)絡(luò)潛在的社區(qū)結(jié)構(gòu)。

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

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

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

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

圖5　各算法的運行時間Fig.5　The runtime of the different algorithms

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

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

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

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

(a) 模塊度

(b)運行時間圖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ū)個數(shù)方面，由于MLW算法充分考慮了各子網(wǎng)間的吸引程度，因此穩(wěn)定性較強，從圖7(b)中可以看出，MLW始終能夠保持識別的社區(qū)個數(shù)為3，而LBSM和SC-ML則波動較大。不同的是LBSM在單質(zhì)網(wǎng)絡(luò)上較為穩(wěn)定，但網(wǎng)絡(luò)合成為異構(gòu)網(wǎng)絡(luò)時，由于其多目標(biāo)的優(yōu)化策略，因此識別出的社區(qū)數(shù)大于Ground-truth社區(qū)數(shù)。與之相反，SC-ML選擇在合成后的網(wǎng)絡(luò)上進行社區(qū)識別，因此當(dāng)處理對象為異構(gòu)網(wǎng)絡(luò)時，準(zhǔn)確率提高。

(a)模塊度

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

5結(jié)束語

本文提出一種基于隨機游走的異質(zhì)社區(qū)識別算法，重要研究了隨機游走在異質(zhì)網(wǎng)絡(luò)中的跨層級游走特性。首先設(shè)計了節(jié)點的同社區(qū)互可達游走約束，進而提出異質(zhì)網(wǎng)絡(luò)節(jié)點相似性度量函數(shù)；然后基于貪婪的層次化聚類算法將相似性較高的節(jié)點合并為同一社區(qū)。由于算法在迭代過程中采用了局部化的校準(zhǔn)策略，因此具有較低的時間開銷。在今后的工作中，將重點研究動態(tài)社交網(wǎng)絡(luò)中的異質(zhì)社區(qū)識別方法，實現(xiàn)對真實世界的精準(zhǔ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]鄧琨, 張健沛, 楊靜. 利用改進遺傳算法進行復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)[J]. 哈爾濱工程大學(xué)學(xué)報, 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-)，男，講師；

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

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

中圖分類號：TP301.6

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

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

doi:10.11990/jheu.201411008