现实生活中存在多种类型的复杂网络, 包括生物网络、文献引文网络以及新兴的社会网络.复杂网络具有小世界、无标度等特点, 对复杂网络的结构特征分析已经成为当前研究的热点.社交网络是一种新兴的复杂网络, 遵循复杂网络的特点, 对社交网络的社区划分能够为商业推荐和用户管理以及研究工作者提供有意义的帮助.

微博(microblog)是Web 2.0时代的标志性产物, 是一种集成化、开放性的社交网络, 是基于用户关系的信息发布、传播以及获取的平台.作为一种新兴的社交网络平台, 用户创造的不同格式(文本、图片)的数据传播到微博网络中, 不仅受到了用户的欢迎, 而且也获得了很多研究人员的关注, 已经成为国内外专家的研究热点.在微博网络中, 用户可以发布简短文本(通常少于140字)信息, 此类信息称为博客(或博文), 而博文信息是通过用户之间的转发或评论等方式在网络中进行传播.作为新兴媒体, 微博网络具有简便、及时等特点, 受到网络用户的日益青睐, 信息涵盖的主题比传统媒体更加宽泛, 有很高的更新与传播速度.对微博网络的用户关系进行分析, 并对潜在主题进行挖掘, 找出兴趣相似的用户以及特定领域的活跃用户, 掌握社区动态, 可以为舆情控制及个性化推荐等提供有力的支撑.

微博网络中的社区是由具有相同或相似兴趣爱好的用户组成的, 可以分享并交流信息的子团体.由于微博网络具有用户规模大、节点的度分布不均匀、弱社交网络等特点, 传统的社区发现算法应用于微博网络具有局限性, 而基于概率主题模型的社区发现算法不仅适用于大规模网络, 而且能够将微博网络中节点的语义信息和微博网络拓扑结构融合, 主要的概率主题模型有LDA (latent Dirichlet allocation)^[1], ATM (author topic model)^[2]等.

由于博文为短文本, 存在数据稀疏性问题, 本文提出DTM (dynamic topic model)主题模型来挖掘微博网络中的作者博文.考虑到博文的动态性, 只选取作者近一年的博文作为研究对象, 将不同作者博文的主题相似度作为作者之间链接的权重, 将微博网络映射为有向加权网络, 并提出复杂度低的标签传播算法WLPA (weighted lebel propagation)进行社区发现.通过在新浪微博数据上进行实验, 结果表明:本文所提出的主题模型DTM与LDA模型相比, 模型的困惑度较低, 并且该模型能够较为准确地定位对某一话题敏感的作者集合; 本文所提出的DC-DTM社区发现算法发现的社区的模块度较高.

本文的主要贡献如下:(1) 根据微博网络中节点自身以及节点之间联系的特性, 建立微博网络的RT模型, 将微博网络映射为有向加权网络; (2) 利用DTM概率模型, 将转发/评论博文与原博文相结合, 挖掘作者的主题分布以及整个网络的主题分布趋势; (3) 将不同作者的主题分布相似度作为作者之间联系的权重, 在此基础上利用标签传播算法对微博网络进行重叠社区发现; (4) 针对微博网络的社区发现, 提出了基于语义的微博网络社区的评价指标; (5) 在大量新浪微博数据中进行实验, 实验结果表明本文所提出的DTM模型在生成主题质量、内容困惑度以及模型复杂度等方面的指标都优于传统LDA模型, 本文的DC-DTM算法发现的社区比传统的基于标签的社区发现算法的模块度高, 稳定性好.

1 相关工作

目前研究者已经提出了许多社区发现算法, 从传统的根据网络拓扑结构进行社区发现发展到基于语义的社区发现以及融合拓扑结构和语义的社区发现算法.下面分别对这3类算法进行阐述.

1.1 基于网络拓扑结构的算法

微博网络中用户之间的关注或好友关系形成了用户网络结构, 此类方法以图论为基础进行社区挖掘, 主要分为非重叠社区划分和重叠社区划分.

所谓非重叠社区划分, 即此类方法所划分的社区中, 某个节点只能属于某一个社区, 不能同时属于多个社区, 此类方法是最早出现的社区划分方法.算法主要有谱方法、模块度优化方法、层次聚类方法、边预测方法等^[3-6].

现实生活中, 一个节点可能以不同的角色参与到不同的社区, 重叠社区结构更贴近网络的真实结构.2005年, Palla等人^[7]对传统的社区发现方法进行扩展, 允许一个节点同时隶属于多个不同的社区, 提出了具有重叠特性的社区结构, 并设计了重叠社区发现算法.在重叠社区发现中, 重叠节点是社区之间的桥梁, 对社区演化和社区间互通信息起到关键作用.当社区间的重叠度高时, 表明共同拥有大部分的成员, 那么这些社区即将融合为一个大社区; 反之, 若社区间的重叠度低, 则说明网络的社区间相对独立.因此对社区重叠结构的研究不仅更贴近网络实际的社区结构组成, 而且也有助于分析网络的演化趋势.此类算法主要是CPM (clique percolation method)算法^[7].该算法的基本思想是社区内部的节点由于具有较高的密度而更容易形成派系; 分区的优化算法都是对社区的基本度量标准, 如密度、模块度和导电率等进行优化.其中, OSLOM (order statistics local optimization method)^[8]算法是通过增加或删除社区内的节点来增强社区的适应度函数; 最著名的是, Baumes等人在文献[9]中提出了一种两阶段方法, 首先将网络划分为不相交的“种子”社区, 然后通过增加或移除某些邻接节点来达到社区的“密度”最大的效果.这些算法大部分都存在需要先验知识或时间复杂度较高的缺点.

