多维社交网络中的社区发现算法研究

朱家磊　马强　邢玲

摘 要：多维社交网络中蕴含着多个维度的信息，若单独选择其中一维进行社区发现显然是不合理的。为解决这个问题，提出一种综合社交关系（包括好友关系、评论关系、推荐转发关系等）和兴趣相似的社区发现方法。首先研究用户的社交行为关系，定义用户社交强弱度，推出用户紧密度公式；然后使用主题模型研究用户博文主题特性，定义主题相似度公式；再推出用户总相关度公式，并用其计算节点间的传递概率，使用Label Propagation算法对用户进行划分；最终划分出综合用户社交联系紧密且兴趣相似的社区，在真实微博上验证该方法的合理性和有效性。

关键词：多维社交网络；微博；社区发现；主题模型；兴趣相似

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2018）03-00-04

0 引 言

新浪微博已经成为国内重要的社交网络，为了对社交网络进行分析[1]，可以将网络画成图，图中的节点表示用户，图中的边表示用户的关系，这种网络中所表现出的结构称为社区结构[2，3]。社区发现可以研究社交网络中的社区结构[4]，而且已发展成为数据挖掘领域中的热点。

在社会媒体中，人们与其他人的联络比以前更方便。通过观察社会媒体上的用户行为，可以看到用户之间存在着多个以不同方式交互的网络。以微博为例，两个用户可以互相关注而建立“朋友”关系，也可以互相“评论”或 “推荐转发”所发的微博，这些不同类型的行为方式会形成一个多维的社交网络。多维网络是指一个网络中的不同节点间有不同的联系方式，每一种联系方式构成一维网络[5]。用户间的以上行为（本文概括为社交关系）就构成了一个三维有向网络（好友关系网络，评论关系网络，推荐转发网络）。同时，基于用户所发的博文、相互之间所讨论的内容以及共同关注的话题，利用LDA主题模型[6]挖掘出共同的兴趣爱好，衍生出第四维网络——兴趣相似网络。在这种多维网络中，若只考虑其中一维而进行社区发现是不准确的，因为仅仅一维很难概括出整个多维网络的信息，前人已提出或总结出一些经典的算法。K-L算法[7]由Kernighan和Lin提出，算法中定义了一个增益函数Q，然后用贪婪算法原理交换节点对，使Q值达到最大，最后划分出两个大小已知的社区，该算法的缺点在于只能划分出两个社区且必须知道这两个社区成员的数量；2002年，Girvan和Newman提出了GN算法[8]，GN算法是通过不断地移除介数最大的边，直到整个网络退化成一个社区为止，该算法的优点在于无需预先知道社区的数目，但其计算复杂度较高；Lei Tang等[9]提出了先将多维网络集成（主要有4种，即网络集成、效用集成、特征集成、划分集成），然后利用谱聚类方法、随机块模型方法或隐含空间模型将上述集成后的网络进行社区划分，但缺点是都只能针对中等规模的无向网络，并不适于复杂的有向多维社交网络的社区发现。因此，为了能够在多维有向社交网络中进行准确有效的社区发现，本文提出了一种基于多维社交网络的社区发现方法，并采用真实的微博社交媒体网络[10]数据进行实验。实验结果表明，本文方法能够更加有效地进行社区发现。

1 基于社交关系和兴趣相似的微博社区发现

微博的社交模式让交友更加便捷，用户与用户之间可以互相关注成为好友，也可以互相评论、转发、推荐取得联系。通常在社交网络中，互动频繁的用户更容易在一起，也更容易被划分到同一个社区；另外，微博中的用户喜欢发一些博文或者转发一些自己喜爱的微博，通过分析博文主题可以找到相似性，而博文相似度较高的用户也更容易被划分到同一个社区。因此通过分析研究微博用户间的社交行为模式以及微博主题的相似性，即可归纳出用户社交关系紧密程度和主题相似程度。本文算法首先将三维有向网络融合成一维无向带权网络，并计算其紧密度；然后利用LDA模型计算出主题相似度；再使用用户总相关度公式计算每对用户的相关度，并将其作为网络图中节点间边的权值，最终发现社区。

