【毕业学位论文】（Word原稿）基于多目标遗传算法的复杂网络社区划分

兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 1 第一章 绪论 题的背景和意义 20世纪 90年代以来 ，随着 息技术得到了前所未有的大发展、大繁荣，人类社会已经进入一个由各种网络构成的全新时代。现在，无论你从事何种工作、身处某个地方，都能发现网络的存在，出行有交通网、政府有办公网、买东西有采购网、部队有指挥网，就连交友、找对象都有社交网、婚恋网，可以说，网络已经完全融入到当今社会的方方面面，复杂网络成为 体现各种网络系统关系的有效形式 。这些复杂网络系统的出现，深刻改变了人们传统的生活、工作方式，极大地丰富了人们的生活，改善 了社会生产关系，提高了工作效率，有力地促进了经济社会发展。但我们也要看到，复杂系统是一把“双刃剑”，它在给人类带来便利的同时，也给我们制造了麻烦，比如，一个计算机病毒的传播就会波及成千上万台电脑，造成网络瘫痪；一个电力系统出现故障，就会影响好几个地区的生产生活，甚至会发生重大安全事故。因此，在网络化的今天，我们必须对复杂网络系统进行重新认识，只有真正掌握了它的优缺点和利弊，掌握了它的内在规律，才能更好地运用和服务于人类社会。 目前对复杂网络的定量与定性特征的科学理解已成为网络时代科学研究中一个极其重要的挑战性 课题。 一直以来，各专业学科只注重研究本专业领域相关的网络系统的发展运用，而对由多个不同领域网络构成的复杂网络却很少有人涉及。只是在本世纪初以来，复杂网络的研究才开始兴起，并且逐渐渗透到涵盖通信、电力、生物、数理、社会、工程等各个领域。那么，如何找出不同性质网络之间的共性和差异，如何解决由多个不同网络构成的复杂系统存在的问题，并且找出规律、拿出具有普遍适用性的处理方法，就成为一项具有很大挑战性的课题，这也是当今科学研究的一个重点方向。 随着复杂网络理论和实用价值的体现，人们不断对其物理意义和数学特性进行深入 探索。社区结构的发现方法，也被称为“分群”，也就是说，把一个网络分成节点群，这些群被称为“社区”，“团”或是“单元”，位于每个群内部的节点相互之间连接密度很高，但不同群内节点间的联系却很稀少 1。 社区结构是复杂网络最普遍和最重要的拓扑结构属性之一，与小世界性 2、无标度性 3基本统计特性相并列 。我们只有发现了复杂网络潜在的规律，了解了复杂网络的 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 2 性质，才能更好的应用复杂网络，而挖掘网络中的社区结构，给我们提供了一个很好的途径。用发展的眼光来看，随着复杂网络理论研究的深入和实证研究成果的推广，其应用 前景将会越来越好，并且将会对网络安全与管理维护、社会行为与行政管理、疾病预防与传播控制、防灾减灾与应急处置、生态系统与环境保护等各专业学科的研究产生重要影响。比如， 目前已被应用于恐怖组织识别等社会网络分析 6,7，新陈代谢网络分析 7、基因调控网络分析和主控基因识别 8等各种生物网络分析以及 区挖掘和基于主题词的 档聚类 9等众多领域 。 内外研究现状 目前，复杂网络社区发现的研究越来越深入，应用也越来越广泛，而且已经引起数学、生物、生命科学、物理、医药卫生、通信等各专业领域 学者的关注和参与，这为复杂网络社区发现研究搭建了更加广阔的平台，创造了更加有利的条件。而鲜为人知的是，复杂网络社区发现最早却是社会学的研究范畴，人们在研究社会学中的分级聚类（ 题时，发现它与计算机科学中的图形分割（ 论有十分密切的关系，这种关系具有社区结构属性，从而衍生出复杂网络社区发现这一门新的学科。 由于社区结构划分对更准确地理解复杂网络的组成原则、拓扑结构与动力学特征具有十分重要的意义，因此，诸多学者从不同角度对如何发现网 络中的社团结构问题进行了广泛研究。 来自物理，统计，数据挖掘，进化计算等领域的各种算法都被用于复杂网络的社区划分。 其中，最早的算法要追溯 到 1970 年的 法 10，它是一种基于贪婪算法原理将网络划分为两个大小已知的社团的二分法。它的基本思想就是定义一个增益函数 Q，这里 Q 指两个社团内部节点之间的连边数量与社团之间节点连边数量之差，目的就是选出使 Q 值最大的方法。但这种算法必须事先知道网络的社团数目，因此很难应用于实际的网络分析。另一种 用于复杂网络的社区结构划分的算法称为基于 特征值的谱 平分方法（ 该算法中，当网络由两个社团构成时，根据非 0 特征值相应的特征向量中的元素所对应的社区内的节点进行划分 11。这类算法的时间复杂度比较低，但每次只能将网络平分是它的最大问题，而且与 法一样，这类二分法无法确定算法要重复到哪一步为止。 分级聚类法 (复杂网络社区结构划分的一种传统算法，这种 算法 总体分为两类： 一种是 将所有的样本点自底向上合并组成一棵树 的 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 3 凝聚算法，另 一种是 自顶向下分裂成一棵树的 分裂方法 。 2002 年 出一种通过去除边数对网络进行反复分割的法 6。这种查找网络中社区结构的分裂方法已经成为了该领域研究的一个分支，引起了其他领域研究人员的关注，成为一项现代社区结构分析方法的开创性工作。它把网络中经过每条边的最短路径的条数定义为边介数 (通过不断地从网络中移除最大的边介数从而将整个网络分解为各个社区。为了评价由这种分裂方法划分的网络社区结构的准确性或者质量， 计了一个 数量测度，称为模块度 (记为 Q， 12。尽管模块度 Q 弥补了 法的一些缺陷，但模块度的算法计算的时间复杂度较高，况且 法本身计算复杂度就很大。之后， 人针对上述缺陷提出了一种新的方法，即自包含 法（ N 13。为了确定社区结构，他们给出了一种强社区结构和弱社区结构的定义作为衡量标准。该算法与 法的效果相当，但是速度却有了较大的改善。 2003 年， 于电阻网络的性质提出了 W 一 H 算法 14，它将网络看成一个电阻网络，然后，利用 理求解各个节点的电压值，绘制电压谱，进而根据不同的阈值进行社区划分。该算法有一个很大的好处，就是不需要计算出网络中的所有社区就可以找到包含指定结点的社区，在实际应用中有很重要的意义。 2004 年， 法的基础上提出了一种 速算法 12，它是一种基于贪婪算法思想的凝聚算法。该算法将每个节点作为一个社区，然后依次合并有边相连的社区对，也就是说合并的结果要么使模块度 Q 增 大最多，要么使其减少最多，直到整个网络合并为一个社区。算法总的时间复杂度为O(m+n)n)。整个算法结束后形成了一个社团结构分解的树状图，要想得到哪种网络社区结构，只需要选择在不同位置断开即可。随后， 人又以 速算法为基础提出了一种新的贪婪算法，称为 15。该算法在计算和更新网络的模块度时运用了堆的数据结构，因此与原来算法相比，效率极大的提高了，在大型复杂网络上的成功分析证明了该算法的复杂度低，只有 2n n ，几乎达到了线性复杂性。此外还有 人提出的结合谱分析的凝聚算法 16等。 除此之外，还有一类基于优化的算法。如 提出了一种 法 17，这种算法把模块度 Q 作为优化目标，引入模拟退火局部搜索算子，增强了算法全局探索的能力，避开了局部最优解，因此具有很高的聚类精度。但在 2007 年， 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 4 人 18通过系统地研究，发现了这类方法存在的问题，在大型网络中，Q 函数直接影响着 划分的结果，它更多的是找到网络中大的社区结构，对于隐含的小型社区却无能为 力，所以划分的结果就不是精确的网络社区结构。这说明这类算法不适合大规模网络的划分，只能在节点数量较少的小型网路上准确发现所有社区结构。极值优化（ 法是另一种行之有效的、求解模块度最优值的启发式搜索方法 19。陈国强，王宇平 20提出了一种基于极值优化模块密度的划分方法，分析了基于优化模块度检测复杂网络社区结构的算法存在解的限制问题，即不能检测出小于一定内在尺度的社区。 目前，绝大多数算法不考虑重叠的网络社区结构。但现实生活中的网络经常会出现相互重叠的、互 相关联的社区结构，一个节点有可能属于两个或者更多的社区，并不是都完全独立存在。所以，若能发现可交叠的社区结构，则更具有实际意义。而 人 21在 2005 年已经开始从事此项工作。他们认为网络社区由 多个相邻的 k 成，相邻的两个 k 节点，每个 k ，但属于不同网络社 区 的 k 该 算法的好处是时间复杂度低，但算法需要事先知道派系的大小，这个参数很难得到。 彭佳扬等人 22在此基础上提出了一种发现交叠社区 的快速层次化算法。该算法基于极大团扩展发现社区结构，针对社区结构明显的网络敏感度更大，对于大规模网络，所需的时间相对较短。 虽然复杂网络的社区结构研究取得了一些成果，但远没有达到学者们期望的结果，还有许多难题甚至是基本问题没有解决。比如，算法优越但计算量大的问题，概念被广泛使用但数学定义不严格、不明确的问题，等等。这些已经成为制约复杂网络社区结构研究的短板和障碍。因此，如何提高社区划分准确率，如何改善算法的时间复杂度，逐渐成为复杂网络社区研究的重点和难点。 文的主要工 作及内容安排 本文深入 研究了复 杂网络现有的社区划 分的经典算法，对不同算法的优缺点进行详细分析。结合之前学者的研究成果，研究了一种新的解决方案，即把复杂网络中社区划分问题看多一个多目标优化问题，构造两个目标函数，用多目标遗传算法进行优化。并对算法在模拟和人工网络上进行验证和详细分析。 本文分为六部分， 内容安排如下： 第一章 绪论，简要介绍本文的研究背景和意义，当前复杂网络社区结构划分的国内外研究现状。 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 5 第二章 对复杂网络社区的概念和社区划分问题进行阐述，并介绍社区划分的一些经典算法的思想和优缺点。 第三章 把社区划分问题作为一个多目标优化问 题来进行阐述，构造了两个目标函数。 第四章 对多目标遗传算法采用的遗传表示法和使用的变量运算符进行描述。 第五章 把 法在虚拟和实际网络中进行验证，将结果与现有的一些算法进行对比，讨论本文算法的优点。 第六章 对本文所做的工作进行了总结，并提出今后下一步研究工作的方向。 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 6 第二章 复杂网络社区划分算法概述 本章简要介绍了复杂网络问题的起源，研究简史以及基本特征。阐述了复杂网络社区结构的普遍定义及社区结构划分算法的几大种类，并着重研究了其中几个经典算法，分析了这些算法的优缺点。 杂网络概述 杂网络研究历史 复杂网络的研究现今已成为一个热点，网络结构复杂性及其与网络行为之间的关系引起大家的广泛关注。为了便于研究，学者们用图（ 种工具来描述各个领域不同的复杂网络。这种实际网络的图表示起源于 桥问题。 现在俄罗斯的一个小镇，镇上有七座桥，人们提出能否一次不重复地走完七座桥，最后回到原点，结果没有人能做到。 1736 年，数学家欧拉注意到了这个问题，他利用数学抽象法把这个问题表示成图，这样就转化成了一个数学问题，最后研究证明这个问题无解。但欧拉却 因此开创了图论 (研究。 20 世纪 60 年代匈牙利数学家 立了随机图理论，这被公认为是开创了复杂网络理论的系统性研究。他们认为对每一个 机图，任意给定一个概率 P，这些图几乎都会同时具有或者没有某种性质 Q, 这被认为是最重要的发现。 上世纪 60 年代，美国著名的社会心理学家 了一个关于人传人送信的实验，通过这样的社会调查研究，最后得出著名的“六度分离”推断，就是说地球上任意两个人之间的平均距离是 6。这个结论反映了人与人之间联系的紧密程度，也说 明社会网络中存在着一种小世界现象。 1998 年 6 月，美国 学理论和应用力学专业的博士 其导师授在 志上发表了题为 文章 23。 1999 年 10 月 ， 美国 学物理系的 志上又发表了 of 12。这 两篇文章分别揭示了复杂网络的小世界特征和无标度特性，同时也代表复杂网络的研究进入了一个全新的时代。 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 7 实网络的图表示 现实世界中的网络可以抽象为图 (构 ，其中 ， 节点表示网络中的目标对象，边表示这些对象之间的某种联系， V 是所有结点的集合， E 是 所有边的集合。当图中的任意点对 与 对应同一条边的网络就为无向网络，而任意一条边的权值都相等时就称为加权网络，反之就称为有向网络、无权网络。网络中的节点也并非都是一样的，不同性质的个体就代表不同类型的节点。此外，我们也可以定义一个 的邻接矩阵 A 来表示图 G 。当网络为无权无向网络时，邻接矩阵 A 是个 0 1 对称矩阵。当矩阵中元素 1示两个节点 有边相连，当 0网络是加权网络时，边的权重由矩阵 A 中的非零元素来表示。本文主要研究无向无权网络。图 2几个不同类型网络的例子。 (a)单一类型节点和 (b)不同类型节点和 (c)节点和边权重变 (d)有向网络 边的无向网络； 边的无向网络； 化的无向网络； 图 2不 同类型网络的例子 杂网络基本特征 实践表明，现实社会和自然界的许多系统普遍存在网络结构，比如：因特网、万维网、社交网络、政府机构的内部组织网络、铁路交通网络、捕食者之间的生态网络等等。这些 各个领域的网络 虽然在表现形式上、组织构成上不尽相同，但近年来的研究发现，这些系统网络还是有一些共同的内在结构特征 : （ 1） 小世界特性：现实世界的网络大部分既不是完全规则，也不是完全随机的，能够准确反应真实网络的模型就是由 入的 世界模型。在我们生活中经常会有这样的现象，即大部分人的朋友 都是和他们住在同一条街上的邻居或者是自己的同事、同学。很多人可能都遇到过这样的情况：因为某个机会认识了一个新朋友，在彼此聊天的过程中会突然发现他和你的某个亲戚或者同学原来也很熟悉，然后你们会惊奇的感叹“这个世界太小了”。“小世界”效应是现实网络的一个重要特征，它指的是网络中任意两点间的平均最短距离不与网络规模的增长成正比，也就是说每个节点的度都近似相等的均匀网络。 （ 2） 高聚集特性：聚集系数是衡量网络传递性的一个度量指标。通常指一 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 8 个节点的直接邻居间有边相连的可能性。从网络的拓扑结构来看，这种传递性表示网络中普遍存 在着三角结构。研究人员发现，现实世界中真实网络的聚集系数要明显比具有相同度分布的随机网络高很多。真实网络有很多有趣的性质，比如更强的信号传导能力，更快的疾病传播速度等。 （ 3）节点度服从幂律分布：度分布是描述网络性质的一个重要统计量。结点 i 的度定义为与结点 i 连接的边的数目。在有向网络中，节点的度根据节点间指向的不同还分为入度 (出度 (节点的度的大小决定着它在网络中的重要性，可以说度越大，这个节点就越重要。一般用分布函数 描述网络中度分布的情况， 示的是一个随机选定节点的度为 k 的概率。研究人员发现，许多真实网络的度分布都遵循幂律分布，幂律分布也称为无标度分布，用幂律形式表示为 （ 2 其中， k 表示结点的度值， 为幂指数，一般介于 2 到 3 之间。一般地，结点度服从幂律分布的网络也被称作无标度网络，如 会网络等。 杂网络社区结构定义 生活中各种各样的网络存在于我们周围，但网络中的社区结构并不是抽象的。从社会网络、生物网络到信息网络，社区结构随处可见。 目前 ， 关于 复杂网络社区概念的定义并不是十分严格，因为其定义会受到应用领域的影响。那种认为在一个社区内的边的数量应该远多于图表中其他剩余节点之间边的数量的直觉概念形成了一种普遍的社区定义。这种直觉定义主要遵循了两个不同的目标：将内部联系最大化和把外部联系最小化。 一个网络中的社区（也称为群或单元）就是一组其内部有着较高边密度而组与组之间拥有较少连接边的顶点（也就是子图）。这种社区的定义比较模糊，对密度的定义也没有一个一致的意见。文献 24中介绍了一个更为正式的定义，把节点 i 的度j k，这里 A 是 G 的邻接矩阵，如果节点 i 和 j 之间有一条边相连，则为 0。考虑网路 G 的一个子网络 ,节点 i 属于该子网络 S ，节点 i 的度包含两个分量，即 （ 2 其中 表示节点 i 连接子网络 S 中其他节点的边的条数，而 表示节点 i 连接子网络 S 外其他节点的边数。 Sj Sj 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 9 如果对于任意节点 i ，子网络 S 满足 （ 2 则称 S 为该网络的强社区结构。 如果子网络 S 满足 （ 2 则称 S 为该网络的弱社区结构。 因此，在一个强社区结构中，该社区内任意一个节点与这个社区内部其他点的连接，比它与该社区外部所有点的连接要紧密。在一个弱社区结构中，社区内部的边数之和大于社区边界上的边数之和。在本文中，我们将采取弱社区的概念，也就是说社区被定义为一组内部联系多于不同群之间联系的节点。 典社区结构划分方法 优化算法定义了一个目标函数，将图分为若干子图，并试图将这一目标最大化以实现网络的最佳划分 25在优化算法中，有几种方案是由进化技术演变而来。很多方法采用了多目标进化算法来分割图 或是在度量空间对目标进行分群。下文中，我们首先回顾一下来自物理和数据挖掘领域的主要算法，然后再看一下多目标进化分群方法。 目前最有名的算法之一是由 2002 年提出的 法 6。该算法通过 反复识别和删除社区间连接的策略 对网络进行反复分割。采用边介数这个度量标准来选择要去除的边。其中 边介数就是指网络中经过每条边的任意两点间最短路径的条数。 观察发现，如果两个社区有几条边相连，那么所有从一个社区内的节点到另一个社区内的节点之间的路径都将经过这几条边，边介数的提出即 是基于这一特点。由于路径决定边介数分值，因此通过计算所有经过每一个边的介数，去除分值最高的边，网络内部的联系即被打破。多次重复此过程，进而将 整个网络分解为 更小的组成部分，直到边消失。 法能更准确地划分社团结构，弥补了一些传统算法的不足，但是， 由于边介数的计算开销过大 ， 法具有很高的时间复杂性 2 。并且在一般的现实网络中很难知道社区的具体 数目，所以 法无法判断分解要执行到什么时候为止，它同样缺少一个指标来评价划分结果是否最优。因此， 出 需要一个评估网络分区质量的标准。为此，他们提出了 Si , 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 10 模块度（ 概念 （将在后面章节中给出模块度的正式定义）作为衡量网络划分好坏的标准 28。通俗来说，模块度定义为网络中连接两个同种类型的节点的边的比例减去相同划分结构下任意连接这两个节点的边的比例的期望值。因此，该算法要计算网络每个划分社区对应的模块度。作者还指出，当社区结构已知时，模块度峰值的位置与期望中的网络 分区高度一致。经过改进后的法不需要多余的信息来判断所划分的社区结构是否符合实际，但还是有一些缺点，如时间复杂度较高，为 O(所以更适合于分析中等规模的网络。不过 法首次发现了复杂网络中普遍存在的网络社区结构 ， 启发了其他研究者对这个问题的深入研究和探索。在复杂网络社区划分问题的研究中有着不可替代的重要意义。 法虽然在划分准确度上有了很大提高，但它只适合于中等规模网络的局限性导致应用领域有限。尤其现在对互联网、博客网、移动数据网等大型网络的研究越来越多，就 对算法提出了更高的要求，而传统 法明显不能满足需要。 为，既然模块度的峰值相当于较好的网络分区，只需要对模块度进行优化即可实现网络的最佳划分。为此，在 法的基础上， 出一种快速算法 12。 这是一种基于贪婪算法思想的将模块度数值增长最块的社区合并在一起的凝聚算法。 该算法经过一次合并就计算相应的一个模块度，直到合并结束，在所有得出的模块度中，选取值最大的就对应着最优的划分。该算法的时间复杂度为 。 算法如下： 初始化网络，将每个节点作为一个社区，即有 n 个社区。初始的 果 节点 i 和 j 之间有边相连 其他 ，其中i 的度， m 为网络中总的边数。 依次就有边相连的社区两两合并，同时计算合并后的模块度增量 2 2( )ij ji i j ji i jQ e e aa e （ 2 对上述步骤重复执行，不断合并社区，最终使整个网络成为一个社区。 整个算法结束后就能得出一个表示网络社区划分的树状图，只要任意选择一个位置断开就能得到不同的网络社区结构。 ,0,2/1 州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 11 为了进一步提高算法的速度， 人在 速算法的基础上提出了一种新的贪婪算法（ 15。算法在计算网络模块度时用了另一种思路，即采用了堆的数据结构。 人发现，在实际网络中往往存在不少不相连的社区，合并这样的社区并不能影响模块度 Q 的值，反而消耗了时间和存储空间。因此，提出直接构造一个模块度的增量矩阵通过更新的元素来改变 Q 值。该算法在稀疏网络上的时间复杂度为 已接近线性复杂性，可以处理百万级节点规模的网络。算法用到了三种数据结构：模块度增量矩阵最大堆 H 及辅助向量法步骤如下。 初始化：同 速算法一样也是初始化网络为 n 个独立社区。此时 ,有 Q =0。初始的如果节点 i 与 j 之间有连 边 其他 其中i 的度， m 是网络的总边数。初始的的元素满足 如果节点 i 和 j 相连 其他 最大堆 H 就是由这个初始的模块度增量矩阵每一行的最大元素组成。 从最大堆 H 中选择最大的对相应的社区 进行合并，同时更新 H 和 重复上述步骤直到所有节点都属于一个社区为止。 在算法执行 过程中会发现模块度 Q 的最大值是唯一的，当的最大元素都为负数时，模块度 Q 的值就会呈下降趋势。因此，这个时候就没有必要再进行合并，此时的社区结构就是实际网络的结构。由于采用了堆结构，算法的计算速度有了显著的提高。 发式优化算法 所有的启发式优化方法在本 质上都是迭代方法。不同于凝聚方法，这种方法搜索过程遵循的思路简单而直接，在社区结构划分中通过节点移动和社区的分裂或合并直接搜索模块度的最大可能值。常用的启发式优化算法包括模拟退火算法、遗传算法、粒子群优化算法等。 人提出了一个名为 基于模块度优化的划分较大网络的方,0,2/1 ,0,2/2/12州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 12 法 29。这一算法由两个迭代重复的过程组成，直到无法改进为止。假设网络是一个有 N 个节点的加权网络。开始的时候，每个节点都作为一个单独的社区。移动节点时首选这个节点周围的社区，如果能将节点移至模块度增加最大的社区中就执行，否 则不移动。这一过程不断重复，直到没有可以改善模块度的节点移动。值得注意的是，算法的输出取决于节点的排序。选择一个合适的顺序可以提高计算效率，因此这个问题是值得研究的。 移动一个孤立的节点 i 到社区 C 中所增加的模块度 Q 可以很容易得出 （ 2 其中 是社区 C 中链接权重的总和， 是 C 中易发生改变的节点链接的权重和，i 的链接权重总和， i 到 C 中节点链接权重的总和， m 是网络中所有链接权重总和。实际上，通过从 i 所在社区中移除它来改变模块度，而后移动它到邻近的社区。 第二个过程将建立一个由被认为是新节点组成的网络，如果 a 社区的一个节点与 b 社区的一个节点之间有一个边，那么两个社区就存在一种联系。可以对这个网络进行衡量，在这种情况下， a 和 b 之间边的权重是相关社区节点之间联系权重的总和。同一社区节点之间的连接导致在新网络中这个社区自循环。一旦第二个阶段完成，它可能再次运用算法的第一个阶段产生加权网络并迭代。在这一点上，这一算法可以反复进行直到无法通过以上节点的移动来改善模块度。我们用一个过程来表示这两个阶段的组合。每一个 过程中社区数量都在减少，因此，计算时间大多用于第一个过程。这个过程一直重复直到没有更多的改变为止，而且模块度得到最大值。如下图所示： 图 2图形化 法步骤 222,222222it ot 1 51 01 21 41 310428673591 11 51 01 21 41 31 41 643114212 6 1 43模 块 度 优 化社 区 聚 合过 程 1 过 程 2 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 13 每一个过程包含两个阶段，一是由只允许局部社区的改变来优化模块度，二是为了建立一个新的网络社区，发现的社区被聚合。这种变化不断重复，直到模块度不可能再增加。 这种方法的优点是运行效率很高，但问题是社区划分结果受节点的移动顺序影响较大。 极值优化算法（ 另一种启发式优化算法。算法的目标也是求解模块度最优值，通过 用局部变量来代替全局变量的调整加快运算速度。我们首先要解决的问题是用什么样的一个局部变量来代替全局变量。在模块度的优化问题中，这个局部变量的取值应该与每个节点对模块度的贡献大小有关。然而这种方式有两个缺陷，一是划分结果过多的取决于初始网络的划分情况；二是所得结果容易陷入局部极值而无法得到全局最优值。 出了一种改进算法 30。这种算法搜索模块度最优值的办法是把网络随机平均分成两部分，计算所有节点适应度并选取其中值较低的节点，然后将其从一个社区移动到另一社区。 此算法中，当网络的 模块度不再增加的时候就停止迭代。但事实上，模块度是否会继续增加是很难定量判断的。在算法具体实现中，如果模块度在 n 步内都没有继续增加，就认为此时模块度已经达到了一个局部极大值，这里 是一个设定常数， n 为网络的节点个数。其时间复杂度为 此外， 法实际上是一种二分算法，每一次分裂并不能保证得到最好的分裂结果，即不能保证得到最好的社区结构。 他社区结构分析算法 出了一种融合了光谱分析和模块度优化的聚类算法（简称 法）31。该算法在划分网络的初期同样也引入了随机游走的概念，然后采用了不断将两个社区合并的聚类算法。在合并的过程中，为整个模块度贡献最小的节点将被选中并加入到模块度增长最大的群中。转移概率矩阵 M 定义为 1 （ 2 其中 I 是单位矩阵， D 是一个 j D 1的对角矩阵 ，这个过程由随机游走执行，定义为 1 （ 2 其中 包含每个随机游走概率分布的矩阵。 j 在 t 时刻节点 i 上的概率。通常这个过程反复执行直到静止状态。尽管如此，随机行走的暂 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 14 态也是值得注意的。因此这个过程不断重复直到得到 止， T 设为 3。因此每一个随机游走已 经有 3 次跳跃，这是最小的跳数完成原点的最短路径。一旦随机过程完成，每个节点 i 被分配到组 j 中，与 G 中 i 行的最大列相符。通过这样的过程，最初的 n 个顶点被分成大约 s 个组，而同一组内的所有顶点拥有最多相同的随机游走者。这意味着他们属同一个社区。尽管这种方法不够完美，允许大幅度的减少初始组数目。由于随机游走者可以排除其他人，组的最终数目可能不完全符合 s 。当所有节点通过一个随机游走者 i 访问的同时也常被其他随机游走者访问，就排除 i 。此外，由于马尔科夫过程只迭代 T 次，不能保证所有节点都至少被访问一次，而这种情况下一个有单一节点的额外的组就被创建了。 考虑当前组的数目，在最坏的情况下合并线性时间内即可完成，为 此外，运算需要进行 1s 次，所以建立 层次的复杂度为 2该算法在中大型网上运算时间及聚类质量都要好于 速算法。 出了一个基于 S 模块的社区适应度的概念发现重叠和分层社区结构的方法 32。把社区 S 内节点的内部度和外部度设为么社区 S 的适应度 可以定义为 Si 2 其中 被称为解析度参数，是一个正实值参数，用来控制社区的大小。对一个固定的 ，当 0Sk 到其最大值。社区适应度的概念被用来逐个划分社区，作者引入了节点适应度的概念。 该算法首先是随机选取一个节点，把该节点假设为社区 S ，然后在 S 以外的所有相邻节点中画一个圈以选取加入 S 的相邻节点。通过计算每个节点的适应度来进行选取。然后重新计算每个节点的适应度，结果为负值的节点将被从 S 中删除，持续这一过程直到 S 里所有节点的尚未包含在内的相邻节点的适应度都为负数为止。在得到 一个社区后，再选取一个新的节点，重复上面的步骤，直到所有的节点都被分配到至少一个群。作者发现当 1 的时候，所得出的分区都是相关联的。不过，作者引入了一种以稳定性概念为基础的选取分区的标准。如果一个分区在一定范围的 值上传递，那么这个分区就被认为是稳定的。这一范围越大，分区越稳定，得出的结果越好。 目标聚类方法 近些年利用多目标优化来对数 据进行聚类越来越受到关注 33尽管很少有 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 15 人想到利用其来划分网络。 出了一种利用多目标聚类算法来分析数值和分类数据的参考方法，名为 动多目标聚类法 (35。 法包含两个主要阶段，在初始聚类阶段， 法用一个多目标进化算法来优化两个互补的聚类目标。第一阶段输出一组符合两个目标之间不同折衷的相互非支配的解，以及不同数量的群。第二个阶段即模型选择阶段， 法分析折衷曲线的形状并与随机聚类得到的折衷进行比较。该算法所选 的两个目标函数一个是基于群的紧密度，另一个是基于群的连通性。 首要目标即群的紧密度通过计算分区的总体偏差来表示，也就是数据项与其所在的群中心总距离最小化，即 （ 2 其中 C 是群的集合，k是群 .,. 是所选的距离函数（这里是欧氏距离）。 第二个目标是将群的连通性最小化，对每个群数据点的相邻最近的被放置在同一群内的点的数量进行评估，即 （ 2 其中 i 个数据的最近邻， N 是聚类数据集的大小，而 L 是一个有助于连通性测量的决定邻居数量的参数。 该算法采用了 出的基于轨迹的邻接表示法 38，使用一种基于减少运行时间的最小生成树的解的特殊初始化。多目标遗传算法也引用了这一方法，并将在下一章节中进行描述。由于多目标聚类返回的是一组聚类解，因此要求解决方案的范围应该尽可能的小，或者只有一个最好解被自动的选择。法使用了一种能够在一组方案中识别出有用的解决方案的方法，选择一个单一的解决方案然后自动发送一个估计的数据集中原有群的数量。虽然法并不是专门为网络划分而发明的，但我们可以把网络的邻接矩阵设想为相似矩阵，利用 法在图上进行划分。 i kk e v , :/,01, o n , 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 16 人提出了一个用图分割优化三 个不同目标的方法 39。当两个相连的节点位于不同的组时，目标将把边的净损量，小组差异的规模和群的分布最小化。作者强调了图中的区域概念，被看作相邻节点的组。因此一个染色体就是一批节点，每个节点都是以其在图中的位置来表述的。这种算法可以把图分成可变数量的若干区域，不过区域的范围和每个区域内的节点数量必须被固定为输入参数。 近期， 人提出了一种专门对网页用户会话进行分类的多目标进化算法 40。 该算法所得的群被用来在网页推荐系统中表示使用模式。 以一个带权值的无向图来表示用户访问过的网页的序列，每一个序 列为一个节点，连接两个序列的边的权值由计算两个节点的相似性得出。这种名为 算法采用了与法 相同的表示，但是优化的两个相互矛盾的目标分别是 者将类内物体相似性最大化的同时将类间物体相似性最小化，后者计算同一类内的点的平均线条指数。为了得到相似矩阵，首先原始的务器日志文件会被转换成用户会话中的说明附录。用户会话集分为训练集和测试集。序列的相似矩阵通过基于 方法计算训练集中两两相似的用户会话来得到。衡量会话相似性的 基本思想是使用动态编程技术，以便找到两个序列之间的最佳匹配。找到两个序列中的最优列后，用一个相似性分值函数来评估这些序列的两两相似性。相似性分值函数返回值在 0 到 1 之间，这里 1 表示两个用户会话完全相同，而 0 说明它们完全不同。 数旨在最大化每个子图内的相似性，而试图最小化子图之间的相似性，即 （ 2 等式中 k 是群的数量， ,是顶点之间连边权重的总和。 是节点 i 与 j 之间边的权重。这个目标是最小化。 下面的公式来计算，即 （ 2 其中 顶点 i 的轮 廓值，i 和其他群之间的最小平均差异。差异值由 1 来计算。每个群（ 2 其中 群终 计算为 u u tM i n M a ,_ ab m j 1 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 17 （ 2 群验证指数，可以用于比较具有不同群数目的聚类解决方案的质量。它的值在 1,1 之间。 章小结 本章介绍了复杂网络的基本特征、社区发现问题的定义，并对几种有代表性的社区发现算法进行了分析。重点研究各种社区发现算法的优缺点，为本文在社区划分方法的研究上提供了很大的帮助。 在下一章节中，我们将把社区划分问题作为一个多目标优化问题来进行阐述。 kj j 1 兰州大学硕士研究生学位论文 基于多目标遗传算法的复杂网络社区划分 18 第三章 多目标优化问题与复杂网络社区划分 复杂网络社区划分可以被当做一个优化问题来处理，考虑到多目标优化算法在处理问题中的优势，把复杂网络社区划分问题看做一个多目标优化问题，构造两个目标函数，通过对这两个函数的优化折衷求解最优的划分结果。 目标优化 目标优化问题及其数学描述 最优化问题是工程实践和科学研究中主要的问题之一 。 其中，仅有一个目标函数的最优化问题被称为单目标优化问题 ，但现实世界中许多优化问题的处理都不仅仅是一个目标函数。当不同目标之间存在矛盾和冲突时 ， 处理的难度就增加了。的确在自然科学、工业制造、城市布局等很多重要的决策问题中都存在多个目标需要在固定范围内同时达到最佳的优化问题，这些问题被称为多目标优化问题 ( 多目标优化也称为多标准优化，多绩 效或多向量优化问题。 对于多目标优化问题，一个解可能对于某个目标来说是较好的，而对于其他目标则可能是较差的 。 因此， 找出一个能同时满足所有的优化目标的解就成了解决问题的核心部分，而这个解一般都是一个不确定的点集。这样就 存在一个 折衷 解的集合，被称为优解集（ 非支配解集（ 因此多目标优化的任务就是想办法的得出这个解集的分布情况，然后根据问题的具体情况找出符合要求的解。经济学家 1986 年提出了 优解的概念 41。 优是指资源分配的一种状态，即如果现有的境况在某一方面保持不往差的方向变，那么也就不可能使某它方面的情况有所改进。 进则意味着一种变化，即保持现有境况的所有方面都不变坏的前提下，使得其中一个方面有了好的变化。也就