內容相似度微博社區發現方法研究

王高飛，張月琴，陳 健

(太原理工大學 信息與計算機學院，太原 030024)

微博作為一種新興的社交媒體，以其平臺開放性、微博信息簡短性、信息共享及時性等優勢被越來越多的用戶所使用。據《第41次中國互聯網發展狀況統計報告》數據顯示，截止2017年9月中國微博活躍用戶規模達3.16億，與2016年同期相比增長16.4%.隨著微博的迅猛發展，越來越多的商家看到了其潛在的巨大利益和商機，進而不斷地把廣告內容發到微博中。然而大多普通用戶只是不斷地發表自己日常的衣食住行，轉發一些大V的生活瑣事，微博內容的信息量正在逐漸減少，其他用戶在刷微博的時候很難找到自己感興趣的內容。目前微博還未真正建立完善信息監管系統，一些人將不加甄別的信息發到微博上，造成某時間段微博上謠言四起。這些現象難免會使用戶對微博產生抵觸心理，進而對微博的好感度下降。在復雜的微博網絡中發現微博的社區結構將有助于提高微博個性化推薦系統、商家市場營銷活動、各類媒體新聞推薦的精準性，從而使用戶體驗度上升。

目前社區發現算法可以分為兩類。第一類是基于微博用戶關注關系構建復雜網絡圖，通過圖的劃分方法發現社區結構；第二類是基于用戶節點內容，將興趣相似性用戶劃分在同一社區。在基于圖劃分的方法中，CHEN et al[1]提出將動力學模型引入網絡圖中，利用網絡動態交互模擬距離動態從而進行社區發現。MA et al[2]提出了一種基于核心標簽的重疊式微博社區檢測算法，利用標簽與交互頻率開發一種標簽加權策略，進而完成社區發現。朱牧等[3]提出基于鏈接密度的DBLINK算法，利用密度的算法對邊集進行聚類完成社區發現。在微博社交網絡中存在一部分彼此之間沒有鏈接關系，但他們本身興趣相投，因此單純考慮用以上方法進行微博社區發現必然會使結果不理想。LI et al[4]改進了非負矩陣分解(NMF)方法，將網絡建模為加權有向圖，并利用對角占優矩陣作為約束條件，得到各節點的社團隸屬度以及群落間的相互作用。HE et al[5]通過分析微博網絡中用戶的交互信息構建用戶興趣模型，可提高用戶興趣發現的精準度。閆光輝等[6]提出將用戶鏈接與主題屬性相結合計算用戶之間相似度，然后通過標簽傳播算法發現微博社區結構。孫怡帆等[7]在基于以共同關注與粉絲構建用戶相似度的基礎上加入用戶標簽信息，一定程度上提高了用戶相似度準確性。

基于上述研究，本文提出了一種綜合考慮用戶節點屬性的社區發現方法。該方法首先對微博用戶意見領袖進行識別，然后利用AP算法發現領袖用戶興趣中心集合，進而利用模塊度優化方法實現社區劃分，可以在一定程度上減少微博噪音數據的影響，提高社區發現的準確度。

1 相關技術及基本概念

1.1 用戶興趣模型

微博是一個基于用戶關系的信息分享、傳播和獲取的平臺。以往的研究大多以用戶微博文本內容作為用戶興趣來源，但大多數用戶自身微博信息并不能準確反映用戶興趣所在；因為大多數用戶為普通用戶，原創微博較少，大多為日常生活瑣事，并且大部分用戶利用微博只是瀏覽自己感興趣的內容，很少會對微博轉發、評論、點贊。

通過對微博用戶的行為信息、關注信息、活躍度等信息分析可以發現，一部分用戶發表的微博內容原創度高，且微博內容大多為自己所關注的領域，并在該領域有一定的影響力，此類用戶稱為意見領袖。另一部分用戶即為微博中的大多數用戶，其關注列表一般分為親戚、朋友、同學等現實生活圈和關注的自己感興趣的意見領袖圈。綜合上述分析，本文將通過分析意見領袖微博內容作為其興趣來源，而普通用戶的興趣來源為自身微博內容與其所關注的意見領袖的微博內容。

1.2 LDA語義相似度

TF-IDF向量空間模型常用來計算文本間的相似度，該方法沒有考慮到文字背后的語義關聯。因此本文選取LDA算法計算微博用戶間的興趣相似度。

LDA(latent Dirichlet allocation)模型由BLEI et al[8]于2003年提出，現被廣泛應用于文本語義相似度計算中。LDA是一種三層貝葉斯模型，三層分別為：文檔層、主題層和詞層。圖1為LDA模型結構圖。

圖1 LDA模型結構圖 Fig.1 LDA model structure diagram

