2.2 复杂网络社团

复杂网络起源于20世纪末计算机时代的物理学，是由线性物理学家和统计物理学家创立的学科，也是在对互联网和WWW等大规模网络的研究过程中出现的。复杂网络强调自然现象和社会现象下包含的复杂的客观规律，随着计算机技术的飞速发展，近年来得到多个学科的关注，已成为最重要的多学科交叉研究领域之一。

具有共同兴趣、思想、目标或任务的人，跨越时间、空间和组织界限，在互联网上的虚拟社区内交换信息，并相互影响形成了社会网络，是各种信息技术广泛应用于人际交往活动和组织而形成的社会技术复杂系统。虚拟社区是典型的复杂系统，复杂网络作为复杂系统各组元相互作用的最简单的抽象，已经成为理解虚拟社区组织演化和功能形成的主要手段。近年来对于复杂网络的研究得到了学术界前所未有的关注。研究人员发现，复杂网络普遍存在一些基本统计特性，如“同一社团内节点连接紧密、不同社团间节点连接稀疏”特点的“社团结构特性”。

随着网络动态演化研究的不断深入，人们发现许多实际的网络都具有一个共同特性——社团结构，即整个网络是由若干个社团组成的，一个社团又是由具有相似特征或共同爱好的成员组成的。每个社团内部的节点之间连接相对来说非常紧密，但是各社团之间的连接相对较为稀疏，如图2-4所示。

进行社团演化探测的前提如下：一是怎样定义社团结构，二是如何有效地寻找到社团结构。网络中的社团结构就是一组相互之间有着比较大的相似性而与网络中的其他部分有着很大不同的节点的群。也就是说，在社团内部，节点之间的联系非常紧密，而社团之间的联系相对而言就比较稀疏。寻找社团结构并对其演化规律进行分析是了解各种现实生活中复杂网络组织结构的一种很重要的方法，并在生物学、计算机科学及社会学等领域都有着广泛的应用。

2.2.1 社团研究中的基本概念

1．社团的定义

如何精确地定义一个社团是研究社团结构的首要问题。社会网络学家和计算机学家等根据节点之间的内部联系给出了多种社团的定义，这些定义总体上可以分为3种主要类型。

第一种是局部定义：这一种定义主要集中关注所研究子图的节点，以及与它们直接相邻的邻居节点，而不考虑图的其他部分。例如，派系的定义就是一个相互连通即全耦合的最大子图，其中任意一个节点和其他所有的节点都相邻。

第二种是全局定义：通常从一个空模型开始，通过比较原始图中子图的连接特性与相对应的空模型中的子图，当子集中边的数目超过了空模型中所预测的边数时，这些节点的子集就构成了一个社团。

第三种是基于节点相似性的定义：即社团是由一组具有相似性的节点所组成的，不论它们是否直接相连，均可通过定量的判据来评价每对节点之间的相似性。

尽管社团的定义多种多样，但在很多社团结构发现算法中，并没有给出社团的精确定义，而只是在分析具体网络时所得到的一个结果而已。

2．模块化函数

即使利用社团发现算法求得了网络中的社团结构，但是如何确认这样的社团结构是否与实际网络中的社团结构相吻合或相接近？因为从不同出发点来划分的网络社团代表不同的网络意义，因此，需要一些其他评判指标来推断这样的划分是否能更好地展现网络的实际特性。

为了区分社团的“稠密”和“稀疏”，Newman等引入一个衡量网络划分优劣的标准——模块化函数。这一概念在提出后，得到众多研究者的认同和接受，该文章也被奉为复杂网络社团结构研究的经典文献。

模块化函数的定义如下：对于给定的一个网络G，假设已被算法成功地划分成k个社团，此时定义一个k×k的矩阵E=（eij），矩阵中的元素eij代表由社团i和社团j中的节点相连接的边在G的总边数中所占的比例；矩阵中对角线元素之和表示由网络中同一个社团内的节点相连的边在总边数中所占的比例；而矩阵中每行或每列元素之和表示与这个给定社团内的节点相连的边在总边数中所占的比例。

3．层次性

网络中的节点可能具有不同层次的组织结构，例如，大的社团内部可能包含较小规模的社团，而这些小社团还可能包含其他更小规模的社团。在这种情况下，就称该网络具有层次性。体现网络层次性结构的一种最简单的方法就是画出该网络所对应的树状图。图2-5所示为12个节点的层次性划分。在底层，每个节点被看作一个社团，节点通过不断聚合而形成较大规模的社团，顶层则表示将整个网络看成一个大社团。每个低层次的社团都被完全包含在高一层的社团当中。

4．重叠性