由于社会网络的数据集非常庞大, 社区发现算法的速度变得尤为重要.迄今为止速度最快的算法之一就是Raghavan等人^[10]提出的RAK算法.Raghavan等人的社区发现算法除了具有线性时间复杂度的特性以外还具有简单和无需先验知识等优点.但是, 像大多数社区发现算法一样, 它只能发现不重叠的社区.由于标签更新阶段是按照随机的顺序对节点进行更新, 并未考虑到节点在网络中的重要程度, 这会导致标签传播过程的“逆流”现象, 影响算法的稳定性.

研究人员围绕Raghavan等人提出的标签传播算法进行改进, 分别在算法的传播规则、收敛条件和更新策略等方面进行相关研究.但这些算法都只能发现非重叠社区.随后研究人员将标签传播算法进一步改进, 使其应用于重叠社区的发现.第一个使用标签传播算法解决重叠社区发现问题的是Steve提出的COPRA算法(community overlap propagation algorithm)^[11].该算法虽然能够解决重叠社区的发现问题, 但COPRA算法要求输入节点所属重叠社区的数量, 这对于大型网络并不适用.在大型网络中, 为网络设置一个全局的重叠社区个数上限很难符合不同网络、不同节点所处的网络情况, 并且算法仍然存在不稳定等缺点.还有一些算法针对标签传播算法的稳定性进行改进, 但这些算法都存在一定的局限性.文献[12]提出了一种基于标签传播概率的LPPB (label-propagation-probability-based)重叠社区发现算法.该算法在标签传播的过程中, 综合网络的结构传播特性和节点的属性特征共同计算标签传播的概率, 同时利用节点的历史标签记录修正标签更新结果; 最后将传播后具有相同标签的节点划分为同一社区, 社区间的重叠节点构成了社区重叠结构.

此类方法仅仅考虑了用户之间的关系, 并未考虑用户的内容, 而微博网络中用户的内容能够体现用户的兴趣, 对于衡量用户之间的相似度具有指导意义.

1.2 基于用户内容的算法

考虑到微博网络中除了用户之间的关注关系之外, 用户发布的博文是用户兴趣的真实反映, 是用户兴趣的重要依据, 以用户内容为研究对象的微博网络社区发现算法应运而生.此类方法主要通过计算博文内容的相似性进行文本聚类, 将内容相似的博文划分为社区.主题模型是最典型的文本聚类算法.2003年, Blei等人引入了Dirichlet先验分布, 形成了一个“文档-主题-词”3层的贝叶斯模型LDA^[1].该模型首先提出了“主题”的概念, 在主题模型的框架下, 主题是语料集合上语义的抽象, 是语料集合依赖的, 不同的语料潜在的语义是不同的; 随后通过概率方法对模型推导, 即可挖掘出文本集的语义结构.标准LDA模型认为一篇文章的每个词都是通过“以一定概率选择了某个主题, 并从这个主题中以一定概率选择某个词语”这样一个过程得到的.

LDA首先从先验Dirichlet分布中抽取该文档的主题分布, 然后, 从主题多项式分布中选择当前单词的主题; 最后, 从先验Dirichlet分布中抽取该主题的单词分布, 并选择具体单词.LDA模型的参数估计主要采用近似推理算法, 方法主要有变分最大期望算法^[13]、期望传播算法^[14]、吉布斯采样算法^[15].其中, 吉布斯采样算法由于简单易懂和运行速度快等优点, 常被用来求解LDA模型.

近年来, 随着主题模型研究的深入, 研究者开发了多个LDA派生模型.这些模型从不同的角度增加辅助信息以解决数据稀疏问题, 提高了微博的主题挖掘效果.算法主要有:文献[16]针对微博网络高维稀疏空间的问题提出了基于LDA的文本分类方法; 文献[17]通过用户标签的使用频率等信息对用户兴趣进行聚类分析, 将兴趣相似的用户加入到同一个社区, 该方法忽略了微博网络中的关注关系, 而微博网络的关注关系恰恰是微博网络信息传播的桥梁, 在微博网络中能够及时反映用户的兴趣.文献[18-22]利用LDA模型对语义网络进行主题挖掘建立语义空间, 分别利用标签传播算法、BLOCK场、随机游走以及话题综合因子分解等方法进行社区发现.

以上算法在对微博网络进行主题挖掘时, 并没有将转发博文或评论博文与博客原文建立联系, 也未区分博文的类型, 导致算法效果并不理想.

1.3 融合网络结构和用户内容的算法

针对以上两种社区发现算法的不足, 研究人员将上述两种方法相结合, 根据网络结构提取用户联系, 根据用户的博文信息提取用户的兴趣, 将用户联系和用户兴趣进行融合实现社区的划分^[23-29].代表性的文献主要有:文献[23]构建了以关注关系为网络节点, 以关注关系之间是否有共同的用户作为其潜在的边构建了微博网络的R-C模型; 文献[24]通过融合微博内容和微博之间的交互关系对用户的兴趣进行挖掘; 文献[25]将用户和文本内容相融合来发现社区, 文章采用AT (author topic)模型进行用户兴趣社区的发现, 采用NMF方法进行用户关系社区发现, 算法最后将两种社区进行融合来发现最终的社区; 文献[26]在研究LDA的基础上, 对微博的联系人关联关系以及文本之间的关联关系进行统一建模.随着微博的普及, 微博数据量急速增长, 微博中用户的行为更加丰富, 用户的转发、评论等行为是信息在微博网络中传输的原动力, 也是用户兴趣的真实反映, 而上述模型并未考虑到用户行为的因素, 也未对特定主题下用户的影响力进行研究.

