融合主题相似度权重的主题社区发现模型

钱芸芸，杨文忠，姚 苗，李海磊，柴亚闯

1.新疆大学 信息科学与工程学院，乌鲁木齐830046

2.新疆大学 软件学院，乌鲁木齐830046

现今社会存在许多复杂网络，如社交网络、科技文献合著网络等，都具有明显的社区结构。在社区中人们进行资源共享、兴趣互动以及信息传播，带来数据爆炸式增长，给在复杂网络中挖掘有效信息并针对特定群体应用分析的任务带来了巨大的挑战。为此，有许多主题社区的挖掘方法被提出。Kim等[1]提出了在线社区中用户特征的主题建模方法。Henry等[2]使用贝叶斯模型在动态文本网络中进行社区发现和主题建模。Ye等[3]采用标签传播算法发现社区，然后跟踪主题的演化。黄琳凯[4]关联知识图谱挖掘主题社区。Yang等[5]利用关键图和社区划分检测主题。Jin等[6]在含时间信息的网络上结合模张量检测社区。

目前普遍认为良好的社区结构是同一社区节点链接紧密，不同社区节点链接稀疏。基于此，针对主题社区的挖掘，多基于简单的链接关系和文本信息或在已有社区上挖掘主题，前者忽略了社区内节点成员之间的主题相似性，后者分离了主题与社区的概念，因而挖掘的主题社区质量并不高。此外，真实网络中往往不同社区也可能讨论同一主题，只是两个社区间可能链接稀疏或不存在链接关系因而应被划分成同一主题的不同社区。

针对以上存在问题，本文致力于充分利用节点文本语义信息，将其转化为边权重以划分社区，并使用新的主题计算方法从社区层面语义得到潜在的社区主题。由此挖掘的主题社区，在主题提取和社区划分阶段均用到语义信息，并且在不分离两者概念的前提下，保证了主题和社区的紧密性和相关性。

1 相关工作

近年来，主题社区挖掘在国内外均受到广泛关注，主要分为两种方法：一是基于链接关系和文本信息挖掘主题社区，二是在已划分社区基础上挖掘主题。

贺超波等[7]集成链接和属性信息，结合非负矩阵分解模型以获得节点与社区归属关系矩阵、属性与社区关联矩阵，保证了社区成员链接结构的紧密度。实验表明该方法适合用于挖掘复杂网络中的主题社区及重叠社区。何翔等[8]结合链接关系及文本内容挖掘微博中的主题社区，同时创造性地融入了领袖发现、文本分类等链接分析技术。但该模型实验结果的好坏依赖于领域分类器的性能。针对传统社区挖掘注重链接关系而忽略内容信息的不足，徐彬等[9]利用LDA主题模型，通过计算用户间的主题相关性，重新定义用户链接关系，最后进行社区划分。该方法虽然考虑了内容信息，但改变了原有链接关系不符合真实网络。针对传统方法没有考虑用户社会信息的限制，闫光辉等[10]提出了综合链接和主题的社区发现算法。定义了链接和主题相关度，用改进后的标签传播算法对用户分类以划分兴趣相似且联系紧密的社区。郑伟涛等[11]提出一种结合链接关系和用户兴趣分析的社区发现方法。但其认为用户有共同兴趣即使没有链接关系也应被分到同一社区不符合真实网络。王卫平等[12]综合网络结构和节点内容提出基于主题相似性和网络结构的社区发现方法。该方法挖掘的社区内节点相似度高，社区间相似度低，但真实网络中不同社区可能讨论相同话题。

由于CPM（Clique Percolation Method）算法对社区定义过于严格，得到的社区规模较小，Chen等[13]引入结构相似度和属性相似度对CPM算法得到的社区进行合并解决了社区规模小的问题，但合并过程不符合实际社区的定义。欧卫等[14]基于文档间并不相互独立的假设改进LDA模型使其模拟社交网络中关系的生成过程来挖掘主题社区，实验结果证明了用户兴趣存在级联现象的假设。Zhang等[15]提出了一种集网络结构、文本和时间为一体的动态主题社区检测方法，实现了主题社区随时间变化的演化过程。Yin等[16]将链接和内容信息映射成文本关联图，将社区发现过程变成文本关联图的主题分析过程，保证主题的一致性，分离了社区和主题的概念，但往往社区和主题是相互作用的。Wang等[17]基于Infomap算法划分社区，在已划分社区基础上通过社区中用户tweet信息，利用LDA模型得到用户主题，并用距离来量化单个用户、团体和社区的主题相似性。秦春秀等[18]提出P2P主题社区发现模型，基于给定社区主题及相关本体知识，然后通过衡量P2P中对等节点知识地图的类别概念树与社区主题概念树的内容相似度来识别社区成员。Aktunc等[19]通过修改已知的静态社区检测算法，提出了动态模块度优化框架。Blondel等[20]基于模块度划分社区的方法进行优化试图最大化模块度以得到最优社区划分，Louvain算法是其具体实现。

