基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

韋慶杰　李京騰　汪　雨

1(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　重慶 400065)2(重慶郵電大學(xué)軟件工程學(xué)院　重慶 400065)

?

基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

韋慶杰1李京騰2汪雨2

1(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院重慶 400065)2(重慶郵電大學(xué)軟件工程學(xué)院重慶 400065)

針對(duì)微博網(wǎng)絡(luò)社區(qū)難以準(zhǔn)確劃分的問題，根據(jù)微博網(wǎng)絡(luò)的特性，提出一種基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。根據(jù)微博網(wǎng)絡(luò)中用戶間的交互度與共有鄰居相似度來計(jì)算用戶緊密度，并與傳統(tǒng)的GN算法相結(jié)合對(duì)微博網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。通過對(duì)真實(shí)社會(huì)網(wǎng)絡(luò)和微博模擬網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，該算法可以有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

社區(qū)發(fā)現(xiàn)微博網(wǎng)絡(luò)GN算法用戶緊密度共有鄰居相似度

0　引　言

微博作為目前國(guó)內(nèi)最具代表性的社交網(wǎng)絡(luò)平臺(tái)，已經(jīng)成為人們?nèi)粘＿M(jìn)行信息分享和交流的重要工具。由于其具有實(shí)時(shí)性強(qiáng)、傳播速度快、覆蓋范圍廣和信息傳播方式多樣簡(jiǎn)便等特點(diǎn)，吸引了越來越多的用戶。微博采用了全新的社交模式—“關(guān)注”，用戶間不需要經(jīng)過授權(quán)就能建立關(guān)注關(guān)系[1]。在關(guān)注關(guān)系基礎(chǔ)之上，微博的部分用戶通過更多的“評(píng)論”、“轉(zhuǎn)發(fā)”等用戶行為逐步形成一個(gè)社區(qū)。社區(qū)這一概念來源于對(duì)復(fù)雜網(wǎng)絡(luò)的研究，“小世界特征”[2,3]和“150法則”[4]的提出使復(fù)雜網(wǎng)絡(luò)的研究進(jìn)入了一個(gè)新的階段。Girvan等人[5]于2002年正式提出了復(fù)雜網(wǎng)絡(luò)中社區(qū)的概念，社區(qū)的一般定義是同一社區(qū)內(nèi)節(jié)點(diǎn)間的連接很緊密，而社區(qū)之間的連接比較稀疏[6]。發(fā)現(xiàn)微博網(wǎng)絡(luò)中潛在的社區(qū)，能更好地理解社區(qū)內(nèi)個(gè)體的屬性，社區(qū)內(nèi)個(gè)體之間以及社區(qū)之間的結(jié)構(gòu)關(guān)系，可以為個(gè)性化推薦等實(shí)際應(yīng)用提供重要的理論依據(jù)。

近年來，國(guó)內(nèi)外學(xué)者在社區(qū)發(fā)現(xiàn)方面做了大量研究，已有的社區(qū)發(fā)現(xiàn)算法多種多樣。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法主要分為兩類，即圖分割算法和層次聚類算法。其中圖分割算法中具有代表性的算法包括Kernighan-Lin算法[7]和譜二分算法[8]，GN算法[5]則是層次聚類算法中的經(jīng)典代表。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法關(guān)注圖的幾何特征以及圖論概念，而忽視了節(jié)點(diǎn)本身的屬性以及節(jié)點(diǎn)與節(jié)點(diǎn)之間的信息交互影響。而目前微博網(wǎng)絡(luò)中存在著大量的信息分享和交互等用戶行為，所以再對(duì)微博網(wǎng)絡(luò)使用傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法已不能得到準(zhǔn)確的社區(qū)劃分結(jié)果。考慮到微博這類真實(shí)網(wǎng)絡(luò)所具有的特性，Lin等人[9]提出了NAS算法和CNS算法來進(jìn)行社區(qū)發(fā)現(xiàn)，算法考慮了節(jié)點(diǎn)屬性的相似度以及共有鄰居的相似度；喬秀全等人[10]在對(duì)電子商務(wù)的研究中，考慮了用戶的社會(huì)信息和交互行為來進(jìn)行社區(qū)發(fā)現(xiàn)，也提到在采集用戶信息時(shí)有一定的局限性；林友芳等人[11]的研究是在GN算法的基礎(chǔ)上改進(jìn)，提出CIG_ESC算法將邊介數(shù)轉(zhuǎn)化成緊密度，基于緊密度進(jìn)行刪邊得到社區(qū)劃分結(jié)果，雖然算法易于理解，但是該算法沒有給出緊密度計(jì)算的具體公式，只給出了抽象函數(shù)公式，不容易實(shí)現(xiàn)。

