一種新的微博社區發現算法

楊長春 劉 玲 李雪佳 呂 晨 顧 寰

(常州大學信息科學與工程學院 江蘇 常州 213164)

一種新的微博社區發現算法

楊長春 劉 玲 李雪佳 呂 晨 顧 寰

(常州大學信息科學與工程學院 江蘇 常州 213164)

在輿情分析、微博營銷和個性化推薦等方面，微博社區發現的研究都具有重要的應用價值。為了準確而有效地發現微博社交網絡中的社區，提出一種基于信任關聯度的微博社區發現算法(TRKM算法)。該算法通過微博用戶的評論、轉發、原創微博等屬性來構造節點間信任關聯度，再利用微博社區的模塊度對網絡社區劃分效果進行評價。在新浪微博明星和普通用戶數據集上進行實驗，并將TRKM算法與傳統K-means算法作比較。實驗表明，該算法能夠更有效地發現微博用戶關系網絡中的社區結構。

微博網絡 社區劃分 TRKM算法 信任關聯度 社區模塊度

0 引 言

在Web 2.0時代的大環境下，社交型網站(SNS)也成為了應用熱點。微博作為SNS的一種升級版社交網絡交互模式，正逐漸成為眾多研究者關注的熱點[1-2]。社交網絡和其他的復雜網絡一樣，都具有社區結構。不同屬性、興趣的社區結構組成了人類最復雜的網絡之一即社交網絡。

社區結構是社交網絡具有的一個共同特性[3]，滿足不同社區間節點連接相對稀疏，同一社區內部節點連接相對緊密的特點。社區形成的原因多種多樣，不管是微博還是微信社區，最重要的基礎是信任關系[4]。興趣和需求不同的用戶會選擇關注相關的、信任的社交圈、朋友圈來進行互動、交流。由于微博用戶大部分是真實的人群，對微博用戶的合理分群對廣告投放、微博營銷和準確定位目標用戶群體都具有非常重要的意義。

目前，微博網絡社區發現方面的研究大致分為兩種：一種是基于文本的能發現在對同一主題感興趣的人群的方法，主要通過定義文章相似的度量來構造節點之間的相似度，將相似度值比較接近的聚類成一組用戶社區。另一種是基于行為聯系的方法，在微博行為的基礎上利用圖模型進行建模來尋找出互相聯系緊密的用戶群體。

針對微博網絡的社區發現在國內外已有一些研究成果。國內方面，曾王輝[5]利用微博網絡的特殊性，提出了在微博網絡中運用廣度優先搜索和模塊度相結合的社區發現方法，提高了社區劃分的準確性和有效性，但是該算法對于微博網絡的研究信息還僅限于用戶之間的關注信息，沒有轉發、評論等重要信息。閆光輝等人[6]通過綜合考慮用戶關注關系和用戶主題相關度來對微博用戶社區進行劃分，但是該算法沒有考慮用戶間的交互行為如發帖和回帖數對用戶相關度的影響；蔡波斯等人[7]利用用戶行為來建模，從而構造用戶行為相似度來劃分微博社區。但是，上述方法并不能反映用戶隸屬于多個社區的重疊問題，僅僅局限于用戶之間的關聯關系，事實上，用戶在興趣社區中，會隸屬于多個興趣社區。丁虹等人[8]提出了一種基于K-means算法的微博社區發現新方法，通過微博博主的評論、轉發屬性來定義節點間的關聯度，從而一定程度上提高了社區劃分的質量。國外方面，對于Twitter的社區發現研究，Naresh等人[9]通過用戶所發表的內容、鏈接關系等來建相似度矩陣，從而在傳統聚類方法的基礎上來發掘微博社區；Deitrick等人[10]通過微博用戶與用戶之間所發送的tweets信息內容來逐步提高社區發現的有效性和準確性。

本文充分利用節點屬性信息，提出一種基于信任關聯度的微博社區發現算法(TRKM算法)。該算法引入信息群度的概念，將微博社區網絡邊權重的值不設為固定值1，而是動態設定。在模式歸類的基礎上，按最大信任關聯度原則選取新的代表對象，直至劃分節點的過程全部完成為止，最后根據模塊度來確定理想的微博社區數目。該算法能夠更貼近微博網絡的特性并且較好地找到聚類中心，使得社區發現的質量大大提高，并且能夠滿足微博營銷的目標用戶群體發現的基本需求。

