有向網絡興趣社區的快速挖掘算法及其在僵尸粉檢測中的應用

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

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

有向網絡興趣社區的快速挖掘算法及其在僵尸粉檢測中的應用

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

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

針對傳統的無向網絡社區挖掘方法無法實現大規模有向網絡中社區有效發現的問題,提出了一種新的有向圖社區及其興趣特征快速挖掘算法。采用貪心算法求解社區劃分模塊性最大化的優化問題,較好地平衡了有向圖社區挖掘中準確性與有效性之間的矛盾,實現對大規模微博類有向網絡社區結構的有效識別;基于發現的社區,采用tf-idf算法進一步挖掘社區用戶的興趣愛好,實現了對微博網絡中興趣小組的精確挖掘。基于新浪微博的實驗結果表明:所提算法不僅可以快速有效地挖掘有向網絡中的社區結構及其用戶的興趣特征,還能夠準確地檢測出微博網絡中的僵尸粉社區,研究結果對微博系統的凈化、謠言控制、網絡廣告的精準投放等研究具有重要的參考價值。

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

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

針對上述問題,從有向圖的模塊性定義出發,本文提出一種適用于大規模有向網絡的社區發現算法,該算法使用貪心策略來避免矩陣特征值的計算,在考慮了邊的方向性的同時有效地提高了計算效率,能夠找到與最優解相當的次優解,從而有效地平衡了算法準確性和效率之間的矛盾。隨后基于所挖掘出的社區結構,對社區成員發布的微博內容進行分析,進一步挖掘社區成員的興趣愛好。由于某些具有公共話題屬性的短語并不能反映社區成員的興趣特征,本文提出了一種基于搜索引擎tf-idf算法的興趣短語評分算法,實現了對社區用戶興趣愛好關鍵詞特征的有效提取。

基于新浪微博數據集的測試結果顯示,本文所提出的算法不僅可以快速有效地挖掘出微博系統中存在的用戶社區,還可以有效準確地識別社區用戶的興趣愛好。在實驗中發現由正常微博用戶構成的社區話題內容豐富且興趣愛好特征明顯,而僵尸粉社區則話題內容單一且用戶之間的連接不符合小世界特性,因此所提社區興趣發現算法能夠應用于由惡意用戶所組建的僵尸粉社區的識別。

1 微博網絡社區發現算法

微博關注網絡的定義如下。

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

1.1 無向網絡社區模塊性定義及其增益計算

被多數研究者所接受的一個復雜網絡中社區結構的定義是,社區結構內部節點連接緊密而與結構外的其他節點連接稀疏[9-10]。Girvan與Newman定義了社區結構的模塊性,用來評價社區成員之間連接的緊密程度,定量地衡量社區劃分的好壞[10]。

定義2無向圖社區結構的模塊性定義為,原始網絡中連接社區內部節點的邊所占比例與隨機網絡中連接社區內部節點的邊所占比例的期望的差值

(1)

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

(2)

式中:∑in為社區C內部所有邊的權值之和;∑tot為外部節點連接社區C內部節點所有邊的權值之和;si為節點i的強度;si,in為節點i連接社區C內部節點的邊的權值之和;w為所有邊的權值之和。

1.2 有向網絡社區模塊性定義及其增益計算

無向圖模塊性的定義并不能直接應用于有向網絡,這是因為在構建隨機有向網絡時需要分別根據節點的出度和入度對邊進行隨機連接,而不是僅僅根據節點的度(出度和入度之和)進行連接。為了計算有向圖的模塊性,Leicht和Newman在文獻[5]中對有向圖的模塊性做了定義。

定義3有向圖社區結構的模塊性定義為,原始有向網絡中連接社區內部節點的邊所占比例與有向隨機網絡中連接社區內部節點的邊所占比例的期望的差值

(3)

由有向圖的模塊性公式導出將單個節點i歸入或移除社區C所獲得的有向圖模塊性增益為

(4)

1.3 微博關注網絡社區發現算法

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

步驟1為網絡G(V,E)中的每一個節點vi∈V分配一個獨立的初始社區標簽,記為c(l)={vi},其中l為社區標識號。

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

(5)

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

步驟3重復步驟2,直到不再有節點歸并和移除為止。

步驟4生成社區衍生圖,將步驟2得到的社區看作獨立節點,將社區之間的邊作為新的邊構建新的有向圖,其中邊的權重為社區之間同向邊的權值之和,社區內部的邊用自環表示。衍生圖的生成過程如圖1所示。

步驟5將步驟4得到的衍生圖應用到步驟2、3中,對衍生圖進行社區劃分,對被劃分到同一社區的節點內部的子節點全部合并到同一社區。

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

圖1 社區挖掘算法計算過程示意圖

2 微博社區興趣挖掘算法

(6)

然后計算話題在所有社區中出現次數的逆向頻率

(7)

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

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

(8)

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

3 實驗結果與分析

3.1 實驗數據

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

圖2 新浪微博關注網絡出入度互補累積分布

3.2 社區發現算法性能評估

為了驗證有向圖社區挖掘算法(DFC)的有效性和準確性,與基于無向圖的社區快速發現算法(FC)[12]和基于譜分析的有向圖社區發現算法(SDC)[10]進行了比較。實驗時對構建的關注網絡進行節點采樣,使得網絡節點的個數按遞增數列增長,最后選取采樣網絡的最大弱連接子圖進行實驗,每個網絡計算100次,每個數據點為這100次實驗的平均值。

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

(a)算法所需時間與網絡中節點數的關系

(b)社區模塊性與網絡中節點數的關系

3.3 社區興趣挖掘算法有效性評估

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

表1 前5位社區及其興趣特征

4 挖掘算法在僵尸粉檢測中的應用

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

圖4 僵尸粉社區檢測示意圖

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

5 結 論

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

[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社區發現技術綜述 [J].計算機研究與發展,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]張云.基于開源軟件的中文學術文獻計量軟件的開發實踐 [J].現代圖書情報技術,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].現代圖書情報技術,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—),男,博士生;秦濤(通信作者),男,講師。

國家自然科學基金資助項目(61221063,61103240,6113241);國家科技支撐計劃資助項目(2011BAK08B02);中央高校基本科研業務費資助項目(2012jdhz09,xjj2011015)。

時間:2014-05-30

10.7652/xjtuxb201406002

TP393

:A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.002.html