基于鏈路結構和轉發(fā)行為的微博社交網絡重疊社區(qū)劃分方法

張中軍，于來行，李潤川

(1.周口師范學院 計算機科學與技術學院 河南 周口 466001；2.農產品質量安全追溯技術河南省工程實驗室 河南 周口 466001；3.鄭州大學 互聯網醫(yī)療與健康服務河南省協同創(chuàng)新中心 河南 鄭州 450001；4.鄭州大學 產業(yè)技術研究院 河南 鄭州 450001)

0 引言

微博社交網絡社區(qū)挖掘對于阻斷網絡謠言傳播和輿情監(jiān)測有重要作用，并且，對個性化服務推薦和廣告精準投放等商業(yè)應用也有重要意義。近年來，社交網絡社區(qū)劃分方法的研究成為計算機領域比較熱門的課題。Chouchani等[1]提出一種基于用戶興趣的社區(qū)挖掘方法，以興趣為側重點衡量用戶關系、發(fā)現社區(qū)。Mahabadi等[2]設計一種標簽傳播算法，無須使用預先訓練或符合特定要求的預定義特征，就能獲得更好的加速比和半確定性結果。Liu等[3]推導出計算局部重疊模塊化增量的新公式，可以準確而快速地找到重疊的社區(qū)，減少運算時間，并設計了一種新的相似度度量來減小孤立群體的影響。Kumar等[4]提出了一種基于雙目標函數的重疊社區(qū)檢測方法，運用兩個目標函數分別實現最大化社區(qū)內部連接密度和最小化社區(qū)外部連接密度。Messaoudi等[5]將重疊社區(qū)檢測問題轉化為優(yōu)化問題，并設計了一種新的優(yōu)化算法來求解所建立的優(yōu)化模型，提出了一種混合元啟發(fā)式方法來檢測網絡中的重疊社區(qū)。Trivedi等[6]提出了一種基于容忍度鄰域的混合計算方法來檢測社交網絡中的重疊社區(qū),成功將平面劃分方法應用于社區(qū)挖掘。李政廉等[7]引入網絡節(jié)點的社區(qū)連通度得分和鄰域連通度得分，提出基于局部信息的快速重疊社區(qū)檢測算法，能夠挖掘出近似最優(yōu)的社區(qū)，收獲了低復雜度。Kumar等[8]設計了基于鄰域鄰近度的加權網絡重疊社區(qū)結構檢測算法，綜合了相鄰接點的鄰近度和網絡邊的權重，更適合有權重區(qū)分的網絡結構。Javed等[9]從傳統到最新，回顧了當前流行的社區(qū)檢測算法，重點介紹了基于非負矩陣分解等降維技術。Hajiabadi等[10]通過一個集成的框架來提取重疊和非重疊的社區(qū)結構，而不需要依賴于網絡上的先驗結構連通性。杜航原等[11]基于搜索密度峰值的聚類思想設計了一種網絡節(jié)點的中心性度量模型，用網絡節(jié)點的內聚度和分離度，分別描述網絡社區(qū)內部連接稠密和外部連接稀疏的結構特征。閆涵等[12]和陳珂等[13]分別在微博用戶興趣度和文本情感分析的應用方面取得了較好的成果，對于社交網絡社區(qū)挖掘有較高的參考價值。Newman[14]利用模塊度衡量社區(qū)結構的質量，提出了基于貪心思想的快速算法，社區(qū)挖掘效果較好。Blondel等[15]提出了檢測大型網絡社區(qū)結構的方法，引入模塊度增量決定節(jié)點的歸屬，并且每次迭代基于單節(jié)點的處理，能應用于大規(guī)模社交網絡，減少時間開銷，給本文的研究提供了啟發(fā)。

1 重疊社區(qū)劃分方法

微博社交網絡由用戶作為網絡節(jié)點，用戶之間的關注關系作為網絡連邊，現實情況下，用戶之間的關注關系具有方向性，所以，微博社交網絡中的邊為有向邊，微博社交網絡可以看成一個有向圖D=〈V,E〉，其中：V是D中的節(jié)點集；E是有向邊的集合，E中的每一個元素均是有序偶〈u,v〉。

