一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法

蔣盛益，楊博泓，姚娟娜，吳美玲,張鈺莎

(1. 廣東外語外貿(mào)大學(xué) 信息學(xué)院,廣東 廣州 510006; 2. 阿里巴巴,廣東 廣州 510620; 3. 廣東外語外貿(mào)大學(xué) 南國商學(xué)院,廣東 廣州 510545)

一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法

蔣盛益1，楊博泓1，姚娟娜1，吳美玲2,張鈺莎3

(1. 廣東外語外貿(mào)大學(xué) 信息學(xué)院,廣東 廣州 510006; 2. 阿里巴巴,廣東 廣州 510620; 3. 廣東外語外貿(mào)大學(xué) 南國商學(xué)院,廣東 廣州 510545)

微博是當(dāng)前最流行的在線社交媒體之一，有效地檢測出微博用戶的社區(qū)結(jié)構(gòu)，能夠幫助人們理解微博社交網(wǎng)絡(luò)的結(jié)構(gòu)和用戶的行為特征，從而為用戶提供個性化的服務(wù)。然而，現(xiàn)有社區(qū)檢測算法大多只考慮社交網(wǎng)絡(luò)節(jié)點(diǎn)之間的直接鏈接關(guān)系，忽略節(jié)點(diǎn)自身的內(nèi)容特征。針對此問題，提出一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法。該算法通過融合社交網(wǎng)絡(luò)的鏈接信息以及用戶在微博上所發(fā)布的博文內(nèi)容信息構(gòu)建增廣網(wǎng)絡(luò)，然后以模塊度為目標(biāo)函數(shù)快速挖掘增廣網(wǎng)絡(luò)中的主題社區(qū)。通過真實(shí)微博社交網(wǎng)絡(luò)的實(shí)驗(yàn)表明，提出的算法能夠高效地檢測出社交網(wǎng)絡(luò)的主題社區(qū)。

微博;社區(qū)檢測;模塊度;主成分分析;增廣網(wǎng)絡(luò);主題社區(qū)

1 引言

進(jìn)入Web2.0時代，人們交流的方式漸漸從傳統(tǒng)的面對面交談轉(zhuǎn)換為在線社交網(wǎng)絡(luò)上的互動。據(jù)CNNIC統(tǒng)計(jì)，截至2014年7月，我國微博用戶規(guī)模已達(dá)到了2.75億，微博已成為中國網(wǎng)民進(jìn)行網(wǎng)絡(luò)社交最主要的工具。有效地檢測出微博網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，一方面能夠?yàn)橛脩籼峁﹤€性化的服務(wù)，另一方面也能為商家的定向廣告投放提供依據(jù)[1]。

社區(qū)檢測(community detection)，也稱作社團(tuán)識別、社區(qū)發(fā)現(xiàn)，是指將網(wǎng)絡(luò)劃分成若干個子網(wǎng)絡(luò)，使得同一子網(wǎng)絡(luò)中節(jié)點(diǎn)間聯(lián)系較大，不同子網(wǎng)絡(luò)中節(jié)點(diǎn)間聯(lián)系較小[2]。已有社區(qū)檢測算法主要分為基于分裂的算法[3]、基于模塊度的算法[4-6]、基于譜聚類的算法[7]等，其中常用的社區(qū)檢測算法主要有GN算法[3]、CNM算法[5]、BGLL算法[6]和CPM算法[8]等。