借鑒林友芳等人[11]的研究，本文引入用戶緊密度這一概念，針對(duì)傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法難以對(duì)微博網(wǎng)絡(luò)進(jìn)行準(zhǔn)確的社區(qū)劃分的問題，提出一種基于用戶緊密度的社區(qū)發(fā)現(xiàn)算法。該算法首先考慮了轉(zhuǎn)發(fā)微博、評(píng)論微博等用戶行為對(duì)用戶間交互關(guān)系的影響，然后考慮了用戶間共有鄰居相似程度并計(jì)算用戶緊密度，最后與傳統(tǒng)的GN算法相結(jié)合對(duì)微博網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)。

1　相關(guān)研究

1.1微博網(wǎng)絡(luò)

微博網(wǎng)絡(luò)即是對(duì)微博社交平臺(tái)系統(tǒng)的一種抽象。將微博中的用戶抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)，將微博中用戶間的關(guān)注關(guān)系抽象為網(wǎng)絡(luò)中的邊，將微博中用戶的交互行為抽象為網(wǎng)絡(luò)中邊的權(quán)值，這樣就抽象出一個(gè)由節(jié)點(diǎn)、邊和邊權(quán)值構(gòu)成的微博網(wǎng)絡(luò)。

1.2社區(qū)概念

社區(qū)這一概念起源于社會(huì)學(xué)研究領(lǐng)域中，一個(gè)被大家普遍接受的概念是社區(qū)內(nèi)部的節(jié)點(diǎn)之間的連接非常緊密，而社區(qū)外部的節(jié)點(diǎn)之間的連接極為稀疏。

1.3GN算法

GN算法是基于刪邊的聚類算法，其基本思想是不斷地從網(wǎng)絡(luò)中刪除介數(shù)最大的邊，通過計(jì)算模塊度Q值[12]來判斷算法是否終止以及評(píng)價(jià)社區(qū)劃分的優(yōu)劣。

GN算法的流程包括：(1)計(jì)算網(wǎng)絡(luò)中每條邊的邊介數(shù)；(2)刪除邊介數(shù)最大的邊；(3)判斷網(wǎng)絡(luò)是否產(chǎn)生新的社區(qū)結(jié)構(gòu)，如有進(jìn)行第4步，若無則進(jìn)行第2步；(4)計(jì)算模塊度值；(5)將新的模塊度與之前的模塊度進(jìn)行比較，如果新模塊度大于之前的模塊度，則將刪除后的網(wǎng)絡(luò)作為新網(wǎng)絡(luò)進(jìn)行第1步，反之輸出之前模塊度對(duì)應(yīng)的社區(qū)結(jié)構(gòu)，算法結(jié)束。

1.4微博用戶交互度

文獻(xiàn)[13]通過分析用戶行為的相互性和頻度來評(píng)估用戶交互程度，但是該文獻(xiàn)中沒有給出具體的算法公式。本文考慮了微博中轉(zhuǎn)發(fā)與評(píng)論行為，量化了用戶交互程度。假設(shè)Wij表示網(wǎng)絡(luò)中用戶i與用戶j連接邊的權(quán)值，對(duì)應(yīng)微博網(wǎng)絡(luò)中用戶i對(duì)用戶j主動(dòng)發(fā)生Wij次轉(zhuǎn)發(fā)和評(píng)論的次數(shù)總和；Fij表示用戶之間的交互程度值，計(jì)算公式如下：

(1)

Fmax=maxi=1→N,j=1→N{Fij}

(2)

接下來使用Fmax對(duì)Fij的結(jié)果進(jìn)行歸一化處理，最終的用戶交互程度值為：

(3)

經(jīng)過上述處理之后，能保證Fij的值均在(0,1)之間，這樣能夠更好地反映網(wǎng)絡(luò)中用戶的交互程度，同時(shí)微博網(wǎng)絡(luò)可以使用無向帶權(quán)圖來表示，大大降低了算法的難度。

