基于JSCNM算法的微博网络社区发现研究

刘发升，刘艳军，葛海明/

（江西理工大学信息工程学院 赣州341000）

1 引言

近年来，数据挖掘一直是科学研究中非常重要的领域，尤其在这个海量数据时代。目前，在数据挖掘领域，分析复杂网络[1]的结构成为研究的热点，发现社区结构对于企业或者科研工作来说都具有重要意义。社交网络是一种从现实社会中抽象出来的复杂网络，遵循小世界理论[2]、服从幂律分布[3]并且可以对网络结构进行社区划分。在线用户社交网络改变了用户间的交流方式，影响了社会互动，微博网络是社交网络的典型代表。微博（Weibo）是Web 2.0技术的标志性产物，是以用户间的关系为桥梁，将用户创造的数据以文本、图片、视频等方式对外传播来进行交流沟通。微博网络具有文本内容简明扼要、用户可实时交互并且关系结构稀疏等特点。国外著名的社交网站Twitter、Facebook以及国内的新浪微博、腾讯微博均拥有庞大的用户群。根据2014年7月 《第34次中国互联网络发展状况统计报告》可知，我国网民数量达6亿多，手机网民数量达5亿多，并且微博平台的用户增长率仍然处于领先地位。以新浪微博为例，截至2014年9月，微博月活跃用户数达1.67亿。如今，微博已经成为人们网络生活中获取新闻热点、娱乐生活等必不可少的网络媒体。通过分析微博网络中用户的行为特征和相互关系，找出兴趣相投的用户社区，成为社交网络在数据挖掘领域研究的重点。

社区是社交网络结构中一种重要的属性，目前对于社区并没有统一的定义，研究学者普遍认为社区内部节点联系较为紧密，外部节点联系较为稀疏[4]。在复杂网络的研究中，网络结构通常被抽象为图模型表示G={V,E}，其中，V={v1,v2,…,vn}表示节点集合，E={e1,e2,…,em}表示边的集合。在具体的网络中，V表示为网络实体的集合，E表示为实体之间关系的集合。例如，在微博网络中，V表示微博用户的集合，E表示不同用户之间的关注关系。

传统的社区发现算法研究中，将微博作为客体对象较少，近几年对于微博网络社区发现的研究一般分为3种方法。

（1）基于用户结构

用户网络结构包括用户之间的关注或者好友关系，此类方法是通过将用户结构抽象为图论等问题进行社区发现。参考文献[4]通过采集微博用户原生指标和构造指标信息，利用派系过滤算法对用户行为相似度进行聚类，进而发现用户社区。参考文献[5]通过用户关系紧密度构造微博无向加权图，根据加权算法发现微博社区。该类方法没有考虑用户兴趣特征，仅通过用户间关系发现社区，无法体现用户兴趣对社区的重要性。事实上，即使没有直接关系相连的两个用户，若他们发布的内容相似，这两个用户在很大程度上可能拥有相似的兴趣并且应该被加入到同一个社区中。

（2）基于用户内容

此类方法一般采用提取用户在网络中发布的微博文本内容以及用户行为等特征属性，来比较用户兴趣相似度，通过相似度计算公式将用户进行划分。参考文献[6]将用户对地理位置和社区的选择偏好引入到时空主题模型中发现用户社区。参考文献[7]采集用户标签信息，将其使用频率和稀疏度作为用户兴趣进行聚类形成社区。该类方法没有考虑到用户关系在数据传播中的桥梁作用，显性的好友关系对社区发现起到重要的作用。

（3）基于用户结构和内容的综合方法

此类方法的一般流程是提取基于用户结构的微博社区以及基于用户兴趣的微博用户社区，然后采用某种聚类算法将两种社区进行融合。参考文献[8]分析用户关系和微博主题，通过相似度公式计算节点间的传递概率，利用标签传递算法发现社区。参考文献[9]利用关注关系为节点将用户和文本内容融合来发现社区。

