链接相似性的微博重叠社区发现算法

链接相似性的微博重叠社区发现算法 于洪涛，崔瑞飞，黄瑞阳 (国家数字交换系统工程技术研究中心，郑州 450002) E-mail:cuiruifei0815@163.com 关键词: 虚拟兴趣网;关注网络;链接相似性;层次聚类;重叠社 区 中图法分类号:TP393 文献标识码:A A link-based similarity micro-blog overlapping community detecting algorithm YU Hong-tao, CUI Rui-fei, HUANG Rui-yang (National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China) Abstract: It is impossible to detect overlapping community with traditional node clustering algorithms and they need priori-knowledge. To solve the problem, this paper proposed a link-based similarity micro-blog overlapping community detecting algorithm. Firstly, the paper mapped the interest similarity matrix to a virtual network and sought its link similarity and then attained the total link similarity by combing real attention relationship among users. To utilize link similarity to community detection, we generalize the Ward hierarchical clustering algorithm so that it is applicable to any object that has similarity measurement. And as an application we particularly employ this algorithm to detect community. Experiments on real data sets show that the algorithm can detect micro-blog overlapping community without priori-knowledge, with the accuracy of 83.4%. Keywords: virtual interest network; attention network; link similarity; hierarchical clustering; overlapping community 0引言 近年来，复杂网络逐渐成为了人们研究的热点[1]。复杂 网络具有诸多特性，其中社区结构特性在复杂网络的研究中 扮演着十分重要的角色[2]，对于理解网络功能和预测网络行 为具有重要意义。真实世界中，社区结构大部分是重叠的[3]， 即一个节点会同时属于多个社区，如图1所示。因此，本文 只关注重叠社区的研究，事实上，近年来有关社区发现的大 部分研究也都是基于重叠社区的，这些研究大致可分为两 类:基于节点相似性的算法和基于链接(边)相似性的算法。 图1 重叠社区示例图 Fig.1 Diagram of overlapping community 基于节点相似性的算法利用节点的结构信息直接对网 络节点进行聚类。OSBM[4]和MOSES[5]等算法采用模糊匹配 的思想，通过计算节点对社区的隶属度实现重叠社区的划 分，但这些算法需要提前设定社区的数目。COPRA[6]和 ——————————————— 基金项目:国家“863”资助项目(2011AA010603, 2011AA010605) 作者简介: 于洪涛，男，1970年生，博士，教授，研究方向为通信与信息系统、社交网络;崔瑞飞，男，1989年生，硕士研究生，研究方向为通信与信息系统、社交网络;黄瑞阳，男，1986年生，博士，讲师，研究方向为通信与信息系统。 SLPA[7]是两种基于标签传播的算法，这些算法复杂度较低，但是其出的社区的尺寸往往偏小。 2010年，Ahn、Bagrow和Lehmann[8]提出了一种基于边聚类的社区发现，该方法的基本思路是首先通过边聚类发现边社区，然后再将边社区映射为节点社区。这一思路的提出解决了节点聚类算法需要先验知识的缺点，为重叠社区发现的研究提供了一种全新的思路。因此，基于边聚类的算法也成为了近年来社区发现领域的主流，如SHI [9] 和YE [10] 。 不管是基于节点相似性的算法还是基于边相似性的算 法都是从社区内部联系紧密这一拓扑结构特性来解决问题的。但在微博网络中，一些新的特性使得上述方法并不是很理想。这些特性主要表现为用户之间的连接大多数是单向的，连接关系较弱。鉴于以上特性，众多学者也开始探索微博社区发现技术。闫光辉[11]综合考虑用户兴趣相似性和网络拓扑结构，得到了用户之间的总相似度，然后使用标签传播算法发现微博社区;王卫平[12]也从用户兴趣相似性和网络拓扑结构两个方面着手，改进了k-means算法，提出了一种微博社区发现方法。这两种方法比单纯基于某一方面的方法更加准确，但是不能发现重叠社区。蔡波斯[13] 采用主成分分析法构造用户行为相似度矩阵，然后使用改进的派系过滤方法发现微博社区，该方法虽然可以发现重叠社区，但是仍需要一些先验知识。 通过以上分析可知，要想准确发现微博社区，必须综合考虑用户兴趣和网络拓扑结构两个方面;而从边聚类的角度出发，能更方便地发现重叠社区。因此，本文融合用户兴趣和网络结构信息，提出了一种基于边聚类的微博重叠社区发现算法，该算法无需先验知识。 本文的主要贡献如下: 1)将用户兴趣相似度矩阵映射为虚拟兴趣网并求该网络的链接相似度，然后求解用户真实关注网络的链接相似度，综合以上两点得到总的链接相似度; 2)对传统的Ward层次聚类进行了推广，依据微博网络的特点优化了目标，然后以总的链接相似度为基础，对网络中的边进行层次聚类，选取使得目标函数最优的划分作为输出结果。 1链接相似性度量 链接相似性是指网络中边与边之间的相似程度，相似性越大则同属一个边社区的概率越大[8]。 1.1虚拟兴趣网及其链接相似度 微博网络中提供了大量的用户信息，利用这些信息能够挖掘出用户的兴趣[14],[15]，表示为B={b1,b2,?,bn}，其中bi表示用户对第i个话题的兴趣度。通过计算任意两个用户之间的兴趣相似度就可以得到兴趣相似度矩阵E=(eij)，本文使用余弦相似度计算eij，如式(1)所示。 eBi?Bjij? B (1) iBj 矩阵E可以映射为一个加权网络，如图2(a)所示，该网络中任意两个节点之间有一条权重为eij的虚拟边。 (a) (b) 图2 虚拟兴趣网络示意图 Fig.2 Diagram of virtual interest network 删除图2(a)中权重小于阈值w*的边，得到(b)所示的加权网络，本文将该网络称为虚拟兴趣网，其边权重wij满足关系式wij ?eij,eij?w*。 假设图2(a)中有n个节点，那么该图共有n(n-1)/2条边，把虚拟兴趣网的边数与n(n-1)/2的比值称为虚拟兴趣网边百分比，它反映了虚拟兴趣网中边的稠密程度。 虚拟兴趣网中，边的相似性可由(2)计算得到[8]。 ??A?1 w?ijii'?ij?? ki'?wiji?n(i)?ai?(Ai1,Ai2,,AiN) (2) ???S(l)? aiaj? ik,ljk|ai|2?|aj|2 ?aiaj其中，n(i)={ j | wij > 0}为节点i的邻居节点集合，ki=| n(i)|为集合n(i)中的元素个数，N为网络中的节点数;当i=j时，δij=1，否则δij=0。需要指出的是，只有两条边相邻(有公共端点k)时，它们才具有相似度;换句话说，计算某条边与其它边的相似度时，只需关注局部(邻居)范围即可。 1.2关注网络及其链接相似度 1 4 图3 微博关注网络示意图 Fig.3 Diagram of micro-blog attention network 微博中，用户之间通过“关注”联系在一起构成关系网络，本文把该网络称之为关注网络。图3为一个微博关注网络示意图。下面来分析如何度量关注网络中边的相似性。 本文采用Jaccard指标度量关注网络的链接相似性，如式(3)所示。其中，nout(i)为节点i及其指向的邻居节点的集 合，nin(i)为节点i以及指向i的邻居节点的集合。 ??S(l|nout(i)?ik,lnout(j)|jk )?|nout(i)n? out(j)| ? |n(3) ?S(lin(i)nin? ki,l(j)|kj )?|nin(i)nin(j)|只有当两条边共同指向某节点，或者共同从某节点出发 指向其它节点时，这两条边才具有相似性。这里需要特别指出 ， 在 有 向 网 络 中 ， 关 系 式 S(l1 ik,ljk)?2 [S(lik,ljk)?S(lki,lkj)]成立，若某有 向边不存在，则对应的相似度值为0。以下为几个计算图3所示关注网络边相似性的例子:S(l23,l53)=1/2(1/2+0)=1/4、S(l25,l35)=1/2(0+2/5)=1/5、S( l54,l34)=1/2(1/2+1/2)=1/2、S(l12,l32)=0。 1.3总链接相似度 本小节将对虚拟兴趣网和关注网络的链接相似度进行合并得到总的链接相似度。 1 4 4 (c) 1 4 (d) 图4 虚拟兴趣网和关注网合并过程 Fig.4 Combination process of virtual interest network and attention network 图4形象地表示出了虚拟兴趣网和关注网合并的过程，(a)和(b)分别为虚拟兴趣网和关注网，(c)为两者合并的结果，(c)中包含了(a)和(b)中的所有边，(d)为(c)的等价网络。这里等价的含义是网络(c)和(d)满足条件Sc(lij,lmn)= Sd(lij,lmn)，即任意一对边的相似度在网络(c)和(d)中是相等的。 为了表示的方便，把虚拟兴趣网的链接相似度记为S1(lik,ljk)，关注网络的链接相似度记为S2(lik,ljk)，网络(d)的链接相似度记为S(lik,ljk)，那么S(lik,ljk)的计算方法如式(4)所示。 S(lik,ljk)? 1 2 [S1(lik,ljk)?S2(lik,ljk)] (4) 至此，得到了网络总的链接相似度，该相似度为局部范围内的度量，具有较小的计算复杂度。 2基于层次聚类的社区发现 本节首先在传统Ward层次聚类[16]的基础上，将欧式距离推广为广义距离，然后依据微博特点优化了目标函数，最后利用推广的Ward层次聚类算法进行社区划分。 2.1Ward层次聚类及推广 Ward层次聚类每次合并欧式距离最小的两个社区，并更新合并得到的新社区的社区中心，重复以上过程直到所有数据合并为一个大社区。 设ci、cj分别为社区Ci和Cj的中心，那么合并形成的新社区记为Ci j ，新社区的中心为: cici?Njcji j ? NNi?N (5) j 其中，Ni表示Ci中的数据个数。每个社区中的所有数据到其中心的距离之和反映了该社区的紧密程度，表示为: W(Ci,ci)? (xk ,ci ) (6) x?dk?Ci c 令W(C,c)? ?W(Ci ,ci )，那么W(C, c)的取值 k?1 越小，说明C={C1,C2,?,Cc}对数据的划分效果越好。在Ward层次聚类的过程中，总是选取使得W(C, c)增加最少的两个社区合并。设合并Ci和Cj得到的新划分为C'，则称 W(C',c')?W(C,c)?W(Cij,cij)?W(Ci,ci)?W(Cj,cj) 为Ward距离，它反映了社区Ci和Cj的距离，记作dw(Ci,Cj)。它的一个等价表示式[16]为: dw(Ci,Cj)? NiNjN(ci,cj) (7) i?Ndj 通过以上分析可知，Ward层次聚类就是每次合并dw值最小的两个社区，并按照式(5)更新合并之后新社区的中心，直到所有的数据点合并为一个大社区的过程。 设y1,y2,?,yn为n个抽象对象，dij为任意两个对象之间的距离，则任意对象yj到社区Ci的距离可表示为: d(y1 j,ci)? Nd jk (8) i y?k?Ci 那么，任意两个社区中心之间的距离可表示为: d(c1i,cj)? NiNj y? dkl (9) k?Ci,yl?Cj 综上可知，只要得到任意两个对象之间的距离，就可以对这些对象进行Ward层次聚类，并且这些对象无需限定到欧式空间。 2.2目标函数 在非重叠社区发现算法中，通常采用模块度[17]衡量社区划分效果的好坏，它表示社区内部连接边的占比与随机网络相比的差值。通常，社区内部连接越多、社区间连接越少，模块度越大，社区划分效果越好。但是在重叠社区中，这一指标不再适用[18]，因为多个社区可能共享一个节点(图1)，社区之间的连接边会显著增多。为此，文献[8]提出了划分紧密度(Partition Density)D指标，较好地衡量了重叠社区的划分效果。 对于一含M条边的无权无向网络，{C1,C2,?,Cc}为该网络的一个社区划 分,那么第i个社区的社区紧密度Di表示为: Di?(ni?1) i? mnn(n (10) i(i?2)2?i?1) 其中，mi、ni分别表示第i个社区的边数和节点数，ni=2时，Di的值为0。划分紧密度D为所有社区划分紧密度的加权平均值，第i个社区的权值为mi/M，因此，D可表示为: D? 2?mmi?(ni?1)M i (n i?2)(ni?1)(11) i 为了使划分紧密度指标适用于加权网络和有向网络，本文对D做了改进，得到了加权网络划分紧密度指标(Weighted Density)WD和有向网络划分紧密度指标(Directed Density)DD，如(12)和(13)所示。 WD? 2 wi?(ni?1)W ?wi i (nn (12) i?2)(i?1)DD?2 (p?2qiP?2Q?(p)?(ni?1)i?2qi)i (13) i(ni?2)(ni?1) 式(12)中，W为加权网络中所有边的权重之和，wi为第i个社区内所有边的权重之和;式(13)中，P和Q分别为有向网络中单向边数和双向边数，pi和qi分别为第i个社区内的单向边数和双向边数。由于本文融合了虚拟兴趣网和关注网络，所以本文的目标函数为WD和DD的加和，如(14)所示。 LD?WD?DD (14) 需要指出的是，D和LD均有可能为负值，但是这并不影响对社区划分效果的评估，只要某划分的D或LD高于另一划分，那么就可以说明前者优于后者。 2.3基于广义Ward层次聚类的社区发现算法 根据2.1节的分析，只需提供网络中边之间的距离信息就可对边进行层次聚类。边之间的距离可取为相似度的单调减函数，这里令 Dij?1? (15) Dij构成一个距离矩阵D，由式(15)可求得D的初始值， 算法求解过程就是不断更新D的过程。当合并Ci和Cj时，将Cj并入Ci，对?k?i, k?j按照式(16)更新矩阵D的i行: DNi?Nk)Dik?(Nj?Nk)Djk?NkDij ij? (N (16) i?Nj?Nk 然后删除D的j行和j列。聚类过程得到了一系列划分序列，记为C(n), C(n-1), ?,C(1)，其中C(k)表示该划分将所有边分成了k个社区。最后输出使得目标函数取值最大的划分Cm作为社区发现的结果。本文把上述社区划分的过程称为基于广义Ward层次聚类的社区发现算法(Ward-based Community Detection algorithm, WCD)，用伪代码表示如下: 输 入:边相似度矩阵S ; 输 出:最优社区划分Cm。 初始化:C={C1,C2,?,Cn}，其中Ci={li}，li表示第i条边; 算 法: 1) D?12) WHILE |C|>1 3) 求D下三角部分的最小值，得Dij=min(D); 4) FOR k=1:|C| 5) IF k? i&& k? j 6) IF k<i 7) DNi?Nk)Dik?(Nj?Nk)Djk?NkDij; ik? (Ni?Nj?Nk 8) ELSE 9) DNi?Nk)Dik?(Nj?Nk)Djk?NkDij; ki? (Ni?Nj?Nk 10) END IF; 11) END IF; 12) EDN FOR; 13) C?C\?Ci,C j ??C i Cj?; 14) C(|C|)?C; 15) 删除D的j行和j列; 16) END WHILE; 17) C(tree) ?{C(n), C(n-1),?,C(1)}; 18) Cm? arg MAXC?C(tree) LD(C); 19) RETURN Cm; 不难看出，WCD算法涉及矩阵循环，因此其复杂度为O(m2)。在实际计算过程中，只需计算相邻边的相似度，层次聚类时只需对每条边附近进行局部搜索即可，因此算法实际复杂度要远远低于O(m2)。 3实验 3.1实验准备 3.1.1实验数据 微博用户可以通过添加标签的方式标示自己的兴趣爱好和所关注的热门话题，还可以创建或加入群组。新浪微博 和腾讯微博是目前中国运营最为成功、用户量最为庞大的两个运营商，本文分别从新浪微博和腾讯微博随机选取了 20 个已知标签的群组，然后 在每个群组里随机挑选50个(不足50的选择全部)符合群组标签的成员。对数据做预处理，剔除其中的僵尸用户[19](这些用户极不活跃，没有研究价值)，最后新浪微博数据集剩余了873个有效用户数据，腾讯微博数据集剩余了796个有效用户数据。 3.1.2评价指标 设Co和Ce为两个划分，那么可以用归一化互信息(Normalized mutual information, NMI)[20]来度量两个划分之间的相似程度，其定义如式(17)所示。 NMI(C)? o,Ce (17) 其中, H(C) 表示划分C的香农信息熵。NMI(Co, Ce)是 一个0~1的值，其值越大，说明两个划分越相似。 3.1.3实验环境 本实验在一台PC机上进行，其CPU为Intel Core i5 2.8GHz，内存4GB，操作系统为windows7。 3.2实验结果与分析 3.2.1阈值w*的选择 图5为随着阈值w*的增加，社区数目和虚拟兴趣网边百分比的变化趋势。从图中可以看出: % /比分目 百数边区络社网趣兴拟虚阈值w* 图5阈值w*的影响效果图 Fig.5 Impact effect of threshold w* 1) 起初社区数目较少且增加较快，而后增加速度减慢，最后收敛于某最大值，下面来分析其原因。起初社区数目较少，是因为w*较小时网络中几乎每两个节点之间都有连接边，致使算法对社区的区分度下降的缘故; 社区数目不断增加，是因为虚拟兴趣网中权值小的边逐渐被删除，从而使得社区结构更加明显;最后收敛于某最大值，是因为w*较大时虚拟兴趣网中的边已非常稀疏，其对社区划分的贡献微乎其微，此时，社区划分算法基本依赖于关注网络，而关注网络中的边是稳定的。 2)虚拟兴趣网边百分比呈现出长尾效应:w*在取值较小的范围时，下降得非常快;随着w*的增加逐渐趋于稳定。这符合网络的一般特点。 表1 w*最优值的选择 Table1 Choice of optimization of w* 社区数目 5 10 15 20 w*最优值 0.35 0.38 0.38 0.37 边百分比 10.7% 8.9% 8.7% 9.3% 图5中示出的社区数目随w*的变化曲线是对全部20个群组进行实验的结果，因此本文假设社区数目为20时，w*的取值为最优值，此时w*约为0.37。为了验证这种选取w*方法的合理性，本文又对其中的5、10、15个已知群组进行了实验，分别选取其对应的w*的最优值，结果如表1所示。可以发现，不管已知群组为多少，w*的最优取值比较稳定，基本位于0.35~0.38之间，所以这种选取w*的方法是合理的， 本文将其取为0.37。 3.2.2算法对比实验 为了测试WCD算法的性能，本文与常用的社区发现算法进行了对比实验，参与对比的算法包括: 1) 综合1:文献[11]综合用户兴趣和网络拓扑结构，利用标签传播算 法发现微博社区，本文将该算法称为综合1; 2) 综合2:文献[12]也从用户兴趣和网络拓扑结构出发，改进了k-means算法来发现微博社区，本文将该算法称为综合2; 3)SI:仅保留综合1方法中的用户兴趣因素，然后利用标签传播算法发现微博社区。由于该算法仅仅依赖用户兴趣这一单一因素，因此本文将此算法称为Single-Interest(SI)。 4)GaoCD[10]:本算法依据网络拓扑结构，使用遗传算法对网络中的边进行聚类发现边社区，然后再将边社区映射为点社区。 表2 各算法的结果对比(新浪) Table2 Result contrast of every algorithm (Sina) NMI LD 社区数目 运行时间(s) 综合1 0.751 0.322 27 5.35 综合2 0.712 0.296 23 2.83 SI 0.521 0.273 13 0.05 GaoCD 0.645 0.342 28 32.72 WCD 0.834 0.523 20 38.34 表3 各算法的结果对比(腾讯) Table3 Result contrast of every algorithm (Tencent) NMI LD 社区数目 运行时间(s) 综合1 0.743 0.343 28 4.96 综合2 0.690 0.312 25 2.72 SI 0.531 0.285 16 0.05 GaoCD 0.624 0.352 28 29.94 WCD 0.812 0.496 21 36.35 表2、表3分别为在新浪微博数据集和腾讯微博数据集上各算法社区发现的对比结果。数据显示，各算法的性能在两个数据集上基本一致。从NMI和LD上来看，SI和GaoCD较低，这是因为这两种算法只考虑了单方面的影响因素使得 结果不准确的缘故;综合1、综合2和WCD均考虑了用户兴趣和网络拓扑两个方面的因素，所以NMI值和LD值都较高;WCD明显优于综合1和综合2，是因为WCD能够发现重叠社区，真实网络中社区更多地是以重叠形式存在的。从社区数目上来看， GaoCD发现的社区数目相对偏多，这是由于GaoCD只考虑了网络拓扑结构信息，而微博网络中的边大多为单向，致使网络结构稀疏造成的;综合1发现的社区数目也相对偏多，这是因为综合1采用的基础算法为标签传播算法，该算法倾向于发现小社区。从运行时间上来看，SI的复杂度低是因为标签传播算法的复杂度低;综合1明显慢于SI是因为其中涉及了网络最短路径的计算，致使复杂度增加;GaoCD和WCD的运行速度相对较慢，是因为两者对边进行聚类，而网络中的边数一般会大于节点数。 综上可知，由于WCD算法能有效发现重叠社区，所以其检测出的社区结构与实际社区吻合度更高，但复杂度也相对较高。因此，WCD算法适合于对社区划分精度要求较高的场合。此外，WCD算法还具有不需要先验 知识的优点。 4 结束语 本文第一部分综合微博用户兴趣和网络拓扑结构，提出了一种链接相 似性度量方法。首先将用户兴趣相似度矩阵映射为虚拟兴趣网，并计算该 网络的链接相似度;然后计算用户真实关注网络的链接相似度;最后，综 合以上两点得到总的链接相似度。该相似度为局部度量，只需计算相邻边 的相似度即可，大大降低了全局相似性度量的复杂度。 第二部分通过对Ward层次聚类算法的分析，发现其优化目标是待处 理数据距离的线性函数，进而提出将聚类对象拓展到具有两两距离的抽象 对象。通过相似性度量的减函数来定义广义距离，设计了推广的Ward层 次聚类算法用于网络社区结构发现。该算法对距离度量的要求低，只需将 “距离”取为相似性度量的单调减函数即可。 此外，本文主要研究静态网络中微博重叠社区的发现。而事实上，微 博网络具有一定的动态性和即时性。如何动态发现微博网络中的社区结构 将会成为下一步工作的重点。 参考文献 [1] Scheffer M. Complex systems: foreseeing tipping points[J]. Nature, 2010, 467(7314): 411-412. [2] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174. [3] 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. [4] Latouche P, Birmelé E, Ambroise C. Overlapping stochastic block models with application to the french political blogosphere[J]. The Annals of Applied Statistics, 2011, 5(1): 309-336. [5] Lee C, Reid F, McDaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[J]. arXiv preprint arXiv:1002.1827, 2010. [6] Gregory S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10): 103018. [7] Xie J, Szymanski B K, Liu X. SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on. IEEE, 2011: 344-349. [8] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761-764. [9] Shi C, Cai Y, Fu D, et al. A Link Clustering based Overlapping Community Detection Algorithm[J]. Data & Knowledge Engineering, 2013. [10] Ye Q, Wu B, Zhao Z, et al. Detecting link communities in massive networks[C]//Advances in Social Networks Analysis and Mining (ASONAM), 2011 International Conference on. IEEE, 2011: 71-78. [11] YAN Guang-hui, SHU Xin, MA Zhi-cheng, et al. Community discovery for micro-blog based on topic and link analysis[J]. Application Research of Computers, 2013, 30(7): 1953-1957. [12] WANG Wei-ping, FAN Tian, Community Discovery Method Based on Users’ Interest Similarity and Social Network Structure[J]. Computer Systems & Applications, 2013 (6). [13] CAI Bo-si, CHEN Xiang. Research on Micro-blog Community Discovery Based on Behavior Similarity[J]. Computer engineering, 2013, 39(8). [14] Zhiheng Xu, Long Ru, Liang Xiang, Qing Yang. Discovering User Interest on Twitter with a Modified Author-Topic Model[C]//International Conferences on Web Intelligence and Intelligent Agent Technology. IEEE/WIC/ACM, 2011:422-429 [15] Hong L, Davison B D. Empirical study of topic modeling in twitter[C]//Proceedings of the First Workshop on Social Media Analytics. ACM, 2010: 80-88. [16] Mirkin B. Core concepts in data analysis: summarization, correlation and visualization[M]. Springer, 2011. [17] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118-1123. [18] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41. [19] YUAN Fu-yong, FENG Jing, FU Qian-qian, et al. A Method to Reduce the Impact of Zombie Fans in Micro-blog[J]. New Technology of Library and Information Service, 2012, 5: 70-75. [20] Danon L, Diaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): P09008 附中文参考文献: [11] 闫光辉, 舒昕, 马志程, 等. 基于主题和链接分析的微 博社区发现算法[J]. 计算机应用研究, 2013, 30(7): 1953-1957. [12] 王卫平, 范田. 一种基于主题相似性和网络拓扑的微 博社区发现方法[J]. 计算机系统应用, 2013 (6). [13] 蔡波斯, 陈翔. 基于行为相似度的微博社区发现研究 [J]. 计算机工程, 2013, 39(8). [19] 原福永, 冯静, 符茜茜, 等. 一种降低微博僵尸粉影响 的方法[J]. 现代图书情报技术, 2012, 5: 70-75.