1.5微博用戶共有鄰居相似度

在微博網(wǎng)絡(luò)，處在同一社區(qū)的兩個(gè)節(jié)點(diǎn)往往比處于不同社區(qū)的兩個(gè)節(jié)點(diǎn)擁有更多相同的鄰居節(jié)點(diǎn)，所以用戶的相似程度是從兩個(gè)用戶的共同朋友的相似度來考慮的。假設(shè)N(i)表示用戶i的鄰居節(jié)點(diǎn)，N(j)表示用戶j的鄰居節(jié)點(diǎn)，Sij表示用戶相似度，CNS算法中計(jì)算用戶相似度的公式如下：

(4)

從式(4)中可以看出，兩個(gè)節(jié)點(diǎn)共同朋友的數(shù)量在它們所有朋友中所占的比例越高，它們的相似度越大。

2　基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

2.1問題提出和改進(jìn)思想

目前已有的社區(qū)發(fā)現(xiàn)算法在計(jì)算微博用戶間的緊密度時(shí)，缺乏對(duì)轉(zhuǎn)發(fā)微博、評(píng)論微博以及共有鄰居相似性等信息對(duì)微博用戶間緊密度有較大影響的考慮。針對(duì)這一問題，本文提出了一種新的用戶間緊密度計(jì)算方法，同時(shí)考慮微博用戶的交互程度與共有鄰居相似程度，使計(jì)算結(jié)果能夠更加全面地反映用戶間的緊密關(guān)系。在新的微博用戶緊密度計(jì)算方法的基礎(chǔ)上，結(jié)合GN算法的思想，在GN算法進(jìn)行刪邊時(shí)使邊介數(shù)除以用戶緊密度值作為邊的權(quán)值，降低緊密度強(qiáng)的邊被刪除的概率，通過刪除權(quán)值對(duì)微博網(wǎng)絡(luò)社區(qū)進(jìn)行劃分。

2.2算法定義

定義1微博網(wǎng)絡(luò)是一種加權(quán)圖G(V,E,W)，其中V為微博網(wǎng)絡(luò)中包含n個(gè)節(jié)點(diǎn)的集合{v1,v2,…,vn}，vi表示一個(gè)微博用戶；E為包含m條邊的集合{e1,e2,…,em}，ei=(vi,vj) 表示用戶vi和vj之間存在關(guān)注關(guān)系；W為用戶間緊密度的集合{w1,w2,…,wn}，wij表示用戶vi與vj的緊密程度。

定義2微博用戶緊密度是兩個(gè)微博用戶間關(guān)系親密度的體現(xiàn)，是劃分微博網(wǎng)絡(luò)社區(qū)的依據(jù)，由以下公式求得：

(5)

為了便于后續(xù)的計(jì)算，這里對(duì)Gij進(jìn)行歸一化處理，和處理用戶交互程度時(shí)相同，先從Gij中找出一個(gè)最大值，將它定義為：

Gmax=maxi=1→N,j=1→N{Gij}

(6)

(7)

使用上述的用戶緊密程度，更加全面地衡量了用戶之間的緊密關(guān)系。

3　算法描述

本文提出了基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，首先計(jì)算用戶間的緊密度，然后與GN算法相結(jié)合。算法流程如下：

算法1改進(jìn)的GN算法

輸入：經(jīng)過預(yù)處理的網(wǎng)絡(luò)

輸出：社區(qū)列表以及各社區(qū)內(nèi)的節(jié)點(diǎn)

方法：執(zhí)行以下步驟

步驟1根據(jù)式(1)-式(3)計(jì)算所有邊的用戶交互程度值；

步驟2根據(jù)式(4)計(jì)算所有邊的用戶相似度值；

步驟3根據(jù)式(5)-式(7)計(jì)算所有邊的用戶緊密度值，并乘以一個(gè)設(shè)定的正整數(shù)，使緊密度最小值大于1；

步驟4計(jì)算網(wǎng)絡(luò)中每條邊的邊介數(shù)，并用邊介數(shù)除以用戶緊密度值作為每條邊的權(quán)重；

步驟5刪除權(quán)重最大的邊，如果有多條邊的權(quán)重都為最大值，則隨機(jī)選取一條邊刪除；