一般来说，朋友之间更有可能分享相同的兴趣。基于这样的原则，在推荐系统的研究中，较为准确的推荐往往会综合考虑用户的好友关系和生成内容。同样，在文档检索（Document Retrieval）和文档分类（Document Classification）中也经常运用。如此便说明这一原则在多关系网络中具有实际意义，因此，该原则对于微博网络社区发现也同样适用。

根据用户关系和内容对发现社区的重要性，本文采用适合微博网络的主题模型生成用户兴趣特征，利用JS距离（Jensen-Shannon Divergence）公式计算用户的兴趣相似度，并在CNM算法的基础上提出一种改进的JSCNM算法。该算法将用户兴趣主题和用户关系进行融合以取代模块度增量对微博网络的凝聚。最后在真实数据集中进行实验，发现用户社区。

2 相关术语

2.1 微博网络结构

国内较为著名的社交网络有新浪微博（Sina Weibo）、 腾讯微博 （Tencent Weibo）、 人人网（Renren）、豆瓣（Douban）等。 以新浪微博为例，每一个微博用户允许发表不超过140字的微博文本，可包含表情、图片、视频、话题等内容。兴趣相投的不同用户之间可以在不必告知对方的情况下彼此关注或者单方面关注。也就是说，一个用户可以关注其他用户，同时也可以被其他用户所关注。用户可以转发其他用户的微博。图1为微博的复杂网络结构。

微博网络用图模型G=（V,E）表示，其中，V表示在微博网络中所有节点类型的集合，E表示在节点V之间有联系的边的集合。如图1所示，所有节点类型集合V可以表示为V={U,C,W,R}={,,,}，其中，Ui（i=1,2,3）表示微博用户，Cj（j=1,2,3,4）表示用户发布的微博内容，Wk（k=1,2,3）表示组成用户发布的微博内容的词语序列，R1和R2分别表示用户U2和U3评论且转发U1和U2的微博C1和C3的行为。边集合E={,…,,…,,…}表示用户—用户之间、用户—内容之间以及内容—词语之间的联系。表示用户U1被U2关注，表示用户U1发布的微博内容C1，表示微博内容C1由词语W1构成。在用户关系中，存在一个子图G′=，其中，Eu={,,}，这说明微博网络中用户之间的关注关系是有方向的。

2.2 模块度

模块度Q（Modularity）[10]是Newman提出的用于识别社区划分结果好坏的度量标准。模块度定义为每个社区内部的连接数与维持度序列不变的随机化网络的期望连接数的差值的累加和。换言之，模块度较高的网络社区内连接比随机化网络更密集。假设一个网络划分成多个社区，可以用式（1）判断它是否为一个好的划分。

针对上述不足之处，模块度在CNM算法[11]中得到优化，有

其中，ki表示节点i的度大小。

实验表明，网络拥有社区结构的模块度值范围为0.3～0.7。一般来说，当模块度值大于0.3时，就可以看作是一个好的社区划分。经过实验证明，模块度仍然存在一些不足之处，比如存在过拟合现象以及有限分辨率的现象等。尽管如此，目前尚未存在其他更好的度量方法能够像模块度函数一样，在发现社区结构划分的同时确定社区的数目。通过对模块度进行优化来更加有效地发现社区结构仍具有重要的研究意义。

2.3 相似度中心性

用户兴趣相似度是指不同用户对某一事物感兴趣或者喜好的程度。在微博网络中，用户兴趣相似度表示为用户发布的微博内容之间相关联的程度，因为用户发布的内容可以彰显用户当时的喜好。用户相似度中心性是指某一用户节点和其所有邻居节点相似度的总和。用户相似度中心性计算公式为

其中，Sim（i,j）表示节点i和节点j之间的兴趣相似度，n表示网络中用户总数。一个节点的邻居节点越多，它的中心度越大。表示整个网络中所有用户节点的中心度总和。

3 相关算法简介

3.1 CNM算法