1.1 社交关系紧密度计算

1.1.1 好友关系由有向無权网络转化为无向带权网络

用户社交关系网络主要有三种，分别是好友关系网、评论关系网以及推荐转发关系网。首先分析好友关系，在微博社交网络中，用户A关注用户B（在网络图中表示为A指向B）称A为B的粉丝，若B也关注A，则A与B为好友关系（在网络图中表示为A指向B，B也指向A），这是一种强关系，且有些在现实生活中也可能是朋友关系。这种强关系非有即无，所以若A与B互相关注，则定义A与B之间边的权值为1；若只有A关注B或只有B关注A，则定义A与B之间边的权值为0.5。转化图如图1所示。

1.1.2 评论关系、转发推荐关系网络融合

用户间的“评论”和“推荐转发”往往带有方向且次数较为频繁。例如，在微博中，用户A评论用户B所发的博文，用网络图表示就是A指向B。通常，人们将多维网络中的有向网络当做无向网络，然后将多维网络中边的权值进行加权平均得到集成网络[11，12]，这种处理多维有向网络的方式显然不太合理。文献[13]提出社交网络中用户间联系的频繁性、紧密性等关系和节点间的方向、边的权值大小有着密切的联系[13]。根据这种思想，结合真实微博情况，定义用户关系强弱度：

其中：Recij=min（wij，wji）/max（wij，wji）；，wij表示用户i与用户j之间发生的wij次“评论”或“推荐转发”。Recij2写为平方的形式是为了侧重微博用户间相互性的重要性，因为当两个用户间的互动更加频繁时才有更大的概率被划分到同一个社区。例如，在明星和粉丝的微博关系中，粉丝可能会对其关注的明星所发的博文评论转发上万次，但明星可能只回复一两次，甚至无回复，这种情况是单向的，通过式（2）计算得出的关系强弱度就很小。只有当两者之间的互动次数非常接近时，关系强弱度才更大。式（2）具有以下性质：

①当wij=0或wji=0时，得到的Sij为0；

②当wij=wji时，关系强弱程度为wij。

由于关系强弱度Sij值的范围会大于1，为了后面方便导出关系紧密度公式，故先将Sij标准化。令D=max（Sij），则标准化后的Dij=Sij/D，Dij的取值范围为[0，1]。

1.1.3 三网集成后的社交关系紧密度计算

在得到Fij和Dij后，二维网络已变为无向网络，因此需要再次降维，降成一维无向网络。定义社交关系紧密度为：

其中： Cij是大于0小于1的值，并且0和1都可能取到，根据实验，调整参数α与β，当取α=0.618，β=0.382时，实验结果最佳。

1.2 主题相似度计算

一般来说，同一个社区内的成员有着相同或者相似的兴趣爱好。例如，某人喜欢前NBA巨星科比，那么此人就很有可能和一些同样喜欢科比的人划在同一个社区。

若对微博用户发表的每条留言或博文进行主题分析会导致工作量很大。为了更加方便快速地抽取出用户的兴趣主题，本文首先将同一用户的所有评论或博文集中到一篇文档中；然后用分词工具去掉文档中的介词、感叹词等冗余词汇，只留下部分能够代表主题的名词、动词等；再用LDA模型[6]抽取每篇文档的主题，然后把主题等信息存储在矩阵中。

现设如下矩阵：矩阵DT为D×T矩阵，行D表示网络中节点的数目，列T表示用户的主题数量。对DT进行标准化，使‖DT‖=1，则Dij表示用户文档对每个主题的占有比例。根据DT所列出的比例即可看出每个用户的兴趣所在。

其中：Tij的值越小说明相似程度越小，值为0时表示完全不同；值越大说明相似程度越大，值为1时表明主题完全相同。DJS （i， j）是两个概率分布间的Jensen-Shannon散度 [14]，其计算公式为：

1.3 总相关度计算及社区划分