以上算法没有充分考虑微博网络的特点, 只是将微博网络抽象为无向无权网络或有向无权网络, 并未抽象为更贴近现实的有向加权网络.除此之外, 以上算法并未对微博网络中的博文进行分类, 未将转发或评论博文与相关原创博文进行联系.本文所提出的DTM (data topic model)模型将评论或转发博文与原博文相关联, 不仅解决了数据稀疏性问题, 而且能够更好地理解博文内容.除此之外, 考虑到博文的动态性以及作者的兴趣变化, 该模型主要挖掘作者最近1年发布的博文主题, 并计算不同作者的博文之间的相似度.由于要将微博网络抽象为有向网络, 本文采用KL (kullback Leibler)距离进行相似度度量, 将不同作者之间博文的KL距离作为作者的相似度.将作者兴趣相似度作为网络中链接的权重, 对微博网络进行建模, 将微博抽象成有向加权网络.在此基础上, 通过标签传播算法WLPA对抽象模型进行社区划分.本文提出的稳定的标签传播算法WLPA (weighted label propagation algorithm), 对关注某一特定主题的用户按照用户的影响力进行排序, 在标签传播过程中, 标签按照用户的影响力大小进行传播, 在增强算法的稳定性、准确性及鲁棒性的同时, 保证了算法的线性复杂度的优点.

2 基于DTM模型的微博社区挖掘算法DC-DTM

本文在分析微博网络特性的基础上提出了DC-DTM算法.该算法首先建立微博网络的RT (reply and forward post)模型, 将微博网络映射为以博主为节点, 以博主之间的关注关系为边, 将博文主题之间相似度作为边权重的有向加权网络, 其中, 博文主题之间的相似度是通过本文所提出的概率模型DTM对微博网络中各节点的主题进行挖掘, 将不同作者微博的KL距离作为其兴趣相似度, 即连边的权重.利用该模型挖掘出每个主题中各节点的影响力, 将影响力最高的节点作为之后标签传播算法的初始节点, 通过标签传播算法WLPA, 对微博网络进行社区发现.

2.1 微博网络RT模型

本文首先对微博网络进行抽象建模, 由于微博网络中的关注关系具有方向性, 并且不同用户之间的联系紧密程度不同, 本文将微博网络抽象为有向加权网络.网络中的节点为微博中的用户, 如果用户A关注用户B, 则存在一条边E_AB由用户A指向用户B.将用户之间的兴趣相似度作为边的权重.通过对微博网络的研究发现, 在微博网络中, 以下因素能够阐释用户的兴趣特征.

(1) 发表博文内容

用户只发布自己感兴趣的内容, 所以用户以往发布的博文能够直接表征用户的兴趣.

(2) 转发和评论博文的内容

用户在阅读其他用户发布的博文之后, 如果对该博文感兴趣, 一般会对其进行转发或评论, 这种转发或评论的行为也能够映射出作者的兴趣点.本文中将转发和评论行为归为一类, 统称为关注.

(3) 用户的标签

用户标签是用户在完善个人资料时指定的一组描述用户兴趣、爱好的关键字, 是表征用户兴趣、爱好的一种手段.但用户的兴趣会随时间的推移变化, 并且用户一般不会经常更改自己的标签, 标签信息对本文研究贡献度较低, 本文中不考虑此类内容.

综上所述, 本文中将用户的发布或转发/评论的博文内容作为其兴趣特征.利用主题模型对用户的博文内容进行主题挖掘, 将作者关注主题之间的相似度作为作者联系的权重.

本文所建立的微博RT模型如图 1所示.在图 1中, 有两个用户发布的两个博文, 其中用户B发布4号博文, 用户C发布2号博文, 而用户A的1号博文关注了用户B的4号博文, 用户A的5号博文关注了用户C的2号博文, 用户C的3号博文关注了用户B的4号博文.由博文之间的关注关系得到用户之间的关联关系, 用户A关注用户B和C, 用户C关注用户B.其中, 用户之间的关系为有向边, 边的权重为用户兴趣的相似度.例如, E_AB边的权重为用户A所发博文1和博文5与用户B所发博文4之间的相似度.在此模型中, 用户博文的相似度通过博文之间的主题相似度KL距离表征.

至此, 在RT模型中, 微博网络用图模型G=(V, E)表示, 其中, V表示在微博网络中所有节点的集合, 每个节点都有内容集合M_i, 表示用户i所发布的所有博文(包括转发博文、评论博文), E表示在节点之间有转发关系的边的集合.

2.2 模型介绍 2.2.1 DTM模型