以上方法部分弥补了传统社区发现方法中单一考虑链接结构的不足，但都只是把语义信息用在提取主题上，再进行社区划分，因此得到的主题社区结果不理想。目前方法还不能够将主题挖掘和社区划分二者紧密结合，针对以上不足，本文提出一种融合主题相似度权重的主题社区发现模型。不仅将语义信息用在社区划分上，还将其用在计算社区潜在主题上。主要将语义信息转化为链接权重以影响社区划分结果，根据划分结果，再综合社区内节点语义计算得到潜在主题。

2 相关技术

2.1 LDA

LDA（Latent Dirichlet Allocation）[21]是一种主题生成模型，被用来识别文档集或语料库中潜在的主题。LDA主要任务是识别主题，即把文档-词汇矩阵变成文档-主题矩阵（分布）和主题-词汇矩阵（分布）。

文档集合D中的每个文档d都可以看做一个单词序列，词与词之间无先后顺序。此外，一篇文档可以包含多个主题，文档中每个词都由其中一个主题生成。LDA找到文档的主题分布以及主题的词分布，将文档的主题以概率分布的形式给出。

2.2 主题相似度

常用于相似性度量的函数有欧氏距离、曼哈顿距离、切比雪夫距离、夹角余弦距离等，但这些距离函数都要求样本属性对称，不便于度量非对称二元属性的样本集合相似度。Jaccard系数[22]统计两个样本包含的共同特征个数，主要应用于计算文本相似度，如式（1）所示，被定义为两个集合的交集大小与两个集合并集大小的比值，取值在[0，1]之间。

Jaccard系数越大，表示样本的相似度越高。与Jaccard系数相反的度量函数即为Jaccard距离。Jaccard距离用于描述集合间的不相似程度，Jaccard距离越大，样本相似度越低。

2.3 模块度

模块度（Modularity）[23]也被称为模块化度量值，常被用来衡量网络社区结构强度，最早由Newman提出。当网络为无向无权图时，模块度定义如下：

其中，m表示网络中边的总数，∑表示遍历所有的顶点i和j，Aij代表网络中节点i和j的边数，ki和kj分别表示网络中节点i和节点j的度数，Ci表示节点i所属的社区，当节点i和节点j属于同一个社区时，δ函数值为1，否则为0。当网络为无向带权图时，模块度函数定义如下：

式（3）与式（2）的区别有三，一是W代替了m，这里W是整个网络所有边的权值之和。二是Wij代替了Aij，这里Wij表示节点i与j之间的边权值，可以取任何表示边权值的非负值。第三是sisj代替了公式（2）中的kikj，si和sj分别表示链接到顶点i和顶点j的边的权值之和。

模块度的取值取决于网络中节点的社区分配，即整个网络社区的划分情况，模块度值一般用来衡量社区的划分质量，值越接近1，表示划分出的社区结构强度越强，划分质量越好，因此，可以通过最大化模块度得到最优的社区划分。

3 融合主题相似度权重的主题社区发现模型（TSWTCD）

3.1 模型框架

融合主题相似度权重的主题社区发现模型核心任务是从包含直接链接关系以及文本内容的网络中提取节点主题，计算节点间主题相似度并转化为权重，然后在包含主题相似度语义的带权图上利用模块度划分社区，最后根据本文提出的社区主题计算方法得到社区潜在主题。图1为TSWTCD模型框架，主要分为三部分：数据处理模块、主题相似度权重生成模块、社区主题生成模块。

图1 TSWTCD模型框架

3.1.1 数据处理模块

数据处理模块的主要任务是对数据集进行预处理。首先根据正则表达式匹配节点标识信息，如姓名。然后正则表达式匹配节点标识得到每个节点对应的文本内容。最后根据关注信息或引用信息或评论信息得到每个节点的直接链接关系。为简化模型，在处理链接关系时对其去重得到网络中的无向边。

