复杂网络社区划分方法综述

摘 要：复杂网络在现实网络表现为多种形式，本文将从2002年以来经典社区划分方法入手，对复杂网络社区划分的研究现状进行一个综合简单的描述和概括，试图为社区划分研究描绘出一个较为全面和清晰的轮廓，为该领域的后续研究提供有益的参照。

关键词：复杂网络；社区划分；形式；综述

中图分类号：TU984.12 文献标识码：A 文章编号：1674-7712 （2014） 12-0000-02

复杂网络在现实网络表现为多种形式，如社会系统中的科学合作网、人际关系网，生物系统中的基因调控网、蛋白质大分子之间交互网和流行病传播网、蛋白质交互网，科技系统中的电话网、因特网和万维网等等。同时，复杂网络更加普遍存在一些统计特征，如表达复杂网络中节点服从幂律分布特征的“无标度特性”，反映网络短路径长度和高聚类系数特点的“小世界效应”和反映网络中普遍在的同一社区中节点连接紧密、不同社区节点连接稀疏特征的“社区结构”等等 。一般认为社区结构（簇）是指复杂网络中由具有相同或相似属性构成的社区，不同的社区结构在特定的网络中具有不同的性质和特征，如：人际关系网络中由相同的兴趣而形成的人群，蛋白质网络中具有相似功能的蛋白质群等。

自从2002年，Girvan和Newman提出著名的社区挖掘GN（Girvan-Newman）算法[1]，此后很多复杂网络社区挖掘方法相继被提出，在新的理论、方法层出不穷，新的应用领域也不断涌现的背景下。如何发现复杂网络中的社区结构，已经成为最具挑战的多学科交叉研究课题之一，吸引了来自生物、社会、物理、计算机、数学等多领域的研究者。

本文将从2002年以来经典社区划分方法入手，对复杂网络社区划分的研究现状进行一个综合简单的描述和概括，本文试图为社区划分研究描绘出一个较为全面和清晰的轮廓，为该领域的后续研究提供有益的参照。

一、社区挖掘方法

（一）基于模块度的社区划分

2002年，Girvan和Newman基于启发式规则提出著名的社区挖GN（Girvan-Newman）算法[1]，该算法从社区间的连接边介数入手，根据社区间边介数应大于社区内部链接的边介数，通过反复计算边介数，移除边介数最大的边，自顶向下的方式建立一颗层次聚类树的方法来划分社区。其中边介数定义为：网络中经过每条边的最短路径的数目。通过在实际网络中的应用发现该方法的划分的结果精度高，但是计算速度较慢；对于一个具有m条边，n个节点的网络时间复杂度为O（mn2），并且该算法没有对于社区在什么时候进行划分提出一个有效的方法。

2003年，Tyler等人将采用蒙特卡洛方法[3]引入GN算法中，引入统计方法来估算其中部分节点的链接的近似边介数，提出了一种近似的Gn算法，由于其实计算部分网络而不是全部网络，因此，该算法是以牺牲精度为代价来提高计算的精度。

2004年，Girvan和Newman针对GN算法中无衡量社区划分标准的不足，引入的函数Q值模块度计算。将次改进算法运用到了实际网络跆拳道网络中得到了很好的划分结果。该模块度定义为以后社区划分的优劣提供了一个衡量的标准。该算法的缺点是算法的复杂度和之前相比并没有什么改进。

于是同年，Newman又提出了基于模块性优化的快速社区发现算法（FN算法[2]），该算法的过程和GN算法恰好相反，算法采用自底向上的层次聚类过程构成一颗层次聚类树，在合并的过程中引入DQ，每次合并选择使函数Q值增大最大或者减小最小的方向进行社区的合并操作，当最终社区合并为一个社区时，只要在对应Q值最大处断开即可得到聚类的结果。通过对实际网络划分的应用，对于一个m条边，n个节点的网络，该算法的复杂度为O（mn+n2）。算法的时间复杂度得到了很大的改善。但是算法也具有很大缺陷，在于其求解是局部最优解，精度相较于GN算法低。虽然其后Newman、Clauster等人继续对FN算法进行了优化，利用堆栈结构队，提出了一种新的贪婪算法CNM算法。该算法的复杂度O（nlog2n），已经接近于线性复杂度，但是算法的局部最优解问题依旧没有得到改善。