针对现有模型的不足, 尤其是微博网络的稀疏性问题, 在综合考虑微博的时间信息、主题信息、微博的标签以及作者的兴趣等问题的基础上, 本文提出了适用于微博网络的主题模型, 对博主的博文进行主题提取.DTM模型是在LDA的基础上, 针对微博类网络结构中潜在的作者联系信息, 集成主题挖掘、作者兴趣度挖掘以及计算作者与主题相关性等功能.模型在挖掘微博主题的同时, 可以挖掘出作者的兴趣分布以及作者与特定主题的相关系数, 这正是DC-DTM算法中标签传播的依据.

2.2.2 定义及符号说明

在微博文本挖掘的研究中, 如果采用标准的LDA模型, 如图 2所示, 通常会由于短文本造成高维系数, 导致文本中词之间的相关性不易挖掘, 因此, 本文首先抽取了一定量的博文进行研究, 发现博文通常存在3种产生途径, 表现在消息发布方式上就是:原创博文、转发博文以及具有评论性质的博文.原创博文是微博用户发布的原创信息, 内容大多是微博用户感兴趣的主题, 例如, 一个篮球迷可能会发一条这样的博文“科比要退役了, 好遗憾!”, 而转发博文相对比较特殊, 它的内容往往比较简单, 在新浪微博中, 通过“//@”把转发部分与原创部分相互隔开, 而在Twitter中是使用RT标识一篇博文为转发博文, 而转发博文的内容往往是被转发博文的链接等.对于对话形式的博文, 使用@标识被评论微博的用户, 而评论内容相对博文更简单, 例如, 对上述博文的评论内容可能会是“是呀”.而无论是转发博文还是评论形式的博文, 其主题与原博文都具有很强的相关性.如果单独看评论形式的博文, 博文中的词语对博文的主题贡献度很小, 并且评论形式的博文内容较少, 有些只是表明博主的态度等, 无法单独从这些博文中进行主题挖掘.而如果将转发或评论形式的博文与原博文连接到一起, 就能对转发博文进行主题挖掘, 例如上述的评论内容与原博文联系在一起, 通过主题挖掘可以发现该评论是关于科比退役这件事情的评论.

上述分析是从博文的内容进行分析, 从信息传播层面上, 微博中信息的传播主要是通过博主之间相互转发或评论等途径进行.某一博主之所以转发或评论其他博主的博文, 是因为对博文的主题或观点感兴趣(这里所指的感兴趣, 包括反对或支持等态度), 这种对其他微博转发或评论的行为也是博主兴趣点的体现.

根据以上分析, 给出如下定义.

定义1(博文). 博主发表的博文, 在此包括评论博文与转发博文.如果是评论博文, 则将评论博文与被评论博文内容整合在一起, 如果是转发博文, 并且转发博文的表现形式是链接或其他非原博文形式, 则将转发内容与被转发的博文结合在一起.

定义2(用户图). 用户图GT=(U, E).其中, U为博文集合中所有作者的集合, 形成用户图GT的节点; E为博文集合中作者之间形成的共现关系, 形成用户图GT的边.

此处的用户图即为RT模型得到的图模型, 即如果用户u_x的博文评论(或转发)了用户u_y的博文, 那么在用户图中, 节点u_x和节点u_y将有一条有向边E_xy相连, 从用户u_x指向用户u_y.

定义3(关注关系). 如果微博b₁评论或转发了微博b₂, 那么称b₁关注b₂, 同时, 微博b₁的作者a₁也关注微博b₂的作者a₂.

定义4. 用户a的被关注概率, 是指在某个特定的主题T中, 在所有与主题T相关的被关注用户中, 用户a占所有被关注用户的百分比.

例如, 与主题T相关的关注微博共1万条, 由于一个用户可能存在多个关于主题T的博文被关注, 假设用户a有100条与主题T相关的博文被关注, 那么用户a被关注的概率为100/10000, 也就是说, 用户在主题T中被关注的概率为0.01.

DTM模型所使用的符号见表 1.

2.2.3 DTM模型

DTM模型是一种基于主题模型的概率生成模型, 模型图如图 3所示.该模型在进行文档主题建模的同时, 也进行用户兴趣建模.同时, 根据微博所对应的被关注用户概率分布生成微博的被关注者, 因此, 模型也能对特定主题中的用户被关注情况进行建模.用户的兴趣建模成为计算用户兴趣相似度的基础, 用户被关注情况建模成为本文后续的标签传播算法中, 标签传播的依据.模型的基本思想是:将每个作者的所有发布、转发或评论的博文都作为文档, 每个文档可以表示为词--文档矩阵, 在词汇层次中, 每个文档都可以表示成一系列主题的混合分布, 记为P(z); 同时, 每个主题是词汇表中所有单词上的概率分布, 记为P(w|z); 在作者层次中, 每个文档可以看做是词--作者矩阵, 同时, 由于在本模型中, 作者也具有语义信息, 某个作者代表了其所感兴趣的主题, 因此每个主题又是作者集合中所有作者上的概率分布, 记为P(u|z).

DTM模型将所有微博作为语料库, 计算用户的兴趣分布; 将转发微博提取出来, 计算某一主题下用户的影响力.

