网络的社团

**章　网络社团的概念 **节　网络社团的定义 在讨论网络社团的概念前，首先要了解图论、社会网络分析、复杂网络、异构网络、同构网络等相关概念。图论本身是数学的概念，利用节点和节点之间的边所构成的网络来表示现实世界中的各类复杂系统，与网络相关的主要概念如表1-1所示。 社会网络或复杂网络具有社团结构是网络非常重要的性质，是在生物网络、万维网、社交网络、合作网络、引文网络等网络中常见的特征（Fortunato and Castellano，2007）。社团可以看作是在网络中拥有相似属性或扮演相似角色的节点集合，通常社团内部的节点之间连接紧密，而社团之间的节点连接稀疏。为了鉴别网络中的社团结构，研究人员开发了大量的方法，如KL算法（Kernighan and Lin，1970）、谱分解法（Fildler，1973；Pothen et al.，1990）和分层聚类算法（Boccaletti et al.，2006）等。其中，KL算法通过基于贪婪优化的启发式过程将网络分解为两个社团；谱分解法诞生于20世纪70年代，通过分析网络（对称矩阵）拉普拉斯（Laplacian）算子的特征向量来挖掘社团结构；分层聚类算法的总体思路是基于距离*近、相似度*高的社团开始合并，直到所有元素都归于一个社团为止。然而，这些传统的算法存在准确度不高、时间复杂度大以及需要事先知道网络中社团规模大小等缺点（Shi，2011）。 为此，过去二十多年中涌现出了大量可用于检测网络社团结构的工具，其中以2002年Girvan和Newman提出GN算法*具有里程碑意义（Girvan and Newman，2002）。GN算法的提出掀起了新社团研究的热潮，但该算法依然存在时间复杂度高、不考虑社团划分的真实意义等缺点。随后，Newman于2004年又提出FN贪婪算法（Newman，2004），并基于模块度函数（Q函数）（Newman and Girvan，2004）值*大化来进行社团划分，可得到与GN算法相似的结果，但计算时间大大缩短。然而，由于以上算法的时间复杂度较高，所以仅适用于数据规模较小的网络。为此，Blondel等提出了Louvain算法（Blondel et al.，2008），该算法可以相对快速地处理数以亿计的节点网络。随后Rotta和Noack在Louvain算法的基础上提出了Louvain算法的多级细分算法（Rotta and Noack，2011）。Waltman和van Eck在上述两种算法的基础上提出了SLM算法（Waltman and van Eck，2013），后又将其升级为Leiden算法（Traag et al.，2019）。 对网络进行社团划分研究有助于理解其拓扑结构，具有重要的理论意义和应用价值。当前，科学研究的日益复杂性与交叉性使学科边界变得日益模糊，进而使科学结构越来越难以被清晰地认识。如何有效地发现科学结构已成为知识发现研究长期关注的焦点问题，对探索学科演化、发现学科交叉渗透、挖掘前沿方向具有重要价值。在网络中，社团内部节点之间具有很高的相似度，实际上标志着有共同兴趣或背景的成员集合，表示具有某种特性的社会团体，对网络的社团结构的分析有助于理解社会组织的构成及社会的演变；对生物网络中社团结构的分析可以揭示生物功能的模块、位置和作用等；对引文网络中社团结构的分析可以对相关学科主题进行探索，通过引入时间节点，可以分析学科主题的演变、预测学科主题的发展，还能对某一学科的产生背景、发展概貌等进行分析，从而揭示科学动态结构和发展规律。挖掘作者合作网络的社团结构，可以发现全球范围内科学家共同体的科研活动格局，揭示科学结构特征。 第二节　典型社团划分算法 本节对图书情报领域常用的Q函数、GN算法、FN算法、Louvain算法、Louvain多级细分算法、SLM算法、Leiden算法、Kernighan-Lin算法等社团划分算法的原理和方法逐一进行介绍。 一、Q函数 Q函数由Newman和Girvan于2004年提出（Newman and Girvan，2004）。其含义是：网络中连接社团内部顶点的边所占的比例与另外一个随机网络中连接社团内部顶点的边所占的比例的期望值相减得到的差值。这个随机网络的构造方法为：保持每个顶点的社团属性不变，顶点间的边根据顶点的度随机连接，如果社团结构划分得好，则社团内部连接的稠密程度高于随机连接网络的期望水平。一般认为，模块度值越大，所得到的划分越好。Q函数已成为当前衡量社团划分效果所采用的*广泛的方法（Blondel et al.，2008），可用于任何类型网络的社团划分（Chen and Redner，2010）。 二、GN算法 GN算法的基本流程是：首先计算网络中所有边的介数（Newman，2001），然后找到介数*高的边并将其从网络中移除，不断重复第二步，直到每个节点成为一个独立的社团为止（Janssens et al.，2009）。在执行该算法的过程中，若不提前给定社团数目，则算法无法确定*佳社团，也会导致算法提前结束。GN算法有利有弊，优势是对一些简单的中小规模的网络，执行效率相对较高；劣势是对网络结构复杂且规模较大的网络，该算法执行效率较低。究其原因：GN算法在社团划分过程中以计算边介数为主，而边介数的计算耗时较长。在形成社团的过程中，需要不断地计算边介数，移除网络边，再计算边介数，循环往复，导致运行时间较长。因此，对于巨型网络，GN 算法执行时间久，效率较低。 三、FN算法 由于GN算法在没有确定聚类数目的前提下无法找到*佳社团，因此纽曼等提出了模块度的概念，并利用FN贪婪算法开展社团划分。模块度对于社团划分质量的评估具有一定的说服力，在一定程度上是评估社团划分好坏的相对标准。FN算法的基本流程是：首先将每个节点视为一个社团，然后将社团不断进行合并计算Q值的变化，每次合并都按照Q值增加*大的方向进行，直到所有节点都并入同一个社团。在此过程中，Q值*大时得到*佳的社团划分（Newman，2004）。纽曼提出的FN贪婪算法在时间复杂度和速率方面都有较大提升，利用模块度的变化来确定社团的数量，在一定程度上可以取得很好的划分效果。因此，该算法被广泛应用于大规模网络。 四、Louvain算法 Louvain算法及其多级细分算法、SLM算法的基础都是LMH（局域启发式移除）算法，其思想是按照Q值增加的方向，将一个社团的节点不断移至另一个社团，直至Q函数达到峰值后停止移动。LMH算法采取随机的方式进行迭代，其特点在于效率高，可以处理大规模网络。 Louvain算法（Blondel et al.，2008）以Q函数为衡量指标，执行过程分为两个阶段并反复迭代（图1-1）。①运行LMH算法。每个节点i视为一个社团，其所在社团为C，U为与节点i邻接的社团，如果将i从C移到U后模块度增量*大，则执行此次移动，否则i不移动。对网络中的每个节点都重复以上过程，直到Q值不再增加。②社团合并。将上述划分好的社团作为一个新的节点（即简化网络），新节点之间的权重为社团内节点间的权重和。步骤②结束后则返回步骤①进行迭代计算，直到模块度不再发生变化，算法结束。 五、Louvain多级细分算法 Louvain多级细分算法的特点在于除了利用LMH算法来产生社团进行不断合并外，还可以在划分好的社团间按照增加Q值的方向来移动节点，直到无法移动为止（Blondel et al.，2008）。 六、SLM算法 SLM算法的**步与Louvain算法的步骤①相同，然后也要运行类似步骤②的构建简化网络的步骤，区别在于：在构建简化网络前，还需要增加几个步骤（图1-2）。SLM算法的特点在于允许已经被划分社团的节点被重新划分，因此无须再运行Louvain算法的多级细分而实现社团划分，同时解决了社团合并和单个节点在社团间移动的问题（Blondel et al.，2008）。对于三个基于LMH的算法而言，尽管每运行一次SLM算法需要进行更多的迭代次数，但SLM算法运行一次获得的社团划分效果已经优于多次运行Louvain算法及其多级细分算法的社团划分效果，这意味着利用SLM算法进行社团划分无须多次重复运行。通常SLM算法运行2～5次迭代已经可以超过Louvain算法及其多级细分算法的效果。 七、Leiden算法 Leiden算法基于智能局部移动算法、加速节点局部移动的思想对Louvain