王高飛，張月琴，陳 健

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

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

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

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

1 相關技術及基本概念

1.1 用戶興趣模型

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

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

1.2 LDA語義相似度

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

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

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

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

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

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

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

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

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

根據(jù)LDA模型結構圖可知，整個模型的聯(lián)合概率密度為：

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

2 基于內容的微博社區(qū)發(fā)現(xiàn)

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

2.1 微博意見領袖識別

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

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

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

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

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

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

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

故用戶最終影響力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 微博社區(qū)興趣中心發(fā)現(xiàn)

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

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

(7)

(8)

(9)

為避免算法在信息傳遞過程中發(fā)生震蕩，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，根據(jù)相似度矩陣S計算偏好參數(shù)p=median(S)；

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

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

step4：對于每個數(shù)據(jù)點i，其類代表點為

(12)

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

step6：將擁有同一類代表點的數(shù)據(jù)點歸為一類。

2.3 微博社區(qū)發(fā)現(xiàn)

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

(13)

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

(14)

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

3 實驗及分析

3.1 實驗數(shù)據(jù)

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

3.2 評價指標

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

內聚性表示社區(qū)內部的聯(lián)系緊密程度，內聚性越小，社區(qū)越緊密，其計算公式如下：

(15)

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

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

(16)

式中，K為社區(qū)個數(shù)。

3.3 實驗結果

在微博數(shù)據(jù)集上，將本文方法與社區(qū)發(fā)現(xiàn)GN算法、LPA算法進行了對比試驗。

3.3.1社區(qū)數(shù)目對比

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

表3 社區(qū)劃分數(shù)量對比Table 3 Quantitative comparison of community division

3.3.2內聚性與離散性對比

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

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

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

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

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

4 結束語

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