DTM模型生成文本方式可以用图 3所示的贝叶斯网络图来表示.首先, 某个文档以一定的概率选择某些主题, 这些主题又以一定的概率选择词语和用户.主题是基于词语w的概率分布, 也是基于用户a的概率分布.最初, DTM从参数为β的狄利克雷(Dirichlet)分布中抽取主题与单词的关系ϕ; 从参数为γ的Dirichlet分布中抽取主题与用户之间的关系ϕ.DTM生成一条微博时, 首先判断微博类型, 如果是关注微博, 则从参数为α_r的Dirichlet分布中抽样出该文档与各主题之间的关系θ_r; 否则, 从参数为α_s的Dirichlet分布中抽样出该文档与各主题之间的关系θ_s.然后, 判断文本之间的关系.如果微博为关注微博, 则从参数为θ_dr的多项式分布中抽样出当前单词所属的主题z_dr, 从参数为ϕ_zdm的多项式分布中抽取出具体单词.如果是原创微博, 则从参数为θ_ds的多项式分布中抽样出当前单词所属的主题z_ds, 最后从参数为ϕ_zdsn多项式分布中抽取具体单词.

一条微博中, 所有单词与所属主题的联合概率分布如式(2)所示.

$ P\left( {w,z|\alpha ,\beta } \right) = P\left( {w|z,\beta } \right)P\left( {z|\alpha } \right) $

(2)

同理, 一个文档中所有用户与其所属主题的联合概率分布如式(3)所示.

$ P\left( {a,z|\alpha ,{\gamma _{}}} \right) = P\left( {a|z,\gamma } \right)P\left( {z|\alpha } \right) $

(3)

其中, 变量w, z, α, β, γ根据博客的类型进行选择, 如果是原创微博, 则选择与原创微博相关的参数; 如果是转发微博, 则选择转发微博相关变量.上述过程最终得到用户兴趣的主题分布矩阵.

为了对某一主题下用户的影响力建模, 该模型将所有转发微博提取出来, 对于与主题T相关的转发微博d_r, 用户u生成主题多项式分布θ_r, θ_r服从以α为参数的狄利克雷分布.对于用户u的每条关注微博d_r∈D_r, 根据θ_r为这条关注微博d_r选取主题Z_udr, 根据主题Z_udr所对应的词分布多项式分布参数ϕ_k可生成微博d_u中的词语w_dun, 根据主题Z_ud所对应的被关注用户多项式分布参数φ_r可生成微博d_r的被转发用户a_udr, 因此DTM模型可同时建模微博主题词的概率分布以及主题的用户被转发概率分布.

假设整个转发微博集合中共有|K|个主题, DTM模型生成过程如下.

Step 1. 对于每个主题k∈K, 选取Φ_r~dir(β_r), Φ_s~dir(b_s), φ_r~dir(γ_r), φ_s~dir(γ_s).

Step 2. 将用户集合按照所发博文类型分为发布博文的用户U_s和关注他人博文的用户U_r.

Step 3. 对于原创博文用户u, 用户集合U_s中的每个用户u∈U_s选取θ_s~Dir(α_s).

对于被关注的用户a_uds, 选取a_uds~Multinomial(φ_s).

对于用户u的每条原创博文d∈D, 选择主题Z_ds~Multinomial(θ_s), 其中Z_ds对应主题集合K中的主题k.

对于微博d中的第N_ud个单词w_ud, 选取w_ud~Multinomial(Φ_s).

Step 4. 对于关注的博文用户u_r, 用户集合U_r中的每个用户u_r, 选取θ_r~Dir(α_r).

对于被关注的用户a_ud, 选取a_ud~Multinomial(φ_r).

对于用户u_r的每条关注博文d_r∈D_r, 选取主题Z_dr~Multinomial(θ_r), 主题Z_dr对应主题集合K中的主题k_r.

对于微博d_r中的第N_udr个单词w_udr, 选取w_udr~Multinomial(Φ_r).

2.2.4 模型参数估计

DTM模型的推导采用Gibbs Sampling的采样算法, 计算模型参数α_s, α_r, β_s, β_r, γ_r和γ_s.词与主题以及作者与主题的联合分布公式如式(4)、式(5)所示.

$ P\left( {\theta ,w,z\left| {\alpha ,\beta } \right.} \right) = p(\theta |\alpha )\prod\limits_{n = 1}^N {p({z_n}|\theta )p({w_n}|{z_n},\beta )} $

(4)

$ P\left( {\theta ,a,z\left| {\alpha ,\gamma } \right.} \right) = p(\theta |\alpha )\prod\limits_{n = 1}^N {p({z_n}|\theta )p({a_n}|{z_n},\gamma )} $

(5)

其中, α, β, γ, θ根据微博是原创还是关注微博, 取相应的参数.采用Gibbs Sapling采样算法来近似推导DTM的参数, 得到式(6)、式(7).

$ P({z_i} = j|w,{z_{ - i}},\alpha ,\beta ) = \frac{{P(z,w|\alpha ,\beta )}}{{P({z_{ - i}},w|\alpha ,\beta )}} \propto \frac{{{n_{j,w}} + \beta - 1}}{{{n_{j, \cdot }} + V\beta - 1}} \times \frac{{{n_{d,j}} + \alpha - 1}}{{{n_{d, \cdot }} + T\alpha - 1}} $

(6)

同理,

$ P({z_i} = j|{a_i},{z_{ - i}},\alpha ,\gamma ) \propto \frac{{f_{ - i,j}^{({a_i})} + \gamma }}{{f_{ - i,j}^{( \cdot )} + |a|\gamma }}\frac{{f_{ - i,j}^{({d_i})} + \alpha }}{{f_{ - i, \cdot }^{({d_i})} + T\alpha }} $

(7)

