基于微博媒体的社区发现技术研究

邢东东 王秀文

第3卷第6期2013年12月智 能 计 算 机 与 应 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.6Dec.2013

摘要：微博社交网络是由节点构成的，每个节点代表一个微博用户。节点与节点间存在着关系，因此连接紧密的节点形成了社区。如何从微博社交网络中挖掘出社区，已成为Web2.0的团体挖掘研究热点。详细介绍了传统的网络团体挖掘算法，并提出了一种新的社区发现的算法，称为基于用户兴趣的社区发现算法。该算法不论在计算效率还是社区发现效果上比传统算法都具有明显的提升，取得了不错的实验效果。

关键词：社区发现； 团体挖掘； 用户兴趣； 微博网络

中图分类号：TP3934 文献标识码：A文章编号：2095-2163（2013）06-0074-04

0引言

微博作为一种新兴的社交媒体，其作为媒体平台的影响力已经远超传统的网页、博客等媒体的作用力。例如：全球最大的社交网站Facebook的用户数已经超过10亿，Twitter的用户数也已经超过5亿。中国最大的社交网站平台新浪微博注册用户数也已超5亿，日活跃用户数可达4 900多万，用户日发微博则已超过1亿条。随着Web2.0的迅猛发展，用户之间存在了交互，有的用户之间连接紧密、有的用户之间连接稀疏，这就形成了虚拟社区。因此在复杂网络中，挖掘团体（圈子）已经成为时下的研究热点。

本文先对传统社区发现算法进行了介绍，针对微博媒体的特点，提出了一种结合用户兴趣的社区发现算法，同时对算法进行了详细介绍，其后通过实验证实了算法的有效性。

1社区发现的相关研究

1.1谱平分法（Spectral Bisection）[1-2]

谱平分法是一种基于图分割（Graph Partitioning）的社区划分算法，其基本原理是求解基于图的Laplace矩阵的特征向量。该算法在理论上已经得到证明，非零特征值所对应的特征向量中，被划分到同一社区中的节点是近似相等的。并且在已知社区为两个社区结构时，也取得了不错的效果。

但是，在微博社交网络中，却也存在着明显的不足。微博关系网络不可能只存在两个社区结构，因此，谱平分法并不能很好地解决微博社交网络的社区划分问题。

1.2W-H算法[3]

相对于谱平分法这一类传统的图分割算法，即只能将一个网络结构划分为两个社区的问题，Wu和Huberman提出了一种快速谱平分法[3]，称之为W-H算法[4]。W-H算法解决了谱平分法只能将社区结构划分为两个团体的问题，该算法在不考虑整个网络社区结构的情况下，可以求解一个已知节点所在的网络社区结构，而无需计算所有社区。但如果W-H算法并不知道网络社区结构的部分信息，则很难应用该算法进行社区结构的划分。

1.3GN算法[5]

GN算法是由Girvan和Newman于2001年提出的社区划分算法，该算法现已成为经典的社区划分算法。对微博社交网络来说，最基本的要求就是自然分割，而无需预先确定网络社区的个数以及社区的大小。这是基于一种分裂思想的社区划分算法。其基本原理就是不断地从网络中移除介数（Betweenness）最大的边。边介数则定义为网络中经过每条边的最短路径的数目[6]。GN算法的优点表现在，可以将网络分裂成任意数量的社区，还可以从算法的树状图查看网络社区结构形成的动态过程，如图1所示。

GN算法由网络整体的全局结构出发进行社区识别[7]，避免了传统算法的众多缺点，业已成为目前实现网络社区分

析的标准算法，因而得到了广泛的应用。但GN算法也存在着两个不足，首先，该算法不能确定最后要分解的社区数目。其次，算法的计算效率不佳，最差的时间复杂度为O（m2*n）[7]，其中m，n分别为网络中的边及节点的数目。

1.4CNM算法