CNM算法[11]是Newman提出的基于贪婪思想的快速社区发现算法，通过不断优化模块度函数进行凝聚来实现对社区的划分，该算法的思想是通过迭代发现由合并每一对社区引起的模块度增量的变化，并利用这个变换的最大值，来合并拥有最大变化值的社区。在算法执行过程中，由于模块度增量矩阵和对应的社区编号都采用高效的最大堆数据结构存储，使得最大模块度增量和对应的社区信息可以在常数时间内获取，其时间复杂度接近线性值O（n log2n）。故该算法是第一个适合较大规模网络的社区结构发现算法。虽然目前存在多个优秀的相关算法，但是CNM算法是唯一一个从全局角度考虑社区合并、直接有效地优化模块度的快速算法。

为了运算方便，CNM算法定义了两个变量，即eij和ai，表达式分别为

式（4）分别表示社区i和社区j内部边的总数占网络中全部边的总数的比值以及社区i内部节点关联的全部边的总数占网络中全部边的总数的比值。

CNM算法定义以下3种类型矩阵：存储模块度增量ΔQ的稀疏矩阵；最大堆H；存储向量ai的常规矩阵。

算法基本流程如下。

①初始化。将网络中的每一个节点视为一个社区，利用公式初始化ΔQ和ai。

在算法刚开始时，如果节点i和节点j之间有边相连，则eij=1/2m；如果没有边相连，则eij=0,ai=ki/2m。模块度增量的值为

②初始化最大堆H。将ΔQ矩阵每列中的最大值写入到H中。

③遍历H中的最大值ΔQij，将社区i和社区j根据合并原则进行合并，标记为社区i，并更新ΔQ和H中行和列的值以及辅助向量ai的值。

当社区i和社区j合并到社区i时，需要删除社区j对应的行和列的值，合并规则定义如下

更新后的辅助向量ai的值为ai′=ai+aij，aj=0。记录更新后的模块度Q的值为Q=Q+ΔQ。

④重复步骤②和③，直到所有的节点归到一个社区，算法结束。由于模块度增量矩阵和对应的社区编号都用最大堆数据结构存储，因此可以在常数时间内获取数据，更新和删除操作可以很快地完成。当ΔQ全为负数时，模块度值下降，这个过程中会出现峰值，也就能得到社区最优的划分。模块度值大于0.3就可以看作是一个好的社区划分。

3.2 主题模型LDA

主题模型是对自然语言进行主题挖掘并能识别语义的语言模型。传统的主题挖掘一般采用向量空间模型（Vector Space Model，VSM），将文本表示为特征项集，利用余弦公式计算文本间的相似度，聚类结果往往只能区分类别，不能进行语义识别。例如，“乔布斯离我们而去了”和“苹果价格会不会下降”这两个句子在文本上没有相似之处，但是在语义上是相关的。传统的计算文本相似度发现方法无法解决文本挖掘中的语义问题，但是主题模型能够识别。

LDA[12]（Latent Dirichlet Allocation）是众多主题模型算法中较为经典的一个。LDA是Blei等人提出的能够识别大规模文档集或语料库中潜在的主题信息的算法模型。它使用词袋（Bag OfWords，BOW）方法，该方法将文档视为词语的集合，进而构成词频向量，最后将文本转化成易于建模的数据。LDA模型思想是任意一篇文档都是由若干个主题混合生成的，并且被表示为主题所构成的一个概率多项分布。其中，每个主题都是一个基于文本词语项的概率多项分布。

LDA是一个层次贝叶斯概率模型，由文档（Doc）—主题（Topic）—词语（Word）3层构成，其含义是某一篇文档中的词以一定的概率选择了某一主题，并从这一主题中再以一定的概率选择某些词语。生成一篇文档中每个词出现的概率为P(word|doc)=

词语层：词语集合W={w1,w2,…,wj}，是文档集合中经过预处理后的单词集合。

主题层：主题集合={z1,z2,…,zk}，是基于词语集W的概率多项分布，也可以表示为向量φk=（pk1,pk2,…,pkj），其中，pkj表示词语wj在主题zk上的生成概率。