1.1 鏈路結構

微博社交媒體中，用戶之間為關注或不關注關系，在構造的社交網絡中，A關注B表示A到B存在一條有向邊，并且此邊無權重區(qū)別，所以，傳統網絡社區(qū)劃分方法中，以邊的權重來度量節(jié)點之間距離的方法不適用于微博社交網絡。本文根據微博用戶之間的關注關系構成的網絡拓撲中鏈路結構緊密度來衡量節(jié)點之間關系的緊密度。在網絡拓撲結構中，用戶節(jié)點之間的關系又分為直接相鄰和非直接相鄰兩種：如果x，y∈V，并且〈x，y〉∈E，則表示兩者之間存在直接關注關系，關系相對緊密；如果x和y之間非直接相鄰，則兩者之間的關系緊密度相對較弱。用戶節(jié)點x和y之間鏈路緊密度計算方法為

(1)

式中：dxy表示節(jié)點x到y的入度，即x是否關注了y，如果x關注了y，則dxy=1，否則dxy=0；dyx表示節(jié)點y到x的入度，即y是否關注了x，如果y關注了x，則dyx=1，否則dyx=0；n表示節(jié)點x和y之間建立最短通路需要經過的結點個數，1/(n+2)是兩者之間緊密度權重，建立最短通路需要經過的節(jié)點越多，兩者關系越松散；Exy表示x和y之間建立最短通路所經過的邊的數量，計算公式為

其中：vxy表示節(jié)點x到y之間建立最短通路可能經過的節(jié)點的集合，包含節(jié)點x和y；Oij、Iij分別表示i到j的出度值和入度值。IOxy表示節(jié)點x到y所有最短通路經過的節(jié)點的出度和入度總和，計算公式為

其中：Oi表示節(jié)點i的出度；Ii表示節(jié)點i的入度。

1.2 轉發(fā)行為

用戶之間的關注關系相對隨意，無須身份驗證即可關注，并且還存在友好性關注，實際可能并無共同興趣愛好，也無相似的觀點趨向，所以，用戶之間的關注關系并不能完全代表兩者之間關系的緊密度，只能作為度量用戶之間的關系緊密度的一個因素，但不能完全依賴于關注關系這一種度量標準。微博內容能客觀反映出用戶的興趣偏好，并且也可以合理地認為發(fā)布相同或相似內容的用戶之間具有相同的興趣愛好，但是興趣愛好相同或相似并不等于關系緊密，因為兩個完全無關的用戶也可能發(fā)布相同的內容。所以本文考慮使用用戶轉發(fā)行為作為衡量關系密切程度的標準，如果兩個用戶互相轉發(fā)對方微博的數量或者共同轉發(fā)第三個用戶微博的數量較多、兩者微博被第三個用戶轉發(fā)的比例很大，可以認為兩者更可能屬于同一個社區(qū)。

用戶x轉發(fā)用戶k的微博可以用一個向量Pk→x=(pk1→x,pk2→x，…，pkn→x)表示，pkn→x表示用戶x轉發(fā)用戶k第n個微博的情況，pkn→x=1表示轉發(fā)，pkn→x=0表示未轉發(fā)。為方便計算，用戶x自己發(fā)布的微博可以視為自己轉發(fā)自己微博，即Px→x=(1,1,…，1)。用戶x和y對用戶k的微博轉發(fā)相似度計算公式為

用戶x和用戶y發(fā)表的微博被第三個用戶j轉發(fā)的相似度計算公式為sim(Px,y→j)=(nx→j×ny→j)/(Nx×Ny)，其中：Nx、Ny分別表示用戶x和用戶y發(fā)表的微博總數；nx→k、ny→k分別表示用戶x和用戶y發(fā)表的微博被用戶j轉發(fā)的數量。

綜上，用戶x與用戶y在整個社交網絡結構中的轉發(fā)行為相似度計算公式為

用戶x和用戶y之間的聯系緊密度包括兩部分：1)用戶x和用戶y之間的鏈路緊密度linkxy；2)用戶x和用戶y轉發(fā)行為相似度simxy。