CNM社区发现算法[8]作为一种凝聚思想的团体挖掘算法，由Clauset、Newman等人所提出。该算法以模块度为度量标准，每次都沿着模块度更新最大的方向进行合并。这是一种基于贪心策略的算法，在时间复杂度方面相当于线性时间的复杂度，并已经广泛应用在大型网络的计算中[6]。

本文的实验部分即利用CNM算法与本文提出的基于用户兴趣的社区发现算法[3]进行了对比。

1.5其他社区发现的算法

在最近的社会网络研究中，还有学者提出了一些新的算法。

例如，Radicchi[7]等人给出了边聚类系数（Edge Clustering Co-Efficient）的定义，并以此为基础给出了快速的Radicchi算法[9]。该算法与GN算法的效果相当，但是速度却有了较大提升。

在很多情况下，社区很难实现独立划分，为解决这种相互重叠的社区结构的发现问题，Palla等提出了一种派系过滤算法（Clique Percolation Method，CPM）[10]。

总之，目前的社区网络挖掘算法都是基于分裂或者凝聚的理念，而没能有效利用Web2.0网络自身独具的一些特点来进行团体挖掘，为此，本文提出了一种基于用户兴趣的团体挖掘算法。

2基于用户兴趣的社区发现算法

上一节中介绍的传统网络挖掘算法已经涵盖了目前网络研究中的通用算法，这些方法无论是计算效率、或是挖掘效果均已获得了良好表现，然而对于微博网络这种新媒体，因其具有一些自身特性，就使得已有算法需要进行一定的改进或研发相应的新算法。微博的独特之处则在于微博社交网络中不仅包括关系信息，还包括用户自身产生的信息。每个微博用户具有个人简介、自定义的标签属性、教育信息、以及每天产生的微博文本信息。在此将这些区别于传统网络的额外信息称为用户的兴趣。现实社会中也可以发现，兴趣和社会关系在社区共享和交流方面起着至关重要的关键作用，兴趣一致的用户更容易形成社区，并通过社会关系，兴趣相投的朋友还可以推荐其他朋友加入社区，这是符合现实社会客观实况的。本节对该算法进行详细介绍。

2.1 算法步骤及流程

基于用户兴趣和网络拓扑的社区发现算法，主要分为三个部分。第一部分为构建用户间的拓扑关系网络；第二部分是基于网络拓扑结构，确定用户的兴趣；第三部分，采用聚类算法，根据用户的兴趣发现社区。

第一部分（见2.2节）——用户间的拓扑关系网络的构建。微博社交网络中每个用户都存在着关注关系，根据关注关系可以形成用户间的关系图谱。另外，微博用户A与微博用户B之间存在转发，@以及评论行为。这些内容使得两者之间产生了交互，因此微博用户与用户之间存在交互关系。

第二部分（见2.3节）——用户兴趣的确定。首先每个用户拥有初始的兴趣标签，然后根据用户的关系网络对兴趣标签进行修正，以此完善用户的标签。

第三部分（见2.4节）——聚类、发现社区。根据第二部分的用户兴趣标签，采用聚类算法发现社区。

实验步骤流程如图2所示。

2.2用户间关系网络的构建

本小节在于说明如何构建微博用户之间的关系网络。构建网络的最直接方式就是用户间的关注关系。每个微博用户都存在一个关注列表，根据每个用户的关注列表，则可以构造用户间的关注网络。但却需考虑到这只是用户间的简单关注网络，并不能完全反映用户的兴趣，例如，用户关注“李开复”，但是若用户却从未转发“李开复”的微博，或者“李开复”也从未转发该粉丝的微博，则可认定二者只有简单的关注关系，这是一种弱关系，并不能反映用户的兴趣。

综上所述，即可选择交互性来衡量二者之间是否存在关系。如果用户A与用户B存在着交互关系（A转发B的微博，或者B转发A的微博），就能够认定为二者具有强关系。

首先，提取用户A所发的全部微博的文本信息，提取其中的@，找到用户A与其交互的人物列表。例如：Interact（A）={u1，u2，u2，u3，u3，u4…}. 表示A与u1交互1次，与u2、u3、交互2次，与u4用户交互一次。