1 算法思路

1.1 微博網絡結構

在目前基于復雜網絡的研究中，一般是將網絡結構分為無向圖結構和單向有向圖結構。在微博網絡中，設定每個用戶即博主為一個節點，用戶有關注和粉絲兩類信息，設定關注信息為節點的入度，粉絲信息為節點的出度，因此，網絡中存在單向邊和雙向邊兩種類型的邊。在微博網絡中若單純的從節點間的表面關系來考慮，微博網絡結構就是一個混合有向圖。

根據微博網絡社區的概念，微博社區的存在只取決于用戶之間的信息交流情況即用戶之間互相轉發帖、評論和互贊等的情況，與用戶之間的關注方向無關。本文以用戶為節點，提出節點對的信息群度的概念，即節點之間用戶活躍值與博文質量值之和的倒數。信息群度可以很好的反應出微博網絡中博主之間的互動情況，能更準確地對微博網絡進行社區挖掘。本文根據節點對的信息群度的定義，將微博網絡結構抽象為無向有權圖。

設微博網絡G有n個節點和m條邊，節點對的信息群度為dij。設節點i和j之間的活躍值為aij，評論數為oij，微博轉發數為rij；節點i和j之間的博文質量值為qij，節點之間的原創微博數為cij、贊數為lij，微博總數為n，其中權重因子β1、β2是用來調節評論數、轉發數在節點間的活躍值中所占的比重，同樣λ1、λ2是用來調整節點間的原創微博數和贊數在博文質量值中所占的權重。則aij、qij和dij分別表示為：

aij=(β1×oij+β2×rij)/n

(1)

qij=(λ1×cij+λ2×lij)/n

(2)

dij=1/(aij+qij)

(3)

將節點之間邊權重wij的值設為節點對的信息群度，即：

wij=dij

(4)

1.2 節點間信任關聯度

微博網絡中通常用兩個相鄰節點所共享的邊上的權重來衡量它們之間的信任關聯度。兩個相鄰節點之間共享的邊的權重越小，它們不是社區間傳輸信息的路徑的概率就越大，則它們屬于同一個社區的概率就越大，它們之間的聯系就越緊密，信任關聯度就越高。

通過分析可以得出，社區間的節點對的信息群度大于社區內部節點對的信息群度。顯然，節點i與j之間的節點對的信息群度越小，它們之間交流、互動程度大，從而節點間的信任關聯度就越大，屬于同一個社區的概率就越大，則兩個相鄰節點vi、vj的信任關聯度可定義如下：

nodeTrustRelation(vi,vj)=1-wij

(5)

一般情況，微博網絡中除了相鄰節點還有非相鄰節點，非相鄰節點之間可能沒有路徑或者有多條路徑。一般的，兩個節點之間的路徑越長，它們的信任關聯度就越小。將求最短路徑問題作為計算兩個非相鄰節點之間的信任關聯度的核心思想。經過兩個非相鄰節點之間最少邊的那條路徑決定了它們所求的最短路徑。因此，可以利用廣度優先搜索算法求得圖中所有的非相鄰節點之間的最短路徑，然后再求出非相鄰節點之間的最大信任關聯度。

假設微博網絡中非相鄰節點vi和vj節點之間的最短路徑為ShortPath(vi,vj)={(vi,vk),(vk,vm),…,(vn,vj)}，通過分析可知，非相鄰節點間的信任關聯度是由它們之間所有最短路徑上的節點對的信任關聯度的乘積值來決定的。如果非相鄰節點間的最短路徑數為s，則選擇其中乘積最大的作為非相鄰節點的信任關聯度，即：

nodeTrustRelation(vi,vj)

(6)

通過式(5)和式(6)可以構造微博網絡的節點信任關聯度矩陣R，即：

(7)

很明顯，R是一個對稱矩陣，由于節點與其自身的信任關聯度，不對社區劃分結果產生影響，故有nodeTrustRelation(vi,vi)=1，從而為了計算方便，將矩陣R主對角線上的元素值設為相應節點的度，因而有：

(8)

1.3 社區模塊度

