2014, Vol. 25
2. 北京建筑大学 电气与信息工程学院, 北京 100044;
3. 北京市建筑安全监测工程技术研究中心, 北京 100044
2. School of Electrical & Information Engineering, Beijing University of Civil Engineering & Architecture, Beijing 100044, China;
3. Beijing Engineering Research Center of Monitoring for Construction Safety, Beijing 100044, China
社区发现是指在社会网络中发现内聚的子群.社区发现是社会网络分析的重要问题,它有助于人们进一步认识、理解和掌握所研究的复杂网络对象,进而实现更深入的应用研究,例如个性化推荐[1]、朋友推荐[2]、大规模网络压缩求解[3]、异质网络分析[4]、社会网络演变[5]等.兴趣和网络结构双内聚的用户社区发现,是精准的市场营销和准确的个性化推荐服务等的重要研究内容[6, 7, 8].现实生活中,人们往往传播其所能接触到的感兴趣的信息.因此,好的用户社区发现应同时满足网络结构和兴趣双方面的内聚.网络结构是社区内部节点间信息传播的桥梁,兴趣是信息传播的原因.
得益于移动互联网的发展,微博用户规模及其社会影响力迅速增长.Twitter有不少于5亿的注册用户,每月活跃用户为2.3亿,而日活跃用户为1亿,每天推文5亿次(http://techcrunch.com/2012/07/30/analyst-twitter-passed-500m-users-in-june-2012-140m-of-them-in-us-jakarta-biggest-tweeting-city).新浪微博也拥有超过5亿的注册用户,每天有高达4.62千万的活跃用户和不少于1亿的微博(http://news.xinhuanet.com/info/2013-02/21/ c_132181760.htm).微博是现实社会的缩影,它为人们提供了巨量的有价值的研究数据.人们使用微博进行政
治[9]、市场营销[10]等活动,微博已成为一个公认的发表意见与看法的平台[11].
目前,针对微博用户社区发现的方法大致可分为3种:
(1) 基于用户内容[12, 13, 14, 15, 16].将用户微博内容进行兴趣特征提取,然后,基于兴趣特征进行用户聚类.该类方法忽略了微博网络结构(关注关系)在信息传播中的桥梁作用;
(2) 基于用户联系[17, 18, 19, 20, 21, 22, 23, 24, 25].提取微博网络的关注或好友关系,将问题转化为图论等问题进行社区发现.该类方法没有考虑用户的兴趣特征,因此,无法证明其兴趣的内聚性;
(3) 综合方法[26,27].将微博内容和用户联系相结合,基于内容提取基于兴趣的用户社区,基于用户联系提取基于联系的用户社区,再采用某种方法将两个社区进行融合,形成兴趣和网络结构双内聚的用户社区.该类方法由于需要进行两次社区发现,且需要进行社区融合;因此,算法效率较低.
真实情况中,用户往往对多种兴趣感兴趣,每个用户都应根据其兴趣归属于多个用户社区.因此,用户社区实际上是一个重叠社区.LCA算法[28]是目前较好的重叠社区发现算法,它以边为单元进行边聚类,从而根据边分属不同的社区,将节点划分到多个不同的社区.LCA算法较好地平衡了社区发现中兴趣和网络结构双方面的因素,并且其聚类复杂度较低;然而,LCA算法在边之间的相似度计算上忽略了边的真实兴趣特征.
关注关系是微博网络形成的基础,也是微博信息传播的纽带.关注双方往往因为某个或某几个共同兴趣而建立关注关系.因此,关注关系还体现了关注关系双方的共同兴趣特征.针对现有微博用户社区发现算法的不足,本文以关注关系作为聚类节点,根据用户微博内容提取关注关系的兴趣特征,构建微博网络R-C模型,进而根据关注关系的兴趣特征计算关注关系之间的相似性,将问题转化为加权无向网络社区发现问题,解决了现有算法考虑不周全或效率较低等问题.本文的学术贡献主要有:
(1) 提出了微博网络R-C模型,并探讨了其进行用户社区发现的方法;
(2) 分析了基于R-C模型进行社区发现聚类的时间复杂度;
(3) 以新浪微博为实例,对照节点CNM算法和LCA算法,分析了基于R-C模型的用户社区发现算法所发现的用户社区在兴趣和网络结构上都有更优的内聚性.
本文第1节介绍现阶段微博用户社区发现的相关文献.第2节详细描述微博网络R-C模型及其社区发现方法,并分析使用该方法进行聚类的时间复杂度.第3节以新浪微博数据为实验对象,对照节点CNM和LCA算法,从兴趣内聚和网络内聚两方面验证本文方法能够发现更好的微博用户社区.第4节对本文的工作进行总结. 1 相关工作
近几年,随着在线网络社区的发展,社区发现算法得到了广泛的研究.针对用户社区的发现,人们已经提出了许多方法,这些方法主要可以分为3类:文本聚类法、网络结构法和综合法.
文本聚类法主要通过计算社区内节点的文本内容的相似性,根据相似性将文本内容相似的节点划分为社区.早在1999年,Kleinberg等人提出了基于内容的网页聚类方法,即著名的HITS算法[12].主题模型是文本聚类法最典型的算法.2003年,Blei等人提出了LDA模型[13],认为文档是多个主题的概率分布.2004年,Syeyvers等人认为主题是多个关键词的概率分布,用户也以某种概率分布对多个主题感兴趣,并提出了AT (author-topic)模型[14],用于发现用户、文档、主题和关键词之间的关系.2007年,McCallum等人基于发送-接受关系提出了ART(author-recipient-topic)模型[15],用于聚类具有相似兴趣的用户.在ART模型的基础上,2008年,Pathak等人提出CART(community-author-recipient-topic)模型[16].这些模型都忽略了用户之间显著的关注关系,从而可能导致社区发现结果的不合理.
基于网络结构的社区发现算法是目前较为流行且研究较多的方法,这类方法根据用户之间的相互关系将社区网络划分为社区内联系紧密、社区之间联系稀疏的多个子社区.1970年,Kernighan和Lin针对图分割问题提出了KL算法[17],该算法应用于复杂网络社区发现,就是社区发现图分割法的典型算法.图分割法通过迭代的方式将图分解为最优的两个子图,反复处理,直至得到足够数目的子图.2002年,Girvan和Newman提出了GN算法[18],它通过反复识别和删除网络中边介数最大的连接,实现复杂网络聚类.GN算法的复杂度较高,但它启发了人们对复杂网络社区发现的思路.2004年,Newman和Girvan提出的网络模块性评价函数——模块度Q[19].Q函数为社区内的实际连接数目与随机连接下社区内的期望连接数目之差,它描述了所发现社区的优劣.Q值越大,社区结构越好.在此基础上,Newman提出了基于局部搜索的快速复杂网络聚类算法,即快速Newman算法[20].快速Newman算法通过局部搜索,找到极大化的Q值,从而实现社区划分.同年,Newman等人从算法复杂度的角度出发,通过引入模块度增量矩阵和堆结构,将快速Newman算法演进为了CNM算法[21].2005年,Guimera和Amaral以优化目标函数Q为目标,提出基于模拟退火(simulated annealing,简称SA)算法的复杂网络聚类算
法——GA算法[22].SA的引入,使得GA算法具有找到全局最优解的能力,因而,GA算法具有很好的聚类精度.基于模块度优化的聚合方法是目前比较流行的社区发现算法,并被扩充到了加权网络社区发现[23]、有向网络社区发现[24]和重叠社区发现[25]等.虽然基于网络结构(用户关系)的社区发现算法能够对用户进行聚类,但由于其忽略了用户之间的共同兴趣特征,因此不能保证社区发现的兴趣内聚性.
针对上述两种社区发现在兴趣社区发现上的不足,2012年,Zhang等人[26]提出了将用户关系同用户内容进行结合,发现用户社区.他们采用NMF方法进行基于用户关系的社区发现,采用AT模型用于兴趣社区的发现,并在此基础上将两种社区发现结果进行融合,并在Tweets和Delicious上进行了验证.燕飞等人[27]首先对个人兴趣进行聚类,得到基于兴趣的行动者社区,然后使用社会网络拓扑结构信息对兴趣社区进行扩展,并在Flickr上进行了实验分析.这些方法虽然得到了较好的兴趣社区发现,并能将用户根据其兴趣划分到多个不同的社区,符合实际情况,但其算法逻辑较为复杂,而且复杂度较高.
真实世界中,社区结构大多数都是重叠且具有层次结构[28],微博用户往往具有多样化的兴趣特征,因此微博用户社区发现是重叠社区发现问题.CPM算法[29]是目前流行的重叠社区算法,其在自然和社会学等领域[30,31]都有所应用,且被推广到了加权网络的重叠社区发现[32].然而CPM算法认为社区是强连通的簇,其对社区苛刻的定义使得在稀疏网络(如新浪微博用户联系网络[33,34])中社区发现效果较差.此外,CPM算法需要指定k值,且复杂度较高,制约了CPM算法在大数据网络中的运用.2010年,Ahn等人提出了边社区概念及其算法——LCA算法[28],并在生物网络、社会网络和其他代表性网络(哲学家关系网、单词关系网和Amazon.com产品联系网)上对照CPM算法、Infomap算法[35]和快速Newman算法[20]验证了LCA算法能发现质量更好的重叠社区.
LCA算法以边作为聚类节点,对边进行聚类,并根据边所属的社区,将节点划分到多个不同的社区.在一个
具有N个节点的加权网络中,LCA算法假定对于任意节点i都有属性向量
,且:
其中,wij为边eij的权重;n(i)为与节点i有连接关系的所有邻居节点集合;ki为集合n(i)的元素数量;当i=j时,dij=1,其他情况为0.在LCA算法中,边eij的权重wij表征具有联系的两个节点i和j在某种性质上相关度.通常,权重值越高,相关度越大.根据不同的应用,wij的具体含义也略有不同,在具体应用中,wij可根据社区发现的不同目的和网络的不同特征采用不同的方法进行计算.如:为了发现电影演员之间的协作关系,可以以演员为节点、演员之间是否有合作电影为边、演员间合作的电影数为边的权重构建演员关系网络,此时,wij将表示演员间协作程度[28].又如:为了发现内容和结构双内聚的微博用户社区,可以以用户为节点、相互关注关系为边、用户发布内容之间的相似性为边的权重构建微博网络模型,此时,wij表示微博用户之间兴趣的相似程度.再如:为了挖掘Amazon上不同产品间的关系,可以构建以产品为节点、用户是否同时购买某两种产品为边、产品所包含的用户标签的相似度值为边的权重构建产品网络模型,此时,wij表示产品间用户标签的相似程度[28].
在此基础上,LCA算法采用Tanimoto系数计算公式计算具有公共节点k的两条边eik和ejk之间的相似度.由于边eik和ejk具有公共节点k,LCA算法认为:从网络结构上看,节点k的邻居节点对该两条边相似度的贡献不大,边eik和ejk的计算只考虑节点i和节点j的属性向量ai和aj,忽略节点k的属性向量ak.因此,边eik和ejk的相似度计算公式为
(1)
在计算边边之间相似度的基础上,LCA算法采用单边聚类方法[36]对边聚类,直至形成一个社区.最后,采用最优社区密度对层次进行切分,形成多个社区.在微博网络中,边(关注关系)是微博信息传输的纽带,也是其所相互关联的两个用户共同兴趣特征的体现,即,边的真实兴趣特征为其所关联的两个节点共同的兴趣特征.显然,公式(1)在边边的相似度计算上仅从网络结构出发,忽略了边的真实兴趣特征.
图 1给出了LCA算法未考虑边的真实兴趣特性而导致社区发现不准确的一个案例,该案例由3个节点n1,n2,n3和两条边e12和e13组成.节点n1,n2和n3的兴趣特征及其权重分别为(I1:0.5,I2:0.5),(I1:0.5)和(I2:1).采用Tanimoto系数计算公式分别求得边e12和e13的权重w12和w13为0.5和0.5.进而根据公式(1)可知,边e12和e13之间的相似度为0.5.因此若采用LCA算法,由于边e12和e13间较高的相似度,使得e12和e13将被划分到一个社区,即,节点n1,n2和n3都归属于同一个社区(图 1左下图所示).而事实上,n1和n2的共同兴趣为I1,n1和n3的共同兴趣为I2,而n2和n3之间无共同兴趣.因此,好的社区发现应能将其划分为n1,n2和n1,n3两个不同的社区结构(如图 1右下图所示).显然,LCA算法因未考虑e12和e13的真实兴趣特征,使得其社区发现不够合理.
 | Fig. 1 An example of unconsidered case in LCA 图 1 LCA算法不足案例示意图 |
本文对微博网络进行R-C模型构建,建立以关注关系为节点、以关注关系之间是否有共同用户为边、从用户的微博内容提取用户的兴趣特征、进而转化为关注关系的兴趣特征.在此基础上进行微博用户社区发现,解决了现有算法存在的考虑不全面、效率较低和LCA算法未考虑边的真实兴趣特征等问题. 2 微博网络R-C模型
本节将针对现有微博用户社区发现算法的不足构建微博网络R-C模型,为了更好地进行模型说明,本文有如下定义:
定义1(X社区). 如果一个社区内的对象为X,则称该社区为X社区.例如:在微博社区中,其社区是用户的集合,称为用户社区;在一个节点网络中,节点是社区的元素,称为节点社区;在LCA算法中,其以边为单位进行聚类,所形成的社区成为边社区. 2.1 微博网络R-C模型
一个微博社区的真实内容通常包含3部分内容:用户集合U、用户关系集合L和由U所产生的各类内容T(主要为微博及其评论内容).因此,一个微博通常可以表示为S=(U,L,T),其中,S表示微博社区.针对不同的研究和应用,该模型略有不同.图 2下半部分是一个微博网络真实内容及其关系示意图:U={U1,U2,U3}为微博用户集合;L={L1,L2}为用户联系的集合,也是微博内容T传播的纽带;T={T1,T2,T3}为微博内容集合,Ti为Ui的所有微博内容集合.
 | Fig. 2 Micro-Blog model,top is R-C model,while bottom is traditional model 图 2 微博模型示意图,上半部分为微博网络R-C模型,下半部分为现有微博网络模型 |
微博用户社区发现即是在微博网络S中发现L和T同时内聚的U社区.若以T作为研究对象,采用文本聚类的方法进行社区发现,该方法能够形成兴趣内聚的U社区;但由于忽略了关系L的重要作用,不能保证信息在所发现的社区内部能够畅通传播.若以L作为聚类条件进行U社区发现,无法保证所形成的社区的兴趣内聚.因此,合理的U社区发现应综合考虑L和T.现有的综合方法采用某种方法融合 由L和T所发现的两类U社区,形成网络结构和兴趣双内聚的U社区.先后两次社区发现及社区融合,导致了该类社区发现算法效率较低.而导致该算法需要进行两次社区发现,其最根本的原因是没有充分利用L的信息和价值.L作为用户之间的相互关系,已经体现了U的存在,因此在兴趣社区发现中,如果以L为社区发现对象、以T作为L的属性进行L社区发现,通过一次社区发现找出L社区,进而转化为U社区,将能简化社区发现复杂度.
由于双向关注关系(好友关系)更能体现真实社会情况[10],本文所讨论的关注关系是指双向关注关系.图 2上半部分显示了微博网络R-C模型示意图,它将原有模型中的关注关系L={L1,L2}映射成网络节点R={R1,R2}.
是关注关系R1和R2潜在的连接关系,它体现了R1和R2之间存在着共同用户.同时,关注关系L还潜在着所
关联的两个用户之间的共同兴趣特征.微博内容T是用户兴趣集的具体表现,因此,通过对关注关系所关联的两个用户的微博内容T进行兴趣特征提取,可进一步获得关注关系的所关联的用户的共同兴趣特征C,实现对R-C模型中关注关系兴趣特征的描述,从而将原有微博网络模型转化为R-C模型,即S={R,C}.
由于用户往往具有多个不同的兴趣,现有的方法通常根据用户内容计算出用户对各不同兴趣感兴趣的程度.因此,用户兴趣集是一个带权值的兴趣集合.关注关系Rx的兴趣特征Cx为其所关联的两个用户Ui和Uj兴趣特征的公共部分,因此本文认为,关注关系Rx的兴趣特征Cx为Ui和Uj兴趣的共同兴趣,其兴趣的权值为该兴趣在Ui和Uj兴趣中权重的较小值.为了计算关注关系的兴趣特征,本文做如下定义.
定义2(权值集合). 若给定一个集合A={a1,a2,…,am},其每个元素都含权值,即第i个元素ai的权值为wai,则称A为权值集合.A又表示为A={(a1,wa1),(a2,wa2),…,(am,wam)}.
定义3(权值集合交集). 假定权值集合A={(a1,wa1),(a2,wa2),…,(am,wam)}和B={(b1,wb1),(b2,wb2),…,(bn,wbn)},则集合A和B的交集为:AÇB={(c,wc)|c为A和B的共同元素,若c=ai=bj,有wc=min(wai,wbj)},其中,min(×)函数为取最小值.例如,若权值集合A={(a,1),(b,2),(c,3)},权值集合B={(b,1),(c,2),(d,3)},则AÇB={(b,1),(c,2)}.对于无权值的集合,可以假定其各元素的权重值为固定常数,如1,也可用该定义进行交集运算.在微博网络中,若用权值集合Ii表示用户Ui的兴趣集,则关联用户Ui和Uj的关注关系Rx的兴趣特征Cx可以使用定义3进行计算,即:
Cx=IiÇIj.
在微博网络R-C模型的基础上进行R社区发现,最后将R直接映射为其关联的用户,转化为U社区.它在综合考虑用户联系和用户内容的基础上提高了用户社区发现效率,并解决了LCA算法在社区发现上没有充分考虑边的兴趣特征的问题.以图 1为例,在R-C模型中,假定边e12和e13所对应的关注关系为R1和R2,则不难得出R1和R2所对应的兴趣特征分别为C1={(I1,0.5)}和C2={(I2,0.5)}.由于C1和C2完全不同,因此不论采用哪种聚类方法,R1和R2都分属于不同的兴趣社区,最终发现真实的兴趣社区.
虽然R-C模型和LCA算法都采用边进行聚类,但两者具有本质的不同,具体表现在:
(1) LCA算法只是将边作为一个聚类的对象,其边并不具有兴趣特征描述.而R-C模型在社区发现上将关注关系作为实体进行聚类.在R-C模型中,关注关系不仅仅只是聚类的对象,其还具有其所关联的两个用户的兴趣特征描述.因此,R-C模型更有利于挖掘内容和结构双内聚的社区结构;
(2) LCA算法仅仅只是从网络结构的角度出发进行社区发现,且认为两条具有公共节点的边,其公共节点的属性对该两条边的相似度的贡献不大,即,LCA算法忽略了公共节点的属性特征.因此,LCA算法忽略了边的真实特征.而R-C模型通过对边所关联的两个节点的特征取交集,保留了边的真实特征;
(3) 针对各类型的网络,LCA算法根据不同的社区发现目标构建加权或无权网络,进而从边的角度出发进行社区发现,各节点的属性特征在构建网络时就已转化为数值.而R-C模型首先将关注关系构建为网络节点,并从关注关系所关联的两个用户的兴趣获取该关注关系的特征;接着,根据关注关系的特征计算关注关系间的权重,最后进行社区发现.由于R-C模型在进行社区发现前才将属性特征转化为数值,因而能挖掘更为真实的社区结构. 2.2 基于R-C模型的用户社区发现方法
微博网络R-C模型是一个以关注关系为节点的网络模型,其R社区发现可借鉴现有成熟的节点社区发现算法.一般来说,基于微博网络R-C模型进行R社区发现有两种基本方法:
(1) 将R视为孤立的节点,基于兴趣特征C之间的相似度进行聚类,实现R社区发现.由于R自身为U社区的边结构,因此在一定程度上能够解决文本聚类方法在U社区发现中网络结构内聚不足的问题;但由于忽略了边边之间潜在的关联关系,因此其所发现的社区往往网络结构内聚不足;
(2) 根据R之间是否有共同节点建立R之间的连接关系,接着,根据R的兴趣集计算相互连接的R之间的相似度,并将该相似度设为R之间连接关系的权重值,建立加权无向R网络,将问题转化为加权无向网络的社区发现问题进行求解.该方法在兴趣聚类的同时,更好地考虑了网络结构问题,因此,本文使用该方法进行问题求解.
图 3为使用R-C模型进行微博网络U社区发现的基本框架,大致可以分为两个阶段:微博网络R-C模型构建和社区发现.本文使用LDA模型[13]从微博内容T提取用户兴趣集I={I1,I2,...},进而通过交集运算,计算关注关系的兴趣特征集C.关注关系的兴趣特征集C和关注关系集合R构成微博网络R-C模型.接着,本文通过计算有潜在联系的关注关系之间的兴趣相似度,将微博网络R-C模型转 换为加权无向网络,并使用较为成熟的加权无向网络社区发现算法进行R社区发现.由于CNM算法的聚类复杂度较低,本文使用加权CNM算法进行R社区发现.最后,将R直接映射为相应的U,形成U.
 | Fig. 3 Framework of user community detection using R-C model 图 3 基于R-C模型的用户社区发现方法框架 |
具体地,使用微博网络R-C模型进行社区发现的方法步骤如下:
(1) 微博内容T集合构建.将微博内容依据其所属的用户进行归类,形成T集合;
(2) 用户兴趣集I计算.对T集合中的微博内容进行分词,并采用相关模型(如LDA模型等)构建用户兴趣集合I;
(3) 关注关系特征集C计算.依据关注关系所对应的两个用户兴趣特征集,使用定义3所描述的方法,取交集形成关注关系兴趣特征集C;
(4) 关注关系相似度计算.对于无共同用户的关注关系,将不进行相似度计算.对于有公共用户的两个关注关系,采用Tanimoto系数计算公式计算其的相似度.计算公式如下:
;
(5) R社区发现.采用加权无向网络社区发现算法(如CNM算法等)对上述网络进行R社区发现;
(6) U社区形成.R-C模型中,任意R都包含两个具有相互关注关系的用户.对于某个R社区,其所包含的所有R所对应的用户集形成该R社区所对应的U社区.依次遍历所发现的所有R社区,形成U社区. 2.3 算法复杂度分析
定理1. 在一个有m个节点和n条边的图中,将边转化为节点,节点转化为边,可形成一个包含n个节点和
条边的图,其中,Li为第i个节点的度数,且有
证明:
(1) 将原始图中的边转化为节点后,原始图的n条边自然形成转化后图的n个节点;
(2) 以图中某个节点作为考察对象,若图中节点i的度数为Li,则其所关联的Li条边可形成
种不同的两两组合,在转换后的图中可形成条边.遍历原始图中所有的节点,易知转化后图的边数为
.又由于一条边关联两个节点,因此在上述遍历过程中,每条边遍历2次,故有
.展开,有:
考虑某节点的度数为1的特殊情况,此时,围绕该节点的边之间可形成
种边边关系,符合实
际情况.
假定在一个有m个用户和n条关注关系的微博社区中,将其转化为微博网络R-C模型后,可形成n个节点、条边的无向网络.若所使用的社区发现算法的复杂度为O(f(m,n)),则转化后,其复杂度为
案例1:若使用CNM算法进行R社区发现,CNM算法的时间复杂度为O(f(m,n))=O(ndlogm)[21],d为图的深
度.转换后的算法复杂度为
特殊地,在稀疏网络(如新浪微博[33,34])中,有m~n,d~logm,此时有O(f(m,n))=O(mlog2m),故而,其复杂度为
该时间复杂度基本等同于基于节点的时间复杂度.
案例2:若使用LCA算法中所用的单边聚类算法,单边聚类算法的时间复杂度为O(f(m,n))=O(m2)[37].转换后,算法复杂度为
相应地,在新浪微博等稀疏网络中,由于m~n,因此其时间复杂度为
3 实验及分析
3.1 实验数据
本文实验通过新浪微博开放平台提供的API抓取新浪微博数据进行.通过从种子用户出发,采用广度优先遍历的原则,沿关注关系方向逐层抓取新浪微博用户数据和微博内容数据.由于用户的兴趣可能随时间不断变化,因此本文实验只抓取每个用户最新的200条微博.由于好友数太少可能是僵尸粉,好友数太多可能是组织机构账户,因此本文随机从微博网络中选取好友数在50~100之间的4个不同用户作为种子用户,并分别抓取微博用户、用户双向关注关系及用户的最新200条微博,形成4组数据集.该4组数据集的数据信息见表 1.
|
Table 1 Four datasets for the experiments 表 1 4组实验数据集 |
图 4为所抓取的4组数据的微博网络结构图.图 4(a)从左往右分别为数据集S1,S2,S3和S4的无权重下的网络基本结构图.由图可知:该4组数据所形成的网络的节点都是相互连通的,不存在孤立的节点和节点群.图 4(b)从左往右分别为数据集S1,S2,S3和S4按度进行着色后的网络结构分布(节点度数越高,其颜色越深).该图说明了在新浪微博网络中,大量的节点度数较低,少数节点度数较高.图 5为该4组数据的微博网络节点的度分布情况,它进一步揭示该网络的度数分布特征.由图 5可知,所进行实验的4组数据所形成的微博网络节点的度基本都呈现幂律分布,因此,所进行实验的4组数据集所形成的微博网络都是无标度网络[38].
 | Fig. 4 Micro-Blog network structure of the four datasets 图 4 微博网络结构图 |
 | Fig. 5 Degree distribution of micro-blog networks of the four datasets 图 5 微博网络的度分布 |
由于LCA算法采用Tanimoto系数计算公式计算边边之间的相似度,为了更好地进行实验对照,本实验采用Tanimoto系数计算公式计算节点及关注关系的兴趣集间的兴趣相似度.由于CNM算法在加权无向网络社区发现中具有较好的效率,本文采用加权CNM算法对关注关系进行聚类.
CNM算法是目前较为流行的社区发现算法,并被广泛引用,且本文使用加权CNM算法[23]进行R社区发现,因此,直接用于U社区发现的加权CNM算法(后文称为节点CNM算法)将作为本文的对照实验之一,以更好地分析使用R-C模型进行社区发现的优势.LCA算法[28]作为最新的重叠社区发现算法,且其模型与R-C模型最为接近,因此也作为本文的对照算法.在本文实验中,节点CNM 算法和LCA算法的边权重都采用Tanimoto系数计算公式进行计算.
为了更直观地显示实验网络中用户之间以及关注关系之间的兴趣相似度情况,本文以图形的形式描绘了这两个相似度矩阵.图 6(a)从左往右分别为数据集S1,S2,S3和S4用户兴趣集的相似度矩阵,图 6(b)从左往右分别为数据集S1,S2,S3和S4关注关系的兴趣相似度矩阵.在相似度矩阵图中,点的颜色越深,则与其对应的一对用户或关注关系拥有更高的兴趣相似度.从4组数据的用户兴趣集相似度矩阵和关注关系兴趣集相似度矩阵可以看出:用户兴趣集相似度矩阵和关注关系兴趣相似度矩阵较为显著的特点在于沿对角线方向有一条较明显的黑线,即对角线周围的用户相似度和关注关系相似度较高.由于用户兴趣集矩阵按用户的广度优先遍历所形成的层次关系有序排列,关注关系兴趣相似度矩阵按节点有序排列,因此,较为明显的对角线特征体现了节点与其邻居及同一节点的多条边之间往往具有较高的相似度.在微博网络中,它说明了用户与其邻居用户及同一用户的多个关注关系之间存在较大的相似性,同时也佐证了人以群分的观点.
 | Fig. 6 Similarity matrixes of user interest sets and relationship interest sets 图 6 用户兴趣集相似度矩阵和关注关系兴趣集相似度矩阵 |
经社区发现,本文方法、节点CNM算法和LCA算法在4组数据集中的社区发现统计见表 2.
|
|
Table 2 Community size distribution of the three methods 表 2 3种算法的社区划分大小分布 |
本文算法和节点CNM算法所划分的社区数量相差不大,主要因为两者采用了相同的聚类算法.在4组实验数据集中,本文算法所发现的社区数量都要多于节点CNM算法,主要是因为本文算法采用边进行聚类.一方面,在微博网络中边数通常为点数的数倍(例如,数据集S1的边数为点数的4倍左右);另一方面,本文算法所发现的社区为重叠社区,而节点CNM算法挖掘非重叠社区.因此,本文算法的社区数量多于节点CNM算法.在4组数据集中,LCA算法所划分的社区数量都最多.此外,从4组实验结果可知:本文算法和LCA算法都产生了大量的零碎社区(2个节点、1条边的社区),且零碎社区的比重都比较大.以数据集S1为例,本文算法有630个零碎社区和102个非零碎社区,而LCA算法零碎社区和非零碎社区的数量分别为7 064和1 535,两者所发现的社区有85%左右都为零碎社区.这些零碎社区是在切割条件(最大社区密度或最大模块度)下没有被聚类产生的,也即,微博网络中存在着大量相似度较低的边边关系.而大量的相似度较低的边边关系也使得LCA算法在微博网络用户社区发现中的不足更加明显.
图 7为3种社区发现算法在4组数据集中所发现的最大的20个社区大小分布图.相较而言,本文算法和节点CNM算法由于都采用了CNM方法进行聚类,其能发现更多用户数较大的社区结构;而LCA算法采用单边聚类算法进行聚类,其次大社区和最大社区的大小比值在0.5左右,落差较大;而这与Ahn等人所述的“LCA算法中,较优社区发现情况下,次大社区和最大社区的大小比值趋近于0.5[28]”基本吻合.此外,由于本文算法和LCA算法都以边为聚类对象并发现重叠社区,因此所发现的社区相对较大.
 | Fig. 7 Distribution of the number of users on top rank 20 user communities 图 7 3种算法所发现的最大的20个社区用户数分布 |
兴趣内聚是指兴趣社区应具有高度兴趣聚集的特性.为了更好地描述兴趣内聚特性,本文作如下定义:
定义4(兴趣内聚指数E). 兴趣内聚指数用于描述社区内的用户之间的兴趣相似度与整个社区用户相似度之间的比值.若微博网络中任意两个用户Ui和Uj的兴趣相似度表示为m(i,j),则兴趣内聚指数E可以表示为
显然,E值越高,表明所发现的社区总体具有更好的兴趣内聚性,用户社区发现算法越优越.虽然E值描述了社区发现算法的总体兴趣内聚特征,但却无法描述单个社区的兴趣内聚性.因此,本文定义兴趣平均指数用于描述单个社区的兴趣内聚情况.
定义5(兴趣平均指数e). 兴趣平均指数用于描述社区内节点对社区总相似度的平均贡献值.若社区C有|C|个用户,则社区兴趣平均指数e可以表示为
易知:e越高,社区内节点对社区总兴趣相似度平均贡献越大,社区兴趣内聚性越好.
本文采用TF-IDF模型构建用户兴趣集向量,并采用余弦公式计算用户之间的兴趣相似度.经计算,实验所用的4组数据集的总相似度分别为365 911.1,470 122.9,174 433.3和49 293.2.4组数据所得社区的兴趣内聚指数见表 3.由表 3可知:在4组数据集实验中,本文算法所划分的社区,其社区内部的总相似度值都最高,分别为135 393.2,329 698.1,78 055.0和20 674.3,相应的兴趣内聚指数分别为0.370,0.701,0.447和0.419.在数据集S1和数据集S4中,LCA算法的兴趣内聚指数要高于节点CNM算法.究其原因,主要在于CNM算法是非重叠社区发现算法,它使得一个节点只能归属于一个社区,从而漏失许多相似兴趣.而在数据集S2和S3中,LCA算法虽然发现重叠社区,然而其兴趣内聚指数都要低于CNM算法,其主要由于LCA在进行边相似度计算时忽略了边的真实兴趣特征和公共节点.由实验可知,本文算法在兴趣内聚指数上要明显优于节点CNM算法和LCA算法.
|
|
Table 3 E values of the three methods 表 3 兴趣内聚指数E |
图 8显示了3种算法中在4组数据集中最大的20个社区的兴趣相似度贡献.由图可知:社区用户数越多的社区,其对社区总体相似度的贡献越大,从而说明了3种聚类算法在兴趣聚集上都是有效的.在4组数据集中,本文算法主要社区的兴趣贡献度都优于节点CNM算法和LCA算法.在数据集S1中,本文算法挖掘的最大社区兴趣贡献度略小于LCA算法,主要是因为LCA算法最大的社区用户数要明显多于本文算法的最大社区.
 | Fig. 8 Interest contribution of top rank 20 user communities图 8 3种算法最大的20个社区内部相似值贡献 |
图 9为3种算法在4组数据集中最大20个社区的社区兴趣平均指数,该图直观描述了在最大20个社区中,3种算法的兴趣平均指数对照情况.显然,本文方法在单个社区的兴趣平均指数上基本都优于节点CNM和LCA算法.因此,本文方法所发现的用户社区具有更好的兴趣内聚性.
 | Fig. 9 Average interest values e of top rank 20 user communities图 9 3种算法最大20个社区兴趣平均指数e值 |
网络结构内聚是指兴趣社区除了应具有高度兴趣凝聚外,其网络结构也应高度内聚.社区密度是LCA算法进行社区层次切分的标准,但其并不是较好的网络结构评价指标,且LCA算法本身都不以社区密度作为社区结构评价的指标,因此,本文也不将社区密度作为网络结构的评价指标.
模块度是目前评价网络节点凝聚度的常用指标.假定一个无向无权网络拥有m条边,节点i的度为ki,经社区发现后,总共有v个社区,节点i其所归属的社区数目为Oi,则重叠社区模块度[25]定义为
其中,A为网络的邻接矩阵,描述节点i和j之间的连接关系,若节点i和j有连接,则Aij为1,否则为0.在非重叠社区划分算法(例如节点CNM算法)中,每个节点只能归属于1个社区,此时,对任何节点i,有Oi=1.显然,当所划分的社区内部边数越多时,Q值越大,社区结构越明显.
为了讨论单纯的网络结构凝聚性,本文在不考虑网络权重的情况下,对所发现的用户社区重新计算模块度,它避免了本文方法和节点CNM算法采用最优加权模块度进行层次切分所带来的评价不公平问题.同时,为了避免大量的零碎社区导致各算法模块度不均衡,本文在模块度计算上滤除了零碎社区.
表 4为本文方法、节点CNM和LCA算法在4组数据集上所发现社区的模块度值.
|
|
Table 4 Q values in the three methods 表 4 3种算法的Q值 |
在4组数据集中,CNM算法都具有最大的模块度值,其值分别为0.316,0.195,0.323和0.368.一个好的社区发现,其模块度应在0.3~0.7之间[19].在4组数据集中,除了数据集S2外,其他3组数据集的节点CNM的模块度值较好,基本满足一个好的社区发现的模块度标准.本文方法和LCA算法的模块度较低,主要是因为重叠社区使得节点通常分布于多个不同社区,进而降低了模块度值.从总模块度上看,本文方法在4组数据集中所发现社区的模块度值分别为0.167,0.089,0.111和0.187,而LCA算法在4组数据集中所发现社区的模块度值分别为0.110,0.030,0.048和0.097.因此,本文算法所发现的社区在总体网络结构上都在不同程度上优于LCA算法.此外,图 10为3种算法最大20个社区的模块度贡献分布图,在4组数据集中,本文方法的模块度贡献值几乎都高于LCA算法.因此总体上说,本文方法更适合于微博网络的用户社区发现.
 | Fig. 10 Distribution of modularity Q on top rank 20 communities 图 10 3种算法用户数最多的20个社区内部模块度值分布 |
为了进一步讨论所划分用户社区的质量,本文抽取本文算法和LCA算法所划分的最大用户社区进行的讨论.由于节点CNM算法社区较小,不进行对比.表 5从图密度、网络直径、平均路径长度和平均聚类系数对两种算法最大社区进行了对比.由表 5可知:在4组数据集中,本文方法和LCA算法所发现的最大社区都有相同的网络直径,分别为9,7,6和5,在网络直径上两者持平.在数据集S1和S4中,本文方法最大社区的平均聚类系数分别为0.128和0.497,略低于LCA算法的最大社区的0.239和0.617;但在该数据集S1和S4中,本文方法最大社区的图密度分别为0.003 47和0.003 4,都要优于LCA算法的最大社区的0.003 42和0.022;且本文方法的平均路径长度也要略优于LCA算法.在数据集S2和S3中,虽然本文方法的平均路径长度和图密度都略差于LCA算法,但本文方法所发现的最大社区有着较优的平均聚类系数.因此,本文方法所发现的单个社区在网络结构上也不劣于LCA算法所发现的社区.
|
|
Table 5 Comparison of network statistics over the largest user communities 表 5 最大社区网络参数统计对比 |
本文在分析现有社区发现算法(尤其是LCA算法)在微博用户社区发现上存在不足的基础上,提出了微博网络R-C模型,探讨了使用R-C模型进行微博用户社区发现的方法,分析了其社区聚类的时间复杂度,并以CNM算法和单边聚类算法为例,说明了该方法在微博网络等稀疏网络中,其聚类复杂度较低,近似等同于原有模型的复杂度.在4组新浪微博真实数据集下,通过对比节点CNM算法和LCA算法,本文从兴趣内聚和网络结构内聚两方面分析了本文方法所发现微博用户社区具有较优的兴趣和网络结构内聚性.
本文将R-C模型应用于新浪微博进行社区发现,并取得了较优的社区结构.R-C模型和本文方法将同样适用于其他具有双向关注关系并能提取用户内容的在线社区,如Twitter、Google+、人人网、QQ微博等.在后续的工作中,我们将会在更多的数据集上使用R-C模型并验证其能发现更优的用户社区.
| [1] | Lim KH, Datta A. Following the follower: Detecting communities with common interests on Twitter. In: Proc. of the 23rd ACM Conf. on Hypertext and Social Media. New York: ACM Press, 2012. 317-318 . |
| [2] | Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007,58(7):1019-1031 . |
| [3] | Dourisboure Y, Geraci F, Pellegrini M. Extraction and classification of dense communities in the Web. In: Proc. of the 16th Int’l Conf. on World Wide Web. New York: ACM Press, 2007. 461-470 . |
| [4] | Tang L, Wang X, Liu HF. Uncoverning groups via heterogeneous interaction analysis. In: Proc. of the Ninth IEEE Int’l Conf. on Data Mining. Miami: IEEE, 2009. 503-512 . |
| [5] | Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Trans. on Knowledge Discovery from Data (TKDD), 2009,3(4):16 . |
| [6] | Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing. In: Proc. of the 8th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 2002. 61-70 . |
| [7] | Iyer G, Soberman D, Villas-Boas JM. The targeting of advertising. Marketing Science, 2005,24(3):461-476 . |
| [8] | Kaplan AM, Haenlein M. Two hearts in three-quarter time: How to waltz the social media/viral marketing dance. Business Horizons, 2011,54(3):253-263 . |
| [9] | Larsson AO, Moe H. Studying political microblogging: Twitter users in the 2010 Swedish election campaign. New Media & Society, 2012,14(5):729-747 . |
| [10] | Lim KH, Datta A. Finding twitter communities with common interests using following links of celebrities. In: Proc. of the 3rd Int’l Workshop on Modeling Social Media. New York: ACM Press, 2012.25-32 . |
| [11] | Jansen BJ, Zhang MM, Sobel K, Chowdury A. Micro-Blogging as online word of mouth branding. In: Proc. of the 27th Int’l Conf. on Extended Abstracts on Human Factors in Computing Systems. New York: ACM Press, 2009. 3859-3864 . |
| [12] | Kleinberg JM. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 1999,46(5):604-632 . |
| [13] | Blei DM, Ng AY, Jordan MI. Latent dirichlet allocation. Journal of Machine Learning Research, 2003,3:993-1022. |
| [14] | Steyvers M, Smyth P, Rosen-Zvi M, Griffiths T. Probabilistic author-topic models for information discovery. In: Proc. of the 10th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 2004. 306-315 . |
| [15] | McCallum A, Wang XR, Corrada-Emmanuelm A. Topic and role discovery in social networks with experiments on Enron and academic email. The Journal of Artificial Intelligence Research, 2007,30:249-272. |
| [16] | Pathak N, Delong C, Banerjee A, Erickson K. Social topic models for community extraction. In: Proc. of the 2nd SNA-KDD Workshop 2008. Las Vegas: ACM Press, 2008. |
| [17] | Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970,49(1): 291-307 . |
| [18] | Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. of the National Academy of Sciences, 2002, 99(12):7821-7826 . |
| [19] | Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004,69(2):026113 . |
| [20] | Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E, 2004,69(6):066133 . |
| [21] | Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E, 2004,70(6):066111 . |
| [22] | Guimera R, Amaral LAN. Functional cartography of complex metabolic networks. Nature, 2005,433(7028):895-900 . |
| [23] | Newman MEJ. Analysis of weighted networks. Physical Review E, 2004,70(5):056131 . |
| [24] | Leicht EA, Newman MEJ. Community structure in directed networks. Physical Review Letters, 2008,100(11):118703 . |
| [25] | Shen HW, Cheng XQ, Cai K, Hu MB. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications, 2009,388(8):1706-1712 . |
| [26] | Zhang ZF, Li QD, Zeng D, Gao H. User community discovery from multi-relational networks. Decision Support Systems, 2013,54(2): 870-879 . |
| [27] | Yan F, Zhang M, Tan YW, Tang J, Deng ZH. Community discovery based on actors’ interests and social network structure. Journal of Computer Research and Development, 2010,47:357-362 (in Chinese with English abstract). |
| [28] | Ahn YY, Bagrow JP, Lehmann S. Link communities reveal multiscale complexity in networks. Nature, 2010,466(7307):761-764 . |
| [29] | Derényi I, Palla G, Vicsek T. Clique percolation in random networks. Physical Review Letters, 2005,94(16):160202 . |
| [30] | Palla G, Barabási AL, Vicsek T. Quantifying social group evolution. Nature, 2007,446(7136):664-667 . |
| [31] | Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005,435(7043):814-818 . |
| [32] | Farkas I, Ábel D, Palla G, Vicsek T. Weighted network modules. New Journal of Physics, 2007,9(6):180 . |
| [33] | Xiong X, Niu X, Zhou G, Xu K, Huang YZ. Microgroup mining on tsina via network structure and user attribute. In: Proc. of the 7th Int’l Conf. on Advanced Data Mining and Applications. Berlin: Springer-Verlag, 2011. 138-151 . |
| [34] | Xiong X, Zhou G, Niu X, Huang YZ, Xu K. Remodeling the network for microgroup detection on microblog. Knowledge and Information Systems, 2013:1-23 . |
| [35] | Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Proc. of the National Academy of Sciences, 2008,105(4):1118-1123 . |
| [36] | Gower JC, Ross GJS. Minimum spanning trees and single linkage cluster analysis. Applied Statistics, 1969:54-64. |
| [37] | Sibson R. SLINK: An optimally efficient algorithm for the single-link cluster method. The Computer Journal, 1973,16(1):30-34 . |
| [38] | Barabási AL, Albert R. Emergence of scaling in random networks. Science, 1999,286(5439):509-512 . |
| [27] | 燕飞,张铭,谭裕韦,唐建,邓志鸿.综合社会行动者兴趣和网络拓扑的社区发现方法.计算机研究与发展,2010,47:357-362. |