王晨旭,秦濤,管曉宏,2,周亞東

(1.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點實驗室,710049,西安;2.清華大學(xué)自動化系智能與網(wǎng)絡(luò)化系統(tǒng)研究中心,100084,北京)

有向網(wǎng)絡(luò)興趣社區(qū)的快速挖掘算法及其在僵尸粉檢測中的應(yīng)用

王晨旭1,秦濤1,管曉宏1,2,周亞東1

(1.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點實驗室,710049,西安;2.清華大學(xué)自動化系智能與網(wǎng)絡(luò)化系統(tǒng)研究中心,100084,北京)

針對傳統(tǒng)的無向網(wǎng)絡(luò)社區(qū)挖掘方法無法實現(xiàn)大規(guī)模有向網(wǎng)絡(luò)中社區(qū)有效發(fā)現(xiàn)的問題,提出了一種新的有向圖社區(qū)及其興趣特征快速挖掘算法。采用貪心算法求解社區(qū)劃分模塊性最大化的優(yōu)化問題,較好地平衡了有向圖社區(qū)挖掘中準(zhǔn)確性與有效性之間的矛盾,實現(xiàn)對大規(guī)模微博類有向網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的有效識別;基于發(fā)現(xiàn)的社區(qū),采用tf-idf算法進(jìn)一步挖掘社區(qū)用戶的興趣愛好,實現(xiàn)了對微博網(wǎng)絡(luò)中興趣小組的精確挖掘?；谛吕宋⒉┑膶嶒灲Y(jié)果表明:所提算法不僅可以快速有效地挖掘有向網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)及其用戶的興趣特征,還能夠準(zhǔn)確地檢測出微博網(wǎng)絡(luò)中的僵尸粉社區(qū),研究結(jié)果對微博系統(tǒng)的凈化、謠言控制、網(wǎng)絡(luò)廣告的精準(zhǔn)投放等研究具有重要的參考價值。

微博;有向圖;社區(qū)挖掘;用戶興趣小組;僵尸粉

微博作為一種新興的社交媒體,自其創(chuàng)建以來便迅速得到了眾多用戶的喜愛和參與,因其對網(wǎng)絡(luò)營銷、社會輿論的極大影響力而受到越來越多學(xué)者的關(guān)注。微博通過用戶之間的相互關(guān)注而構(gòu)成網(wǎng)絡(luò),且這種關(guān)注關(guān)系是單向的,使微博關(guān)注網(wǎng)絡(luò)成為典型的有向網(wǎng)絡(luò)[1]。在社會網(wǎng)絡(luò)中,具有相似角色、擁有共同興趣的用戶往往會自覺或不自覺地緊密聯(lián)系在一起,進(jìn)而構(gòu)成網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。社區(qū)發(fā)現(xiàn)作為復(fù)雜網(wǎng)絡(luò)研究的核心內(nèi)容,在朋友關(guān)系網(wǎng)絡(luò)、在線社會網(wǎng)絡(luò)以及Web網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)中有著重要的應(yīng)用[2-4],對微博網(wǎng)絡(luò)中的社區(qū)及其用戶興趣愛好進(jìn)行挖掘是實現(xiàn)高效網(wǎng)絡(luò)管理與控制的基礎(chǔ)。傳統(tǒng)方法由于忽略了邊的方向性信息,導(dǎo)致挖掘結(jié)果有一定的誤差,Leicht等強烈建議在對有向圖進(jìn)行社區(qū)挖掘時應(yīng)盡可能地利用邊的方向性信息[5]。Nicosia等在Newman給出的有向圖模塊性定義的基礎(chǔ)上,提出了一種可用于發(fā)現(xiàn)有向網(wǎng)絡(luò)中有交疊的社區(qū)發(fā)現(xiàn)方法[6]。Levorato等提出了一種發(fā)現(xiàn)有向網(wǎng)絡(luò)中p-連接子圖的方法,并將其用于有向網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)[7]。Wang等研究了大規(guī)模社交網(wǎng)絡(luò)中核心社區(qū)的檢測[8]。這些有向圖社區(qū)發(fā)現(xiàn)算法雖然考慮了邊的方向性,但計算復(fù)雜度高或定義不明確,很難應(yīng)用于微博類大規(guī)模有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