文档层：对于词语层来说，文档层使用词袋方法，将每一个文档表示成一个词频向量di=（tfi1,tfi2,…,tfij），其中，tfij表示词语j在文档i中出现的次数。对于主题层而言，文档集合可表示成Θ={θ1,θ2,…,θd}，且每一篇文档由一个向量 θd=（pd1,pd2,…,pdz）表示，其中，pdz是主题z在文档d中的生成概率。

在LDA中，α表示文档—主题多项分布的先验知识，β表示主题—单词多项分布的先验知识，其中，α和β都服从狄利克雷分布。

LDA生成过程如下所示。

选择参数 φ～Dir（β）;

选择参数 θ～Dir（α）;

对于N个单词中每一个单词w:

选择一个主题z～p（z|θ）;

选择一个单词w～p（w|z,φ）;

主题向量φ表示词语在主题上的生成概率，服从狄利克雷分布。主题向量θ表示每个主题在文档中出现的概率，也服从狄利克雷分布，该向量是非负归一化向量。N表示要生成文档的单词总数，w表示第n个单词。z表示要选择的主题，p（z|θ）表示在给定θ的情况下，主题z的多项概率分布。p（w|z,φ）表示在选定一个主题z的情况下，该主题所对应的单词的多项概率分布。

由上述过程可知，LDA联合概率分布表达式为

LDA模型中，θ表示文档—主题 （doc-topic）的概率分布，φ表示主题—词语（topic-word）的概率分布。这两个参数是模型最终要得到的值，根据联合概率分布公式，使用吉布斯（Gibbs Sampling）公式对其采样并进行求解。吉布斯采样是一种马尔可夫链—蒙特卡罗（MCMC）算法过程。步骤如下。

①初始化。通过将文档中的所有单词随机赋予主题来构造马尔可夫链的初始状态。

②求解下一个状态。对每篇文档Di的每个单词wn进行迭代，根据吉布斯公式计算当前单词的各个主题zn的概率p（zn=k|wn），k表示主题数；通过概率随机采样确定当前的分配主题。

③迭代执行步骤②，直到马尔可夫链达到稳定状态。

吉布斯采样表达式为

其中，zi表示第i个词对应的主题，┐i表示去除下标为i的词，表示除去当前单词项在第m篇文档中单词项所对应的主题个数，表示除去当前单词项在第k个主题中产生单词的个数。

吉布斯采样过程结束后，文档—主题（doc-topic）的概率分布θ以及主题—词语（topic-word）的概率分布φ可由后验概率近似估算出来。

其中，变量解释如式（7）所述。m表示文档数，k表示主题数，t表示单词数。

3.3 JS距离

JS距离[13]是在KL距离[14]的基础上改进的用于测量随机变量的概率分布的相似度。KL距离是Kullback-Leibler差异（Kullback-Leibler Divergence）的简称，它用于检测在同一事件空间里两个概率分布的差异情况。在本文中可以用于计算用户相似度距离。假设P、Q表示两个随机变量的概率分布，用KL距离公式计算概率P和概率Q之间的距离为DKL（P||Q）。KL距离具有不对称性、非负性的特点，DKL（P||Q）≠DKL（Q||P）≥0。 当两个概率分布完全相同，即P=Q时，DKL（P||Q）=0。

针对KL距离的不对称特性，将KL公式改进成JS距离公式，首先取两个概率分布的平均值，分别利用KL公式计算两个概率分布和其平均值的距离，再对距离之和求平均值，这样可以更准确地计算两个概率分布的相似程度。JS距离和KL距离的计算公式分别为

其中，P、Q表示两个随机变量的概率分布，R是随机变量P、Q的均值。

根据主题模型中用户和主题之间的概率分布，利用JS距离计算方法，可以求出不同用户之间的兴趣相似度。其中，JS距离值越小，用户主题之间的相似度越大，当两个对象具有相同的概率分布时，JS距离的值为0。JS距离的倒数表示用户之间的相似度，则两个用户u1、u2之间的相似度可以表示为Sim

4 JSCNM算法在微博中的应用

4.1 LDA在微博文本中的应用