用戶x和用戶y之間的緊密度計算公式為Closenessxy=αlinkxy+βsimxy，其中：α和β(α+β=1)分別表示鏈路緊密度和轉發(fā)行為相似度的權重，即對用戶間關系的貢獻度。

1.3 社區(qū)中心的選擇

社交網絡社區(qū)中心也稱為種子節(jié)點，是一個社區(qū)內具有“影響力”的節(jié)點，這類節(jié)點一般具有兩個特點：一是與社區(qū)內其他節(jié)點緊密度較大；二是與其他社區(qū)中心節(jié)點之間的緊密度較小，所以社區(qū)中心的選擇對于社區(qū)劃分的結果非常重要。社區(qū)中心的選擇有社區(qū)中心數量和社區(qū)中心節(jié)點兩個問題。

1)社區(qū)中心數量代表最終社區(qū)的數量，但是實際上在社區(qū)劃分之前，一般不能確定社交網絡當中存在多少社區(qū)結構。在傳統的網絡社區(qū)挖掘中，K-MEANS等經典的聚類方法取得了很好的劃分效果，但是，這類聚類方法共同的缺點就是需要指定社區(qū)數量，這在實際應用中難以做到。Louvain算法[15]是大型網絡社區(qū)結構挖掘算法，它根據模塊度增量確定合并的節(jié)點，自底向上進行合并，直到整個網絡的模塊度不再變化或者變化極小。因為合并后節(jié)點急劇減少，所以能夠處理大規(guī)模網絡結構，并且時間開銷較少，效率高。本文使用該算法來確定社區(qū)數量，因為只是確定大致社區(qū)數量，對社區(qū)質量要求不高，所以此處利用鏈接緊密度作為度量即可。算法執(zhí)行停止后產生的社區(qū)數量即為該社交網絡內包含的社區(qū)結構數量。

2)社區(qū)中心節(jié)點是社區(qū)的核心，確定社區(qū)數量之后，就要選出相應數量的中心節(jié)點，本文算法選擇社區(qū)中心節(jié)點的方法為：將所有節(jié)點形成一個集合，計算所有節(jié)點的出度和入度之和，并降序排列，因為社區(qū)中心局部內聚性強，所以社區(qū)中心的出度和入度之和相對較高；然后取出度與入度之和最高的節(jié)點作為其中一個中心節(jié)點，并計算該節(jié)點與其他每個節(jié)點的鏈接緊密度，根據鏈接緊密度計算公式，鏈接緊密度小于0.5的節(jié)點肯定不相鄰，而中心節(jié)點之間也不可能相鄰，所以選出鏈接緊密度小于0.5的節(jié)點形成新的集合，重復以上步驟，直到取出的中心節(jié)點數與目標社區(qū)數量相等為止。中心節(jié)點選擇算法流程如下。

輸入：社交網絡節(jié)點集合Set，社區(qū)數量M。

輸出：中心節(jié)點集合Center。

S1)forSet集合中的每個節(jié)點I；

S2)計算IOi=Ii+Oi，存儲于集合IO中；

S3)將IO中的元素按節(jié)點度降序排序；

S4)ifIOk最大，將節(jié)點k移入Center集合，標記IOk；

S5)forSet集合中的每個節(jié)點j，j≠k；

S6)iflinkjk≥0.5；

S7)標記IOj；

S8)if 集合IO剩余節(jié)點數小于M減去集合Center節(jié)點數；

S9)撤銷所有已選中心節(jié)點，標記其中出入度最大的節(jié)點，重復S4～S9直到Center集合中元素數等于M；

S10)返回中心節(jié)點集合Center。

在實驗中，對實驗數據進行了清洗，將出度和入度比例比較極端的節(jié)點去除，剩余節(jié)點中，出度或入度偏大的節(jié)點，可能正是要選取的中心節(jié)點，或是社區(qū)重疊的部分，并且，在選擇中心節(jié)點過程中，如果出現剩余節(jié)點數量較少，以至于最終不足M個社區(qū)中心節(jié)點的情況，則說明在已選的中心節(jié)點中，存在幾乎與其他所有節(jié)點均存在直接關注關系的節(jié)點，那么該節(jié)點只有兩種情況：一是出度和入度比較極端的節(jié)點；二是高度重疊的節(jié)點。如果是前者，在數據清洗階段已經處理。如果是后者，該節(jié)點的出入度則異常大，將直接排除，不再作為備選中心節(jié)點。中心節(jié)點選擇的原則就是找出M個出入度較大但又相互聯系松散的節(jié)點。