其中, n_{j, w}表示单词w属于主题j的个数, n_j,·表示属于主题j的单词总数; n_{d, j}表示文档d属于主题j的词数, n_d,·表示文档d所有被分配主题的词数; $f_{ - i,j}^{({a_i})}$表示除当前样本外, 作者a_i对主题j感兴趣的次数, $f_{ - i,j}^{( \cdot )}$表示除当前样本外, 对j感兴趣的作者总数; $f_{ - i,j}^{({d_i})}$文档d_i中关注主题j的作者个数, $f_{ - i, \cdot }^{({d_i})}$表示文档d_i中的作者总数; |a|表示作者总数目, T表示话题总数.

模型最后将某一作者的转发微博的主题分布与原创微博的主题分布进行加和归一, 即为作者的主题概率分布.

2.3 节点的微博主题相似度及作者影响力计算

通过第2.2节得到的主题--用户分布矩阵, u₁与u₂之间的相似度可以通过计算其主题分布p_u1和p_u2相似度进行计算, 分布的相似度可以有许多计算方式.KL散度^[30]是衡量不同分布p和q之间相异度的主要指标, 如式(8)所示.

$ KL{\rm{(}}p{\rm{,}}q{\rm{) = }}\sum\limits_{j = 1}^T {{p_j}lo{g_2}\frac{{{p_j}}}{{{q_j}}}} $

(8)

为了体现作者之间的相似度越高, 作者之间的连边权重越大, 本文使用D(p, q)计算作者之间的相似度, 如式(9)所示.

$ D(p,q) = 1 - \sum\limits_{j = 1}^T {{p_j}lo{g_2}\frac{{{p_j}}}{{{q_j}}}} $

(9)

其中, 如果p_j与q_j相等, 则KL(p, q)=0, D(p, q)=1.

在DTM模型中, 得到每个特定主题T下, 作者被关注的概率分布φ_r.φ_ra表示a在主题T中的被关注概率, 即为用户a在主题T中的影响力.将用户在某一主题中的影响力按照从大到小排序, 此顺序即为之后的标签传播算法WLPA中标签传播的顺序.

2.4 基于标签传播的社区发现算法WLPA

针对RT模型, 在利用DTM模型的进行微博主题挖掘并计算出博主之间的兴趣相似度之后, 本文提出基于有向加权网络的标签传播算法WLPA进行挖掘.挖掘过程分为4个阶段.

(1) 初始化阶段, 网络中所有节点的最大标签数即为DTM模型中挖掘出的主题个数k, 也就是每个节点所隶属的最大社区个数.用P_i表示节点i的标签矩阵, p_ij表示节点i属于第j个社区的概率, 即DTM中用户--主题概率分布, 即用户对不同主题感兴趣的程度.

(2) 在标签传播阶段, 标签更新过程中, 按照某一主题中用户的影响力排序进行更新, 标签传播过程是一个迭代的过程, 假设在第s次迭代过程中, 对于网络中的某一节点, 考虑所有指向节点的边, 假设节点i有h个邻接节点, 每条链路的权重为w_t, t∈{1, 2, …, h}, 该节点的标签更新矩阵计算如式(10)所示.然后对p_ij归一化处理, 最后删除p_ij < 1/k的标签.每次迭代, 根据节点的更新顺序重新计算各节点的标签分布.

$ {p_{ij}} = \sum\limits_{t = 1}^h {\left( {\frac{{{w_t}}}{{\sum\limits_{t = 1}^h {{w_t}} }} \times {p_{tj}}} \right)} $

(10)

(3) 经过迭代计算后, 网络中各个节点的标签不再变化, 达到稳定状态, 迭代结束.

(4) 最后, 根据每个节点的标签分布向量C_i将具有相同标签的节点划为同一社区.在所得到的社区中删除重复节点个数多的社区, 最后得到重叠社区结构, 其中某些节点拥有多个标签, 这些节点即为重叠节点.

算法1. WLPA算法描述.

输入:加权有向网络G(V, E), 参数k, 网络总节点数n.

输出:重叠社区C_ov.

    For $v \in V$ do

        Initialize P_v

    End for

    t=0    //迭代次数

    while (!converged()) do

        sort(v)    //对节点按照影响力排序

        t=t+1

        for $v \in V$ do

            for $j \in k$ do

                calculate p_ij

                if max (p_ij) > 1/k

                    p_ij=max (p_ij)

                else if p_ij < 1/k

                    p_ij=0

                end if

                normalize(p_ij)

            end for

        end for

    end while

    C=postProcessing()    //后续处理

    Return C

其中, 函数converged()用于判断迭代是否收敛.本算法中, 如果具有相同标签的节点个数不再变化, 则认为算法收敛, converged()返回值为真, 算法迭代结束.函数postProcessing()用于进行算法的后续处理, 即将具有相同标签的节点归为一个社区.

2.5 算法复杂度分析

关于本算法的复杂度分析:假设网络有|V|个节点、|E|条边、节点归属的最大社区数C、主题个数K以及文档中词的总数N.

(1) DTM模型的算法复杂度与LDA模型的算法复杂度都与主题个数以及文档中词的总数有关, 单次迭代的复杂度为O(K×N).