在对数据集进行预处理以后得到节点标识、节点文本内容以及直接链接关系等信息。文本内容为下一步提取节点主题做准备，链接关系构成初始网络结构，这时的网络是一个整体，还不具有社区特征。

3.1.2 主题相似度权重生成模块

主题相似度权重生成模块的主要任务是提取节点的主题生成主题词袋，由节点主题和词袋得到主题特征集合以计算节点间主题相似度权重。首先利用LDA模型基于节点文本内容提取节点主题Ti(t1,t2,…,ts)，综合所有节点的主题并去重，然后给每个主题赋予唯一标识得到主题词袋TW{t1:1,t2:2,…,tm:m}，每个编号代表唯一的一个主题。然后综合节点主题和主题词袋得到可以代表节点主题的特征集合Mu(1,2,…,m)，每个编号代表一个主题，编号按升序排序。最后采用Jaccard系数计算节点间主题相似度值作为链接权重Weightuv，取值在（0，1]之间，如公式（4）：

其中，Mi表示第i个节点的主题特征集合。Jaccard(Mu,Mv)表示节点u和节点v的主题相似度，衡量两个节点对相同话题感兴趣的程度，值越大表示感兴趣的话题越相似。遍历网络中的每条边，通过以上计算得出所有边的权值。

3.1.3 社区主题生成模块

社区主题生成模块的主要任务是划分社区并生成每个社区的主题。首先利用带权模块度函数对网络进行社区划分，然后根据提出的社区主题计算方法计算每个社区对各主题的相似度，其值表示社区为该主题的可能性大小，具体计算方法如公式（5），最后取最大值对应的主题作为该社区的主题（公式（6）），对所有社区做以上计算，最终得出每个社区的社区主题。

其中，CTSij为第i个社区的主题是tj的可能性，i表示社区编号，j表示主题编号。Ci表示第i个社区，Jaccard(Mn,Mj)为社区中第n个节点的主题和主题词袋中第j个主题的相似度。CTi为第i个社区的主题，选择使CTSij达到最大值的j对应的主题。

4 实验

4.1 实验数据集

为验证在不同情况下TSWTCD模型的有效性，本文实验数据集选取链接结构紧密的DBLP文献合作网络（https://dblp.uni-trier.de/）以及链接结构稀疏的Cora引文网络（https://linqs-data.soe.ucsc.edu/public/lbc/cora.tgz）。

（1）DBLP数据集

实验筛选了从2015年至今在几个领域上发表的一些学术论文。这几个领域包括CN（计算机网络）、AI&PR（人工智能与模式识别）、N&IS（网络与信息安全）、SE（软件工程）、DB（数据库）。

在DBLP数据集中，作者作为网络中的节点，作者间的合著关系作为边，若作者A与B存在合著关系，相应地在A与B之间生成一条无向边，作者发表的文章标题作为节点的文本内容。数据集中包含1 873个节点，7 474条边。

（2）Cora数据集

Cora数据集为机器学习类的引文网络，由基于案例、遗传算法、神经网络、概率方法、强化学习、规则学习、理论7类论文组成。每篇论文都有唯一的编号，作为网络中的节点，论文之间的引用关系作为网络中的边，若论文A引用了论文B，则A与B之间生成一条无向边。Cora引文网络中共有2 708个节点，5 429条边。

4.2 评价指标

本文引用社区Density（链接密度）以及社区Entropy（信息熵）[24]综合度量主题社区的质量，两者分别定义如下：

其中，k为社区编号，m为主题编号，vi表示节点i，cj表示第j个社区，E为边集合，V为节点集合。entropy(ai,cj)=-pijlbpij，pij为社区j中节点具有主题ai的比例。Density代表一个社区内节点链接的紧密程度，Entropy代表一个社区内节点主题的不一致性。前者度量社区质量，后者衡量主题质量，因此Density值越大，Entropy值越小说明主题社区质量越好。

4.3 实验结果

4.3.1 TSWTCD模型节点主题

在DBLP数据集上进行实验，经过多次实验比较确定将主题个数m定为5最合适，此时主题与词相关性较强，LDA主题-词分布结果如表1所示。

表1 主题-词分布