步驟6判斷網(wǎng)絡(luò)是否產(chǎn)生新的社區(qū)結(jié)構(gòu)，若產(chǎn)生則執(zhí)行步驟7，否則執(zhí)行步驟4；

步驟7計(jì)算網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)模塊度Q值并記錄對(duì)應(yīng)的社區(qū)劃分結(jié)構(gòu)，模塊度初始化值為0，得到模塊度的增量ΔQ；

步驟8若ΔQ>0，執(zhí)行步驟4，否則輸出之前模塊度Q值對(duì)應(yīng)的社區(qū)劃分結(jié)構(gòu)，算法結(jié)束。

4　實(shí)　驗(yàn)

4.1實(shí)驗(yàn)設(shè)計(jì)

在本節(jié)，因?yàn)椴杉奈⒉┱鎸?shí)數(shù)據(jù)沒有社區(qū)劃分的標(biāo)準(zhǔn)，不能驗(yàn)證算法的準(zhǔn)確性，所以采用了真實(shí)社會(huì)網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)來驗(yàn)證本文算法的有效性和準(zhǔn)確性。實(shí)驗(yàn)環(huán)境為CPU雙核2.4 GHz，內(nèi)存4 GB，操作系統(tǒng)為Win8；開發(fā)語言為Java，編程工具為Eclipse。

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

Zachary網(wǎng)絡(luò)[14]是1970年Zachary用了兩年時(shí)間觀察美國(guó)一所大學(xué)空手道俱樂部成員間的社會(huì)關(guān)系得到的。這個(gè)俱樂部由34個(gè)人組成，由于俱樂部主管和校長(zhǎng)之間產(chǎn)生爭(zhēng)執(zhí)，俱樂部分裂成為兩個(gè)分別以主管和校長(zhǎng)為核心的小團(tuán)體。將該網(wǎng)絡(luò)抽象成一個(gè)擁有34個(gè)節(jié)點(diǎn)、78條邊的圖，圖中邊的權(quán)值代表兩個(gè)節(jié)點(diǎn)成員的交流頻率。

LFR人工生成網(wǎng)絡(luò)[15]通過設(shè)定不同的網(wǎng)絡(luò)參數(shù)和社區(qū)參數(shù)來生成帶有劃分標(biāo)準(zhǔn)的復(fù)雜網(wǎng)絡(luò)，可以用來生成與微博網(wǎng)絡(luò)特征相似的人工網(wǎng)絡(luò)，其源程序可以從Fortunato[16]的個(gè)人網(wǎng)站中下載。該算法提供了社區(qū)劃分的標(biāo)準(zhǔn)，即帶有原始社區(qū)，解決了驗(yàn)證算法正確性的問題。使用LFR人工生成網(wǎng)絡(luò)時(shí)需要設(shè)置的主要參數(shù)如表1所示。

表1　LFR人工生成網(wǎng)絡(luò)主要參數(shù)

在LFR人工生成無向加權(quán)網(wǎng)絡(luò)時(shí)，n、k、maxk、muw的值需要設(shè)置，其他值都有默認(rèn)初始值，t1=0，t2=1，beta=1.5，mut=muw，minc和maxc的取值根據(jù)節(jié)點(diǎn)度數(shù)序列的范圍來選取。網(wǎng)絡(luò)是否具有社區(qū)性主要與參數(shù)mut和muw有關(guān)，當(dāng)mut越接近0時(shí)，社區(qū)結(jié)構(gòu)越顯著；越接近1，社區(qū)結(jié)構(gòu)越不顯著。muw同樣類似，越接近0時(shí)，社區(qū)中節(jié)點(diǎn)的權(quán)值會(huì)更加集中在社區(qū)內(nèi)部，社區(qū)之間的權(quán)值會(huì)越小。

4.3評(píng)價(jià)標(biāo)準(zhǔn)

為驗(yàn)證算法的有效性和準(zhǔn)確性，本文采用模塊度值和純度值來作為評(píng)價(jià)標(biāo)準(zhǔn)。模塊度Q值[14]定義為社區(qū)內(nèi)實(shí)際邊數(shù)與隨機(jī)連接情況下社區(qū)內(nèi)期望邊數(shù)之差，用來定量地描述網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的優(yōu)劣，公式如下：

(8)

