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

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

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

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

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

微博是當(dāng)前最流行的在線社交媒體之一，有效地檢測(cè)出微博用戶的社區(qū)結(jié)構(gòu)，能夠幫助人們理解微博社交網(wǎng)絡(luò)的結(jié)構(gòu)和用戶的行為特征，從而為用戶提供個(gè)性化的服務(wù)。然而，現(xiàn)有社區(qū)檢測(cè)算法大多只考慮社交網(wǎng)絡(luò)節(jié)點(diǎn)之間的直接鏈接關(guān)系，忽略節(jié)點(diǎn)自身的內(nèi)容特征。針對(duì)此問題，提出一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測(cè)算法。該算法通過融合社交網(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)表明，提出的算法能夠高效地檢測(cè)出社交網(wǎng)絡(luò)的主題社區(qū)。

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

1 引言

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

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

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

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

本文余下章節(jié)安排如下： 第二節(jié)描述增廣網(wǎng)絡(luò)的構(gòu)建方法，第三節(jié)中給出社區(qū)檢測(cè)算法相關(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ò)的過程主要分為三個(gè)步驟： 用戶內(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)對(duì)微博博文進(jìn)行分詞的效果并不理想，因此本文采用結(jié)巴分詞系統(tǒng)對(duì)用戶微博博文進(jìn)行分詞。結(jié)巴分詞基于Trie樹結(jié)構(gòu)生成句子中漢字所有可能成詞情況所構(gòu)成的有向無環(huán)圖，并采用動(dòng)態(tài)規(guī)劃查找最大概率路徑, 找出基于詞頻的最大切分組合。對(duì)于未登錄詞，采用了基于漢字成詞能力的隱馬爾可夫模型，使用了Viterbi算法[13]。

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

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

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

微博中的鏈接信息表現(xiàn)為用戶的粉絲和關(guān)注信息。一般情況下，擁有共同關(guān)注和共同粉絲較多的兩個(gè)用戶之間存有較大的鏈接相似度。本文采用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)融合兩個(gè)相似度矩陣，獲得用戶相似度矩陣，即增廣網(wǎng)絡(luò)sim。具體處理方法如式(5)所示。

3 社區(qū)檢測(cè)算法

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

3.1 相關(guān)定義

定義1 模塊度[4]是評(píng)價(jià)社區(qū)檢測(cè)效果的指標(biāo)。模塊度越高，則表示社區(qū)檢測(cè)效果越理想，社區(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時(shí)，δ(ci,cj)=1，反之，則δ(ci,cj)=0；m為網(wǎng)絡(luò)連邊的權(quán)重之和。

定義2 當(dāng)節(jié)點(diǎn)i轉(zhuǎn)移社區(qū)時(shí)，其模塊度增益[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ò)。對(duì)增廣網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)，循環(huán)計(jì)算節(jié)點(diǎn)轉(zhuǎn)移社區(qū)得到模塊度增益，若最大模塊度增益大于0，則將該點(diǎn)轉(zhuǎn)移至獲得最大模塊度增益的社區(qū)中，從而不斷提升模塊度，當(dāng)模塊度不再提升或模塊度增益均小于0時(shí)結(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í)際性，本文以作者所在高校的微博用戶為主要分析對(duì)象，通過設(shè)定學(xué)校教師等種子用戶進(jìn)行廣度遍歷爬取數(shù)據(jù)，最終得到的大部分微博用戶都與所在的高校密切相關(guān)。

為去除網(wǎng)絡(luò)中的“僵尸”用戶，本文對(duì)數(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個(gè)特征值。在設(shè)定信息利用率為大于85%，進(jìn)行主成分分析后得到585個(gè)主成分，各個(gè)主成分信息利用率如表1所示。

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

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

CD-AN在構(gòu)建增廣網(wǎng)絡(luò)的過程中使用了兩個(gè)融合參數(shù)α和β，為分析參數(shù)對(duì)算法進(jìn)行社區(qū)檢測(cè)時(shí)產(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時(shí)，在圖2中模塊度隨α的變化發(fā)生較大變化，且在α=0.7時(shí)模塊度達(dá)到峰值。進(jìn)一步試驗(yàn)選定α=0.7時(shí)，觀察β變化過程中模塊度的變化是否如α=0.5時(shí)一樣，不發(fā)生明顯變化。實(shí)驗(yàn)結(jié)果表明，α參數(shù)能夠較大的影響社區(qū)檢測(cè)的效果，而β參數(shù)對(duì)社區(qū)檢測(cè)效果的影響不明顯。在保留社區(qū)的主題特征下，當(dāng)α=0.7，β∈[0.2,0.9]時(shí)，社區(qū)檢測(cè)效果較為理想。

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

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

為驗(yàn)證融合文本內(nèi)容和鏈接信息策略比只考慮鏈接信息或只考慮內(nèi)容信息的社區(qū)檢測(cè)結(jié)果更好，分別對(duì)用戶鏈接相似度網(wǎng)絡(luò)、內(nèi)容相似度網(wǎng)絡(luò)和融合內(nèi)容與鏈接信息的增廣網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè)。為去除用戶順序?qū)λ惴ㄔ谏鐓^(qū)檢測(cè)時(shí)產(chǎn)生的影響，對(duì)用戶數(shù)據(jù)序列亂序并進(jìn)行10次仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中算法對(duì)三種網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè)獲得模塊度的最大值、最小值和平均值如表2所示。(本文實(shí)驗(yàn)平臺(tái)的服務(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)容信息時(shí)，檢測(cè)出社區(qū)后的模塊度很小，且達(dá)不到具有社區(qū)結(jié)構(gòu)下界。

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

續(xù)表

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

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

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

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

圖5 時(shí)間開銷對(duì)比圖

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

在選定融合參數(shù)α=0.7，β=0.5時(shí)，CD-AN在融合內(nèi)容和鏈接信息的增廣網(wǎng)絡(luò)上社區(qū)檢測(cè)效果如圖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個(gè)社區(qū)，其中大型社區(qū)(社區(qū)節(jié)點(diǎn)占有率>20%)有二個(gè)，中型社區(qū)(社區(qū)節(jié)點(diǎn)占有率>5%)有三個(gè)，其余均為小型社區(qū)。

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

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

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

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

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

續(xù)表

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

5 結(jié)束語

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

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

[1] 蔣盛益, 楊博泓, 吳美玲. 基于快速社區(qū)檢測(cè)的協(xié)同過濾推薦算法[J]. 廣西大學(xué)學(xué)報(bào)(自然科學(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)系挖掘和個(gè)性化推薦。E?mail：boryee@qq．com姚娟娜(1992—)，學(xué)士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、社會(huì)網(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é)社會(huì)科學(xué)“十二五”規(guī)劃項(xiàng)目(GD14YXW02)

TP391

A