基于Louvain算法的社交网络社区发现研究

来源:用户上传      作者:

　　摘要：社区发现常用来了解复杂网络的结构，挖掘社区成员之间内在的关联关系，当今检测大型网络中社区最广泛使用的方法之一是Louvain算法。Louvain是一种用于识别大型网络中的社区的简单，高效且易于实现的方法，它揭示了社区的层次结构，并允许在社区中进行缩放以发现子社区。本文分析了Louvain算法的基本思想，并用该算法对两个社交网络进行分类，得到了较好的分类结果。
　　关键词：社区发现;Louvain算法;社交网络
　　中图分类号：  TP311           文献标识码：A
　　文章编号：1009-3044（2020）23-0197-02
　　在线社交网络，通讯网络中的交互可以自然地建模为图形。图中的结构群落通常定义为图中的高度连接的顶点/节点的组。这些群体通常代表相似的兴趣群体，朋友社区等，彼此之间有更多的互动或相似之处。社区检测和分析是了解各种现实世界网络的组织的一种重要方法，并且在包括（但不限于）科学计算、生命科学、社会网络分析和互联网应用程序[1]在内的各个领域的数据分析中变得越来越普遍。给定一个图，社区检测的问题是将图中的顶点划分到不同的社区，使同一个社区内的社区成员之间具有较大的相似度，不同社区的成员之间具有较小的相似度。模块化[2]是一个可以衡量社区划分效果好坏的重要指标，也是Louvain算法的核心思想，Louvain算法是一种基于模块度优化的高效算法，除了时间上的优势，还能探测到层次的社区结构，不会遗漏一些小型的社区[3]。在本文中，我们分析了Louvain算法思想和评价模型，并用该算法对两个社交网络数据集进行了分析，效果较好。
　　1 Louvain 算法
　　1.1 算法思想
　　Louvain算法是由Blondel在2008年提出的用于网络社区发现的方法，算法思想简单，算法主要分为节点的局部移动和网络社区聚合两个阶段[4]。首将每个节点看作一个独立的类，并依次迭代每个节点，将单个节点移动到产生最大质量函数增长的社区，并做好标识。然后初始化整个图，将分区中的每个社区成为聚合网络中的一个节点，按照步骤一的方式迭代对网络社区进行迭代归类，直到满足迭代结束条件为止。该算法在两个基本阶段对质量函数如模量度或CPM进行优化，直到评估函数不在变化为止。在每次迭代中，算法都会以任意预先定义的顺序线性扫描顶点。对于每一个点v，会对它的所有邻近社区进行检查，并计算从当前社区移动到每个相邻社区的模块度增益值。一旦增益被计算出来，算法就会将该节点分配给一个能产生最大模块增益的邻近社区作为新社区，并更新以该节点为源和目标维护的相应社区结构。反之，如果所有的增益都是负的，顶点就留在它的当前共社区中。一旦所有顶点都以这种方式线性扫描，迭代就结束了。在一个阶段结束后，该算法通过将一个个小的社区归并为一个超结点来重新构造网络，这时网络中边的权重为两个结点内所有原始结点的边权重之和;以及在两个元顶点之间放置一条边，其权重等于对应两个社区之间的所有社区间边的权重之和。这样就形成了一个由多个子社区压缩的图G′（V′，E′，ω′），并将它作为下一阶段的输入，随后，进行多次迭代计算，直到模块度的值收敛。注意，每个阶段代表社区检测过程中形成的粗糙层次结构。
　　1.2 评价模型
　　Louvain算法是一个不断迭代和合并的过程，在这个过程中是否需要进行下一次是由模块度增益来确定的。在图中每一种结构都对应着一个模块度值，其计算方法如公式（1）所示：
　　当图的结构发生变化，如一个节点a从当前社区C（i）移动到另外一个社区Qi 时，图的结构就会发生变化，相应的模块度也会发生变化，把这种变化称为模块度增益，用[?Q]表示，计算方法如公式（2）所示：
　　在维护的几个数据集中，算法都可以让QiC（j）的每个实例在O（1）时间内计算。因此，算法的时间复杂度为O（M）。虽然在迭代次数或相位数上没有确定上限，但很明显，该算法可以通过使用模块增益来截止 （因为模块是一个单调递增的函数，直到终止）。在实践中，该方法只需要几十次迭代和更少的阶段就能终止大多数真实网络的输入。
　　1.3 算法基本流程
　　Louvain社区发现是一个不断移动节点，对节点和社区进行合并的过程，，其执行流程如下图1所示。
　　2 基于Louvain的社交网络分类
　　社交网络是一個由若干个体构成的交互网络，这些个体之间存在着不同的连接，有的个体之间保存在较为密切的联系，而有的个体之间存在着较少的联系，朋友之间的联系用图中节点之间的边表示，节点之间的边越多，则他们之间的关系越密切。一个大型的社交网络通常是由若干小型网络组成的，因此可以通过Louvain算法对社交网络进行分类。本文在两组社交网络数据集上进行了实验.其中一个是从Facebook上抓取的社交数据集，命名为socialship，另一个则是根据美国大学生足球联赛而创建的一个复杂的社会网络football。
　　2.1 实验结果
　　socialship网络是从facebook社交平台上抓取的社交关系网络，网络中的成员来具有不同的学历，在不同的年份参加了不同的假期活动，具有一定的社交关系。通过Louvain算法聚类分析后得到如图1的结果。从聚类结果可以看出，socialship网络主要被分成了8个社区，分类依据主要是成员的学历、是否参加了相同的活动。分类效果较好，但仍然存在模糊的区域。
　　football网络包含115个节点和616条边，其中网络中的结点代表足球队，两个结点之间的边表示两只球队之间进行过一场比赛，参赛的115支大学生代表队被分为12个联盟。比赛的流程是联盟内部的球队先进行小组赛，然后再是联盟之间球队的比赛。通过聚类分析得到如图2所示的结果。由图可知115成员被很好地划分成立12支球队。
　　3 总结
　　本文对louvain算法的思想、流程、评价模型进行了分析，并应用该算法对社交网络数据集进行分类。由于本次研究的网络数据集较小，且是静态网络，社区结构相对简单，因此得到了较好的实验结果。在下一步的研究中，将试图对louvain算法进行改进，用于更大的或动态的社交网络社区发现。
　　参考文献：
　　[1] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics：Theory and Experiment， 2008，2008（10）：P10008.
　　[2] M. E. J. Newman and M. Girvan， Phys. Rev. E69，026113 （2004）.
　　[3] 李沐南. Louvain算法在社区挖掘中的研究与实现[D]. 北京： 中国石油大学， 2016.
　　[4] 夏玮，杨鹤标.改进的Louvain算法及其在推荐领域的研究[J].信息技术，2017（11）：125-128.
　　【通联编辑：梁书】
转载注明来源:https://www.xzbu.com/8/view-15316532.htm