針對上述問題,從有向圖的模塊性定義出發(fā),本文提出一種適用于大規(guī)模有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法,該算法使用貪心策略來避免矩陣特征值的計算,在考慮了邊的方向性的同時有效地提高了計算效率,能夠找到與最優(yōu)解相當(dāng)?shù)拇蝺?yōu)解,從而有效地平衡了算法準(zhǔn)確性和效率之間的矛盾。隨后基于所挖掘出的社區(qū)結(jié)構(gòu),對社區(qū)成員發(fā)布的微博內(nèi)容進(jìn)行分析,進(jìn)一步挖掘社區(qū)成員的興趣愛好。由于某些具有公共話題屬性的短語并不能反映社區(qū)成員的興趣特征,本文提出了一種基于搜索引擎tf-idf算法的興趣短語評分算法,實現(xiàn)了對社區(qū)用戶興趣愛好關(guān)鍵詞特征的有效提取。

基于新浪微博數(shù)據(jù)集的測試結(jié)果顯示,本文所提出的算法不僅可以快速有效地挖掘出微博系統(tǒng)中存在的用戶社區(qū),還可以有效準(zhǔn)確地識別社區(qū)用戶的興趣愛好。在實驗中發(fā)現(xiàn)由正常微博用戶構(gòu)成的社區(qū)話題內(nèi)容豐富且興趣愛好特征明顯,而僵尸粉社區(qū)則話題內(nèi)容單一且用戶之間的連接不符合小世界特性,因此所提社區(qū)興趣發(fā)現(xiàn)算法能夠應(yīng)用于由惡意用戶所組建的僵尸粉社區(qū)的識別。

1 微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

微博關(guān)注網(wǎng)絡(luò)的定義如下。

定義1微博關(guān)注網(wǎng)絡(luò)為G(V,E),其中V為微博用戶的集合,E為用戶之間關(guān)注關(guān)系的集合。邊的構(gòu)造原則為:如果用戶u,v∈V,且用戶u關(guān)注了用戶v,則存在一條從u指向v的有向邊,即euv∈E。

1.1 無向網(wǎng)絡(luò)社區(qū)模塊性定義及其增益計算

被多數(shù)研究者所接受的一個復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的定義是,社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點連接緊密而與結(jié)構(gòu)外的其他節(jié)點連接稀疏[9-10]。Girvan與Newman定義了社區(qū)結(jié)構(gòu)的模塊性,用來評價社區(qū)成員之間連接的緊密程度,定量地衡量社區(qū)劃分的好壞[10]。

定義2無向圖社區(qū)結(jié)構(gòu)的模塊性定義為,原始網(wǎng)絡(luò)中連接社區(qū)內(nèi)部節(jié)點的邊所占比例與隨機網(wǎng)絡(luò)中連接社區(qū)內(nèi)部節(jié)點的邊所占比例的期望的差值

(1)

式中:Aij為邊eij的權(quán)值;si=∑j∈N(i)Aij為節(jié)點i的強度;N(i)為節(jié)點i的鄰居節(jié)點的集合;w=∑i,jAij為無向圖所有邊的權(quán)值之和;ci為節(jié)點i所屬社區(qū)的標(biāo)簽;δ(a,b)為Kronecker沖擊函數(shù)。如果a=b,δ(a,b)=1;否則,δ(a,b)=0。社區(qū)發(fā)現(xiàn)問題可以轉(zhuǎn)化為求解模塊性最大化這一優(yōu)化問題,然而這一問題的精確求解已被證明為NP-hard[11],為了提高在大規(guī)模網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的效率,Blondel等提出了一種基于無向圖模塊性優(yōu)化的社區(qū)結(jié)構(gòu)快速發(fā)現(xiàn)方法[12]。該方法的核心思想是計算將單個節(jié)點i歸入其相鄰社區(qū)C所獲得的模塊性增益,而該增益的計算無需考慮全局信息而僅需考慮節(jié)點i所在的局部結(jié)構(gòu)信息,大大減少了計算所需時間。無向圖模塊性增益計算公式為

(2)

式中:∑in為社區(qū)C內(nèi)部所有邊的權(quán)值之和;∑tot為外部節(jié)點連接社區(qū)C內(nèi)部節(jié)點所有邊的權(quán)值之和;si為節(jié)點i的強度;si,in為節(jié)點i連接社區(qū)C內(nèi)部節(jié)點的邊的權(quán)值之和;w為所有邊的權(quán)值之和。

1.2 有向網(wǎng)絡(luò)社區(qū)模塊性定義及其增益計算