从每个主题下概率最大的几个词进行分析，可以发现LDA提取的主题与词相关性较强。如CN主题下都是计算机网络领域内的一些专用名词，包括缓存、无线、延迟等词汇，还有N&IS主题下的词分布为加密、安全、密钥等都是与信息安全领域相关的。

综合上述主题-词分布的结果生成主题词袋为：TW{CN：1，DB：2，AI&PR：3，N&IS：4，SE：5}。

Cora引文网络为标准分类的数据集，因此主题词袋为：TW{基于案例：1，遗传算法：2，神经网络：3，概率方法：4，强化学习：5，规则学习：6，理论：7}。

4.3.2 TSWTCD模型社区主题

根据节点主题特征集合计算节点间的主题相似度作为边权重，然后利用带权模块度划分社区。基于DBLP网络划分的社区结果如图2（a）所示，共得到23个社区，社区规模有大有小，以不同颜色区分不同社区。Cora网络划分的社区最小规模为1，这是由于链接结构稀疏导致的，这些社区相对于整体的影响是极小的。因此，为便于观察，本文筛选了规模大于15的社区进行分析，基于Cora引文网络的社区划分结果如图2（b）所示，共得到27个社区。

对于划分后的每个社区，采用提出的社区主题计算方法，得到每个社区主题及对应主题相似度值，结果如图3所示。横坐标表示每个社区的主题在主题词袋中对应的标识；纵坐标表示社区主题相似度值，描述社区中节点主题的一致性强度。

从图3（a）可以看出，DBLP网络得到的社区中，主题为CN、SE、AI&PR的社区各有5个；主题为DB、N&IS的社区各有4个。社区对应主题相似度值均大于0.97，说明社区内节点成员主题高度一致。社区在相应主题下的主题相似度值没有达到1是由于DBLP网络中节点的主题不唯一，一部分成员可能对其他主题也感兴趣从而产生对其他主题的相似度。

图2 社区划分图

图3 社区-主题相似度

从图3（b）可以看出，Cora网络得到的社区中，基于案例的社区有3个；主题为遗传算法、规则学习、理论的社区各有2个；主题为神经网络的社区有12个；主题为概率方法的社区有5个，主题为强化学习的社区有1个。社区对应主题相似度值均为1，这是由于Cora网络中每个节点有唯一的主题，因此只要基于语义权重正确划分社区，就不存在信息熵的干扰。

4.4 实验对比分析

本文选取Wang等人论文中采用的Infomap划分社区方法与Blondel提出的Louvain社区发现算法做对比实验并分析结果。前者基于Infomap划分社区，然后在已划分社区基础上提取社区主题。后者试求最大化模块度值以得到最优社区划分。

以下主要从Density-Entropy值、社区-节点主题相关性、社区-节点主题分布三方面做对比分析。

4.4.1 Density-Entropy值

在不同数据集上用不同方法挖掘的主题社区Density-Entropy值如图4所示。

图4 Density-Entropy

从图4（a）可以看出，由于Infomap和Louvain直接根据网络结构划分社区，因此Density值高，但其既未融合语义也未考虑权重，而是在社区基础上单独提取主题，因而Entropy值也高。TSWTCD模型在划分社区时就融合语义并转化为权重，又从社区语义计算得到社区主题，相互作用得到的结果最为理想。

从图4（b）观察到当网络链接稀疏时三种模型的Density值相差不大，但Entropy值相差很多。Louvain划分的主题社区Entropy值甚至超过了13，这说明社区内节点成员的主题一致性非常低，而TSWTCD模型划分的主题社区Entropy值为0，说明社区内节点成员的主题高度一致。

4.4.2 社区-节点主题相关性

每个节点都有其所属社区，但社区的主题与节点成员所感兴趣主题是否真相关是划分社区并确定主题后需要进一步考虑的问题。主题社区中的节点由真相关节点与假相关节点组成，真相关节点是其主题包含社区主题的节点，假相关节点是其主题与社区主题毫不相关却被划分到该社区的节点。因此采用社区与节点成员主题相关性来衡量主题社区质量的优劣，社区中真相关性节点数量越接近社区节点数量，表明该主题社区质量越好。在两个数据集上基于不同方法得到的社区-节点主题相关性如图5、图6所示。图中蓝色线表示主题社区的节点数量，橘色线表示相应社区中与社区主题真相关的节点数量。

图5 基于DBLP的社区-节点主题相关性对比

