基于隨機游走的級聯網絡社區發現算法

王亮 楊海陸 陳德運

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

關鍵詞： 級聯網絡; 社區發現; 隨機游走; 層次聚類

【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技術的不斷推廣以及“互聯網+”戰略的積極部署，微信、微博等社交網絡早已融入人們的日常生活及學習之中。更多的人選擇在社交網絡進行交流、發表觀點，社交網絡早已成為現實世界在網絡空間的真實縮影，社交網絡結構分析也因此成為各學科領域的研究熱點和學術前沿問題。

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

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

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

為了解決這一問題，提出一種基于2-hop結構探測的社區識別方法。基本思路是：如果“游走者”的起始點位于相同社區，則“游走者”能夠囊括的2-hop探測節點集應該具有較高的重疊性。該思想充分考慮了節點的直接相似性和結構相似性，因此識別出的社區結構具有一定的穩定性。

1 定義及算法

3.2 真實網絡社區識別結果

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

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

研究中關注于社區模塊度以及社區個數，實驗結果如圖7、圖8所示。

從實驗結果來看，HCD算法的模塊度函數略小于COPRA，優于其他5種方法。原因在于微博網絡具有典型的級聯特性，星形結構更加清晰，因此社區粒度普遍較低。HCD識別社區個數較少，這表明HCD的局部游走策略是有效的，并且具有較高的效率。

為了更清晰地給出HCD算法的社區識別結果，研究還選擇了節點數較少的Football網絡給出社區識別結果。如圖9所示，HCD識別出的社區結構具有較低的粒度，但總體來看，仍然保證了較高的緊密性。

4 結束語

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

參考文獻

[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]劉陽， 季新生， 劉彩霞. 網絡社區發現優化： 基于隨機游走的邊權預處理方法[J]. 電子與信息學報， 2013， 35（10）： 2335.

[4]楊海陸， 張健沛， 楊靜. 利用2-hop隨機游走進行異質網絡社區發現[J]. 哈爾濱工程大學學報， 2015， 36（12）： 1626.

[5]辛宇， 楊靜， 謝志強. 基于隨機游走的語義重疊社區發現算法[J]. 計算機研究與發展， 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 ）.