圖中，φ表示詞分布，θ表示主題分布，α是主題分布θ的先驗分布參數，β是詞分布φ的先驗分布參數，N表示文檔的單詞總數，M表示文檔的總數。

LDA模型文檔的生成過程如下：

1) 根據先驗知識α確定某篇文檔的主題分布θ.

2) 從該文檔所對應的多項分布(主題分布)θ中抽取一個主題Z.

3) 根據先驗知識β確定當前主題的詞語分布φ.

4) 從主題Z所對應的多項分布(詞分布)φ中抽取一個單詞w，重復N次結束。

根據LDA模型結構圖可知，整個模型的聯合概率密度為：

(1)

對文本中詞分布φ以及主題分布θ利用Gibbs抽樣估計原理，排除當前詞的主題分配，利用文本中其他詞的主題分配和觀測到的單詞來計算當前詞的主題分配，公式如下：

(2)

式中：zi表示第i個單詞對應的主題變量；i表示不包括文本的第i項；表示k主題中出現詞t的次數；表示文本m出現主題k的次數；βt表示詞t的Dirichlet先驗；αk表示主題k的Dirichlet先驗。

求出單詞的主題分布后即可由公式(3)求出文本中的主題概率：

(3)

將每個用戶的興趣主題模型映射為向量后，即可通過JS散度[9]計算用戶間內容相似度：

(4)

式中DKL為兩概率分布對應對數的差的期望值：

(5)

本文LDA參數值取經驗值。令α=50/T，β=0.01；其中T=50，迭代次數為100.

2 基于內容的微博社區發現

本文提出了一種將AP算法與模塊度優化算法相融合的算法來進行社區發現。觀察已知微博興趣社區的組織結構可以發現，微博社區大多數是以少數意見領袖為中心，經過大多數興趣相投用戶的參與逐步擴展為一定規模的社區結構。由于一個社區中可能存在多個意見領袖，因此本文以AP算法對微博中意見領袖進行初始聚類，得到各個社區興趣中心，然后利用模塊度優化算法對社區進行劃分。

2.1 微博意見領袖識別

在現有意見領袖識別的基礎上，本文采用將用戶影響力與用戶活躍度相結合的方法進行領袖識別。指標體系構建如表1.

表1 意見領袖識別指標體系表Table 1 Opinion leader index system table

用戶粉絲數/關注數：微博中用戶可以根據自身興趣愛好，關注自己喜歡的用戶，成為其粉絲。粉絲數或關注數越大，代表用戶的關注度越高，越能成為意見領袖。

微博平均轉發數：用戶可以對自己喜歡的或覺得有價值的微博進行轉發；如果用戶微博被轉發得越多，說明用戶的影響力越大。

微博平均評論數：用戶可以對感興趣的話題引發思考然后進行評論，因此評論數更能體現用戶影響力。

微博平均點贊數：用戶可以對自己感興趣的微博點贊表示支持、贊同，同樣可以體現一定的用戶影響力。

用戶近3個月日均發表微博數：用戶近期發表的微博數反映了用戶的活躍程度，同時該指標可以剔除部分僵尸用戶。

故用戶最終影響力F計算公式為：

F=I·WT.

(6)

式中：I向量中每個分量代表上述一個指標，W向量中各分量表示上述五類指標的權重。本文采用AHP層次分析法，確定各指標權重，其判斷矩陣如表2所示。

表2 指標體系判斷矩陣Table 2 Indicator system judgment matrix

由方根法計算得出：

W=(0.417,0.161,0.263,0.097,0.062) .

文獻[10]表明微博中90%的微博來自10%的核心用戶，因此本文取影響力前10%的用戶為意見領袖。

2.2 微博社區興趣中心發現

AP(affinity propagation)算法又稱為近鄰傳播算法，是DUECK et al[11]于2007年提出的一種快速、有效的聚類算法。AP算法無須事先指定聚類數目，把所有的樣本點都看作潛在的聚類中心。為找到最優的聚類中心，該算法將樣本點之間組成的相似度矩陣S作為輸入，以相似度矩陣對角線上的數值s(k,k)作為樣本點k能否成為聚類中心的程度，又稱為參考度，參考度越大則說明個數據點成為聚類中心的能力越強，則最終聚類中心的個數則越多，其取值一般為相似度矩陣中所有值的最小值或者中位數，在本文中取中位數。

AP算法有兩個重要概念：吸引度(responsibility)和歸屬度(availability)。R(i,k)表示數據對象k適合作為數據對象i的聚類中心的程度；A(i,k)表示數據對象i選擇數據對象k作為其聚類中心的適合程度。R(i,k)與A(i,k)越大，數據對象k就越有可能作為聚類的中心。AP算法就是不斷迭代更新每一個數據對象的吸引度和歸屬度，直到迭代一定的次數，產生聚類中心，同時將其余數據對象分配到相應的聚類中。吸引度和歸屬度更新規則如下：