(2) 标签传播算法复杂度:第1步初始化标签分布矩阵复杂度为O(C×|V|); 第2步获取节点的影响力以及节点之间的相似程度的复杂度:为了降低算法复杂度, 本文只计算单向的相似度, 如在主题T中, 作者a的关注度大于作者b的关注度, 则只计算KL(a, b)而不计算KL(b, a), 因此, 此步骤的复杂度为O(C²×|V|); 第3步, 整个传播过程复杂度$O\left( {C \cdot \left| E \right| \cdot \log \left( {\frac{{C \cdot \left| V \right|}}{{\left| E \right|}}} \right)} \right);$第4步, 划分社区需要O(C×(|E|+|V|)).由于与|V|相比, C取值很小, 又由于微博网络为大型稀疏网络, |E|的取值相对于|V|也很小, 因此, WLPA算法的总时间复杂度为O(|V|×log|V|).

DC-DTM算法复杂度为O(K×N+|V|×log|V|), 算法复杂度具有线性特征, 在真实网络的实验中能够快速收敛.

3 实验及结果分析 3.1 实验准备 3.1.1 数据集

本文采用的数据集来源于新浪微博.该数据集收集了2013年1月~2014年2月之间的948 648条微博内容.首先对该内容进行实验准备:将数据集中转发或评论微博与原微博结合在一起, 而原微博保持不变.本文选取了160 748个联系人的博文作为实验数据.通过数据预处理, 选择出10个主题社区:电影、美食、IT、母婴、文艺漫画、电视台主持人、经济、休闲、健身、官方微博作为测试集, 其他博文作为模型的训练集.

3.1.2 数据预处理

由于数据集本身包含的原始数据没有用户关系信息, 并且原始的博文包含所有词汇, 不适合直接使用DTM模型进行分析.在分析之前, 从具有@关系或//@关系的博文中抽取用户之间的关系形成用户图.对中文语料进行分词, 利用中国科学院的分词工具对微博数据进行去停用词、清洗数据以及中文分词等操作.

3.1.3 参数设置

困惑度(perplexity)^[1]是一种信息理论的测量方法, 是主题模型评价的常用方法.某一个概率模型的perplexity值定义为基于该概率的熵的能量, 表示预测数据的不确定性.模型的perplexity值越小, 表示主题建模的效果越好, 模型的推广性越高.

Blei的论文里列出了LDA语言模型的perplexity的计算公式, 如式(11)所示.

$ perplexity(D) = exp\left\{ { - \frac{{\sum\limits_m {\ln p\left( {{d_m}} \right)} }}{{\sum\limits_m {{N_m}} }}} \right\} $

(11)

其中, D为测试集, d_m为每个测试文档, N_m为第m篇文档的大小(即单词个数).

由于模型的性能与参数有关, 首先对模型参数进行实验, 将6个超参取值为[0.1, 0.9]之间进行组合, 分别观察不同情况下, 模型的困惑度.经过多次实验, 结果表明, 当α_r=α_s=0.5时模型困惑度较小, 在此情况下进一步实验, 实验数据见表 2.实验结果表明, 当α_r=α_s=0.5, β_r=β_s=0.3, γ_r=γ_s=0.2时, 模型困惑度最小.接着在上述参数设定的情况下, 通过改变主题个数对模型进行实验, 实验结果如图 4所示, 当T=8时, 模型的困惑度达到最低值, 也就是说, 主题划分最合理.通过对实验数据的分析发现, 将健身主题与休闲主题看作同一个主题分类, 将文艺漫画与电影划分为一类, 因此, 原来的10类微博数据被分为8类.通过迭代次数的实验, 如图 5所示, 当迭代次数为800时, 模型收敛, 模型的困惑度趋于常量, 因此, 在后续实验中, 模型中的采样迭代次数为800次.

3.2 模型分析 3.2.1 模型的困惑度

在上述参数情况下, 对比DTM, LDA以及MB-LDA (microblog-latent Dirichlet allocation)模型^[24]的内容困惑度发现, 在相同参数设置的情况下, DTM所挖掘出的主题模型的内容困惑度较低, 如图 6所示.

3.2.2 发现主题的质量

DTM共挖掘出了8个主题, 表 3中展示了8个主题.根据各个主题对应的关键词值, 分别选择其中6个最主要的, 从这6个词中可以发现, 主题1与休闲相关, 主题2与母婴相关, 主题3与IT相关, 主题4与娱乐相关, 主题5与经济相关, 主题6与美食相关, 主题7与官方微博相关, 主题8是电视台主持人的微博.DTM挖掘出的主题基本与我们预先了解到的语料库的主题类似.

3.2.3 作者兴趣相似度度量

本文中作者兴趣相似度计算方法如式(8)所示.随机选择10个作者, 其兴趣相似度如图 7所示.图中颜色越浅, 表示作者的相似度越高; 对角线上为作者自身的相似度, 当值为1时, 颜色最浅.从图 7中可以看出, 1号作者与3号、5号、8号、9号作者之间的相似度较高, 而10号作者与2号、4号作者的相似度较低.

作者兴趣的相似度可以进一步作为社区发现的基础, 通过对比作者之间兴趣的相似度进行作者的社区发现, 是一种可调节社区大小, 具有层次的重叠社区发现.

3.3 社区发现算法比较

将本文算法与经典的COPRA算法进行比较, 由于COPRA算法解决的是无权网络的社区发现, 在此通过将COPRA扩充, 将其改变为适用于有向加权网络的WCOPRA算法.实验选取模型困惑度最小时的社区数目, 本数据中, 该社区数目为之前实验得到的主题个数, 此时模型的拟合程度最好.