在社區結構發現的方法中，都缺乏一個量的定義來描述網絡的社區結構。因而，不能直接從網絡的拓撲結構去判斷所求得的社區是否已經是實際網絡中的社區結構。而且社區劃分的合理程度取決于社區內部的連接是否緊密以及社區內部的連接數是否大于社區間的連接數。所以本文采用文獻[12]所提出的社區模塊度指標方法來評價微博社區劃分的效果，它只與社區的內聚系數和連接密度相關，與社區的內部節點度值之和無關。

社區模塊度可以分為兩部分理解：(1) 社區內部節點連接的緊密程度，稱為連接密度L(Si)；(2) 社區內部節點的連接數是否大于社區間的節點連接數，稱為內聚系數Coh(Si)。設定微博網絡含有社區S1，S2，…，Sn，根據上述社區模塊度的描述，則有如下定義：

(9)

其中，ni表示社區Si所包含的節點數；E(Si)表示社區Si內部所包含的邊數。明顯地，連接密度L(Si)描述了社區Si內部節點的連接密度。然后，計算社區Si的內聚系數Coh(Si)，即：

(10)

根據社區模塊度的解釋和上述L(Si)、Coh(Si)的描述，本文采用的社區模塊度的定義如下，Q值越大說明社區結構越明顯。

(11)

2 基于信任關聯度微博社區發現算法

傳統的K-means算法[13]是在使聚類準則函數最優原則的基礎上，利用最接近于聚類中心的數據點作為類的中心以增強算法的魯棒性。但其在處理過程中還存在著對初值敏感，對于不同的初始值會導致不同聚類結果的問題。

3．瘤組織凋亡相關分子Bcl-xl、Survivin、Bax、caspase3 mRNA表達的檢測：提取各組移植瘤組織總RNA，檢測RNA純度及濃度，經逆轉錄后PCR擴增，以β-actin為內參。引物序列見表1，由金唯智公司合成。擴增產物經1.5%瓊脂糖凝膠電泳分離，紫外成像系統觀察、拍照并分析圖像。

而基于節點信任關聯度的微博社區發現算法(簡稱TRKM算法)是結合了微博網絡的結構屬性，并充分利用了用戶的評論、轉發、原創微博等屬性來構造節點間信任關聯度，通過將網絡邊權重的值進行動態設定，重新進行聚類分析。在所有節點都劃分完之前，先以最大信任關聯度原則選取新的代表對象，再在最小信任關聯度原則的基礎上進行模式歸類，最后再通過初始聚類中心微調，將聚類中心輪換，具體步驟如下：

輸入：微博網絡節點的信任關聯度鄰接矩陣

輸出：微博網絡的社區結構

方法：

(1) 設center=?(作為聚類中心的節點集合)，V1=V0-center(除聚類中心以外的所有點的集合)，初始j=2。根據式(5)和式(6)求出微博網絡節點的信任關聯度矩陣R。

(2) 選取信任關聯度值最大的節點d1作為節點集合V1中第一個代表對象(聚類中心)，以此類推，再選擇節點集合V1中信任關聯度值最小的節點d2作為第二個聚類中心，將這樣的節點放在集合dx中，(x=1,2,…,n,n<|V1|，即先為每個類任意選擇一個聚類中心，剩余節點根據其與聚類中心的信任關聯度值大小分配給最近的一個類)，其中：

center=center∪{dx},V1=V1-{dx}

(4) 初始聚類中心微調：以簇類各個節點輪換為相應的聚類中心，根據信任關聯度矩陣R，計算出待劃分節點集V1中各個節點vk(k=1,2,…,|V1|)與代表對象(簇類中心)節點集合center中各個節點di(i=1,2,…,|center|)之間節點的平均信任關聯度的最小值rmin所對應的節點v∈V1，把它作為微調的簇類中心添加到center中。用rki表示節點vk與聚類中心di的節點信任關聯度，rk表示節點vk與聚類中心center中各節點信任關聯度的平均值，則：

center=center∪{v},V1=V1-{v}

轉步驟(3)。

(5)V1≠?，計算節點vk(k=1,2,…|V1|)與所有簇類中心節點之間的信任關聯度值，哪個值越大，該節點就屬于信任關聯度最大值所對應的聚類。每個社區所屬一個聚類，再將社區的劃分結果輸出出來。

