（电路与系统专业论文）基于改进+nnia+算法的网络社区检测方法研究.pdf

学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。（保密的 论文在解密后遵守此规定） 本人签名： 日期： 导师签名： 日期： 摘要 i 摘要 近些年来,复杂网络逐渐成为受人关注的研究领域,越来越多的科研工作者投 身其中。研究发现，复杂网络通常会呈现出社区结构特性，如何在实际网络中高 效地发现社区结构是近年来复杂网络的研究热点之一。本论文主要研究复杂网络 中社区检测问题，基于改进非支配邻域免疫算法(improved non-dominated neighbor immune algorithm，innia)，分别提出针对静态网络和动态网络的社区 检测算法。下面是本文的主要工作： 1. 提出了一种基于改进nnia的网络社区检测方法innia-net， 该方法通过对 两个目标函数进行优化，将社区检测问题模型转化成了一个多目标优化问题，每 次运行可产生一组解，这组解对应着对网络不同层次的划分，每个解可以自动确 定网络中社区数目。 2.提出一种动态网络社区检测方法dyn-innia，该方法以模块度和规范化的 互信息熵作为优化的目标函数，用社区划分得分(cs)作为每个时刻最优解的选择 标准。该方法对于随时间逐步变化的动态网络，可得到较好的检测结果。 本文的工作得到了国家自然科学基金(批准号：60703107)，国家863项目(批 准号：2009aa12z210)，教育部新世纪优秀人才支持计划(no. ncet-08-0811)， 陕西省科技新星支持计划(批准号：2010kjxx-03)和中央高校基本科研业务费重 点项目(批准号：k50510020001)资助。 关键词：复杂网络 社区检测 目标函数 动态网络 摘要 ii abstract iii abstract in recent years, the complex networks has gradually become a popular research field. and more and more researchers is working on it. it has been found by research that complex networks are usually has the characteristics of community structures. how to mine the meaningful community structures efficiently in the real network has become one of the hotspots in the research fields in recent years. in this thesis, the research is mainly focused on the community detection in complex networks. based on the improved non-dominated neighbor immune algorithm (innia), the community detection applied to static networks and dynamic networks are proposed. the major works of this paper are listed as follows: 1. a network community detection algorithm based on improved non-dominated neighbor immune algorithm is proposed. by optimizing two objective functions, the problem model of ommunity detection is transformed into a multiobjective optimization problem. each operation can produce a set of solutions which are corresponding to the different layers of the network. and every solution can automatically determine the number of communities. 2.a dynamic networks detection algorithm dyn-innia is proposed. the modularity and mutual information entropy are chosen as the cost function of optimization. the community score(cs) is chosen to be the selection criteria of each optimal solution. it is proved that this detection algorithm works well enough to the time-varying dynamic networks. this work was supported by the national natural science foundation of china (grant nos. 60703107), the national high technology research and development program (863 program) of china (grant no. 2009aa12z210), the program for new century excellent talents in university (grant no. ncet-08-0811), the program for new scientific and technological star of shaanxi province (grant no. 2010kjxx-03), and the fundamental research funds for the central universities (grant no. k50510020001). keywords: complex networks community detection objective function dynamic networks iv abstract 目录 目录 摘要 . i abstract . iii 第一章 绪论 . 1 1.1 引言 . 1 1.2 复杂网络概述 . 1 1.3 研究现况 . 2 1.4 目标函数 . 4 1.5 论文的主要工作和内容安排 . 6 第二章 复杂网络社区检测 . 7 2.1 社区检测概述 . 7 2.2 静态网络社区检测 . 8 2.3 动态社会网络社区检测 . 11 2.3.1 动态社会网络的特性及存在的问题 . 11 2.3.2 现有的动态社区检测算法 . 12 2.4 非支配邻域免疫算法介绍 . 14 2.5 本章小结 . 15 第三章 基于改进 nnia 的网络社区检测算法 . 17 3.1 非支配邻域免疫算法变异部分的改进 . 17 3.2 innia-net 算法流程 . 20 3.2.1 目标函数 . 20 3.2.2 locus-based 基因编码方法. 20 3.2.3 算法流程图及具体步骤 . 21 3.2.4 种群初始化 . 22 3.2.5 克隆 . 22 3.2.6 交叉和变异 . 23 3.3 innia-net 仿真实验结果 . 23 3.3.1 评价标准 . 23 3.3.2 innia-net 在 gn benchmark 上的实验结果 . 24 3.3.3 innia-net 在真实网络上的实验结果 . 25 3.4 本章小结 . 27 第四章 基于 innia 的动态网络社区检测算法 . 29 4.1 动态网络研究背景和发展概况 . 29 4.2 dyn-innia 算法介绍 . 30 4.2.1 目标函数 . 30 4.2.2 dyn-innia 算法流程 . 30 4.3 dyn-innia 实验结果及分析 . 32 4.4.1 dyn-innia 在人工数据 gn benchmark 上的实验结果 . 32 4.4.2 dyn-innia 在真实网络 football 上的实验结果 . 33 4.4 本章小结 . 35 第五章 总结和展望 . 37 目录 5.1 总结 . 37 5.2 展望 . 37 致谢 . 39 参考文献 . 41 攻读硕士研究生期间的成果 . 47 第一章 绪论 1 第一章 绪论 1.1引言 随着科学技术的不断发展和和生活生产范围的不断扩大，人类社会已经呈现 出网络化的趋势1。各种复杂网络在人类社会随处可见，例如：交通网络、电力 网络、通信网络、计算机网络、各种经济、政治和社会网络等。这些复杂网络在 给人类带来巨大便利和帮助的同时，也带来了一些新的问题，如某个交通要道的 堵塞可能导致整片的交通网络阻塞，或计算机网络中网络病毒的爆发性感染传播 等等。如何科学的定性定量的认识复杂网络，使其更好的为我们服务，便成为现 代科学研究的一个重要课题2, 3。 1.2复杂网络概述 一个具体的网络可抽象为一个由点集v和边集e组成的图( ,)gv e。节点数 记为|nv，边数记为|me。e中每条边都有v中一对点与之相对应。网络 中连接各个节点的边，表示各个事物之间的关系。图1.1展示的就是一个有10个节 点的网络，它有16条边。 图 1. 1 10 节点网络。 从简单的可以在纸上清晰画出并通过肉眼观察可进行结构分析的小型网络， 到社会网络、信息网络和生物网络等大型网络，网络的规模已经增长到了一个非 常大的数量级。在这些大的网络中，以前小规模网络研究中的重要问题，诸如移 除某个结点或某条边对整个网络结构的影响这类问题，已不再有重要研究意义， 因为一个结点或一条边的移除对大型网络的结构影响是可以忽略不计的。例如， 几个路由器不能正常工作了， 或者某条网线断了， 整个internet网络还能正常工作。 因此，在大型网络的研究中，人们往往更关心关于网络结构的一些统计特征的研 2 基于改进 nnia 算法的网络社区检测方法研究 究，如整个网络的结点度的取值分布的形态，要破坏多大比例的网络结点或边才 能使整个网络结构被破坏等等。 网络的研究具有重要意义。例如，准确地刻画internet网络的结构可以更好地 改进网络通信协议的设计，通过建立符合internet结构特性的网络模型可以更有效 地进行网络的各种行为机制模拟；对社会网络结构的清晰认识，人们可以更好地 理解各种各种社会现象。 网络的社区通常是指网络的由一组网络结点组成的结点间紧密互联的各个连 通子网络，相对独立的各个社区之间的稀疏连接勾画了网络的社区结构。社区的 概念最初在社会学领域被提出4, 5， 社会网络通常呈现出社区结构， 例如我们人可 以按照年龄，职业等被划分成一个个社区。近年来的研究表明，其它非社会网络 也呈现出社区结构。例如，www网络中的社区表示一类主题相关的web页面；代 谢网络中的社区往往指示了细胞中的功能单元如代谢通道。2002年givran和 newman提出了一种基于边移除的社区分离算法并分析了一些社会网络和生物网 络的社区结构，引起了人们对复杂网络社区结构分析的兴趣6。 社区结构反映了网络中各个节点间的关系及网络的整体结构。同一个社区中 的节点，它们之间有较大的相似性，联系较为紧密而与网络中的其他部分的节点 联系相对而言比较稀疏。也就是说，在社区内部，节点之间的联系非常紧密，而 社区之间的联系相对而言比较稀疏。 社区结构揭示了给定网络隐藏的特性。 因此， 对网络中社区的检测不仅是研究网络中实体是如何组合在一起的基本步骤，也是 理解大规模网络全局结构和功能特性的方法。 由于复杂网络社区检测具有重要的理论意义和应用价值，它吸引了数学、计 算机、统计物理、生物、经济学和社会学等众多领域的研究者，掀起了一股研究 热潮。从2002年至今，不同领域的权威国际杂志和多个重要国际学术会议多次报 道这方面的研究工作。 复杂网络社区检测已成为图论、复杂网络、数据挖掘等理论的重要组成部分 和相关课程的核心内容。如康奈尔大学计算机系开设了the structure of information networks课程，麻省理工电子工程和计算机系开设了networks and dynamics课程。 1.3研究现况 网络的社区结构分析就是将网络按其内在的社区结构划分成一个个子网络 的过程。实际上，将网络划分成子网络的问题并不是近些年才被研究的问题，而 是过去几十年里在计算机科学和社会学领域被广泛研究的课题，并且发展出了一 类重要的分析方法。在计算机科学领域，这类问题一般称作图分割（graph 第一章 绪论 3 partitioning） ，其主要目的是将网络大致等分成给定数量的子网络，使得子网络之 间的边的连接尽可能地少。图分割通常是通过迭代分割将网络划分成子网络的： 先将网络按分成两个子网络进行最优划分，然后再重复对这些子网络进行最优二 分，直到划分成给定数量的子网络。kernighan-lin 算法9和谱平分方法是其中两 种最重要的图分割方法。 而传统的网络划分方法不能有效地处理网络划分时社区大小和社区个数的 确定或者如何确定最优划分等问题，而网络的社区结构分析往往要求算法能够准 确、自动地确定网络的社区个数并给出相应社区的“自然”分割。因此， girvan 和 newman 在 2002 年提出了一种通过边移除按层次地分解网络的社区分析方法 （记为 gn 算法）8，这项工作被认为是现代社区结构分析方法的开创性工作， 引起了各个领域研究人员的广泛兴趣。gn 算法通过反复计算边介数、识别簇间 连接、删除簇间连接，以自顶向下的方式建立一棵层次聚类树(dendrogram)，从而 寻找到网络中的社区结构。此后，又出现了一些对此算法的改进算法，这些改进 算法都是改进边的度量方法以提高算法的执行速度，如 tyler 算法10，radicchi 算法11；后来，newman 又提出了基于局部搜索的快速复杂网络社区检测算法 fn 算法9，其优化的目标函数被称作模块度 q，q 函数定义为簇内实际连接数 目与随机连接情况下簇内期望连接数目之差，q 值越大，说明划分出的社区结构 越好。优化模块度 q 是一个 np 难问题，因此，相继有学者用贪婪算法，极值优 化算法，遗传算法，模拟退火算法等启发式方法来解决复杂网络中的社区检测问 题。 其中还有一类方法为谱方法， 谱方法将社区检测问题转化为二次型优化问题， 通过计算特殊矩阵的特征向量来优化预定义的“截”函数，当一个网络被划分为 两个子网络时， “截”即指子网络间的连接密度，具有最小“截”的划分被认为是 最优的网络划分12,13。 相对于静态网络社会网络社区检测研究的火热，国内外对于动态社会网络的 社区检测问题研究相对较少。不过，随着动态社会网络得到越来越广泛的关注之 后，仍然涌现了一些优秀的研究成果。sarkar 和 moore 在 2005 年提出了一种利 用隐空间模型来对动态社会网络进行分析的方法，首次将动态社会网络引入到数 据挖掘科研领域，使用统计方法进行分析，给出了确定实体在隐空间位置的方法 14。chakrabarti 等人在 2006 年提出了第一个演化聚类的方法，使用前一时刻网 络的划分结果来约束当前时刻网络的划分，既要求对当前时刻网络的划分尽可能 准确，又要求与前一时刻的划分偏差尽可能的小15。在前人工作的基础之上， tantipathananandh等人在2007年提出了一种基于图着色的动态社会网络社区识别 模型，并很好的使用启发式规则优化目标函数，以加快算法的执行速度16。lin 等人在 2008 年提出了一种 facetnet 算法，使用一个统一的框架模型来对社区结 构及其演化进行分析，用这种方法发现的社区结构更加准确合理，而且鲁棒性也 4 基于改进 nnia 算法的网络社区检测方法研究 更强17。kim 和 han 在 2009 年提出了一种基于演化聚类和粒子密度的方法来对 动态网络进行处理，它可以发现不同时刻社区结构的变化特征，如社区结合，社 区分解，新社区的形成以及旧社区的消亡18。folino 和 pizzuti 在 2010 年首次将 动态社会网络社区检测及其社区演化问题用多目标优化的方法进行求解，这种方 法不用预先设定权重控制参数，直接对预定义的两个目标函数进行优化，用这种 方法不仅可以得到较高质量的当前时刻网络社区划分结果，而且也可以使得相邻 两时刻社区划分的相似度较大19。 1.4目标函数 本文在解决复杂网络社区检测问题的算法中，采取的是基于启发式优化的方 法，这种方法通常都是先预定义一个目标函数，然后将复杂网络社区检测问题转 化为一个函数优化问题。 目前， 学者们已经提出了多个用于社区检测的目标函数， 其中， 比较有代表性的有： 模块度(modularity)9、 模块密度(modularity density)20、 社区划分得分(community score)22、社区适应度(community fitness)22等，在下 文中，我们将对这些准则函数一一进行介绍。 (1) 模块度 基于相对连接频数的定性定义不能度量社区结构划分的优劣，girvan 和 newman 结合社区结构相对连接频数定义给出模块度函数，定量地描述复杂网络 中社区结构划分的优劣。网络的某种划分对应的模块度值越高往往表明该划分越 可能是符合网络社区结构的划分。模块度是现今应用最广泛的评价社区强弱的指 标，它是基于随机网络不存在社区结构的假定，以所有结点的度值与给定网络相 同但边随机连接的网络为参考模型（null model） ，比较给定网络的所有社区内部 边的数量与相应的 null model 对应的社区内部边的期望数量。其最初表达式为： 2 1 2 m ss s ld q ll (1-1) 式中， s l是社区内部连边， s d是s社区所包含节点的度，l是网络中总的连 边。社区模块度q将模块内部的连边和社区之间的连边都与网络总连边相比，而 有相同连边的模块度不一定有相同的节点。 模块度及其推广度量的提出，极大地推动了复杂网络社区结构分析及其应用 的发展。模块度定义时以保持给定网络结点度的随机网络为参考模型，基于随机 网络不存在社区结构的假设，即随机网络模块度值应为 0。但是人们发现由于随 机扰动的影响，由随机网络模型产生的很多随机网络内部边也往往不均匀分布， 导致了在模块度的刻画下具有很高的模块度值。另外，fortunato 和 barthelemy 发 第一章 绪论 5 现，在模块度最大化时，有些小的社区往往不能被检测到，即使这些小社区是完 全图（clique，或称圈，即所有的结点之间都有边相连） ，即模块度的分辨率 （resolution limit） 问题23。 这种分辨率问题的根源在于模块度定义时的 null model 选择：假定了网络中的结点可以与所有结点相连。因此，模块度及其变种也都可 能存在分辨率问题。 虽然模块度及其变种可能存在分辨率问题。 ， 但是模块度函数仍然不失为一个 具有代表性的优秀的目标函数。 (2) 模块密度 li zhenping 等人在 2008 年提出了一个新的基于平均模块度的评价社区结构 划分结果的准则函数，被称作模块密度或 d 值，它可以克服模块度分辨率限制的 问题。模块密度的计算公式如下所示： 11 ( ,)( ,) () mm iiii i ii i l v vl v v dd g v (1-2) 其中() i d g为第i个子网络的平均模块度，()()() iiniouti d gdgdg， 等于第i个 子网络的平均内度减去它的平均外度，具体的说，就是社区内部连边与社区间的 连边之差与社区所含节点之比。模块密度 d 的值越大，社区的划分就越准确。同 时，作者也从理论上证明了最大化模块密度的方法等价于核 k-means 方法，并且 给出了模块密度的一般化形式如下： 1 2( ,)2(1) ( ,) m iiii i i l v vl v v d v (1-3) 当1时，d等价于 ratio association； 当0时，d等价于 ratio cut33； 当0.5时，d等价于模块密度d。因此，d可以看作是 ratio association 和 ratio cut 的凸组合。 (3) 社区划分得分 在 pizzuti 2008 年提出了一种基于遗传算法的社区检测算法 ga-net 中， pizzuti 定义了一个简单有效的适应度函数。通过优化这个适应度函数，可以识别 出社会网络中连接紧密的社区结构和连接稀疏的社区结构。这个适应度函数就是 社区划分得分(community score)，它的定义如下： 1, () k k r m i i c ij ki j c k csa c (1-4) 其中， 1 k iij j c k a c ，r为调节参数，一般取为 2， , k ij i j c a 表示的是社区 i c 内部相连接的边总数，也就是邻接矩阵 ij a中 1 的个数， i 表示 i c内部与节点i相 6 基于改进 nnia 算法的网络社区检测方法研究 连的边占所有节点的比例。 cs 既考虑了社区内部节点连接的比例， 又考虑了社区 之间节点连接的比例，可以对社区进行较好的划分。 (4) 社区适应度 lancichinetti和fortunato等人在2009年提出了第一个用于发现重叠和层次社 区结构的算法，这种算法是基于优化一个被称作社区适应度函数(community fitness)的方法，通过调节一个控制分辨率的参数，可以检测出复杂网络中重叠的 或带有层次的社区结构，该适应度函数定义如下： 1 () ()() s in m is inout si c isis kc cf kckc (1-5) 其中，() in is kc和() out is kc分别表示属于社区 s c的节点的总内度和总外度，是 一个正的实参数，它可以控制生成的社区的大小。除了社区的适应度外，他们也 定义了单个节点相对于社区c的适应度，如下式所示： ( )()() i p cp cip ci (1-6) 1.5论文的主要工作和内容安排 我们在本文中提出利用改进的非邻域人工免疫算法来对静态和动态的网络进 行社区检测的方法。 全文分为五个部分。本章是全文的绪论部分：概述了网络社区检测问题研究 的重要意义，并介绍了该领域常见的典型问题及现有技术。 第二章详细介绍了复杂网络社区检测的发展和现状，介绍了社区检测的相关 已有算法，阐述了非支配邻域免疫算法的具体步骤。 第三章详细介绍我们提出的基于改进nnia的复杂网络社区检测算法 innia-net。对算法的框架及步骤进行详细描述。并分别在人工合成网络上和现 实网络进行实验。 第四章介绍动态网络研究背景和发展概况,详细阐述dyn-innia算法的框架 和步骤，并将该算法用于人工合成的动态网络进行测试。 第五章为全文总结和展望，讨论了在网络社区检测领域一些值得进一步研究 的问题，并展望了网络社区检测研究的未来发展方向。 第二章 复杂网络社区检测 7 第二章 复杂网络社区检测 2.1社区检测概述 通过研究，我们发现社区结构特性是一种介于宏观和微观之间的网络特征，是 真实世界中许多复杂网络所具有的一种普遍性质。目前，社区结构尚不存在统一的 定义。但一般地说，网络中的社区指的是网络中存在的节点子集，该子集内部节点 之间具有稠密的连接而与外部节点具有稀疏的连接。图.1 是社区结构的一个简单例 子。网络中存在的社区结构往往与系统的某种特定属性或功能相对应，例如，社会 网络中的社区对应着具有相似背景或兴趣的群体，科学合作网络图中的社区对应着 某一个学科或研究方向等。 图 2.1 社区结构示例。该网络包含三个社区，每个社区用虚线圆圈表示。 网络中社区结构的检测与识别通常是网络分析的前提和基础，然而上述定性的定 义并不能帮助我们确定网络的社区结构。近几年来，不同领域专家和学者提出了很多 社区结构的定量的定义，大体上可以分为局部性的定义、全局性的定义和基于节点相 似度的定义24。 局部性的定义：社区是网络中的一部分，但是和网络中的其它部分连接较少，因 此在某种意义上，可以认为它们相对独立存在。局部性的定义正是聚焦于要研究的那 一部分，可能包括它直接的邻居，而忽视网络中的其它部分。比如基于团的社区结构 定义指的是网络中的每个社区都是一个团或者多个团的组合23。网络中的团指的是网 络中的全连接子图。最简单的团是三角形，在实际网络中很常见，但规模较大的团却 8 基于改进 nnia 算法的网络社区检测方法研究 很少出现。团的定义非常严格，一个子图如果只缺少所有可能存在的边当中的一条， 那么按照团的定义，它依然不能被称之为一个社区。另外一个问题是，团中所有节点 都是对称的，它们之间没有任何差别，而在很多实际网络中，社区内部往往同时存在 核心和外围这样不同功能的节点。还比如 radicchi 等人提出的强弱社区的定义26，所 谓的强社区指的是社区内的每一个节点的内度大于它的外度，即, inout ii kkiv 。这 个定义同样比较严格，放松一下条件，就是所谓的弱社区的定义： inout ii i vi v kk ， 即社区节点总的内度大于其总的外度。显然，一个满足强定义的社区一定是满足弱定 义的社区，反之则不然。 全局性的定义：从网络整体的角度同样也可以定义社区，特别是某些情况下，网 络中的某一部分对于整个系统的功能非常重要，单独分离这一部分可能会影响整个系 统。近年来研究者们提出了很多全局性的定义，大多数情况下都是间接定义，这些定 义在算法中利用了图的某些全局性特征， 最终在算法结束时社区作为结果输出。 然而， 有一类定义是基于这样一个思想：如果一个图具有社区结构，那么它必然不同于随机 图。一个随机图，比如 erds-r nyi 随机图是没有社区结构的，因为任意两个节点都 有相同的概率相连。因此，可以定义一个空模型(null model)，即满足原图的某些结构 属性的一个随机图。空模型可以用来比较，来判断图中是否存在社区结构。2004 年 newman 和 girvan 提出了一个著名的空模型，即原图的随机化版本，在保持每个节点 的平均度不变的条件下，随机重连每一条边8，这是模块度(modularity)定义背后的基 本概念。模块度是用来评价网络划分好坏的函数，现在已经成了很多社区检测算法的 核心部分，在下一章将会详细讨论这个重要的概念。在标准模块度公式中，一个子图 当其内部边数超过了空模型中相同子图的期望内部边数，则该子图就被认为是一个社 区，这个期望值是在所有可能空模型实现上的平均值。 基于节点相似度的定义：这个定义设想社区是相似节点组成的点集，因此，可以 定义两个节点之间关于某种特性的相似度，不论这种特性是局部的还是全局的，也不 论它们之间是否有一条边相连。有了相似度定义，每个节点会出现在与其相似节点相 同的簇中，形成社区。相似度度量是很多传统社区检测方法的基础，例如基于层次聚 类，划分聚类，谱聚类的方法。 2.2静态网络社区检测 为了研究社会网络中社区结构的特性，学者们提出了多种静态社会网络社区检测 算法，根据它们所采用的基本求解策略，我们将它们归纳为两大类：基于优化的方法 (optimization based method)和启发式方法(heuristic method)。基于优化的方法将社会网 络社区检测问题转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的簇 第二章 复杂网络社区检测 9 结构，如 kl 算法9，fn 算法813，ga 算法27，以及基于遗传算法的方法28等。而启 发式方法将社会网络社区检测问题转化为预定义启发式规则的设计问题，如 mfc 算 法29，hits 算法30，gn 算法及其改进算法5，wh 算法31，fec 算法32，cpm 算 法33等。除了上述方法外，还有基于相似度的层次聚类方法，以及混合方法等，我们 对其中主要的几种算法做一下简单的介绍。 (1) kl 算法 1970年， 针对图分割问题克宁汉林(b.w. kernighan 和s. lin)提出了 kl 算法 ， 该算法也可用于复杂网络聚类。 kl 算法的优化目标是使社区间连接数目与社区内连接数目之差最小，算法的候 选解搜索策略是：移动节点到其他社区或者交换不同社区的节点，观察优化目标函数 的变化情况，算法从初始解开始，计算每个节点移动或交换后的目标函数，当优化目 标得到改进的时候保留此次操作， 否则放弃， 迭代过程直到所有节点都被移动过为止， 从而找到使社区间连接数目与社区内连接数目之差最小的复杂网络划分方案。 kl 算法的不足：找到的解往往是局部最优而不是全局最优解。kl 对初始解非 常敏感，它需要先验知识。而且，kl 算法的时间复杂性较大，为 2 ()o tn，t 表示算法 终止时的迭代次数，n 表示网络节点个数。 (2) fn 算法 2004 年， 纽曼(m.e.j. newman)提出了基于局部搜索的快速复杂网络社区检测算法 fn。 纽曼与格万(m.e.j. newman 和 m. girvan)于同年提出的网络模块性评价函数：q 函数。 q 函数定义为簇内的实际连接数目与随机连接下簇内的期望连接数目之差， 用来定量地刻画网络簇结构的优劣，q 值越大则网络簇结构越好。 q 函数的一种计算形式如式(2-1)所示： 2 1 2 m ss s ld q ll (2-1) 其中，m表示网络社区个数， s l表示社区s中的连接总数，l表示网络连接总数， s d表示社区s中节点度之和。一般的，好的社区结构对应较大的 q 值。候选解的局部 搜索策略为： 选择且合并两个现有的社区， 从初始解开始(每个社区仅包含一个节点)， 在每次迭代中 fn 算法执行使q值最大化的合并操作，直到网络中只剩下一个社区。 fn 算法的时间复杂性是 o (m n)，m 和 n 分别表示网络的连接数和节点数。 (3) ga 算法 2005 年， 吉莫热与阿麦拉尔(r. guimera 和 l.a.n. amaral)采用与算法 fn 相同的 优化目标函数，提出了基于模拟退火算法(sa)的复杂网络社区检测算法 ga，并应用 到新陈代谢网络分析中。 nature2005 年 2 月刊报道了该项研究工作。 10 基于改进 nnia 算法的网络社区检测方法研究 类似于 kl 算法，从初始解开始，在每次迭代中，ga 算法产生、评价、接受或 拒绝由当前解产生的候选解。 ga 算法产生候选解的策略是： 将节点移动到其它社区、 交换不同社区的节点、 分解社区或合并社区。 ga 采用的 metropolis 准则定义如式(2-2) 所示： 1 1 1 1, if exp if tt tt tt cc p cc cc t (2-2) 其中， tt cq ，p表示接受1t 时刻候选解的概率，t表示1t 时刻的系统温度。 算法ga的优点在于 ga采用模拟退火控制策略， 因此 ga具有跳过局部最优解、 找到全局最优解的能力，因而具有很好的聚类精度。但是，ga 的效率取决于算法 sa 的效率，而后者通常收敛很缓慢。另外 ga 对输入参数非常敏感，不同的参数设置往 往导致不同的聚类结果。 (4) gn 算法 2002 年，格万和纽曼(m. girvan 和 m.e.j. n