楊長(zhǎng)春 劉 玲 李雪佳 呂 晨 顧 寰

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

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

楊長(zhǎng)春 劉 玲 李雪佳 呂 晨 顧 寰

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

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

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

0 引 言

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

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

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

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

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

1 算法思路

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

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

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

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

wij=dij

(4)

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

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

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

nodeTrustRelation(vi,vj)=1-wij

(5)

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

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

nodeTrustRelation(vi,vj)

(6)

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

(7)

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

(8)

1.3 社區(qū)模塊度

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

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

(9)

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

(10)

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

(11)

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

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

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

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

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

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

方法：

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

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

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

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

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

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

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

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

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

[13] 趙鳳霞,謝福鼎.基于K-means聚類(lèi)算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法[J].計(jì)算機(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。國(guó)家自然科學(xué)

61272367)；江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項(xiàng)目(BY2014037-08)。楊長(zhǎng)春，教授，主研領(lǐng)域：信息管理，數(shù)據(jù)挖掘。劉玲，碩士生。李雪佳，碩士生。呂晨，碩士生。顧寰，碩士生。

TP391

A

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