2005年，Guimera和Amaral基于退火算法原理，提出了退火模块性优化算法（SA）[3]。该算法的设计思想是在计算之前要给一个初始社区划分，这个初始的社区划分可以任意的，在初始社区的基础上通过迭代不断产生新的社区解，在迭代过程中同时计算相应Q值。SA算法不同与GN算法和FN算法的，SA算法在计算新的候选解时是将节点划分到其他社区、通过社区之间交换节点，再次分解社区或者合并社区。并且该算法中应用了模拟退火策略的Metropolis准则来判断该社区结果是否是当前的最优解。SA算法在实际的数据集上应用的结果中得到了十分好的结果，不足之处是每次迭代都要产生很多的候选结果，因此该算法的时间复杂度较高，运行效率较低。

2006年，Newman基于模块度函数Q值，提出了优化函数Q的谱方法[4]。Newman通过引入谱图理论研究模块度优化。用图拉普拉斯矩阵来表示模块度函数Q，该矩阵又称为模块性矩阵；并证明了这个矩阵的第二大特征值的特征向量的正负二分结果，正好对应了模块性优化的二分结果；通过在实际网络上的应用，该算法的聚类结果接近实际网络，但其时间复杂度仍较高，介于O（n2 log n）和O（n log n）之间。

2007年，杨博、Cheng和Liu等人[3]通过基于马尔科夫随机游走模型提出了网络聚类算法算法（FEC算法）。该算法的假设是：开始从任意社区开始随机游走，根据在整个网络中的随机游走到达该起始社区内节点的期望值，应大于到达起始社区外节点的期望值的思想。算法采用了启发策略，综合了两种分簇标准（连接密度和连接符号）的复杂网络社区发现聚类算法，理论上该算法既能很好的处理符号网络，又能较精确的处理仅包含“正关系”的一般复杂网络，对于噪声高和网络社区结构明显的网络社区划分的结果也相当精确。实验结果表明FEC算法在时间和精度方面有很好的性能。但是由于该算法需要采用随机游走的步长作为参数，而对于这个步长参数，目前还没有一个能够有效针对不同网络设置最优参数的方法，所以对于步长的设置最终会直接影响最终的聚类结果的精度，一般认为对于步长的取值在[6，20]之间较为合适。

2009年，Barber等人将算法LPA[4]转化为一个函数优化问题，给出了目标函数。通过讨论与研究该目标函数的特性，来进行社区的划分，LPA在原理及实际应用方面的缺陷，需要注意，表示社区划分质量的提高并不和目标函数值的增加相一致。因此，他们对目标函数进行了相应的改进，给出一个带约束的标签传播LPAm算法。该算法的目标函数恰好是模块度函数Q值，因此，改进后的算法对应了模块性函数优化，解决了在文献[2]中所提出的问题。

2011年，刘大有等人[3]从局部观点出发，根据复杂网络的规模不断变大、且某些特性呈天然分布式特性的特点。并且针对单个节点社区划分的归属，利用局部目标函数f，对模块度函数Q进行了分析，提出了一种快速的社区挖掘算法（FNCA算法）。该算法证明了模块度函数Q值会伴随着网络中任意节点的函数f的单调递增，Q值呈现出单调递增特性；在此理论的基础上提出基于局部优化的近似线性的社区挖掘算法。在算法中，每个节点只利用网络局部社区结构信息优化自身的目标函数f，通过节点之间的相互协同实现整个网络的聚类过程，该算法能用于分布式网络社区挖掘，又能用于分布式网络社区网络挖掘，通过对实际网络社区划分的结果分析，该算法的时间复杂度较低，精度较高。

（二）基于节点相似性的社区划分

2006年Leicht，Holme P，Newman等人提出的LHN算法[7]，该算利用网络邻接矩阵A来定义矩阵SLHN=2lamtD-1（I-QA/lamt），其中任意一个元素代表两个节点之间的相似度大小，lamt是邻接矩阵A的最大特征值，D是由节点连接数组成的对焦矩阵，QA是一个介于[0，1]之间的参数，以保证矩阵逆的存在，该算法根据随机游走理论，定义节点Vi和Vj间的平均通勤时间定义为：2m（lii+ljj-2lij），其中还lij表示矩阵L=（D-A）+的相应元素，该算法具有很高的计算复杂度，不适合大型网络计算。