然而，現(xiàn)有的社區(qū)檢測算法大多只考慮節(jié)點(diǎn)之間的直接鏈接關(guān)系，忽略了節(jié)點(diǎn)自身的特征屬性。對于微博社交網(wǎng)絡(luò)，由于用戶節(jié)點(diǎn)除了與其他用戶的關(guān)注/粉絲關(guān)系特征之外，還包含了自身發(fā)布博文的內(nèi)容特征，因此直接采用現(xiàn)有的算法對網(wǎng)絡(luò)進(jìn)行社區(qū)檢測效果并不理想。在微博社區(qū)檢測研究中，蔡波斯等人[9]提出了一種基于行為相似度的微博社區(qū)檢測算法，該算法通過對用戶人口特征使用主成分分析法構(gòu)造用戶特征，然后使用CPM算法檢測出社區(qū)結(jié)構(gòu)。閆光輝等人[10]提出了一種基于主題和鏈接分析的微博社區(qū)檢測算法，該算法分析微博用戶的鏈接及博文主題特性,提出了用戶相關(guān)度的度量方法,并以此計(jì)算節(jié)點(diǎn)間的傳遞概率,然后使用標(biāo)簽傳遞算法對用戶進(jìn)行分類，進(jìn)而得到社區(qū)檢測結(jié)果。文獻(xiàn)[11]提出了一種基于k-means聚類的微博社區(qū)檢測算法，該算法先構(gòu)建了微博網(wǎng)絡(luò)模型，然后以LC模塊度作為目標(biāo)函數(shù)，最后采用k-means對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類，通過優(yōu)化目標(biāo)函數(shù)實(shí)現(xiàn)微博社區(qū)檢測。文獻(xiàn)[12]提出了CLARANS算法，該算法首先利用提出的預(yù)處理方法對用戶博文進(jìn)行預(yù)處理，并提取用戶特征，然后采用一種自適應(yīng)的k策略對節(jié)點(diǎn)進(jìn)行聚類，最后以聚類結(jié)果為依據(jù)，檢測出微博的社區(qū)結(jié)構(gòu)。雖然上述方法借助用戶行為特征、主題和鏈接等信息，在一定程度上改進(jìn)了社區(qū)檢測的效果，但并沒有充分考慮用戶節(jié)點(diǎn)的文本內(nèi)容和鏈接信息，并且對于大規(guī)模的微博網(wǎng)絡(luò)，這些方法存在時間復(fù)雜度過高、檢測精度不足等問題。

針對上述問題，本文提出一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法，該算法通過對用戶的鏈接信息和內(nèi)容信息進(jìn)行加權(quán)融合構(gòu)建微博用戶網(wǎng)絡(luò)模型，獲得增廣網(wǎng)絡(luò)，并以模塊度為目標(biāo)函數(shù)，對增廣網(wǎng)絡(luò)進(jìn)行快速社區(qū)檢測，挖掘微博用戶的主題社區(qū)。實(shí)驗(yàn)結(jié)果表明，相比于單純考慮鏈接信息或文本內(nèi)容信息的檢測，提出算法能夠獲得更好的社區(qū)檢測結(jié)果；與現(xiàn)有的方法相比，提出算法能夠更高效的挖掘社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，且檢測出的社區(qū)具有主題特征。

本文余下章節(jié)安排如下： 第二節(jié)描述增廣網(wǎng)絡(luò)的構(gòu)建方法，第三節(jié)中給出社區(qū)檢測算法相關(guān)定義及算法步驟，第四節(jié)給出實(shí)驗(yàn)驗(yàn)證過程及分析，最后在第五節(jié)進(jìn)行全文總結(jié)。

2 增廣網(wǎng)絡(luò)構(gòu)建

為充分考慮微博用戶的鏈接信息及用戶自身的內(nèi)容特征信息，本文通過規(guī)則加權(quán)融合的方式構(gòu)建微博用戶網(wǎng)絡(luò)模型，即增廣網(wǎng)絡(luò)。構(gòu)建增廣網(wǎng)絡(luò)的過程主要分為三個步驟： 用戶內(nèi)容相似度矩陣構(gòu)建、用戶鏈接相似度矩陣構(gòu)建和融合內(nèi)容和鏈接相似度矩陣。具體流程如圖1所示。

圖1 增廣網(wǎng)絡(luò)構(gòu)建流程圖

2.1 用戶內(nèi)容特征提取