在社交中，有可能用户A与用户B发生矛盾而取消互相关注，又或者两个用户因为兴趣相同而互加关注。因此，如果只单纯地依据社交关系或主题相似来划分社区是不准确的，综合考虑社交关系和兴趣相似来进行社区划分能够提高准确性。根据社交关系紧密度Cij和主题相似度Tij推导出总相关度Rij，其公式为：

根据式（6）可以得到每对用户间的相关度，再根据概率传递公式计算节点间的传递概率。本文采用Label Propagation算法[15]，具体步骤如下：

（1）根据式（6）计算每对节点间的相关度。

（2）随机选择一个节点Q，并以此初始化一个标签，计算节点Q到所有邻近点的传递概率。

（3）利用传递概率对所有节点进行标签迭代更新，迭代的标准为该节点的标签由其所有邻近点标签中数量最多的那个标签代替。

（4）将所有节点的标签进行更新，若有多个标签的数量同为最大，则随机选取一个标签作为该节点的标签。

（5）重复步骤（3）和（4），直至每个节点邻近点的标签变化趋于稳定。

（6）将标签相同的节点划分到同一个社区中。

2 实验结果及评价

新浪微博是目前使用人数最多且流行度最高的社会媒体之一，因此选择新浪微博作为研究对象。首先，分别从微博的5个“圈”（如“体育圈”“学术圈”“影视圈”“IT圈”“文学圈”）中选出526个用户，收集这些用户的基本信息，包括用户ID、好友关系、评论次数、推荐转发次数以及微博内容。LDA模型采用贝叶斯统计标准方法[16]，令其中的参数α=50/T，β=0.01，其中T为Gibbs抽样中的主题数，取T=50，迭代次数设为100，这里最优的主题取值以及最优迭代次数是根据多次实验的经验值得到的，会在语料库上有较好的表现。本文得到的具体数据见表1所列。

先利用社交关系紧密度公式（3）对“好友关系网”“评论关系网”“推荐转发关系网”进行融合得到社交关系网（主题相似网不变），见表2所列。

其中：πa和πb表示两个不同的社区划分，k表示社区数量；n表示節点总数； nha代表组员属于πa划分的第h个社区的数量；nlb代表组员属于πb划分的第l个社区的数量；nh，l代表特定组员的数量，这些组员属于nha划分的第h个社区，同时属于nlb划分的第l个社区。NMI的取值范围为0～1，当πa和πb相同时，其值为1。

首先分别单独对社交关系网和兴趣相似网进行社区划分，并结合真实的5个社区进行评价，结果见表3所列。

从表3可以看出，依据社交关系网络划分出的社区结果准确率比依据兴趣相似的要高，比较符合实际情况。在现实生活中，我们和朋友在微博上互相关注，即使没有相似兴趣，也很难取消互相关注，除非有很大的矛盾；反过来，在兴趣相似网中，本来因为兴趣相似或在某段时间和对方聊得火热而互相关注，但随着双方兴趣度转移或双方没有太多话可聊可能会取消关注，当然，也有因为持久的共同兴趣而不会取消关注的。所以综合社交关系与兴趣相似能够更加有效地进行社区划分。

为了确定最佳阀值γ，在实验中分别取值0，0.1，0.2，0.3，…，1.0，发现准确率最大的值落在0.5～0.6之间；γ取值0.55，发现最大值落在0.55～0.6之间，γ再分别取0.56，0.57，0.58，0.59，最终得出取值为0.57的准确率最高。因此γ的值最终取0.57为最佳，实验曲线如图2所示。实验的最终社区划分对比结果见表4所列，且实验用Gephi生成结果如图3所示。

从最终实验结果可知，综合社交联系与兴趣相似划分社区效果更好。在实验中，调整γ阈值，大概取0.57时得到的准确率最高。

将本文提出的社区发现算法分别与经典的G-N算法、谱平均法以及Lei Tang等人提出的多维信息融合的AMM算法进行比较，获得的NMI准确率见表5所列。从表5可以看出，本文提出的算法对于社区发现的准确率有了很大的提高。