1.4 節(jié)點所屬社區(qū)分配

另外，對于重疊社區(qū)，主要是發(fā)現節(jié)點是否同時歸屬多個社區(qū)。本文中，如果節(jié)點對多個社區(qū)的歸屬度滿足一定的條件，則認為同屬于多個社區(qū)。假設社區(qū)p中的節(jié)點vi對社區(qū)q的歸屬度滿足φi,q/φi,p>θ(0<θ<1),則將vi作為社區(qū)p和q的重疊節(jié)點，并同時歸屬到社區(qū)p和q中。節(jié)點所屬社區(qū)的分配過程即本文提出的基于鏈路結構和轉發(fā)行為的微博社交網絡重疊社區(qū)劃分方法(algorithm based on link structure and forwarding behavior，ABLF)如下。

輸入：中心節(jié)點集合Center，網絡節(jié)點集合V。

輸出：社區(qū)結構。

S1)確定社區(qū)數量M；

S2)執(zhí)行中心節(jié)點選擇算法，選取M個社區(qū)中心點；

S3)for 集合Center中每個節(jié)點ci；

S4) form=1,2,…，M個社區(qū)；

S5) ifci是第m個社區(qū)的中心；

S6)φci,m=1；

S7) ELSE；

S8)φci,m=0；

S9)forV-Center中的每個節(jié)點vi；

S10) form=1,2,…，M個社區(qū)；

S11)計算φi,m；

S12)將節(jié)點vi歸屬到φi,m最大的第m個社區(qū)；

S13) ifφi,q/φi,m>θ；

S14)將節(jié)點vi作為第m個社區(qū)和第q個社區(qū)的重疊節(jié)點，并歸屬到第q個社區(qū)；

S15)返回M個社區(qū)結構。

2 實驗及結果分析

2.1 實驗數據

本文所用實驗數據為新浪微博數據，使用網絡爬蟲程序，從某一種子節(jié)點開始，爬取該用戶一年內的微博數據，包括該用戶所發(fā)微博內容，以及從他人微博轉發(fā)的內容，并將爬取內容以單文件形式保存下來，然后根據深度優(yōu)先原則遍歷該用戶的粉絲賬號和其關注的賬號，將遍歷到的賬號以隊列形式保存，隊列中的每個賬號都逐個做上述處理。經過一段時間的爬取，實驗室從新浪微博獲取近1 000萬個用戶賬號、關注關系、微博內容。為了實驗應用，實驗室成員從中抽取出三類實驗數據：第1類實驗數據是從爬取的全部數據中抽取出5個訓練數據集，無標記，節(jié)點數分別為97個、121個、105個、154個、139個，數據內部連邊數分別為1 113條、1 407條、1 265條、1 842條、1 611條，用于測試θ取值較優(yōu)點；第2類數據是經過人工標記的NBA籃球、足球聯賽和韓劇相關的微博信息，這些數據組成的社交網絡子網絡中共有133個節(jié)點、1 531條邊，存在重疊節(jié)點；第3類數據是從爬取的所有數據中抽取8 745個節(jié)點和637 051條邊組成的微博社交網絡。三類數據均為清洗后的數據，已將入度過大但出度較小、入度過小但出度較大或出、入度中一方為零的節(jié)點刪除。實驗前，對于前兩類數據，節(jié)點較少，將出、入度或入、出度比例大于100∶1的節(jié)點去除，對于第三類數據，將比例大于1 000∶1的節(jié)點去除。本文將在這三類數據集上用ABLF算法進行實驗并分析實驗結果。

2.2 評價標準

已經過人工標記的實驗數據可以采用準確率、召回率和F1值來衡量社區(qū)劃分的結果。為了適應對社區(qū)劃分結果的評價，本文對上述三種度量適當調整，采用平均準確率(AVG_P)、平均召回率(AVG_R)和平均F1值(AVG_F1)進行度量。