由于微博用戶發(fā)布的博文常包含著不規(guī)范的網(wǎng)絡(luò)用語，而這些網(wǎng)絡(luò)用語大多是未登錄詞，傳統(tǒng)的分詞系統(tǒng)對微博博文進(jìn)行分詞的效果并不理想，因此本文采用結(jié)巴分詞系統(tǒng)對用戶微博博文進(jìn)行分詞。結(jié)巴分詞基于Trie樹結(jié)構(gòu)生成句子中漢字所有可能成詞情況所構(gòu)成的有向無環(huán)圖，并采用動態(tài)規(guī)劃查找最大概率路徑, 找出基于詞頻的最大切分組合。對于未登錄詞，采用了基于漢字成詞能力的隱馬爾可夫模型，使用了Viterbi算法[13]。

2.2 內(nèi)容特征主成分分析

2.3 用戶內(nèi)容相似度矩陣構(gòu)建

2.4 用戶鏈接相似度矩陣構(gòu)建

微博中的鏈接信息表現(xiàn)為用戶的粉絲和關(guān)注信息。一般情況下，擁有共同關(guān)注和共同粉絲較多的兩個用戶之間存有較大的鏈接相似度。本文采用Jaccard相似性系數(shù)分別計(jì)算用戶的粉絲相似度和關(guān)注相似度矩陣simfans和simfollows。用戶的粉絲或關(guān)注相關(guān)性系數(shù)定義為：

式中，I和J分別表示用戶i和用戶j的粉絲或關(guān)注集，jacij即用戶i與用戶j之間的粉絲或關(guān)注相似度。根據(jù)計(jì)算出的用戶粉絲相似度矩陣和關(guān)注相似度矩陣，定義用戶鏈接相似度矩陣為：

式中，α為融合參數(shù)。

2.5 增廣網(wǎng)絡(luò)構(gòu)建

在獲得用戶的內(nèi)容相似度矩陣simc和用戶的鏈接相似度矩陣sim1后，通過規(guī)則加權(quán)融合兩個相似度矩陣，獲得用戶相似度矩陣，即增廣網(wǎng)絡(luò)sim。具體處理方法如式(5)所示。

3 社區(qū)檢測算法

研究表明，在微博社交網(wǎng)絡(luò)中存在著各種各樣的社區(qū)結(jié)構(gòu)，有效地檢測出微博的社區(qū)結(jié)構(gòu)有利于用戶體驗(yàn)和商業(yè)營銷。為解決現(xiàn)有社區(qū)檢測算法未充分考慮社交網(wǎng)絡(luò)節(jié)點(diǎn)的鏈接信息和內(nèi)容信息及時間復(fù)雜度過高的問題，本文提出一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法(AFastMicroblogCommunityDetectionAlgorithmbasedonAugmentedNetwork, 簡稱CD-AN)，并對微博社交網(wǎng)絡(luò)進(jìn)行社區(qū)檢測。

3.1 相關(guān)定義

定義1 模塊度[4]是評價社區(qū)檢測效果的指標(biāo)。模塊度越高，則表示社區(qū)檢測效果越理想，社區(qū)內(nèi)部更緊湊。其定義為：

式中，Aij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的連邊權(quán)重；ki和kj分別為與節(jié)點(diǎn)i和節(jié)點(diǎn)j有關(guān)聯(lián)的連邊權(quán)重之和；當(dāng)ci=cj時，δ(ci,cj)=1，反之，則δ(ci,cj)=0；m為網(wǎng)絡(luò)連邊的權(quán)重之和。

定義2 當(dāng)節(jié)點(diǎn)i轉(zhuǎn)移社區(qū)時，其模塊度增益[6]定義為：

式中，∑in為節(jié)點(diǎn)i轉(zhuǎn)移到的社區(qū)內(nèi)部連邊權(quán)重之和；∑tot為與節(jié)點(diǎn)i轉(zhuǎn)移到的社區(qū)內(nèi)部節(jié)點(diǎn)有關(guān)的連邊權(quán)重之和；ki為與節(jié)點(diǎn)i有關(guān)的連邊權(quán)重之和；ki,in為節(jié)點(diǎn)i到轉(zhuǎn)移到的社區(qū)內(nèi)部節(jié)點(diǎn)的連邊權(quán)重之和。

3.2 算法描述

