一種新的微博社區(qū)發(fā)現(xiàn)算法

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

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

一種新的微博社區(qū)發(fā)現(xiàn)算法

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

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

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

微博網(wǎng)絡(luò) 社區(qū)劃分 TRKM算法 信任關(guān)聯(lián)度 社區(qū)模塊度

0 引 言

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

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

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

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

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

1 算法思路

1.1 微博網(wǎng)絡(luò)結(jié)構(gòu)

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

根據(jù)微博網(wǎng)絡(luò)社區(qū)的概念，微博社區(qū)的存在只取決于用戶之間的信息交流情況即用戶之間互相轉(zhuǎn)發(fā)帖、評論和互贊等的情況，與用戶之間的關(guān)注方向無關(guān)。本文以用戶為節(jié)點，提出節(jié)點對的信息群度的概念，即節(jié)點之間用戶活躍值與博文質(zhì)量值之和的倒數(shù)。信息群度可以很好的反應(yīng)出微博網(wǎng)絡(luò)中博主之間的互動情況，能更準確地對微博網(wǎng)絡(luò)進行社區(qū)挖掘。本文根據(jù)節(jié)點對的信息群度的定義，將微博網(wǎng)絡(luò)結(jié)構(gòu)抽象為無向有權(quán)圖。

設(shè)微博網(wǎng)絡(luò)G有n個節(jié)點和m條邊，節(jié)點對的信息群度為dij。設(shè)節(jié)點i和j之間的活躍值為aij，評論數(shù)為oij，微博轉(zhuǎn)發(fā)數(shù)為rij；節(jié)點i和j之間的博文質(zhì)量值為qij，節(jié)點之間的原創(chuàng)微博數(shù)為cij、贊數(shù)為lij，微博總數(shù)為n，其中權(quán)重因子β1、β2是用來調(diào)節(jié)評論數(shù)、轉(zhuǎn)發(fā)數(shù)在節(jié)點間的活躍值中所占的比重，同樣λ1、λ2是用來調(diào)整節(jié)點間的原創(chuàng)微博數(shù)和贊數(shù)在博文質(zhì)量值中所占的權(quán)重。則aij、qij和dij分別表示為：

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

(1)

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

(2)

dij=1/(aij+qij)

(3)

將節(jié)點之間邊權(quán)重wij的值設(shè)為節(jié)點對的信息群度，即：

wij=dij

(4)

1.2 節(jié)點間信任關(guān)聯(lián)度

微博網(wǎng)絡(luò)中通常用兩個相鄰節(jié)點所共享的邊上的權(quán)重來衡量它們之間的信任關(guān)聯(lián)度。兩個相鄰節(jié)點之間共享的邊的權(quán)重越小，它們不是社區(qū)間傳輸信息的路徑的概率就越大，則它們屬于同一個社區(qū)的概率就越大，它們之間的聯(lián)系就越緊密，信任關(guān)聯(lián)度就越高。

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

nodeTrustRelation(vi,vj)=1-wij

(5)

一般情況，微博網(wǎng)絡(luò)中除了相鄰節(jié)點還有非相鄰節(jié)點，非相鄰節(jié)點之間可能沒有路徑或者有多條路徑。一般的，兩個節(jié)點之間的路徑越長，它們的信任關(guān)聯(lián)度就越小。將求最短路徑問題作為計算兩個非相鄰節(jié)點之間的信任關(guān)聯(lián)度的核心思想。經(jīng)過兩個非相鄰節(jié)點之間最少邊的那條路徑?jīng)Q定了它們所求的最短路徑。因此，可以利用廣度優(yōu)先搜索算法求得圖中所有的非相鄰節(jié)點之間的最短路徑，然后再求出非相鄰節(jié)點之間的最大信任關(guān)聯(lián)度。

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

nodeTrustRelation(vi,vj)

(6)

通過式(5)和式(6)可以構(gòu)造微博網(wǎng)絡(luò)的節(jié)點信任關(guān)聯(lián)度矩陣R，即：

(7)

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

(8)

1.3 社區(qū)模塊度

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

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

(9)

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

(10)

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

(11)

2 基于信任關(guān)聯(lián)度微博社區(qū)發(fā)現(xiàn)算法

傳統(tǒng)的K-means算法[13]是在使聚類準則函數(shù)最優(yōu)原則的基礎(chǔ)上，利用最接近于聚類中心的數(shù)據(jù)點作為類的中心以增強算法的魯棒性。但其在處理過程中還存在著對初值敏感，對于不同的初始值會導(dǎo)致不同聚類結(jié)果的問題。

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

而基于節(jié)點信任關(guān)聯(lián)度的微博社區(qū)發(fā)現(xiàn)算法(簡稱TRKM算法)是結(jié)合了微博網(wǎng)絡(luò)的結(jié)構(gòu)屬性，并充分利用了用戶的評論、轉(zhuǎn)發(fā)、原創(chuàng)微博等屬性來構(gòu)造節(jié)點間信任關(guān)聯(lián)度，通過將網(wǎng)絡(luò)邊權(quán)重的值進行動態(tài)設(shè)定，重新進行聚類分析。在所有節(jié)點都劃分完之前，先以最大信任關(guān)聯(lián)度原則選取新的代表對象，再在最小信任關(guān)聯(lián)度原則的基礎(chǔ)上進行模式歸類，最后再通過初始聚類中心微調(diào)，將聚類中心輪換，具體步驟如下：

輸入：微博網(wǎng)絡(luò)節(jié)點的信任關(guān)聯(lián)度鄰接矩陣

輸出：微博網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)

方法：

(1) 設(shè)center=?(作為聚類中心的節(jié)點集合)，V1=V0-center(除聚類中心以外的所有點的集合)，初始j=2。根據(jù)式(5)和式(6)求出微博網(wǎng)絡(luò)節(jié)點的信任關(guān)聯(lián)度矩陣R。

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

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

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

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

轉(zhuǎn)步驟(3)。

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

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

3 實驗分析

3.1 數(shù)據(jù)集

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

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

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

3.2 實驗結(jié)果分析

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

圖1 A組數(shù)據(jù)的社區(qū)模塊度值趨勢

圖2 B組數(shù)據(jù)的社區(qū)模塊度值趨勢

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

圖3 A組數(shù)據(jù)的社區(qū)劃分結(jié)構(gòu)

圖4 B組數(shù)據(jù)的社區(qū)劃分結(jié)構(gòu)

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

4 結(jié) 語

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

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

[2] 王林,戴冠中.基于復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的論壇熱點主題發(fā)現(xiàn)[J].計算機工程,2008,34(11):214-216.

[3] 張佳玉.基于節(jié)點相似度的社團發(fā)現(xiàn)算法研究[D].安徽工業(yè)大學,2014.

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

[5] 曾王輝.微博網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究[D].云南大學,2012.

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

[7] 蔡波斯,陳翔.基于行為相似度的微博社區(qū)發(fā)現(xiàn)研究[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] 楊長春,王天允,葉施仁.微博意見領(lǐng)袖影響力評價指標體系研究-基于媒介影響力視角[J].情報雜志,2014,33(8):178-183.

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

[13] 趙鳳霞,謝福鼎.基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)新方法[J].計算機應(yīng)用研究,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)；江蘇省產(chǎn)學研前瞻性聯(lián)合研究項目(BY2014037-08)。楊長春，教授，主研領(lǐng)域：信息管理，數(shù)據(jù)挖掘。劉玲，碩士生。李雪佳，碩士生。呂晨，碩士生。顧寰，碩士生。

TP391

A

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