無向圖模塊性的定義并不能直接應(yīng)用于有向網(wǎng)絡(luò),這是因為在構(gòu)建隨機有向網(wǎng)絡(luò)時需要分別根據(jù)節(jié)點的出度和入度對邊進(jìn)行隨機連接,而不是僅僅根據(jù)節(jié)點的度(出度和入度之和)進(jìn)行連接。為了計算有向圖的模塊性,Leicht和Newman在文獻(xiàn)[5]中對有向圖的模塊性做了定義。

定義3有向圖社區(qū)結(jié)構(gòu)的模塊性定義為,原始有向網(wǎng)絡(luò)中連接社區(qū)內(nèi)部節(jié)點的邊所占比例與有向隨機網(wǎng)絡(luò)中連接社區(qū)內(nèi)部節(jié)點的邊所占比例的期望的差值

(3)

由有向圖的模塊性公式導(dǎo)出將單個節(jié)點i歸入或移除社區(qū)C所獲得的有向圖模塊性增益為

(4)

1.3 微博關(guān)注網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

在求解模塊性最大化問題時引入貪心算法的思想,使得在社區(qū)發(fā)現(xiàn)時僅僅需要考慮單個節(jié)點的本地網(wǎng)絡(luò)結(jié)構(gòu),即與節(jié)點相鄰的社區(qū),從而大大降低了算法的時間復(fù)雜度。算法的基本思想是,每次將節(jié)點歸并到增益最大的社區(qū),直到所劃分社區(qū)的模塊性不再增加為止,具體步驟如下。

步驟1為網(wǎng)絡(luò)G(V,E)中的每一個節(jié)點vi∈V分配一個獨立的初始社區(qū)標(biāo)簽,記為c(l)={vi},其中l(wèi)為社區(qū)標(biāo)識號。

步驟2對網(wǎng)絡(luò)中每一個節(jié)點vi∈V,考慮其鄰居節(jié)點所屬社區(qū)的集合CN(vi)={c(l)|vj∈N(vi),vj∈c(l)},根據(jù)式(4)計算將節(jié)點vi從其所屬社區(qū)中移除并將其歸入鄰居社區(qū)后的模塊性增益。根據(jù)下式選擇將節(jié)點vi歸入的社區(qū)

(5)

如果沒有增益大于0的社區(qū),則節(jié)點vi維持原來所屬社區(qū)不變。一旦有節(jié)點被歸入社區(qū)c(k),則計算將c(k)中每一個節(jié)點移除該社區(qū)所得的模塊性增益,若增益大于0,則將節(jié)點從原社區(qū)中移除。

步驟3重復(fù)步驟2,直到不再有節(jié)點歸并和移除為止。

步驟4生成社區(qū)衍生圖,將步驟2得到的社區(qū)看作獨立節(jié)點,將社區(qū)之間的邊作為新的邊構(gòu)建新的有向圖,其中邊的權(quán)重為社區(qū)之間同向邊的權(quán)值之和,社區(qū)內(nèi)部的邊用自環(huán)表示。衍生圖的生成過程如圖1所示。

步驟5將步驟4得到的衍生圖應(yīng)用到步驟2、3中,對衍生圖進(jìn)行社區(qū)劃分,對被劃分到同一社區(qū)的節(jié)點內(nèi)部的子節(jié)點全部合并到同一社區(qū)。

步驟6重復(fù)上述步驟直到所劃分社區(qū)的整體模塊性不再增加為止。

圖1 社區(qū)挖掘算法計算過程示意圖

2 微博社區(qū)興趣挖掘算法

(6)

然后計算話題在所有社區(qū)中出現(xiàn)次數(shù)的逆向頻率

(7)

式中:|C|為總的社區(qū)個數(shù);|{c|t∈Tc}|為包含話題t的社區(qū)個數(shù)。話題t在社區(qū)c中的代表性可由fc(t)與fi(t)相乘得到

Ic(t)=fc(t)fi(t)

(8)

話題在某一社區(qū)中出現(xiàn)的頻率越高,在其他社區(qū)中出現(xiàn)的頻率越低,Ic(t)值越大,話題t在社區(qū)c中越具有代表性。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