在此，根据用户A与用户B的交互次数定义A与B直接是否存在边，如果用户A与用户B的交互次数超过一定的阈值，即认定A有一条指向B的边。阈值可以设定为3、5、10等不同的数值，文中则选取3作为阈值。

2.3用户兴趣的确定

算法需要根据用户的兴趣来确定社区，因此如何定义用户的兴趣即成为本文的关键。文中定义用户的兴趣是关键词，也就是利用关键词反映用户的兴趣。每个用户都对应着一个标签向量表示其兴趣。

2.3.1用户兴趣词的构建

每个微博用户都有自定义的标签信息、简介信息、工作信息、教育信息以及认证信息，在此将用户的自定义的标签（Tag）、用户的简介信息（Description）、工作信息（Work）、教育信息（Education）以及认证信息（Vertify），组成文本，再通过分词提取用户的兴趣关键词，组成用户的标签向量。例如，T（A）={w1，w2，…，wn}。文中即使用{w1，w2，…，wn}刻画用户A的兴趣。

2.3.2用户兴趣词的修正

微博用户的个人注册信息，可能不全。例如，一些用户没有自定义标签或者并未填写背景信息等，就会导致用户的标签向量为空。还有一种可能是用户自定义的标签不准确，例如很多用户的标签为“80后”，“音乐”等，并不能充分反映用户的兴趣。针对上述问题，本文采用了一种基于标签传播思想的算法解决了这一问题，具体如图3所示。

由图3可见，用户1与用户2， 3 ，4 ，5， 6存在交互，文中的方法是通过用户2， 3， 4， 5， 6的标签去修正用户1的标签。修正方法是提取用户2， 3， 4， 5， 6出现的所有标签，按词频从大到小排序，并提取Top K个出现频率最高的词作为用户1的标签。对网络中的每一个点迭代计算，直到每个用户的标签不再变化为止。修正标签结束。

现给出算法流程如下：

Step1：找到与节点A有边联系的邻居节点，形成邻居节点集合S，S中的这些节点代表了与用户A有过互动行为的用户集合，同时将A也放入集合S中；

Step2：统计集合S所有用户中出现过的不同标签的频次，用户A本身初始的标签按照频次f参与计数，即给用户本身的标签设定一个较大的初始频次；

Step3：将step2获得的标签按照其频次和标签的IDF值使用IF.IDF的计算方式确定其权重，并按照权重得分高低相应排序，取Top K标签作为节点A的新标签集合；

Step4：直到标签不再变化或者达到迭代次数为止。

算法的优点是：

（1）通过引入TF.IDF影响因子，滤去了很多共有的标签，例如“音乐”，“电影”，“80后”等，强化了节点的特有属性。

（2）结合了交互网络图谱，使其自身的标签属性得到了修正，解决了一些用户没有自定义标签或者自定义的标签不足的问题。

2.4聚类及社区发现

根据2.3节的标签传播算法，每个网络节点都有一个标签向量。本节根据用户的标签向量来计算用户之间的相似度，而后采用K-Means聚类[11]，对社区进行划分。

2.4.1用户相似度计算方法

如果微博用户A有n个标签，则用户A的标签向量为T（A）={w1，w2，…，wn}，网络中的每一个用户均用向量表示，则两个用户之间相似度定义为两个标签向量Jaccard系数：

其中，I1，I2分别表示两个微博用户，I1∩I2表示两个用户共有的标签，I1∪I2表示两个用户总共的不同标签数。

2.4.2聚类

通过2.4.1计算每个用户之间的相似度，组成了一个相似性矩阵，根据相似性矩阵，可以采用K-Means聚类的方法对节点进行聚类。

算法流程：

（1）先随机选择K个节点当做中心，为初始社区。

（2）将网络中的每一个节点划分到与其相似度最大的那个中心，即形成初步的社区。

（3）重新计算社区的中心。社区的中心为社区内的其他点到其均方误差最小的那一点。

（4）重复（2）、（3），直到每个社区内的点不再变化为止。

3社区发现算法效果评价