本文提出算法的主要思路是： 首先通過分析微博用戶發(fā)布的內(nèi)容信息和鏈接信息，計(jì)算出用戶的內(nèi)容相似度矩陣和鏈接相似度矩陣，然后通過規(guī)則加權(quán)融合的方式融合用戶的內(nèi)容和鏈接信息，獲得增廣網(wǎng)絡(luò)。對增廣網(wǎng)絡(luò)的每個節(jié)點(diǎn)，循環(huán)計(jì)算節(jié)點(diǎn)轉(zhuǎn)移社區(qū)得到模塊度增益，若最大模塊度增益大于0，則將該點(diǎn)轉(zhuǎn)移至獲得最大模塊度增益的社區(qū)中，從而不斷提升模塊度，當(dāng)模塊度不再提升或模塊度增益均小于0時結(jié)束循環(huán)。算法偽代碼如下所示：

算法 CD-AN

輸入 用戶集U，用戶博文集D，用戶粉絲集FS，用戶關(guān)注集FL,最小模塊度差值ξ，最大迭代次數(shù)T

輸出 社區(qū)摘要

步驟

1) SEGMENT D→W;

2) COMPUTE TFIDF by formula(1);

3) TFIDF→ TFIDF-PC by PCA;

4) COMPUTEsimcbyformula(2);

5)COMPUTEsimfansandsimfollowbyformula(3);

6)COMPUTEsimlbyformula(4);

7)COMPUTEsimbyformula(5);

8)RandomsequenceofU;

9)COMPUTEqbyformula(6);

10)t=0;

11)WHILETrue:

12)FORuinU：

13)FINDneighcommofu;

14)FORncinneighcomm：

15)COMPUTEq-gainofu→nc;

16)MARKmaxq-gain;

17)IFmaxq-gain>0：

18)moveu→nc;

19)ELSE：

20)BREAK;

21)t+=1;

22)IFt>=T:

23)BREAK;

24)COMPUTEqlbyformula(6);

25)IFql-q<ξ:

26)BREAK;

27)RETURN;

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

新浪微博是國內(nèi)最為熱門的網(wǎng)絡(luò)社交應(yīng)用。本文通過編寫網(wǎng)絡(luò)爬蟲算法從新浪微博中爬取了真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，爬取的數(shù)據(jù)內(nèi)容包括了用戶的關(guān)注信息、粉絲信息以及用戶發(fā)布的博文信息。為了獲取的數(shù)據(jù)具有實(shí)際性，本文以作者所在高校的微博用戶為主要分析對象，通過設(shè)定學(xué)校教師等種子用戶進(jìn)行廣度遍歷爬取數(shù)據(jù)，最終得到的大部分微博用戶都與所在的高校密切相關(guān)。

為去除網(wǎng)絡(luò)中的“僵尸”用戶，本文對數(shù)據(jù)進(jìn)行了如下過濾： 1)粉絲或關(guān)注用戶數(shù)少于五人的用戶；2)關(guān)注數(shù)量為粉絲五倍的用戶；3)發(fā)布博文少于五條的用戶。在進(jìn)行過濾處理后，最終選取了1 800位用戶的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

由于用戶發(fā)布的微博數(shù)量規(guī)模大，微博用戶的用詞多樣，導(dǎo)致用戶的內(nèi)容特征向量維度較高。經(jīng)過分詞，計(jì)算TF-IDF后每位用戶的內(nèi)容特征向量包含了85 119個特征值。在設(shè)定信息利用率為大于85%，進(jìn)行主成分分析后得到585個主成分，各個主成分信息利用率如表1所示。

表1 主成分分析結(jié)果

4.2 參數(shù)實(shí)驗(yàn)

CD-AN在構(gòu)建增廣網(wǎng)絡(luò)的過程中使用了兩個融合參數(shù)α和β，為分析參數(shù)對算法進(jìn)行社區(qū)檢測時產(chǎn)生的影響，本文通過采用控制參數(shù)的方式，觀察模塊度隨著參數(shù)變化而產(chǎn)生的變化，以選取最佳參數(shù)取值。