3.3.1 加权有向网络社区模块度

传统的社会网络的重叠社区的评价标准, 是通过文献[31]所建立的重叠社区的模块度标准进行评价, 其公式如式(12)所示.

$ EQ = \frac{1}{R}\sum\limits_{t = 1}^{\left| C \right|} {\sum\limits_{i \in {C_t},j \in {C_t}} {\frac{1}{{{O_i}{O_j}}}\left( {{A_{i,j}} - \frac{{{D_i}{D_j}}}{R}} \right)} } $

(12)

其中, D_i为节点d_i的度数, R为网络节点的总度数, A为网络邻居矩阵, O_i为节点d_i所隶属的社区个数.微博网络的社区需要以用户关注关系和用户博文的语义信息作为基础, 考虑用户关注关系的有向性, 其评价标准WQ定义如式(13)所示.

$ WQ = \frac{1}{R}\sum\limits_{t = 1}^{\left| C \right|} {\sum\limits_{i \in {C_t},j \in {C_t}} {\frac{{S({b_i},{b_j})}}{{{O_i}{O_j}}}\left( {{A_{i,j}} - \frac{{{D_{io}}{D_{jo}}}}{R}} \right)} } $

(13)

其中, s(b_i, b_j)表示用户i与用户j的兴趣相似度.用户i与用户j之间的兴趣相似度为两个用户的博文的相似度, 由于用户博文随时间增长, 并且用户的兴趣也会受到一些实事时间的影响, 因此将用户最近一年的博文的相似度作为用户的相似度度量.D_io为节点i的出度.

首先通过对比算法的模块度进行实验, 表 4为实验结果.结果表明, 本文所提出的算法的模块度WQ值相对较小.从实验结果可以发现, 在使用EQ作为评价指标时, 由于只考虑微博网络的拓扑结构, 并未考虑节点之间的关系, 以此为标准作为评价, 本文所提出的DC-DTM模型表现并不优越, 但是COPRA与WCOPRA两种算法的EQ值相似, 因为在此WCOPRA退化为COPRA, 但当模型的评价指标融入社区节点之间的相似性以及节点之间的关注关系后, DC-DTM算法比传统的COPRA算法以及WCOPRA算法都显示出较优的性能.

3.3.2 划分紧密度指标

文献[32]提出了划分紧密度(partition density)D指标, 能够有效地衡量重叠社区的划分效果.该指标用来衡量无权无向图的划分.

假设一个无向无权网络含有M条边, 该网络划分为{C₁, C₂, …, C_t}个社区, 则第i个社区的紧密度D_i如式(14)所示.

$ {D_i} = \frac{{{m_i} - ({n_i} - 1)}}{{{n_i}({n_i} - 2)/2 - ({n_i} - 1)}} $

(14)

其中, m_i, n_i分别表示第i个社区的边数和节点数, 当n_i=2时, D_i的值为0.划分紧密度D为所有社区划分紧密度的加权平均, 每个社区的权值为社区内的边数与整个网络边数的商, 整个网络的划分紧密度如式(15)所示.

$ D = \frac{2}{M}\sum\limits_i {{m_i}\frac{{{m_i} - ({n_i} - 1)}}{{{n_i}({n_i} - 2)/2 - ({n_i} - 1)}}} $

(15)

为了对本文的有向加权网络进行评估, 将上述划分紧密度进行改进, 得到有向加权网络的划分紧密度指标WDD, 如式(16)所示.

$ WDD = \frac{2}{W}\sum\limits_{i = 1}^t {{w_i}} \frac{{{w_i} - ({n_i} - 1)}}{{{n_i}({n_i} - 2)/2 - ({n_i} - 1)}} $

(16)

其中, w_i为社区中所有节点输出边的权重之和, n_i为属于第i个社区的节点数.由于COPRA未考虑边权重, 在此不做比较.从表 4可以看出, DC-DTM算法的划分密度较高.

3.3.3 作者兴趣相似度比较

图 8为对同一社区内不同作者兴趣相似性的度量.随机选择其中1个社区内的用户的兴趣相似度矩阵图, 颜色越浅, 说明作者兴趣度越相似.从图 8中可以看出, 同一社区内作者兴趣基本相似.图 9为随机选择不同社区内的作者之间的相似度矩阵图, 图中颜色越深, 说明作者的兴趣相似度越低.从图 9中可以看出, 作者兴趣基本不同.但是, 9号作者与2号、3号作者的相似度较高, 说明他们可能是重叠节点.从图中可以发现, 同一社区的作者兴趣相似度较高.不同社区作者的兴趣相似度相对较低.

4 结束语

本文针对微博网络的社区划分问题提出了DC-DTM算法.在标准的LDA模型中, 主题由文本本身确定, 不适合短文本分析, 文中所提出的DTM模型引入了作者的主题分布和对转发微博的处理, 能够弥补LDA模型带来的缺陷.在DTM模型中, 一篇微博如果是原创微博, 则其主题由作者的主题分布中抽取; 如果是关注微博, 则由原创与关注部分的主题来确定.实验分析验证了本文所提出的DTM模型更适合挖掘微博的主题, 所提出的DC-DTM算法所划分出的社区的模块度较高, 社区内作者的兴趣相似度较高, 社区之间的作者相似度较低.另外, DC-DTM算法可为下一步深入研究微博网络的情感分析, 大规模社会网络的推荐等研究领域提供帮助.