其中，eii表示社區(qū)i內(nèi)部邊條數(shù)，ai表示與社區(qū)i中任意節(jié)點(diǎn)相連邊的條數(shù)。Q的取值范圍為[0,1]，在實(shí)際網(wǎng)絡(luò)中，Q值通常在0.3到0.7之間，Q值越大，網(wǎng)絡(luò)的劃分效果越好，社區(qū)結(jié)構(gòu)越明顯。

純度(purity)[16]，評(píng)價(jià)由不同方法生成的社區(qū)的準(zhǔn)確性。純度的定義如下：對(duì)于n個(gè)頂點(diǎn)的網(wǎng)絡(luò)，對(duì)于特定劃分R，其社區(qū)落在標(biāo)準(zhǔn)劃分G中的節(jié)點(diǎn)數(shù)目所占全部節(jié)點(diǎn)的比例。公式如下：

(9)

其中，R為劃分結(jié)果，G為標(biāo)準(zhǔn)結(jié)果，純度的取值范圍為[0,1]，純度值越大表明方法的準(zhǔn)確性越高。

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

為了驗(yàn)證算法的有效性和準(zhǔn)確性，本文對(duì)Zachary網(wǎng)絡(luò)和LFR生成的模擬微博網(wǎng)絡(luò)進(jìn)行社區(qū)劃分實(shí)驗(yàn)。將基于用戶緊密度的社區(qū)發(fā)現(xiàn)算法與GN算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，選用NodeXL[17]作為可視化工具來展示社區(qū)劃分效果。Zachary網(wǎng)絡(luò)原始拓?fù)淙鐖D1所示。

圖1　Zachary網(wǎng)絡(luò)原始拓?fù)鋱D

圖1中每一個(gè)節(jié)點(diǎn)代表一個(gè)空手道俱樂部會(huì)員，每條邊代表成員間的社會(huì)關(guān)系，邊的權(quán)值代表會(huì)員之間交流的頻率。實(shí)驗(yàn)中將邊權(quán)值作為用戶交互程度值來計(jì)算，根據(jù)算法1的步驟計(jì)算出網(wǎng)絡(luò)中緊密度最小值為0.109，將所有用戶的緊密度值乘以10，使用戶緊密度最小值大于1。使用傳統(tǒng)的GN算法、CIG_ESC與基于用戶緊密度的社區(qū)發(fā)現(xiàn)算法進(jìn)行社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)，社區(qū)劃分可視化結(jié)果分別如圖2所示。

圖2　Zachary網(wǎng)絡(luò)劃分結(jié)果圖

圖2(a)中實(shí)心節(jié)點(diǎn)和空心節(jié)點(diǎn)分別代表兩個(gè)社區(qū)內(nèi)的成員，使用GN算法第一次分割把原始社區(qū)劃分成了兩個(gè)社區(qū)，這個(gè)劃分結(jié)果與Zachary網(wǎng)絡(luò)的標(biāo)準(zhǔn)劃分結(jié)果完全一致。(b)的劃分結(jié)果與GN算法的劃分結(jié)果一致，同樣將原始社區(qū)劃分成了兩個(gè)社區(qū)，與Zachary網(wǎng)絡(luò)的標(biāo)準(zhǔn)劃分結(jié)果也一致。圖2(c)中實(shí)心節(jié)點(diǎn)、空心節(jié)點(diǎn)和三角形節(jié)點(diǎn)分別代表三個(gè)社區(qū)內(nèi)的成員，使用基于用戶親密度的算法最終把原始社區(qū)劃分成了三個(gè)社區(qū)。現(xiàn)在根據(jù)式(8)和式(9)的評(píng)價(jià)函數(shù)進(jìn)行計(jì)算，計(jì)算結(jié)果如表2所示。

表2　評(píng)價(jià)函數(shù)結(jié)果