如圖2所示，在試驗(yàn)中，我們控制了鏈接相似度矩陣融合參數(shù)α=0.5，觀察融合參數(shù)β變化過程中模塊度的變化，從圖2可以觀察，在初始階段模塊度出現(xiàn)陡增現(xiàn)象，隨之在β變化過程中，模塊度沒有產(chǎn)生明顯的變化。當(dāng)選定β=0.5時，在圖2中模塊度隨α的變化發(fā)生較大變化，且在α=0.7時模塊度達(dá)到峰值。進(jìn)一步試驗(yàn)選定α=0.7時，觀察β變化過程中模塊度的變化是否如α=0.5時一樣，不發(fā)生明顯變化。實(shí)驗(yàn)結(jié)果表明，α參數(shù)能夠較大的影響社區(qū)檢測的效果，而β參數(shù)對社區(qū)檢測效果的影響不明顯。在保留社區(qū)的主題特征下，當(dāng)α=0.7，β∈[0.2,0.9]時，社區(qū)檢測效果較為理想。

圖2 參數(shù)改變對模塊度的影響

4.3 增廣網(wǎng)絡(luò)的有效性驗(yàn)證

為驗(yàn)證融合文本內(nèi)容和鏈接信息策略比只考慮鏈接信息或只考慮內(nèi)容信息的社區(qū)檢測結(jié)果更好，分別對用戶鏈接相似度網(wǎng)絡(luò)、內(nèi)容相似度網(wǎng)絡(luò)和融合內(nèi)容與鏈接信息的增廣網(wǎng)絡(luò)進(jìn)行社區(qū)檢測。為去除用戶順序?qū)λ惴ㄔ谏鐓^(qū)檢測時產(chǎn)生的影響，對用戶數(shù)據(jù)序列亂序并進(jìn)行10次仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中算法對三種網(wǎng)絡(luò)進(jìn)行社區(qū)檢測獲得模塊度的最大值、最小值和平均值如表2所示。(本文實(shí)驗(yàn)平臺的服務(wù)器配置為Intel(R)Core(TM)2 Duo CPU E8400 @ 3.00GHz x2，8.00GB內(nèi)存，Python 2.7.3)

如表2所示，因?yàn)閮?nèi)容信息網(wǎng)絡(luò)為全網(wǎng)絡(luò)，與現(xiàn)實(shí)存在的社交網(wǎng)絡(luò)并不相符，所以在只考慮內(nèi)容信息時，檢測出社區(qū)后的模塊度很小，且達(dá)不到具有社區(qū)結(jié)構(gòu)下界。

表2 三種網(wǎng)絡(luò)社區(qū)檢測結(jié)果

續(xù)表

相比于只考慮鏈接信息，在融合文本內(nèi)容和鏈接信息的增廣網(wǎng)絡(luò)進(jìn)行社區(qū)檢測時，隨著模塊度的提升，社區(qū)數(shù)量快速地降低，使得檢測過程中計(jì)算節(jié)點(diǎn)轉(zhuǎn)移鄰接社區(qū)的時間開銷降低，且在收斂時模塊度平均提升了0.185，是鏈接信息網(wǎng)絡(luò)的2.083倍。

4.4 算法有效性驗(yàn)證

為驗(yàn)證本文算法相比于其他算法能在更少的時間開銷上獲得更好的社區(qū)檢測結(jié)果，本文將CD-AN與CPM算法[8]進(jìn)行實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果如圖3至圖5所示。在和CPM算法對比的實(shí)驗(yàn)中，本文控制節(jié)點(diǎn)數(shù)量(連邊數(shù)量)這一變量對兩算法進(jìn)行了社區(qū)數(shù)量、模塊度和時間開銷對比。通過圖3可以得出，當(dāng)融合參數(shù)α=0.7，β=0.5時，隨著節(jié)點(diǎn)數(shù)量的增加，本文算法檢測出的社區(qū)個數(shù)與CPM算法較為一致，且隨著節(jié)點(diǎn)增加，CD-AN在社區(qū)數(shù)量增長上更為平穩(wěn)；在圖4的模塊度對比中能明顯看出本文算法檢測社區(qū)后計(jì)算出來的模塊度均比CPM算法檢測社區(qū)后獲得的模塊度高，即本文算法檢測出的社區(qū)更為緊湊；在圖5的時間開銷對比上，隨著節(jié)點(diǎn)(連邊)的數(shù)量增加，CPM算法的時間開銷增長比本文算法的時間開銷增長更為明顯。綜上表明，CD-AN在社區(qū)數(shù)量穩(wěn)定性、模塊度和時間開銷三個指標(biāo)上均比CPM算法理想。