2.3 實驗結果分析

使用獲取的三類實驗數據分別設計實驗，將本文ABLF算法、SL3PA算法[2]、CDCLM算法[3]、COPRA算法[9]和IEDC算法[10]進行對比實驗。因為在實際社區(qū)劃分時，鏈路結構和轉發(fā)行為同等重要，所以α和β均設置為0.5，查看θ取不同值時的社區(qū)劃分結果變化情況。

1)θ取值直接影響重疊社區(qū)劃分的結果，θ取值太小，會導致社區(qū)重疊度較高，甚至完全重疊，如果θ取值太大，又會出現社區(qū)重疊太小，甚至無任何重疊。為了分析參數θ對重疊社區(qū)劃分的影響，取值在0.5～1之間逐漸增加，每次增加0.05，在第1類五個訓練數據上執(zhí)行ABLF算法，查看在θ不同取值下，社區(qū)劃分結果的模塊度變化情況，實驗結果如圖1所示。在五個訓練數據上運行ABLF算法，在D1和D3上，當θ為0.85時模塊度達到峰值，然后回落；在D2和D4上當θ分別為0.9或0.8時模塊度達到峰值，然后回落；在D5上當θ為0.8時模塊度達到峰值，并且θ為0.85時尚未回落。從實驗可知，θ取值在區(qū)間[0.8,0.9]為宜，所以在后面的實驗中，本文ABLF算法的θ值均取0.85。

圖1 參數θ對模塊度的影響Figure 1 Parameter θ Impact on modularity

2)將本文算法與其他四種算法應用于經人工標記的實驗數據。實驗結果顯示，五種方法都成功將該社交網絡子網絡劃分為三個社區(qū)，由于該數據已經進行人工標記，也就是社區(qū)所包含的節(jié)點已經確定，收集實驗返回數據，分別計算五種算法得出的結果的平均準確率、平均召回率和平均F1值。五種算法得出的社區(qū)劃分結果的平均準確率和平均召回率對比如圖2所示。

圖2 平均準確率和平均召回率對比Figure 2 Comparison of average accuracy and average recall rate

從圖2可以看出，ABLF算法的平均正確率和平均召回率都比較高，兩個指標都高于SL3PA算法和COPRA算法，與CDCLM算法和IEDC算法相比，平均準確率略低但平均召回率略高于這兩種算法。準確率和召回率在某種意義上可以作為社區(qū)劃分質量的評估標準，準確率和召回率越高越好，但是，兩者之間也存在一定的矛盾性。假如在某種極端情況下，某社區(qū)所有節(jié)點都歸屬到該社區(qū)，但同時也有大量非本社區(qū)節(jié)點歸屬進來，那么該社區(qū)召回率就是100%，但是準確率卻很低，同理，準確率高，召回率也可能很低。F1度量綜合考慮這兩種衡量標準，兩者都高，則F1也高，其中一個值低，則F1也低，能有效避免準確率和召回率極端不平衡的情況，五種算法社區(qū)挖掘結果的平均F1值如圖3所示。從F1度量值來看，ABLF算法社區(qū)劃分結果的平均F1值明顯高于SL3PA算法和COPRA算法，略高于IEDC算法，略低于CDCLM算法，相差不大。

圖3 F1-measure對比Figure 3 Comparison of F1-measure

在已標記的數據集上的實驗顯示，本文提出的ABLF算法所挖掘的社區(qū)質量相對較高。經分析，這種結果的產生原因在于ABLF算法衡量微博用戶之間緊密度不僅僅依賴于網絡結構，也就是不僅僅考慮用戶之間的關注關系，還綜合衡量了用戶之間的轉發(fā)行為。實際上，用戶之間的關注不能客觀反映其聯系緊密度或者興趣相似度，因為可能存在以關注獲得利益的“水粉”，而用戶之間對第三者微博的轉發(fā)行為或者第三者對他們的轉發(fā)行為更能反映用戶的緊密程度。比如某用戶關注了大量籃球愛好者，但是該用戶所發(fā)表或者轉發(fā)的微博多是韓劇相關內容，那么該用戶屬于韓劇相關社區(qū)更為合適，它對籃球愛好者的關注或許只是源于友情而非愛好，而其他方法多是忽略了用戶之間的這種行為相似度，導致社區(qū)劃分質量略低。