從2011年3月到2011年6月我們爬取了新浪微博中共70806個用戶的用戶信息及其關(guān)注列表,并利用此數(shù)據(jù)構(gòu)建微博關(guān)注網(wǎng)絡(luò)G(V,E)。該關(guān)注網(wǎng)絡(luò)的最大弱連接子圖共有70806個節(jié)點,370748條邊。圖2為所構(gòu)建關(guān)注網(wǎng)絡(luò)的出入度的互補累計分布函數(shù)。由圖可見,微博網(wǎng)絡(luò)中用戶的關(guān)注數(shù)(出度)呈現(xiàn)縱尾現(xiàn)象,表明大多數(shù)用戶僅關(guān)注較少數(shù)量的用戶,而被關(guān)注數(shù)(入度)遵循冪律分布,這與其他研究結(jié)果中的結(jié)論一致[14]。為了對所發(fā)現(xiàn)的微博社區(qū)進(jìn)行興趣挖掘,爬蟲還爬取了所有用戶最近發(fā)布的200條微博,并利用此數(shù)據(jù)挖掘社區(qū)用戶的興趣愛好特征。

圖2 新浪微博關(guān)注網(wǎng)絡(luò)出入度互補累積分布

3.2 社區(qū)發(fā)現(xiàn)算法性能評估

為了驗證有向圖社區(qū)挖掘算法(DFC)的有效性和準(zhǔn)確性,與基于無向圖的社區(qū)快速發(fā)現(xiàn)算法(FC)[12]和基于譜分析的有向圖社區(qū)發(fā)現(xiàn)算法(SDC)[10]進(jìn)行了比較。實驗時對構(gòu)建的關(guān)注網(wǎng)絡(luò)進(jìn)行節(jié)點采樣,使得網(wǎng)絡(luò)節(jié)點的個數(shù)按遞增數(shù)列增長,最后選取采樣網(wǎng)絡(luò)的最大弱連接子圖進(jìn)行實驗,每個網(wǎng)絡(luò)計算100次,每個數(shù)據(jù)點為這100次實驗的平均值。

圖3a為實驗中各算法所需時間與網(wǎng)絡(luò)中節(jié)點個數(shù)的關(guān)系。由圖可知,FC算法的計算速度最快。相比于FC算法,DFC算法的計算時間有所增加,但計算時間仍幾乎是隨著節(jié)點個數(shù)線性增加。SDC算法需要計算網(wǎng)絡(luò)鄰接矩陣的特征值,因此算法消耗的時間幾乎隨節(jié)點數(shù)量指數(shù)增加。圖3b為算法所劃分社區(qū)的有向模塊性值與網(wǎng)絡(luò)中節(jié)點個數(shù)的關(guān)系。由圖可見,無論使用何種算法,所得網(wǎng)絡(luò)社區(qū)模塊性均在0.5～0.8之間,這表明微博網(wǎng)絡(luò)具有很好的社區(qū)模塊性,對其進(jìn)行社區(qū)劃分是可行的。雖然DFC算法所劃分出的社區(qū)結(jié)構(gòu)質(zhì)量不及SDC算法,但所得結(jié)果相差很小,考慮到計算時間上的消耗,DFC算法具有明顯的優(yōu)勢。由以上分析可知,所提有向圖社區(qū)挖掘算法有效地平衡了計算時間和準(zhǔn)確性之間的矛盾,從而能夠應(yīng)用于微博類大規(guī)模有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

(a)算法所需時間與網(wǎng)絡(luò)中節(jié)點數(shù)的關(guān)系

(b)社區(qū)模塊性與網(wǎng)絡(luò)中節(jié)點數(shù)的關(guān)系

3.3 社區(qū)興趣挖掘算法有效性評估

表1列出了由DFC算法所挖掘的最大的前5位社區(qū)的興趣特征:社區(qū)前10位的常用短語(k=10)出現(xiàn)的次數(shù)以及該短語的tf-idf值。由表1可見,出現(xiàn)次數(shù)最多的短語不一定具有更好的代表性,這也表明使用tf-idf算法對短語的有效性進(jìn)行評估的必要性。各個社區(qū)之間的興趣愛好有著很大的不同,例如社區(qū)1更關(guān)注“精選”“笑話”“電影”“搞笑”等內(nèi)容,由此可以推斷該社區(qū)中以年輕用戶為主;社區(qū)2最常出現(xiàn)的短語包括“博文”“手機”“男人”“女人”“星座”等,由此可以推斷該社區(qū)中的用戶更關(guān)注兩性生活;社區(qū)3的興趣愛好則集中于“美國”“公司”“工作”等,可以推斷該社區(qū)為工作族;社區(qū)4更關(guān)注“路況”“孩子”“城市”等,可以推斷該社區(qū)大部分用戶為父母;社區(qū)5更關(guān)注“語錄”“電子產(chǎn)品”以及“影評”等,可以推斷其大部分社區(qū)成員為電子產(chǎn)品和電影愛好者。

