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

王亮 楊海陸 陳德運(yù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)部用戶的強(qiáng)相關(guān)性和一致性，因此廣泛應(yīng)用于病毒防護(hù)、商品推薦等現(xiàn)實(shí)系統(tǒng)。本文提出一種基于隨機(jī)游走的級聯(lián)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，主要解決非直連節(jié)點(diǎn)間的相似性度量問題。提出一種基于2-hop隨機(jī)游走的局部可達(dá)性計(jì)算方法，通過對游走終點(diǎn)一致的節(jié)點(diǎn)進(jìn)行層次聚類，社區(qū)結(jié)構(gòu)可在較短的時間內(nèi)迭代生成。實(shí)驗(yàn)結(jié)果表明，本方法在級聯(lián)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中具有較高的性能和效率，對星形社區(qū)具有較高的匹配性。

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

【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ò)早已融入人們的日常生活及學(xué)習(xí)之中。更多的人選擇在社交網(wǎng)絡(luò)進(jìn)行交流、發(fā)表觀點(diǎn)，社交網(wǎng)絡(luò)早已成為現(xiàn)實(shí)世界在網(wǎng)絡(luò)空間的真實(shí)縮影，社交網(wǎng)絡(luò)結(jié)構(gòu)分析也因此成為各學(xué)科領(lǐng)域的研究熱點(diǎn)和學(xué)術(shù)前沿問題。

社區(qū)結(jié)構(gòu)（Community）是社交網(wǎng)絡(luò)中的重要結(jié)構(gòu)，社區(qū)內(nèi)部用戶之間的鏈接較為緊密，社區(qū)之間的用戶鏈接較為稀疏。從這一角度來看，社區(qū)結(jié)構(gòu)可以廣泛應(yīng)用于諸如商品推薦、病毒防護(hù)等應(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é)點(diǎn)可能不具有直接聯(lián)系，這給社區(qū)識別任務(wù)帶來了極大的挑戰(zhàn)。

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

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

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

1 定義及算法

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[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)化： 基于隨機(jī)游走的邊權(quán)預(yù)處理方法[J]. 電子與信息學(xué)報， 2013， 35（10）： 2335.

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

[5]辛宇， 楊靜， 謝志強(qiáng). 基于隨機(jī)游走的語義重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(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 ）.