针对微博网络自身的特点，如文本内容短、噪声数据多、数据稀疏而且数据具有多样性，LDA在微博网络中需要做些改进以适应真实网络的需要。首先由于微博文本短的特点，采取将每个用户的所有微博作为一个文档集合对待，再根据用户兴趣随着时间或在当下社会热点的改变而改变，将用户内容选择最近时间的文档集合。用户标签是用户在注册时或在使用过程中添加的用来标示自己身份或者兴趣爱好的短文本数据，比如 “90后”、“学生”、“动漫”等。“物以类聚，人以群分”，不管是在现实生活中还是在虚拟的社会网络中，用户往往更倾向于和自己身份相仿、兴趣相似的用户交流。基于这种现象，对标签进行处理作为用户节点的属性然后加入到模型中，更能真实反映用户的兴趣特征。

根据上文的分析可将LDA在微博中的应用表示为 “用户—微博—主题—词语”4层贝叶斯模型。因为标签数据是以短语的形式进行存储，且数据准确性较高，故不用对其进行数据预处理，即可直接保存为用户的属性集合，称为用户层。以用户ui的所有微博文本集合Ti={t1,t2,…,tn}为一个文档D。所有的文档集合定义为微博层，在文档中产生的用户的兴趣主题定义为兴趣层。LDA的图模型如图3所示。根据LDA模型，可以求出每个用户与不同主题之间的概率分布，生成一篇文档，每一个词语出现的概率为文档集中所有词语和主题的联合概率分布为

根据联合概率分布公式，采用吉布斯算法对其进行采样，可以得到用户和主题的概率分布。

用户和主题之间的概率分布矩阵为

其中，T为用户的微博文档，z为兴趣主题，pw表示两者的生成概率。

4.2 JSCNM算法

CNM算法是通过对网络中模块度的增量最大值来进行聚类的，GN算法[15]是通过反复删除网络中边介数最大的边，逐步将网络划分层次结构。CNM算法比GN算法拥有更好的执行效率，但CNM算法对于检测较大规模的网络，可能存在社区划分不平衡的问题。本文在CNM算法的优点的基础上，利用用户相似度距离取代模块度的增量最大值来对网络进行社区划分，此算法简称为JSCNM算法。

JSCNM算法的思想是通过用户节点之间的相似度融合用户间关系即用户相似度中心性的变化Cs(i)来替代模块度增量，根据合并规则对网络进行聚类划分，最后形成多个相似用户社区。其中，根据JS距离公式计算用户兴趣相似度矩阵，然后逐渐根据社区之间相似度的大小来进行合并。

初始化用户相似度矩阵时需要按照一定的规则进行相似度合并。例如，需要将i和j社区合并成新的i社区，合并之后需要删除第j列并且更新第i列，本文的合并规则仍然使用CNM算法的合并规则。定义变量eij和ai的值分别为

其中，Cs(i)是节点i的相似度中心性的值，m是网络中所有节点的中心性值的总和。用相似度取代模块度增量为

其中，α为调和因子。实验表明，当α=5时，效果最好。Sim(i,j)是节点i和j的相似度距离，也是节点间概率分布的JS距离的倒数值。

JSCNM算法流程如下。输入网络的邻接矩阵，输出社区个数、最大模块度Q。

①利用LDA模型计算出用户—主题之间的概率分布矩阵。

②利用JS距离公式初始化用户之间的相似度矩阵S，初始化模块度增量矩阵ΔQ。

③初始化最大堆H，里面存放模块度增量矩阵ΔQ中每列的最大值。

④选择最大堆H中的堆顶元素，参考合并规则公式对增量矩阵最大值对应的行和列来进行合并，更新增量矩阵和大顶堆。

⑤直到所有的节点归于一个社区，否则继续执行步骤④。

5 实验结果

5.1 数据采集

本文实验采用网络爬虫抓取新浪微博用户信息及其微博内容。考虑到用户粉丝数在某种程度上可以反映用户的性质和重要性，本文随机爬取用户粉丝数在50～100、100～150、150～200、200～250的4个用户作为种子用户，并进一步地爬取与其有关联的微博用户信息和用户最新的150条微博内容。因为微博中存在许多噪声数据，例如，一些表情符号、视频链接等。这些噪声数据不但对分析数据没有帮助，而且会影响实验效率，因此需要对噪声数据进行清洗。在数据预处理部分，利用中科院的分词工具对微博数据进行去除停用词、清洗噪声数据以及对中文进行分词操作。