本节将对文中提出的算法和传统的社区发现算法（CNM算法）进行对比，无论在算法性能还是社区发现效果上均获得了很大提高。

3.1数据集描述

利用微博网络爬虫，随机选择一批种子节点，爬取了1 500个人物的基本信息，称为User。其中，包括人物的ID，昵称（Screenname）、自定义标签（Tag）、描述信息（Description）、工作信息（Work）、教育信息（Education），以及人物的关系数据（微博上的关注列表）。另外，还有微博文本信息，将其称为Status， 其中，包括微博mid、微博文本（Text）、原创微博的mid，以及原创微博的文本（Text）。

3.2实验

在此，基于3.1节描述的数据集，在其上进行算法试验，利用本文提出的算法和CNM算法进行对比实验。

对微博文本进行预处理，提取@关系，形成用户间的交互网络，如果用户之间@的次数超过M次，则定义之间存在边。M取值的不同，构建了不同交互强度的网络拓扑。文中规定当M=0时，定义网络为关注网络，而不是交互网络。因为本算法采用了K-Means聚类的思想，则可依据CNM算法所划分的团体个数设定K的取值，也就是说，两个算法所划分的团体的个数相同，社区内的节点却各有不同。

其中，当M=0时，网络中存在95 020条关系；M=3时，网络中存在25 259条关系；M=5时，网络中存在15 453条关系。在三个网络中分别使用CNM算法和本算法进行实验对比。

3.3效果评价

通过实验，将本文提出的基于用户兴趣的社区发现算法与CNM算法在计算效率和算法效果上进行对比。其中，计算效率是指算法的运行时间。社区划分的效果，则采用每个划分的圈子中，用户的平均交互次数作为评价标准。因此，算法的运行时间越短、每个社区内的用户的交互越频繁，就表明社区划分效果越好。实验结果如表1和表2所示。

通过实验对比发现，本文所采用的基于用户兴趣的社区发现算法，在计算效率方面比传统的社区发现算法高，其算法的计算复杂度为线性时间复杂度，因而适合大规模的网络计算。在算法效果方面，其划分的社区内用户的交互比传统算法划分的社区交互更为频繁，因此，整体效果要优于传统算法。

4结束语

在Web2.0媒体的社交网络中，挖掘团体，社区发现具有重要的价值，而识别团体算法的计算效率以及团体识别的准确率则非常重要。本文所采用的数据集只是一个局部数据集，如果在大规模数据集上进行运算，必然能对用户兴趣模型进行更为优异的刻画，而大规模计算技术则可以采用目前流行的Hadoop（Map/Reduce）[12]框架，而这也是今后研究发展的重点和热点。

参考文献：

[1]FIEDLER M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal， 1973， 23（2）： 298-305.

[2]POTHEN A， SIMON H D， LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications， 1990， 11（3）： 430-452.

[3]薄辉. 社区发现技术的研究与实现 [D]. 北京： 北京交通大学， 2009.

[4]WU F， HUBERMAN B A. Finding communities in linear time： a physics approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems， 2004， 38（2）： 331-338.

[5]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

[6]韩瑞凯， 孟嗣仪， 刘云， 等. 基于兴趣相似度的社区结构发现算法研究[J]. 铁路计算机应用， 2010 （10）： 10-14.

[7]汪小帆. 复杂网络中的社团结构分析算法研究综述[J]. 复杂系统与复杂性科学， 2005 （3）： 1-12.

[8]CLAUSET A， NEWMAN M E J， MOORE C. Finding community structure in very large networks. Phys. Rev. E，2004，70：66-111.

[9]PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.

[10]DERNYI I， PALLA G， VICSEK T. Clique percolation in random networks[J]. Physical review letters， 2005， 94（16）： 160-202.

[11]TEKNOMO K. K-Means Clustering Tutorial[J]. Medicine， 2006， 100（4）： 3.

[12]BORTHAKUR D. The hadoop distributed file system： Architecture and design[J]. Hadoop Project Website， 2007， 11： 21.