基于隨機游走的級聯(lián)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

王亮 楊海陸 陳德運

摘要：隨著Web 2.0的不斷推廣以及社交應(yīng)用的不斷普及，在線社交網(wǎng)絡(luò)結(jié)構(gòu)分析得到了各領(lǐng)域?qū)W者的廣泛關(guān)注。社區(qū)是網(wǎng)絡(luò)中內(nèi)嵌的密集群組，保證了社區(qū)內(nèi)部用戶的強相關(guān)性和一致性，因此廣泛應(yīng)用于病毒防護、商品推薦等現(xiàn)實系統(tǒng)。本文提出一種基于隨機游走的級聯(lián)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，主要解決非直連節(jié)點間的相似性度量問題。提出一種基于2-hop隨機游走的局部可達性計算方法，通過對游走終點一致的節(jié)點進行層次聚類，社區(qū)結(jié)構(gòu)可在較短的時間內(nèi)迭代生成。實驗結(jié)果表明，本方法在級聯(lián)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中具有較高的性能和效率，對星形社區(qū)具有較高的匹配性。

關(guān)鍵詞： 級聯(lián)網(wǎng)絡(luò); 社區(qū)發(fā)現(xiàn); 隨機游走; 層次聚類

【Abstract】 With the continuous promotion of Web 2.0 and the continuous popularization of social applications， the structural analysis of online social networks has attracted extensive attention from scholars in various fields. Community is a dense group embedded in the network， which ensures the strong correlation and consistency of users within the community. Therefore， it is widely used in virus protection， commodity recommendation， and other practical systems. In this paper， a cascade network community discovery algorithm based on the random walk is proposed to solve the similarity measurement problem of non-directly connected nodes. The paper proposes a local reachability calculation method based on 2-hop random walks. The community structure can be generated iteratively in a short time by hierarchical clustering of nodes with consistent endpoints. The experimental results show that this method has high performance and efficiency in cascaded network community detection and has a high matching to the star community.

【Key words】 ?cascaded network; community detection; random walks; hierarchical clustering

0 引 言

隨著5G技術(shù)的不斷推廣以及“互聯(lián)網(wǎng)+”戰(zhàn)略的積極部署，微信、微博等社交網(wǎng)絡(luò)早已融入人們的日常生活及學習之中。更多的人選擇在社交網(wǎng)絡(luò)進行交流、發(fā)表觀點，社交網(wǎng)絡(luò)早已成為現(xiàn)實世界在網(wǎng)絡(luò)空間的真實縮影，社交網(wǎng)絡(luò)結(jié)構(gòu)分析也因此成為各學科領(lǐng)域的研究熱點和學術(shù)前沿問題。

社區(qū)結(jié)構(gòu)（Community）是社交網(wǎng)絡(luò)中的重要結(jié)構(gòu)，社區(qū)內(nèi)部用戶之間的鏈接較為緊密，社區(qū)之間的用戶鏈接較為稀疏。從這一角度來看，社區(qū)結(jié)構(gòu)可以廣泛應(yīng)用于諸如商品推薦、病毒防護等應(yīng)用系統(tǒng)。例如，可以對社區(qū)內(nèi)部用戶推薦相似的產(chǎn)品，或切斷社區(qū)之間的聯(lián)系降低病毒的傳播范圍等。級聯(lián)網(wǎng)絡(luò)是一種特殊的社交網(wǎng)絡(luò)，微博網(wǎng)絡(luò)就是典型的級聯(lián)網(wǎng)絡(luò)，這種網(wǎng)絡(luò)中普遍存在星形結(jié)構(gòu)（形成于對高影響力用戶的大量關(guān)注），就使得社區(qū)內(nèi)部節(jié)點可能不具有直接聯(lián)系，這給社區(qū)識別任務(wù)帶來了極大的挑戰(zhàn)。

目前來看，基于隨機游走的動態(tài)算法能夠有效解決這一問題，其基本原理利用了社區(qū)結(jié)構(gòu)對“游走者”的捕獲作用。當“游走者”游走到社區(qū)邊緣時，由于社區(qū)內(nèi)部鏈接遠大于社區(qū)間的鏈接，因此“游走者”有極大的概率再次游走回社區(qū)內(nèi)部。由此可見，位于相同社區(qū)的兩節(jié)點，其隨機游走的探測路徑應(yīng)該具有較高的重疊性。Rosvall等人[1]引入一種信息論方法，揭示加權(quán)有向網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。通過將網(wǎng)絡(luò)隨機游走的概率流作為真實系統(tǒng)中的信息流，社區(qū)結(jié)構(gòu)可以由概率流壓縮生成。Huang等人[2]探討隨機游走思想在構(gòu)建社區(qū)模塊度函數(shù)中的應(yīng)用。在這種方法中，模塊度函數(shù)被定義為社區(qū)引起的馬爾可夫隨機游走和一個零概率模型的之間的差異。劉陽等人[3]提出一種邊權(quán)預(yù)處理方法，根據(jù)多重隨機游走對網(wǎng)絡(luò)連接的遍歷情況重新衡量網(wǎng)絡(luò)邊權(quán)。預(yù)處理后的邊權(quán)作為網(wǎng)絡(luò)拓撲的有效補充信息，能夠?qū)⒕W(wǎng)絡(luò)結(jié)構(gòu)去模糊化，從而改善現(xiàn)有算法的社區(qū)發(fā)現(xiàn)性能。楊海陸等人[4]設(shè)計了一種基于2-hop互隨機游走的異質(zhì)網(wǎng)絡(luò)節(jié)點相似性度量函數(shù)，通過將相似性函數(shù)推廣到層次聚類并設(shè)計相應(yīng)的相似矩陣校準方案，異質(zhì)社區(qū)識別任務(wù)可以在較短的時間內(nèi)迭代完成。辛宇等人[5]提出一種改進的語義社會網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)隨機游走策略，以LDA（Latent Dirichlet Allocation）算法為基礎(chǔ)建立語義空間，實現(xiàn)節(jié)點語義信息到語義空間的量化映射。在后續(xù)的研究中，Xin等人[6]提出適應(yīng)性隨機游走概念，將模型推廣至動態(tài)社區(qū)識別任務(wù)。在最近的研究中，Okuda等人[7]提出了一種帶約束隨機行走相似性度量方法檢測圖的社區(qū)結(jié)構(gòu)。其基本思想是隨機游走能夠途經(jīng)相似節(jié)點的起始點屬于同一社區(qū)的可能性較大。