可以從表2看出基于用戶親密度的算法得到的社區(qū)劃分結(jié)構(gòu)，基于用戶親密度的算法在將網(wǎng)絡(luò)進(jìn)行第一次劃分成兩個(gè)社區(qū)時(shí)，其劃分結(jié)果與標(biāo)準(zhǔn)劃分結(jié)構(gòu)一致。但該算法最終將網(wǎng)絡(luò)劃分為三個(gè)社區(qū)，導(dǎo)致純度值有所降低，但是其模塊度值有所增高。由圖2(a)-(c)可知，(c)中的實(shí)心節(jié)點(diǎn)和三角形節(jié)點(diǎn)屬于(a)和(b)中標(biāo)準(zhǔn)劃分的實(shí)心節(jié)點(diǎn)社區(qū)，可見該算法對(duì)標(biāo)準(zhǔn)劃分中的實(shí)心節(jié)點(diǎn)社區(qū)進(jìn)行了更加深層次的劃分。由此可知，該算法可以將Zachary網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)正確地劃分出。從表2還可以看出，GN算法也能得到正確的劃分結(jié)果，經(jīng)過分析是因?yàn)閆achary網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)非常明顯。為了驗(yàn)證基于微博網(wǎng)絡(luò)時(shí)，基于用戶親密度的算法比傳統(tǒng)GN算法更加有效和準(zhǔn)確，當(dāng)LFR人工生成一個(gè)模擬微博網(wǎng)絡(luò)時(shí)，設(shè)置參數(shù)使muw

圖3　LFR模擬微博網(wǎng)絡(luò)原始拓?fù)鋱D

圖3中的實(shí)心節(jié)點(diǎn)模擬微博網(wǎng)絡(luò)中的用戶，邊模擬微博網(wǎng)絡(luò)中互粉的用戶，權(quán)值模擬微博網(wǎng)絡(luò)中的用戶交互程度值，該網(wǎng)絡(luò)社區(qū)劃分標(biāo)準(zhǔn)結(jié)構(gòu)如表3所示。

表3　LFR人工網(wǎng)絡(luò)社區(qū)劃分標(biāo)準(zhǔn)結(jié)構(gòu)

根據(jù)算法1基于用戶親密度的社區(qū)發(fā)現(xiàn)算法步驟計(jì)算出網(wǎng)絡(luò)中緊密度最小值為0.0000235。將所有用戶的緊密度值乘以100 000，使用戶緊密度最小值大于1。使用傳統(tǒng)的GN算法、CIG_ESC算法和基于用戶緊密度的算法進(jìn)行實(shí)驗(yàn)，可視化效果如圖4所示。

圖4　LFR模擬微博網(wǎng)絡(luò)劃分結(jié)果圖

圖4(a)中實(shí)心節(jié)點(diǎn)、空心節(jié)點(diǎn)、三角形節(jié)點(diǎn)分別代表三個(gè)社區(qū)內(nèi)的成員;(b)中實(shí)心節(jié)點(diǎn)、空心節(jié)點(diǎn)、三角形節(jié)點(diǎn)和正方形節(jié)點(diǎn)分別代表四個(gè)社區(qū)內(nèi)的成員;(c)中實(shí)心節(jié)點(diǎn)、空心節(jié)點(diǎn)、三角形節(jié)點(diǎn)和正方形節(jié)點(diǎn)分別代表四個(gè)社區(qū)內(nèi)的成員。使用CIG_ESC算法與基于用戶關(guān)系緊密度的算法都將原始社區(qū)劃分成了四個(gè)社區(qū)，但是CIG_ESC算法將部分節(jié)點(diǎn)劃分錯(cuò)誤。而基于用戶親密度的算法劃分出的這四個(gè)社區(qū)與標(biāo)準(zhǔn)劃分結(jié)果完全一致，現(xiàn)在根據(jù)式(8)與式(9)的評(píng)價(jià)函數(shù)進(jìn)行計(jì)算，計(jì)算結(jié)果如表4所示。

表4　評(píng)價(jià)函數(shù)結(jié)果

可以從表4看出,基于用戶親密度算法的模塊度值和純度值均高于傳統(tǒng)的GN算法與CIG_ESC算法。該算法可以將LFR生成的微博模擬網(wǎng)絡(luò)正確地劃分出社區(qū)結(jié)構(gòu)，說明基于用戶親密度的社區(qū)發(fā)現(xiàn)算法可以對(duì)具有微博網(wǎng)絡(luò)特征的網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，并能得到有效和準(zhǔn)確的社區(qū)劃分結(jié)構(gòu)，具有一定的實(shí)用價(jià)值。

5　結(jié)　語