对数据集进行预处理，筛选出其中4个用户集合见表1所列。

表1 4组实验数据集统计

5.2 结果分析

图4为4个数据集中各个用户节点的度大小分布。由图4可知，大部分用户节点的度是比较少的，极少数的用户拥有比较多的关联用户，且网络中用户度数服从幂律分布的特征。

表2是4个数据集利用改进的LDA主题模型生成的用户兴趣主题的前20个词语。从表2可以看出，数据集S1中用户比较关心的是球赛、政治、新闻和娱乐等话题；数据集S2中用户较为关心的是宠物、科技、经济和食品安全等话题；数据集S3中用户比较关注的有救援、动物保护、春游等话题；数据集S4中则关心大学生创业、政治经济以及和电影有关的话题。

图5为4个数据集用户之间的兴趣相似度矩阵图。图中点的颜色越深，兴趣相似度越高。因为本文数据是基于用户关系爬取的微博文本，所以在兴趣相似度比较高。而且可以看出，相似度矩阵沿着对角线有一条明显的黑线，说明用户的邻居用户之间有较高的相似度。

表2 4个数据集中用户兴趣主题的前20个词语

表3 3种算法结果对比

通过将本文算法和传统的CNM算法以及GN算法进行对比，使用模块度函数作为评价标准，具体结果见表3。从表3可以看出，本文算法的社区划分比较明显而且用户社区的个数较多，用户分布更加平衡。

6 结束语

本文提出了一种改进的JSCNM聚类算法，利用用户兴趣相似度取代模块度增量对其改进，从而实现了用户关系和用户内容双内聚来划分社区的效果。使用适合微博网络的主题模型LDA对用户兴趣主题进行识别，采用优化的KL距离公式计算用户之间的相似度，在真实数据集上进行凝聚实现社区划分。通过算法的对比实验，证明了该算法流程的科学性、合理性，且实验结果也较为理想。但是因为数据是大规模的文本集，在整个流程中消耗了许多时间资源，如何利用好的模型算法在准确划分社区的同时提高实验效率，将是下一步的研究内容。

[1]丁连红,时鹏.网络社区发现[M].北京:化学工业出版社.2008.

[2]WATTSD J,STROGATZ SH.Collective dynamics of small-world networks[J].Nature,1998,393（6684）:440-442.

[3]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286（5439）:509-512.

[4]蔡波斯,陈翔.基于行为相似度的微博社区发现研究[J].计算机工程,2013,39（8）:55-59.

[5]范超然,黄曙光,李永成.微博社交网络社区发现方法研究[J].技术与方法,2012,（23）:67-70.

[6]段炼,朱欣焰.基于社区时空主题模型的微博社区发现方法[J].电子科技大学学报,2014,43（3）:464-469.

[7]阎春霖,张延园.基于用户标签的社区发现方法研究[J].科学技术与工程,2011,11（6）:1237-1240.

[8]闫光辉,舒昕.基于主题和链接分析的微博社区发现算法[J].计算机应用研究,2013,30（7）:1593-1597.

[9]周小平,梁循.基于R-C模型的微博用户社区发现[J].软件学报.2014,25（12）:2808-2823.

[10]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69（2）:026113.

[11]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69（6）:066133.

[12]BLEID M,NG A Y,JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,（3）:993-1033.

[13]LIN J.Divergence measures based on the shannon entropy[J].IEEE Transactions on Information Theory,1991,37（1）:145-151.

[14]KULLBACK S.Letter to the editor:the kullback-leibler distance[J].The American Statistician,1987,41（4）:338-341.

[15]GIRVAN M,NEWMANM E J.Community structure in social and biological networks[A].Proceedings of the National Academy of Sciences[C].2002,99（12）:7821-7826.