上述方法在社區(qū)識別領(lǐng)域得到了普遍認可，但忽略了以下兩方面要素。首先，沒有對游走長度進行約束，這使得“游走者”能夠捕獲的信息處于不確定狀態(tài);其次，上述方法普遍拒絕“游走者”重復(fù)訪問已經(jīng)通過的頂點，而這一情況在密度較高的社區(qū)中是普遍存在的。

為了解決這一問題，提出一種基于2-hop結(jié)構(gòu)探測的社區(qū)識別方法?；舅悸肥牵喝绻坝巫哒摺钡钠鹗键c位于相同社區(qū)，則“游走者”能夠囊括的2-hop探測節(jié)點集應(yīng)該具有較高的重疊性。該思想充分考慮了節(jié)點的直接相似性和結(jié)構(gòu)相似性，因此識別出的社區(qū)結(jié)構(gòu)具有一定的穩(wěn)定性。

1 定義及算法

3.2 真實網(wǎng)絡(luò)社區(qū)識別結(jié)果

本部分選擇新浪微博作為實驗數(shù)據(jù)。由于新浪微博API存在爬取數(shù)量限制，因此使用Python編寫了面向網(wǎng)頁的微博爬蟲程序，結(jié)果存于MySQL數(shù)據(jù)庫中。

收集了2018年10月～2019年9月共12個月用戶所發(fā)的微博帖子，選取任意網(wǎng)絡(luò)節(jié)點作為初始爬取節(jié)點，采用自底向上的方法爬取初始節(jié)點的6層鄰居結(jié)構(gòu)。向上爬取的主要原因在于大多數(shù)微博用戶的粉絲數(shù)量遠遠大于關(guān)注數(shù)量，因此如果向下爬取數(shù)據(jù)，廣度優(yōu)先會造成過大的時間開銷。最終爬取到的數(shù)據(jù)量較為龐大，因此過濾掉了微博數(shù)少于50的用戶以及關(guān)注數(shù)/被關(guān)注數(shù)少于5的用戶。

研究中關(guān)注于社區(qū)模塊度以及社區(qū)個數(shù)，實驗結(jié)果如圖7、圖8所示。

從實驗結(jié)果來看，HCD算法的模塊度函數(shù)略小于COPRA，優(yōu)于其他5種方法。原因在于微博網(wǎng)絡(luò)具有典型的級聯(lián)特性，星形結(jié)構(gòu)更加清晰，因此社區(qū)粒度普遍較低。HCD識別社區(qū)個數(shù)較少，這表明HCD的局部游走策略是有效的，并且具有較高的效率。

為了更清晰地給出HCD算法的社區(qū)識別結(jié)果，研究還選擇了節(jié)點數(shù)較少的Football網(wǎng)絡(luò)給出社區(qū)識別結(jié)果。如圖9所示，HCD識別出的社區(qū)結(jié)構(gòu)具有較低的粒度，但總體來看，仍然保證了較高的緊密性。

4 結(jié)束語

針對基于隨機游走的社區(qū)識別方法無法有效識別級聯(lián)網(wǎng)絡(luò)中的星形社區(qū)這一問題，提出一種帶約束隨機游走的社區(qū)識別方法HCD。首先定義了隨機游走的探測集合以及探測集重疊性度量函數(shù)，然后設(shè)計了一種面向社區(qū)迭代的相似性度量函數(shù)以及相似性矩陣校準方法，最后采用層次化聚類方法輸出社區(qū)結(jié)果。在人工合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上的實驗結(jié)果表明，HCD算法能夠有效地度量非直連節(jié)點之間的相似性，在星形社區(qū)識別中具有較高的性能和效率。

參考文獻

[1] ROSVALL M， BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences of the United States of America， 2018，105（4）： 1118.

[2]HUANG L C， YEN T J， CHOU S C T. Community detection in dynamic social networks： A random walk approach[C]//International Conference on Advances in Social Networks Analysis and Mining （ASONAM 2011）. Kaohsiung，Taiwan：[s.n.]，2011： 110.

[3]劉陽， 季新生， 劉彩霞. 網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)優(yōu)化： 基于隨機游走的邊權(quán)預(yù)處理方法[J]. 電子與信息學報， 2013， 35（10）： 2335.

[4]楊海陸， 張健沛， 楊靜. 利用2-hop隨機游走進行異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[J]. 哈爾濱工程大學學報， 2015， 36（12）： 1626.

[5]辛宇， 楊靜， 謝志強. 基于隨機游走的語義重疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機研究與發(fā)展， 2015， 52（2）： 499.

[6]XIN Y， XIE Z Q， YANG J， et al. An adaptive random walk sampling method on dynamic community detection[J]. Expert Systems With Applications，2016， 58： 10.

[7]OKUDA M， SATOH S， SATO Y， et al. Community detection using restrained random-walk similarity[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2019： 1-1（ Early Access ）.