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

《复杂网络社区划分方法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复杂网络社区划分方法综述摘要：复杂网络在现实网络表现为多种形式，本文将从2002年以来经典社区划分方法入手，对复杂网络社区划分的研究现状进行一个综合简单的描述和概括，试图为社区划分研究描绘出一个较为全面和清晰的轮廓，为该领域的后续研究提供有益的参照。关键词：复杂网络；社区划分；形式；综述中图分类号：TU984.12文献标识码：A文章编号：1674-7712（2014）12-0000-02复杂网络在现实网络表现为多种形式，如社会系统中的科学合作网、人际关系网，生物系统中的基因调控网、蛋白质大分子之间交互网和流行病传播网、蛋白质交互网，

2、科技系统中的电话网、因特网和万维网等等。同时，复杂网络更加普遍存在一些统计特征，如表达复杂网络中节点服从幂律分布特征的“无标度特性”，反映网络短路径长度和高聚类系数特点的“小世界效应”和反映网络中普遍在的同一社区中节点连接紧密、不同社区节点连接稀疏特征的“社区结构”等等。一般认为社区结构（簇）是指复杂网络中由具有相同或相似属性构成的社区，不同的社区结构在特定的网络中具有不同的性质和特征，如：人际关系网络中由相同的兴趣而形成的人群，蛋白质网络中具有相似功能的蛋白质群等。10自从2002年，Girvan和Newman提出著名的社区挖掘G

3、N（Girvan-Newman）算法[1]，此后很多复杂网络社区挖掘方法相继被提出，在新的理论、方法层出不穷，新的应用领域也不断涌现的背景下。如何发现复杂网络中的社区结构，已经成为最具挑战的多学科交叉研究课题之一，吸引了来自生物、社会、物理、计算机、数学等多领域的研究者。本文将从2002年以来经典社区划分方法入手，对复杂网络社区划分的研究现状进行一个综合简单的描述和概括，本文试图为社区划分研究描绘出一个较为全面和清晰的轮廓，为该领域的后续研究提供有益的参照。一、社区挖掘方法（一）基于模块度的社区划分2002年，Girvan和Newm

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

5、3]引入GN算法中，引入统计方法来估算其中部分节点的链接的近似边介数，提出了一种近似的Gn算法，由于其实计算部分网络而不是全部网络，因此，该算法是以牺牲精度为代价来提高计算的精度。2004年，Girvan和Newman针对GN算法中无衡量社区划分标准的不足，引入的函数Q值模块度计算。将次改进算法运用到了实际网络跆拳道网络中得到了很好的划分结果。该模块度定义为以后社区划分的优劣提供了一个衡量的标准。该算法的缺点是算法的复杂度和之前相比并没有什么改进。10于是同年，Newman又提出了基于模块性优化的快速社区发现算法（FN算法[2]），

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

7、的贪婪算法CNM算法。该算法的复杂度O（nlog2n），已经接近于线性复杂度，但是算法的局部最优解问题依旧没有得到改善。2005年，Guimera和Amaral基于退火算法原理，提出了退火模块性优化算法（SA）[3]。该算法的设计思想是在计算之前要给一个初始社区划分，这个初始的社区划分可以任意的，在初始社区的基础上通过迭代不断产生新的社区解，在迭代过程中同时计算相应Q值。SA算法不同与GN算法和FN算法的，SA算法在计算新的候选解时是将节点划分到其他社区、通过社区之间交换节点，再次分解社区或者合并社区。并且该算法中应用了模拟退火策略

8、的Metropolis准则来判断该社区结果是否是当前的最优解。SA算法在实际的数据集上应用的结果中得到了十分好的结果，不足之处是每次迭代都要产生很多的候选结果，因此该算法的时间复杂度较高，运行效率较低。2006年，Newman基于模块