(7)

(8)

(9)

為避免算法在信息傳遞過程中發生震蕩，AP算法引入阻尼因子λ(λ∈[0,1]，本文設定為默認值0.5)。第t次迭代的加權更新公式如下：

rt(i,k)=(1-λ)×rt(i,k)+λ×rt-1(i,k) ,

(10)

at(i,k)=(1-λ)×at(i,k)+λ×at-1(i,k) .

(11)

AP聚類算法步驟如下。

輸入：相似度矩陣S，阻尼因子λ

輸出：類代表點及聚類結果

stepl：初始化歸屬度a(i,k)=0，根據相似度矩陣S計算偏好參數p=median(S)；

step2：對于每個數據點i，根據公式(7)、公式(10)更新吸引度r(i,k)；

step3：對于每個數據點i，根據公式(8)、公式(9)、公式(11)更新歸屬度a(i,k)；

step4：對于每個數據點i，其類代表點為

(12)

step5：當超過最大迭代次數或選擇的類代表點在連續幾步迭代中保持穩定不變，跳轉到step6，否則返回step2；

step6：將擁有同一類代表點的數據點歸為一類。

2.3 微博社區發現

模塊度是NEWMAN[12]于2004年提出的衡量社區強度的方法。在有權網絡中模塊度的定義為：

(13)

在本文中我們將兩點間權重替換為用戶之間相似度，興趣社區發現就是以意見領袖用戶為初始中心，遍歷其他用戶，分別計算用戶加入到各個群的增量，選取增量最大的中心群加入，直到所有用戶都加入到社區。模塊度增量的計算公式為：

(14)

式中：ki,in是社區c內節點與節點i的邊權重之和；∑win表示社區內部邊權重之和；∑wtot表示與社區c內的節點相連的邊的權重之和。

3 實驗及分析

3.1 實驗數據

本文通過GitHub上公開的微博python爬蟲，以用戶間關注關系進行深度優先爬取，隨機爬取3 742個微博用戶數據。為保證實驗質量，本文剔除了粉絲數小于5、關注數少于10的用戶數據，保留有效用戶數據3 436個。同時微博博文數據預處理去除昵稱、微博號、URL、@某人、數字等無用信息。

3.2 評價指標

本文所得到的社區結構本質上屬于聚類的結果，因此本文采用內聚性與離散性[13]作為實驗結果的評價指標。

內聚性表示社區內部的聯系緊密程度，內聚性越小，社區越緊密，其計算公式如下：

(15)

式中：wi是第i個社區中心點，Ωi為i用戶所在社區集合。

離散性表示社區與社區間的平均距離，離散性越大，社區之間距離越遠，其計算公式如下：

(16)

式中，K為社區個數。

3.3 實驗結果

在微博數據集上，將本文方法與社區發現GN算法、LPA算法進行了對比試驗。

3.3.1社區數目對比

采用3種方法進行社區發現，所得的社區數量如表3所示，從劃分社區的數量上看本算法效果最佳，LPA算法效果最差。由此可見本文算法可以發現更多、更細化的興趣社區。

表3 社區劃分數量對比Table 3 Quantitative comparison of community division

3.3.2內聚性與離散性對比

為分析各方法所發現的社區內部的緊密程度，本文選取各方法的內聚性高的13個社區進行比較，比較結果如表4.

表4 社區劃分內聚性對比Table 4 Comparison of cohesiveness in community division

從表4可以看出由本文算法得出的社區內聚性均低于其他兩種算法，說明本文算法發現的各個興趣社區內部用戶相似度高于其他兩種算法，本算法可更好發現興趣社區。

圖2為幾種算法離散性圖示，從圖中可以明顯看出本文算法較GN算法、LPA算法離散度值較高，說明發現的微博社區間距離較大，對微博各個興趣社區更有劃分度。綜上所述本文算法較其他算法可以更好地完成微博社區發現。

圖2 離散性對比 Fig.2 Discrete-time contrast

4 結束語

本文通過充分研究微博用戶關注關系與博文內容特點分析用戶興趣模型，提出了一種利用AP算法結合模塊度優化算法對微博進行社區發現。本文方法有效提高了社區劃分的效果，同時避免了傳統聚類算法需預先制定社區個數的缺點。但本文用戶興趣模型中，沒有考慮用戶標簽，同時沒有考慮微博社區動態變化的特點，如果能將這些因素考慮進去，最終微博社區發現的準確度將會提高，這是下一步研究工作。