圖3 檢測出的社區(qū)數(shù)量對比圖

圖5 時間開銷對比圖

4.5 社區(qū)檢測效果分析

在選定融合參數(shù)α=0.7，β=0.5時，CD-AN在融合內(nèi)容和鏈接信息的增廣網(wǎng)絡(luò)上社區(qū)檢測效果如圖6和表3所示。由圖6可以看出微博社交網(wǎng)絡(luò)中具有明顯的社區(qū)結(jié)構(gòu)特征，即在同一社區(qū)的節(jié)點(diǎn)之間聯(lián)系較為緊密，在不同社區(qū)的節(jié)點(diǎn)之間聯(lián)系較為松散。由表3可以看出，增廣網(wǎng)絡(luò)共劃分出19個社區(qū)，其中大型社區(qū)(社區(qū)節(jié)點(diǎn)占有率>20%)有二個，中型社區(qū)(社區(qū)節(jié)點(diǎn)占有率>5%)有三個，其余均為小型社區(qū)。

4.6 社區(qū)主題特征分析

由于社區(qū)檢測過程中考慮到了用戶的內(nèi)容信息，通過進(jìn)一步的分析，可以得到各個社區(qū)所關(guān)注的主題。在過濾了一些共有或不帶有主題含義的停用詞如“微博”、“轉(zhuǎn)發(fā)”、“客戶端”、“今天”等后，選擇排名Top 10的詞作為社區(qū)的主題詞集，并通過人工理解獲得社區(qū)的主題描述。各個社區(qū)的主題分布如表4所示。

表3 各個社區(qū)的節(jié)點(diǎn)占有百分比

圖6 融合內(nèi)容和鏈接信息的增廣網(wǎng)絡(luò)社區(qū)檢測結(jié)果

表4 各個社區(qū)的主題詞集

續(xù)表

由于實(shí)驗(yàn)數(shù)據(jù)中的用戶大多為高校的學(xué)生，因此社區(qū)的主題特征帶有校園生活內(nèi)容的特征。部分社區(qū)具有明顯的主題性，如社區(qū)14的主題可理解為“迎新晚會”；社區(qū)18的主題可以理解為“婚禮”等。部分社區(qū)包括1個以上的主題，如社區(qū)6的主題包括了“紅線女之死”和“南京大屠殺”；社區(qū)13的主題包括“電影”和“音樂”。

5 結(jié)束語

微博作為當(dāng)前最熱的社交媒體之一，有效地檢測出微博中的用戶社區(qū)不僅能夠?yàn)橛脩籼峁﹤€性化推薦服務(wù)，而且也能夠?yàn)樯碳姨峁┒ㄏ驈V告投放的依據(jù)。然而，目前的社區(qū)檢測算法大多只考慮了社交網(wǎng)絡(luò)的鏈接信息，忽略了節(jié)點(diǎn)自身的內(nèi)容特征，并且面向微博社交網(wǎng)絡(luò)的社區(qū)檢測算法存在時間復(fù)雜度過高的問題。針對上述問題，本文提出了一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法。該算法首先對用戶發(fā)布的微博博文進(jìn)行分析，獲得用戶的內(nèi)容特征向量，并通過主成分分析對用戶內(nèi)容特征向量進(jìn)行降維處理，提升了算法執(zhí)行效率；其次通過Jaccard相關(guān)性系數(shù)計(jì)算用戶鏈接相似，最后融合用戶的內(nèi)容相似度矩陣和鏈接相似度矩陣，獲得用戶的增廣網(wǎng)絡(luò)，并對增廣網(wǎng)絡(luò)進(jìn)行快速的社區(qū)檢測。實(shí)驗(yàn)結(jié)果表明： 相比于單獨(dú)考慮鏈接信息或節(jié)點(diǎn)內(nèi)容的社區(qū)檢測算法，本文提出的方法能夠高效地檢測出較好的微博社區(qū)，且檢測出的社區(qū)能夠體現(xiàn)不同的主題特征。同時，與CPM算法相比，本文提出的方法時間開銷更小，檢測效果更好。