本文研究了基于用戶緊密度的微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。首先考慮用戶間的交互程度以及共有鄰居相似性，使用這些信息量化了用戶的關(guān)系緊密度，用戶間緊密度值越大表明越難被劃分開。根據(jù)傳統(tǒng)GN算法刪除邊介數(shù)值最大邊的思想，基于用戶親密度的算法在刪邊時(shí)使邊介數(shù)除以用戶緊密度值作為邊的權(quán)值，降低緊密度強(qiáng)的邊被刪除的概率，通過刪除權(quán)值最大的邊得到網(wǎng)絡(luò)的劃分結(jié)構(gòu)。對(duì)真實(shí)社會(huì)網(wǎng)絡(luò)Zachary網(wǎng)絡(luò)以及LFR人工生成的微博模擬網(wǎng)絡(luò)的實(shí)驗(yàn)表明，基于用戶親密度的算法可以發(fā)現(xiàn)這兩類網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，并且對(duì)社區(qū)結(jié)構(gòu)不明顯的網(wǎng)絡(luò)得到的實(shí)驗(yàn)結(jié)果要優(yōu)于傳統(tǒng)的GN算法，表明該算法是有效的。

在下一步工作中，如何降低算法的復(fù)雜度或?qū)⑺惴ú⑿谢瘉硖岣咚惴ǖ膱?zhí)行效率，能夠?qū)Ａ康奈⒉┱鎸?shí)數(shù)據(jù)進(jìn)行社區(qū)發(fā)現(xiàn)將會(huì)成為工作的重點(diǎn)。

[1] Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media？[C]//Proceedings of the 19th international conference on World wide web. New York: ACM, 2010: 591-600.

[2] Milgram S. The small world problem[J]. Psychology today, 1967,1(1): 61-67.

[3] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J].Nature, 1998, 393(6684): 440-442.

[4] Dunbar R. Grooming, gossip, and the evolution of language[M]. Cambridge: Harvard University Press, 1996.

[5] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[6] Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012, 8(1): 25-31.

[7] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291-307.

[8] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.

[9] Liu H, Salerno J, Young M J. Social computing and behavioral modeling[M]. Berlin: Springer Science & Business Media, 2009.

[10] 喬秀全, 楊春, 李曉峰, 等. 社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計(jì)算方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(12): 2403-2413.

[11] 林友芳, 王天宇, 唐銳, 等. 一種有效的社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(2): 337-345.

[12] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

[13] Kahanda I, Neville J. Using Transactional Information to Predict Link Strength in Online Social Networks[C]//Proceedings of the Third International AAAI Conference on Weblogs and SocialMedia, 2009：74-81.

[14] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.

[15] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1): 016118.

[16] Khorasgani RR, Chen J, Zaine C R. Top Leaders Community Detection Approach in Information Networks[C]//4th SNA-KDD Workshop on Social Network Mining and Analysis. Washington DC: USA, 2010, 1-9.

[17] Smith M A, Shneiderman B, Milic-Frayling N, et al. Analyzing (Social Media) Networks with NodeXL[C]//Proceedings of the 4th International Conference on Communities and Technologies. New York: ACM, 2009:255-264.

DETECTION ALGORITHM FOR MICROBLOGGING NETWORKS COMMUNITY BASED ON USER CLOSENESS

Wei Qingjie1Li Jingteng2Wang Yu2

1(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)2(CollegeofSoftwareEngineering,ChongqingUniversityofPostsandTelecommunications,Chongqing400065，China)

Aiming at the problem of difficult in accurately partitioning the microblogging network community, based on the characteristics of microblogging network, this paper proposes a user closeness-based detection algorithm for microblogging network community. The algorithm computes user closeness based on interaction level between users and common neighbours similarity in microblogging network community, and combines with traditional GN algorithm to make community partition in microblogging network. Experimental verifications are conducted on real social network and simulated microblogging network, results show that the algorithm can effectively detect the community structure in networks.

Community detectionMicroblogging networkGN algorithmUser closenessCommon neighbour similarity

2015-04-19。國(guó)家自然科學(xué)基金項(xiàng)目(61171060)；重慶市經(jīng)信委軟件精英人才培養(yǎng)與公共服務(wù)平臺(tái)建設(shè)項(xiàng)目(渝經(jīng)信投資[2011]167號(hào))；重慶市教委基金項(xiàng)目(渝教高[2010]48號(hào))。韋慶杰，教授級(jí)高工，主研領(lǐng)域：協(xié)同計(jì)算，軟件工程。李京騰，碩士生。汪雨，碩士生。

TP391

A

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