3)第三類數據更貼近實際社交網絡數據，未經嚴格的數據清洗和標記，數據內社區(qū)結構不明朗，所以不能再用正確率和召回率來衡量結果，在本實驗中使用模塊度度量。將本文算法和其他四種算法均重復執(zhí)行10次，不但能衡量社區(qū)劃分的結果質量，也能突顯算法的穩(wěn)定性，只有社區(qū)劃分質量好并且結果相對穩(wěn)定的算法才是好的。五種算法重復執(zhí)行10次產生的社區(qū)劃分結果的模塊度如圖4所示。

圖4 社區(qū)劃分結果對比Figure 4 Comparison of community partition results

從圖4可以看出，五種算法重復執(zhí)行的情況下，本文ABLF算法社區(qū)劃分結果的總體的模塊度平均值略優(yōu)于COPRA算法和IEDC算法，比SL3PA算法稍低，與CDCLM算法持平，但是本文ABLF算法重復執(zhí)行的情況下表現比較穩(wěn)定，劃分結果的質量波動平緩，每次執(zhí)行結果差別不大，但是其他四種算法都表現出較大的波動性，原因在于社區(qū)劃分的結果一定程度上取決于社區(qū)中心的選擇，本文ABLF算法的社區(qū)中心節(jié)點選擇方法比較客觀，多次重新選擇社區(qū)中心的情況下，被選中的中心節(jié)點不會有較大變動，即使某社區(qū)在上一輪執(zhí)行時被選中的社區(qū)中心節(jié)點為A，而本輪選中了節(jié)點B，根據本文社區(qū)中心選擇算法可知，A與B的出度與入度之和可能相當，只是在社區(qū)中所處位置不同，雖然會影響社區(qū)劃分結果，但影響不大。其他幾種算法也表現出了很好的劃分效果，甚至平均來看更優(yōu)于本文ABLF算法，但是可能未完全考慮網絡鏈路和用戶行為相似性，導致劃分結果受個別特殊用戶的影響，穩(wěn)定性稍差。另外，因為此數據為未標記數據，未嚴格清洗，存在部分相對孤立的節(jié)點，所以整體的模塊度遠低于人工標記的經嚴格清洗的數據。

4)為驗證算法時間開銷，從第三類數據中抽取不同數量的節(jié)點來測試在不同規(guī)模數據上的運行時間。SL3PA標簽傳播算法相當于節(jié)點的遍歷操作，時間開銷較??；CDCLM算法使用局部模塊度的計算來降低時間開銷，效果比較明顯，并且在數據量逐漸增加的情況下，時間開銷未出現陡增的現象；COPRA算法利用數據降維技術，減小數據維度，節(jié)省運行時間；IEDC算法在發(fā)現社區(qū)結構過程中，對特征矩陣的循環(huán)處理和更新增加了時間開銷。不同規(guī)模數據上的運行時間如圖5所示。

圖5 算法運行時間Figure 5 Running time of algorithms

從圖5可以看出，ABLF算法在時間開銷上相較于SL3PA算法、CDCLM算法和COPRA算法來說有些偏高，比IEDC算法低，原因在于ABLF算法在中心節(jié)點選取以及節(jié)點所屬社區(qū)分配過程中，需要計算多節(jié)點對之間的聯系緊密度，增加了時間開銷。

3 總結

本文提出一種基于鏈路結構和轉發(fā)行為的微博社交網絡重疊社區(qū)劃分方法，在對社交網絡鏈路結構進行分析的同時，綜合考慮了用戶轉發(fā)行為的相似性，將兩者結合，進一步提高了社區(qū)劃分結果的質量。實驗證明了本文ABLF算法不但取得了較好的重疊社區(qū)劃分效果，還具有更好的穩(wěn)定性。但是，本文算法還存在幾點不足，比如，時間開銷略高，對θ取值未進行嚴格的學習訓練。下一步工作的重點是深入分析用戶轉發(fā)行為，設計轉發(fā)行為預測模型，為用戶轉發(fā)行為預測分析提供依據。