社团结构的另一个重要特征是具有重叠性，它是指网络中存在部分节点同时被多个社团所包含，属于这些社团的交叉部分。社团结构的重叠性在真实网络中具有众多体现。例如，在社会网络中，根据人与人之间的交际关系可以划分出许多社团，而每个人可以同时属于多个社团组织，可以同时具有家庭成员、工作伙伴、朋友关系等多种身份，社团结构表现出了明显的重叠特性。又如，在生物网络中，某些基因或者蛋白质也具有多种功能特性，它们在不同的环境条件下会发挥不同的作用，因此，可以同时被划分入多个不同的工作组中，属于这些工作组的重叠部分。

2.2.2 复杂网络社团发现算法

为了研究网络中的社团结构，近年来专家学者们提出了一系列有效的算法来寻找复杂网络中的社团结构。目前这些算法着重研究以下3个方面：①能够给出最有效的社团划分结果；②能够体现出网络社团的层次性和重叠性等重要特性；③能够具有较小的近似线性的时间复杂度，在较短的时间内处理大规模的网络数据。由于分类标准不同，社团发现算法具有多种分类，本节重点介绍非重叠社团发现算法。

非重叠社团发现是指划分出的社团之间互不重叠，每个节点有且仅属于一个社团。基于模块度优化的社团发现算法是该类算法中应用较广泛的一种，它将社团发现问题定义为优化问题，然后寻找目标值最优的社团结构。该类算法主要包含3类：基于贪婪性算法、基于分裂的算法和基于凝聚的算法。本书重点介绍基于分裂的算法。

基于分裂的算法的经典代表，是被现在学者引用和学习最多的Newman的GN算法。它通过不断从网络中移除介数（Betweenness）最大的边将整个网络分解为各社团，边介数定义为网络中经过每条边的最短路径的数目。

GN算法的基本流程如下：①计算网络中每条边的介数；②在网络中找到介数最大的边，再将该边从网络中移除出去；③重复步骤②，直到没有边再符合被删除的要求则停止划分，则每个连通分量便构成一个社团。

GN算法的时间复杂度较高，为O（n3），比较适合计算中小规模的网络。且在不知道社团数目的情况下，何时终止步骤②的重复，是这个算法最大的难点，这一步直接影响划分出的社团是否合理，为此Newman等又提出了用模块度来度量结果。

2.2.3 复杂网络社团演化跟踪算法

2.2.2节介绍了寻找复杂网络中的社团结构时常用的发现算法，但是通常情况下网络不是静止不变的，而是随着时间的推移不断变化发展的，因此，无论是在形式上还是在规模上，网络中的社团结构也会随着整体网络的变化而呈现出一定的时间特性。在研究网络中社团个体的时间特性时，也涉及很多社团演化跟踪算法，如基于边重合的算法和基于中心节点的算法等。通过对社团演化规律的研究，可以更深入地了解复杂网络的动态变化。

1．基于点重合的演化跟踪算法

John Hopcroft等于2004年在PNAS上发表了《在大规模链接网络中跟踪演化社区》一文，其基本思想如下：利用聚类算法找出所谓的具有很强稳定性的“自然社区”（这类社区独立于聚类算法，不随聚类算法的改变而改变），它的稳定性使它很适合被用来完成稳定跟踪。John等使用如下公式来判断在不同时间段社团状态间的相关性：

该算法只考虑了两个社区状态之间的节点重合度，并以此来判断它们之间演化关系的强弱，而没有把其他信息（如拓扑信息）考虑在内。

2006年，Tanya等在KDD上发表了《一种分析动态社会网络的框架》，其中他们用来确定两个社团是否具有演化关系的公式如下：

该公式对网络类型的依赖度很大，所以，论文中也没有给出确切的计算，在确定演化关系时，需要设置一个参数β，但社区演化的实际情况较为复杂，且处于不断变化之中，所以，很难确定一个相对准确的经验值来适应这些情况。

2．基于中心节点的演化跟踪算法

2007年，吴斌等提出了基于中心节点的演化跟踪算法，该算法的基本思想如下：首先找出社团中处于中心位置的节点，这些中心节点的属性可以很好地代表它们所处社团的属性。例如，在在线社会支持网络中，位于中心位置的支持提供者所提供的支持类型（支持寻求者所需要的支持类型），往往就代表了该社团整体的支持供需情况。若能有效地跟踪中心节点的演化路径，那么就可以大致得出对应社团的演化路径。

整个算法的步骤如下：①找出社团中的中心节点和非中心节点；②对于t时刻和t+1时刻的社区Ct和Ct+1，如果Ct的核心节点出现在Ct+1中，那么Ct和Ct+1具有演化关系，即Ct+1很可能是Ct的发展。