表1 前5位社區(qū)及其興趣特征

4 挖掘算法在僵尸粉檢測中的應(yīng)用

在社會網(wǎng)絡(luò)中,被同一個人或組織控制的虛假帳號往往會緊密地連接在一起,Viswanath等發(fā)現(xiàn)無向網(wǎng)絡(luò)中的大多數(shù)惡意用戶檢測算法可以通過社區(qū)發(fā)現(xiàn)算法來實現(xiàn)[3]。僵尸粉是微博系統(tǒng)中的虛假粉絲,通常是由某些應(yīng)用自動產(chǎn)生的惡意注冊用戶。這些賬戶往往被單一的個人或組織控制,因此它們之間往往會緊密地相互連接。由僵尸粉構(gòu)成的社區(qū)與興趣小組社區(qū)有著很大的區(qū)別。首先,共同興趣小組構(gòu)成的子圖具有小世界特性,而這些僵尸粉構(gòu)成的網(wǎng)絡(luò)子圖則隨機連接且緊密,有時甚至是全連接的。其次,僵尸粉社區(qū)從整體上看非常不活躍,即使有發(fā)布的微博,這些微博也往往非常相似,話題單一,而共同興趣小組則非常的活躍,且所發(fā)布的微博形式多樣,內(nèi)容豐富。這就使得通過社區(qū)興趣發(fā)現(xiàn)能夠?qū)⒐餐d趣小組與僵尸社區(qū)區(qū)分開來,從而達(dá)到檢測的目的。

圖4 僵尸粉社區(qū)檢測示意圖

圖4為所發(fā)現(xiàn)社區(qū)的衍生圖,圖中每個節(jié)點代表一個社區(qū)。圓圈標(biāo)識出了高度可疑的社區(qū),這些社區(qū)內(nèi)部連接緊密而與外部其他社區(qū)連接較少,具備僵尸粉網(wǎng)絡(luò)的基本特征。進(jìn)一步對這些社區(qū)的常用短語挖掘發(fā)現(xiàn),61號社區(qū)的常用短語只有“試試”“UC瀏覽器”“發(fā)出”“微博”等少數(shù)關(guān)鍵字,該社區(qū)中共有80個用戶,且所有用戶都僅僅發(fā)布了同樣的一條微博:“酷～試試一條從UC瀏覽器發(fā)出的微博”,進(jìn)一步的調(diào)查顯示這80個用戶的用戶名均為“U友+數(shù)字”形式,由此可以推斷該社區(qū)中的用戶通過UC瀏覽器自動注冊微博帳號,并自動添加其他以同樣形式注冊的用戶為好友,從而形成典型的僵尸粉社區(qū)。這表明所提方法能夠批量地發(fā)現(xiàn)僵尸粉用戶,為微博網(wǎng)絡(luò)的管理提供支持。

5 結(jié) 論

為了高效地挖掘微博網(wǎng)絡(luò)中的用戶興趣小組,本文提出了一種有向圖社區(qū)挖掘算法。該算法考慮了邊的方向性信息,與無向圖社區(qū)挖掘算法相比,較好地平衡了社區(qū)挖掘準(zhǔn)確率和運行效率之間的矛盾,能夠應(yīng)用于大規(guī)模微博網(wǎng)絡(luò)中社區(qū)的發(fā)現(xiàn)和提取。為了能夠有效地提取社區(qū)特有的常用短語以便迅速發(fā)現(xiàn)社區(qū)特有的興趣愛好,引入了tf-idf算法對所挖掘社區(qū)的前100位常用短語進(jìn)行評分,實驗結(jié)果表明,算法可以較好的提取社區(qū)用戶的興趣愛好特征。此外,實驗發(fā)現(xiàn)有些興趣小組的話題單一,社區(qū)成員之間的連接非常緊密且發(fā)布的微博內(nèi)容幾乎完全相同,具有僵尸粉社區(qū)的基本特征。這表明算法能夠發(fā)現(xiàn)連接緊密的僵尸粉社區(qū)網(wǎng)絡(luò),從而適用于對微博網(wǎng)絡(luò)中僵尸粉的檢測。

[1] JAVA A,SONG X,FININ T,et al.Why we twitter: understanding microblogging usage and communities [C]∥Proceedings of the Joint 9th WebKDD and 1st SNA-KDD workshop.Berlin,Germany: Springer,2007: 56-65.