2007年，Frey和Dueck通过3个迭代公式不断的对两个消息R和A进行更新，提出了近邻传播算法AP算法[6]，该算法又被称为基于消息传递的聚类算法。AP算法的思想是将网络中每个点都作为聚类中心节点，然后计算中心节点与其他节点的相互吸引信息R（i，k）和归属信息A（i，k），前者称为点k对点i的吸引度，用来描述数据点k适用于作为数据点i的类社区代表程度，后者代表点i对点k的归属度，用来描述数据点i选择数据点k作为其类代表的适合程度，当二者之和越大，点k作为最终聚类中心节点的可能性就越大。该算法在实际的网络中应用显示精度比K-means算法结果精度要好，时间复杂度为O（n2）。

2010年，AHn[6]等人基于边的思想划分链接的层次聚类社区划分的方法。该算法的思想是：给定由节点k连接的一对边eik和ejk，用jaccard指数来计算节点i和j之间的相似度S（eik，ejk），S（eik，ejk）=|n+（i） n+（j）|/|n+（i） n+（j）|，其中n+（i）为包含节点i及其邻居节点的集合，n+（j）为包含节点j及其邻居节点的集合。而后通过利用单链层次聚类方法，逐层的向上产生一棵连接社区的层次树。最后定义一个用于划分该层次树的密度函数D，在相应位置断开来获得最优链接划分。通过该算法在实际网络划分中的应用，该算法的时间复杂度为O（nk2），其中kmax是网络中最大的节点的度数。

2011年，姜雅文等人针对GN算法的不足，提出一种基于节点相似度的节点分裂算法SCN[5]，该算法通过计算顶点间的相似度而非GN算法中的边介数，针降低了算法时间复杂度。相比传统算法的节点相似性计算和GN算法，在速度和精度上都有较为明显的改善。该算法的时间复杂度介于O（n2）和O（n3）之间。

2011年，刘大有[5]等人提出基于集成网络重叠社区挖掘算法（UEOC），该算法将原始网络同对应的退火网络转换成一个集成网络，针对集成网络给出的Maekov游走方法，逐渐找出网络社区，然后通过引入局部社区函数“导电率”，又被成为相似性函数；通过该函数作为社区划分的标准，将已经找到的社区全部被抽取出来，通过在实际网络中的应用发现该算法不但适合于普通网络，而且适合于重叠网络，且算法只需要一个无需先验知识就能很容易被确定的参数。该算法的时间复杂度为O（Kn2），其中n 为网络中节点的个数K为重叠社区个数。

二、结束语

本文主要是从两个方面对现有的工作进行了综述：（1）根据所采用的原理从模块度与相似性两个角度进行分类，并从中选择了典型的算法进行介绍；（2）从算法辨识的精度和时间复杂度两个方面进行定量分析、比较了一些典型方法的性能。

社区划分的方法基本上都是在以上两种思想的基础上进行的，虽然社区划分算法层出不穷，取得了很多让人兴奋的结果，但是社区划分中依旧还有很多的问题没有得到解决：

第一，关于社区的定义，现在大家公认的是Newman的模块度定义，但是基于相似性、基于反社区的思想在实际应用中也取得了比较好的结果，加上对于现实网络的高度复杂性，网络中节点和边的属性等因素很少被考虑到社区划分中，因此，现在很多各具特色的观点，都尚难以达成共识，人们难以判断一个方法的好坏，也无法控制大量新方法的产生。

第二，关于重叠网络、层次网络、二分网络的划分，目前对于既能发现重叠网络，又能发现层次网络的算法并不多见，并且大多数的都是在单部图上面对网络进行划分；大量的算法在社区划分中既没有考虑到网络本身所具有的各种属性，也没有考虑到网络所具有的结构特征，因此，对于重叠网络、层次网络、二分网络的划分的研究将会继续是一个热点。

参考文献：

[1]Clauset A，Newman M E J，Moore C.Finding community structure in very large network，Phys.Rev.E，2004（70）：066111.

[2]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006（09）.

[3]刘大有，金弟，何东晓.复杂网络社区挖掘综述[J].计算机研究与发展，2012（09）.

[4]Santo Fortunato.Community detection in graphs，fortunato@isi.it，2012（11）.

[5]阳广元，曹霞.国内社区发现研究进展[J].情报资料工作，2014（02）.

[6]Cheng SQ，Shen HW，Zhang GQ，Cheng XQ.Survey of signed network research.Ruan Jian Xue Bao/Journal of Software，2014（01）：1−15（in Chinese）.

[7]金弟，杨博.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报，2012（03）：451-164.

[作者简介]顾跃举，男，辽宁辽阳人，武警辽宁省总队网管中心助理工程师，研究方向：计算机系统应用于维护。

推荐访问:划分 综述 方法 网络 社区