有向网络兴趣社区的快速挖掘算法及其在僵尸粉检测中的应用

王晨旭,秦涛,管晓宏,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