然而，由于新浪微博數(shù)據(jù)開放策略的限制，使得本文獲取的實(shí)驗(yàn)數(shù)據(jù)量較少。在后續(xù)工作中，將采用本文算法對更大規(guī)模的社交網(wǎng)絡(luò)進(jìn)行社區(qū)檢測，并通過分布式計(jì)算進(jìn)一步提高算法的執(zhí)行效率。

[1] 蔣盛益, 楊博泓, 吳美玲. 基于快速社區(qū)檢測的協(xié)同過濾推薦算法[J]. 廣西大學(xué)學(xué)報(自然科學(xué)版), 2013, 38(6): 1408-1412.

[2] Fortunato S, Castellano C. Community structure in graphs[M].Computational Complexity, Springer New York, 2012: 490-512.

[3] 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.

[4] Newman M E J. Analysis of weighted networks[J]. Physical Review E, 2004, 70(5): 056131.

[5] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.

[6] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10): 10008.

[7] Donetti L, Munoz M A. Detecting network communities: a new systematic and efficient algorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2004(10): 10012.

[8] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

[9] 蔡波斯, 陳翔. 基于行為相似度的微博社區(qū)發(fā)現(xiàn)研究[J]. 計(jì)算機(jī)工程, 2013, 39(8):55-59.

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

[11] Yang C, Ding H, Yang J, et al. Mining Microblog Community Based on Clustering Analysis[C]//Proceedings of the International Conference on Information Engineering and Applications (IEA) 2012. Springer London, 2013: 825-832.

[12] Huang T, Peng D, Cao L. Discovering Communities with Self-Adaptive k Clustering in Microblog Data[C]//2012 Proceedings of IEEE, 2012: 383-390.

[13] https://github.com/[OL].[2014-03-02].https://github.com/fxsjy/jieba

A Fast Microblog Community Detection Algorithm Based on Augmented Network

JIANG Shengyi1，YANG Bohong1，YAO Juanna1，WU Meiling2, ZHANG Yusha3

(1. School of Informatics, Guangdong University of Foreign Studies, Guangzhou，Guangdong 510006, China; 2. Alibaba Group, Guangzhou，Guangdong 510620, China; 3. South China Business College,Guangdong University of Foreign Studies, Guangzhou，Guangdong 510545, China)

Microblog is one of the most popular online social media nowadays. Identification of users’ community structure on Microblog can help people understand the community structure as well as users’ behaviors, and even provide personalized service for users. Currently, most of the studies on Microblog community detection algorithm focus on the link information, ignoring the information posted by users. To address this issue, a fast Microblog community detection algorithm based on augmented network is proposed. The algorithm constructs an augmented network by integrating users’ link information and content, on which community can be identified efficiently. Experimental results show that the proposed algorithm performs better in identifying the community structure of social networks in real Microblog network when compared with other algorithms.

Microblog; community detection; modularity; principal component analysis; augmented network; topic community

蔣盛益(1963—)，教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與自然語言處理。E?mail：jaingshengyi@163．com楊博泓(1991—)，碩士研究生，主要研究領(lǐng)域?yàn)橛脩絷P(guān)系挖掘和個性化推薦。E?mail：boryee@qq．com姚娟娜(1992—)，學(xué)士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、社會網(wǎng)絡(luò)分析。E?mail：denayao@foxmail．com

1003-0077(2016)05-0065-08

2014-09-07 定稿日期： 2015-12-20

國家自然科學(xué)基金(61572145);廣東省科技計(jì)劃項(xiàng)目(2014A040401083);廣東省哲學(xué)社會科學(xué)“十二五”規(guī)劃項(xiàng)目(GD14YXW02)

TP391

A