(6) 求出當前社區劃分結果下的社區模塊度Q值。ifQj≥Qj-1thenj=j+1，轉步驟(3)；else結束(最大的社區模塊度值就對應社區劃分的最佳結果)。

3 實驗分析

3.1 數據集

文中采用http://www.datatang.com/data/11819提供的新浪微博用戶數據集進行實驗。該數據集包含六萬條新浪微博用戶數據，包括用戶ID、姓名、注冊時間、數據采集時間、是否為認證用戶、評論數、轉發數、原創微博數、贊數等字段。

在文中提出的社區發現算法中用戶之間的交互頻率是一個很重要的影響因素。新浪微博中，用戶類型主要可以分為兩大類：明星用戶和普通用戶。由于兩類用戶的差異性會影響用戶之間的交互頻率值，文中在兩類用戶中各進行一組實驗以驗證本文算法的可行性和優化性。

分別從上述新浪微博用戶數據包中采集兩組測試用例，每組用例分別為深2度鏈接的用戶數據組成，命名為A和B。A組用例是以加“V”用戶“楊冪”為原始節點，她的粉絲及她所關注的人為深1度鏈接，他們的粉絲及所關注的人為深2度鏈接，共采集了551個用戶的信息數據。B組用例是以普通用戶“國舅爺”為原始節點，利用類似的方法同樣采集了551個用戶的信息數據。

3.2 實驗結果分析

為了驗證TRKM算法的性能，我們將該算法與傳統K-means算法進行比較，隨著K值不斷增大，兩種算法得到的社區結構也在不斷變化。本實驗記錄了每個K值對應的兩種算法在計算時得到的Q值。對比兩種算法的Q值可以看出，K-means算法是在數據集中隨意選擇k個對象作為聚類中心，將所有節點聚類為k個社區，其Q值在達到一定值后趨于平穩。TRKM算法目的是獲得一個最優社區劃分結構，當Q值達到最大值，此時的社區劃分結構為最佳結果。如圖1和圖2中描述了社區數從1到k情況下的Q值的變化趨勢，TRKM算法的Q值幾乎大于K-means算法，K-means算法得到的Q值達到一定數值時趨于平穩，而TRKM算法得到的Q值逐漸上升達到一個峰值，峰值對應的K值就是最優的社區結構數。根據社區模塊度中Q值越大對應的社區結構越明顯的原理，兩組實驗中，TRKM算法得到的社區結構相比于K-means算法更清晰、更準確。

圖1 A組數據的社區模塊度值趨勢

圖2 B組數據的社區模塊度值趨勢

為了將本實驗結果進行可視化，可以利用社會網絡分析工具Ucinet來形象的表示，圖3和圖4分別是兩組實驗利用TRKM算法得到的最終的社區劃分結構，圖3中共有16個社區并且社區數量比較多，圖4中有40個社區，但其多為小團體結構。圖3的社區結構比圖4明顯，零散節點也少于圖4，因為A組數據的原始節點是領袖節點，她的影響力比較大，由她擴散出來的深2度鏈接用戶間互動交流多，所以得到的社區劃分結構比較明顯。B組數據的原始節點是普通用戶，影響力較小，以他擴散出來的深2度鏈接用戶間交流也比較少，很明顯，最終獲得的社區劃分結構不是很符合實際情況，會出現社團內部節點數量少而社團之間節點多的現象。原始網絡被劃分為社區后還存在零散的節點，這是因為有些用戶只關注了其他用戶，但他們之間的交流信息極少或者是沒有。如何去除這些零散用戶，得到一個比較純粹的社區分布結構也是本文后期將要研究的內容。

圖3 A組數據的社區劃分結構

圖4 B組數據的社區劃分結構

總的來說，結合兩組實驗結果進行比較，K-means算法單純將所有節點進行聚類分析，把每個節點進行分類，其對應的Q值只是一開始呈現上升趨勢，直至聚類結束都沒有得到Q值的峰值。而TRKM算法把用戶間的互動交流情況作為社區劃分的考慮因素進行節點聚類，隨著K值的逐漸增大得到了Q值的峰值，聚類結束，同時得到了最優化的社區劃分結構。通過對比兩組實驗最終的社區劃分結構圖可以發現，用戶間的交流情況越頻繁，社區結構越明顯。從上述分析可知，微博社區結構的劃分與用戶間的交流情況以及交流頻率相關。