从图5（a）可以明显看出在DBLP网络上，TSWTCD划分的主题社区中所有节点与其所在社区主题接近完全拟合。而Infomap划分的14个社区中，第2、3社区中有小部分甚至近一半的节点主题与所在社区主题假相关，第4、5、6社区中有极少量节点与所在社区主题是假相关的。Louvain划分的社区中第1个社区有一部分节点与所在社区主题假相关，第2、7社区中也有极少量节点是假相关的。这表示当网络链接结构紧密时本文方法挖掘的主题社区质量优于其他两种方法得到的社区。

图6 基于Cora的社区-节点主题相关性对比

从图6（a）可以看出，在Cora引文网络上，TSWTCD方法划分的主题社区中所有节点成员与其所在社区主题完全拟合。而Infomap得到的结果只有13、14社区完全拟合，第1个社区中的真相关节点不足社区规模的三分之一。Louvain得到的结果只有6、10、23社区完全拟合。这表明当网络链接结构稀疏时，本文方法依然能够很好地划分主题社区，且在节点主题唯一时，效果比较其他两种方法更明显。

4.4.3 社区-节点主题分布

在两个不同数据集上，对于Infomap和Louvain方法所划分的主题社区，各选取假相关节点较多的几个社区，对社区节点成员的主题分布做了进一步分析，结果如图7、图8所示，横坐标表示社区编号及其主题，纵坐标表示社区的节点数量。

图7 DBLP-社区成员主题分布

图8 Cora-社区成员主题分布

图7 （a）可以看到，在链接结构紧密且节点主题不唯一的DBLP网络上，Infomap划分的第2社区中，仅有173个节点与其所在社区主题真相关，还有164个主题为SE的假相关节点；第3个社区中包含55个主题为CN的假相关节点。图7（b）中Louvain划分的第1个社区包含79个主题为SE的假相关节点，第2个社区也存在少量主题为CN和DB的假相关节点。

图8 （a）可以看到，在链接结构稀疏且节点主题唯一的Cora网络上，Infomap方法得到的主题社区并不理想。3个社区中的节点主题混杂且高度不一致，这导致了其Entropy值很高。第1个社区中真相关节点仅有150个，甚至不到其社区规模的三分之一，而假相关节点在其他6个主题都有占比。图8（b）中Louvain方法得到的社区同样如此，第1个社区中真相关节点仅占其社区规模的四分之一，但由于总体社区规模较小，因此其Entropy值没有Infomap高。

另外，将以上假相关节点较多的社区综合其主题社区网络拓扑图分析发现，Infomap和Louvain方法仅适用于社区间界限清晰的情况，即社区内链接紧密社区间链接稀疏或社区间没有链接时划分效果较好，一旦社区间界限模糊链接较密就会被划分到同一社区而不管其主题是否相同。这是由于两种方法都分离了主题和社区的概念，先社区后主题的思想与主题社区概念本身不符，因此挖掘的主题社区质量不高。在结合不同数据集上的实验发现，当节点主题唯一时，Infomap和Louvain方法的弊端表现得更为明显。

本文方法一方面以链接关系为主，另一方面以主题相似度权重为辅，融合语义划分社区，并基于社区中语义提取主题。因此，无论是在网络链接结构稀疏的情况下，还是在链接结构紧密但社区间界限不清晰的情况下TSWTCD都可以得到社区内链接紧密且节点成员主题高度一致的高质量主题社区。

5 总结

网络中潜在的虚拟社区是真实社会人际关系的映射，而隐含的语义信息则代表社区的主题，挖掘主题社区有助于对特定团体兴趣行为进行分析继而做出相应的商业化市场推广。传统挖掘方法未充分利用语义信息，将主题社区任务分割成主题挖掘和社区划分两个子任务从而忽略了两者相互作用关系，因此挖掘结果不理想。本文的主要工作是，针对传统方法的不足，围绕挖掘社区内部联系紧密且成员话题相似度高的主题社区方法给出新的思路。TSWTCD模型基于主题相似度权重，即语义权重划分社区的同时从社区语义层面提出新的社区主题计算方法以达到对主题社区的高质量挖掘。由于现实中的网络错综复杂，很多节点成员具有多个主题且对每个主题偏好程度不同，这会影响节点的社区划分结果，本文方法没有考虑到这一因素。因此在下一阶段的工作中，本文将重点研究融合主题偏好程度的主题社区挖掘问题。