[2] AHN Y Y,BAGROW J P,LEHMANN S.Link communities reveal multiscale complexity in networks [J].Nature,2010,466(7307): 761-764.

[3] VISWANATH B,POST A,GUMMADI K P,et al.An analysis of social network-based Sybil defenses [J].ACM SIGCOMM Computer Communication Review,2010,41(4): 363-374.

[4] 楊楠,弓丹志,李忺,等.Web社區(qū)發(fā)現(xiàn)技術(shù)綜述 [J].計算機研究與發(fā)展,2005,42(3): 439-447.

YANG Nan,GONG Danzhi,LI Xian,et al.Survey of web communities identification [J].Journal of Computer Research and Development,2005,42(3): 439-447.

[5] LEICHT E A,NEWMAN M E J.Community structure in directed networks [J].Physical Review Letters,2008,100(11): 118703.

[6] NICOSIA V,MANGIONI G,CARCHIOLO V,et al.Extending the definition of modularity to directed graphs with overlapping communities [J].Journal of Statistical Mechanics: Theory and Experiment,2009,2009(3): 03024.

[7] LEVORATO V,PETERMANN C.Detection of communities in directed networks based on strongly p-connected components [C]∥Proceedings of the Conference on Computational Aspects of Social Networks.Piscataway,NJ,USA: IEEE,2011: 211-216.

[8] WANG Liaoruo,LOU Tiancheng,TANG Jie,et al.Detecting community kernels in large social networks [C]∥Proceedings of the 2011 11th IEEE International Conference on Data Mining.Piscataway,NJ,USA: IEEE,2011: 784-793.

[9] GIRVAN M,NEWMAN M E.Community structure in social and biological networks [J].Proceedings of the National Academy of the Sciences of the United States of America,2001,99(22): 7821-7826.

[10]NEWMAN M E J.Detecting community structure in networks [J].The European Physical Journal B-Condensed Matter,2004,38(2): 321-330.

[11]DUCH J,ARENAS A.Community detection in complex networks using extremal optimization [J].Physical Review: E,2005,72(2): 027104.

[12]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,2008(10): 10008.

[13]張云.基于開源軟件的中文學(xué)術(shù)文獻(xiàn)計量軟件的開發(fā)實踐 [J].現(xiàn)代圖書情報技術(shù),2010,4(191): 87-91.

ZHANG Yun.The Practice on the development of software on the Chinese academic bibliometrics based on the open source software [J].New Technology of Library and Information Service,2010,4(191): 87-91.

[14]趙文兵,朱慶華,吳克文,等.微博客用戶特性及動機分析 [J].現(xiàn)代圖書情報技術(shù),2011(2): 69-75.

ZHAO Wenbing,ZHU Qinghua,WU Kewen,et al.Analysis of micro-blogging user character and motivation [J].New Technology of Library and Information Service,2011(2): 69-75.

(編輯 武紅江)

AFastMiningAlgorithmforInterestCommunityinDirectedNetworksandItsApplicationtoDetectionofZombieFans

WANG Chenxu1,QIN Tao1,GUAN Xiaohong1,2,ZHOU Yadong1

(1.MOE Key Lab for Intelligent and Network Security,Xi’an Jiaotong University,Xi’an 710049,China;2.Center for Intelligent and Networked Systems,Department of Automation,Tsinghua University,Beijing 100084,China)

A new fast community unfolding and interests mining algorithm is proposed to solve the problem that traditional methods cannot effectively extract communities from large-scale directed networks.A greedy algorithm is used to maximize modularity so that the tradeoff between the accuracy and efficiency in the community mining of directed networks is better balanced and its application to large scale microblog networks can be realized.The users’ interests in the extracted community are then further mined using the tf-idf algorithm to score the most-occurred phrases in the community.Experimental results based on Sina Microblog show that the proposed algorithm can not only find out the community structures and their interests quickly,but also can uncover the zombie-fans community efficiently and accurately.These results exhibit great values for system purification,rumors control and accurate delivery of online advertising in microblog systems.

microblog; directed graph; community mining; user interest groups

2013-12-12。

王晨旭(1986—),男,博士生;秦濤(通信作者),男,講師。

國家自然科學(xué)基金資助項目(61221063,61103240,6113241);國家科技支撐計劃資助項目(2011BAK08B02);中央高?；究蒲袠I(yè)務(wù)費資助項目(2012jdhz09,xjj2011015)。

時間:2014-05-30

10.7652/xjtuxb201406002

TP393

:A

:0253-987X(2014)06-0007-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.002.html