4 結 語

本文提出了一種基于節點信任關聯度的微博社區劃分方法(TRKM算法)，該算法提出了節點對的信息群度的概念，通過動態分配網絡并計算邊權重值，使劃分結果更準確。通過微博用戶之間的評論、轉發等交互行為來刻畫節點之間的動態連接關系，從而比較準確地描述微博用戶之間的聯系緊密程度(信任關聯度)，并最終提高微博網絡社區劃分的質量。微博網絡中用戶之間還存在興趣相似度、用戶交流度這些信息，如何將這種信息運用到社區發現的算法甚至推廣到個性推薦系統中，將是本文接下來的研究目標。

[1] 劉大有,金弟,何東曉.復雜網絡社區挖掘綜述[J].計算機研究與發展,2015,50(10):2140-2154.

[2] 王林,戴冠中.基于復雜網絡社區結構的論壇熱點主題發現[J].計算機工程,2008,34(11):214-216.

[3] 張佳玉.基于節點相似度的社團發現算法研究[D].安徽工業大學,2014.

[4] 余紫丹,虞慧群.基于信任度的并行化社區發現算法[J].計算機工程,2015,41(4):81-86.

[5] 曾王輝.微博網絡的社區發現研究[D].云南大學,2012.

[6] 閆光輝,舒昕,馬志程,等.基于主題和鏈接分析的微博社區發現算法[J].計算機應用研究,2013,30(7):1953-1957.

[7] 蔡波斯,陳翔.基于行為相似度的微博社區發現研究[J].計算機工程,2013,39(8):55-59.

[8]YangC,DingH,YangJ,etal.ResearchofMicroblogCommunityDetectionBasedonClusteringAnalysis[J].AdvancesinInformationSciencesandServiceSciences,2013,5(3):25-31.

[9]NareshM,LramaniK.Communitydetectionintwitter[D].Baltimore:DepartmentofComputerScience,UniversityofMarylandBaltimoreCounty,2011:1-60.

[10] Deitrick W,Hu W.Mutually enhancing community detection and sentiment analysis on twitter networks[J].Journal of Data Analysis and Information Processing,2013,1(3):19-29.

[11] 楊長春,王天允,葉施仁.微博意見領袖影響力評價指標體系研究-基于媒介影響力視角[J].情報雜志,2014,33(8):178-183.

[12] 王林,戴冠中,趙煥成.一種新的評價社區結構的模塊度研究[J].計算機工程,2010,36(14):227-232.

[13] 趙鳳霞,謝福鼎.基于K-means聚類算法的復雜網絡社團發現新方法[J].計算機應用研究,2009,26(6):2041-2043.

A NEW MICRO-BLOG COMMUNITY DETECTION ALGORITHM

Yang Changchun Liu Ling Li Xuejia Lü Chen Gu Huan

(SchoolofInformationScienceandEngineering,ChangzhouUniversity,Changzhou213164,Jiangsu,China)

The research on micro-blog community detection has important application value in public opinion analysis, microblog marketing and personalized recommendation, etc. In order to find communities in micro-blog social networks accurately and efficiently, this paper proposes a micro-blog community detection algorithm based on trust relation degree (TRKM algorithm). This algorithm constructs the trust relation degree between the nodes through user comments, forwarding number, original micro-blog article number and other attributes, and uses the module degree of micro-blog community to evaluate the effects of network community partition. Experiments are carried out respectively on the Sina micro-blog dataset of stars and ordinary users to compare TRKM algorithm with the traditional K-means algorithm. Experimental result indicates that TRKM algorithm can more effectively find the community structure in mirco-blog user relationship networks.

Micro-blog networks Community partition TRKM algorithm Trust relation degree Community module degree

2016-03-03。國家自然科學

61272367)；江蘇省產學研前瞻性聯合研究項目(BY2014037-08)。楊長春，教授，主研領域：信息管理，數據挖掘。劉玲，碩士生。李雪佳，碩士生。呂晨，碩士生。顧寰，碩士生。

TP391

A

10.3969/j.issn.1000-386x.2017.03.035