复杂网络社团发现算法的研究毕业论文.doc

复杂网络社团发现算法的研究毕业论文目录第一章绪论11.1 复杂网络的研究背景11.1.1 从七桥问题开始11.1.2 复杂网络近代的研究21.2 复杂网络社团结构研究的现状31.3 本文的研究内容以及文章结构6第二章复杂网络的基本概念以及网络拓扑的基本模型72.1 复杂网络的基本概念72.1.1 网络的图表示72.1.2 平均路径长度82.1.3 聚类系数82.1.4 精准度92.1.5 复杂网络社团结构定义92.2 网络拓扑基本模型和性质102.2.1 小世界模型102.2.2 无标度网络模型112.2.3 模块性与等级网络12第三章 复杂网络中的社团结构 143.1 分级聚类143.1.1 凝聚算法143.1.2 分裂算法153.2 迭代二分法153.2.1 Kernighan-Lin 算法153.2.2 谱平分法163.3 其他经典算法173.3.1 GN（Girvan-Newman）算法173.3.2 Newman快速算法173.3.3 Radicchi算法17第四章 基于随机游走的社团发现算法194.1 随机游走算法的基本原理194.1.1 随机游走算法的相似度矩阵获取194.1.2 随机游走算法的矩阵融合204.1.3 矩阵元素融合方式214.2 随机游走算法的代码编译过程224.2.1 随机游走算法的相似度矩阵的获取224.2.2 随机游走算法的相似度矩阵融合23第五章 随机游走算法在社团划分中的应用255.1 随机游走算法对复杂网络的划分255.1.1 已知社团结构的复杂网络255.1.2 对复杂网络的划分265.2 随机游走算法的复杂度28第六章 基于随机游走算法的程序优化296.1 随机游走算法的复杂度的优化296.2 随机游走算法的应用于加权网络30第七章总结与展望317.1 总结317.2 对未来的展望31参考文献34致谢35II北京邮电大学本科毕业设计（论文）第一章 绪 论复杂网络一般指节点众多、连接关系复杂的网络。由于其灵活普适的描述能力, 能够广泛应用于各科学领域对复杂系统进行建模、分析, 近年来吸引了越来越多的人对其进行研究。随着研究的深入, 人们发现许多实际网络均具有社团结构,即整个网络由若干个社团组成, 社团之间的连接相对稀疏、社团内部的连接相对稠密。社团发现则是利用图拓扑结构中所蕴藏的信息从复杂网络中解析出其模块化的社团结构, 该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化, 更准确地理解复杂系统的组织原则、拓扑结构与动力学特性, 具有十分重要的意义。自2002 年Girvan 和Newman 基于边介数提出GN 算法以来, 国际上掀起一股社团发现的研究热潮, 来自生物、物理、计算机等各学科领域的研究者们带来了许多新颖的思想和算法, 并广泛应用于各个学科领域的具体问题中。1.1复杂网络研究背景1.1.1 从七桥问题开始近年来复杂网络研究的兴起，使得人们开始广泛关注网络结构复杂性及其与网络行为之间的关系，要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一工具。这种工具在数学上成为图(graph).任何一个网络都可以看做是由一些节点按某种方式连接而构成的一个系统。具体网络的抽象图表示，就是用抽象的点表示具体网络中的节点，并用节点之间的连线表示具体网络中节点间的连接关系。实际网络的图表示法可以追溯到18世纪伟大的数学家欧拉(Euler)对著名的“Konigsberg 七桥问题”的研究。Konigsberg 是东普鲁士（现俄罗斯）的一个城镇，城中有一条横贯城区的河流，河中有两座岛，两岸和两岛间共有七座桥，一个人能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地？1736年，欧拉仔细的研究了这个问题。他用数学抽象法，将被河流分隔开的四块陆地抽象为四个点，分别用A、B、C和D表示，而将七座桥抽象为连接四个点的七条线，分别用a、b、c、d、e、f、g表示，这样就得到了四个点和七条线构成的一个图，如图（图1-1）所示。图1-1 七桥问题于是欧拉考虑如果一笔画出图1-1，则七桥问题迎刃而解。可以想象，能一笔画出的图形，一定只有一个起点和一个终点（这里要求起点和终点重合），中间经过的每一点总是包含进去的一条线和出去的一条线，这样除了终点和起点外，每一点都只能有偶数条线与之相连。因此，如果要求起点和终点重合的话，那么能够一笔画出的图形中所有的点都必然有偶数条线与之相连。从图1-1中四个点看，每个点都是有三条或五条线通过，所以不能一笔画出这个图形，就是说不重复的一次走遍七座桥是据对不可能的。欧拉的七桥问题的抽象和论证思想，开创了数学中的一个分支-图论（graph theory）的研究。因此，欧拉被公认为图论只父，而图1-1被称为欧拉图。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构域网络心智密切相关。1.1.2 复杂网络近代的研究20世纪90年代以来，以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。从Internet到WWW，从大型电力网络到全球交通网络，从生物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治和社会关系网络等，可以说；人们已经生活在一个充满着各种各样的复杂网络的世界中。人类社会的网络化是一把“双刃剑”：它既给人类社会生产与生活带来了极大便利，提高了人类生产效率和生活质量，但也给人类社会生活带来了一定的负面冲击，如传染病和计算机病毒的快速传播以及大规模的停电事故等。因此，人类社会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。长期以来，通信网络、电力网络、生物网络、社会网络等分别是通信科学、电力科学、生命科学、社会学等不同学科的研究对象，而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。从20世纪末开始，复杂网络研究正渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络的定量与定性特征的科学理解，已成为网络时代科学研究的一个极其重要的挑战性课题，甚至被称为“网络的新科学(new science of networks)”1,2 。传欧拉七桥问题之后的近两百年中，数学家们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。随着近年来计算机存储能力和处理数据能力的增强，以及一些大规模系统的数据库的建立，人们重新获得了真实网络的特征数据，发现大多数真实网络既不是规则的，也不是随机的，而是呈现一定规律的复杂网络。复杂网络之所以复杂，不仅在于网络规模的巨大，网络结构的复杂而且网络在时间、空间上都具有动态的复杂性，网络行为也具有复杂性。许多真实系统都可以用网络的形式加以描述，一个典型的网络是由许多结点与连接结点之间的边组成的。结点代表系统中的个体，边则表示结点之间的作用关系。如WWW网络可以看成是网页之间通过超链接构成的网络；Internet网络可以看作不同的计算机通过光缆连接构成的网络；科学家合作网络可以看作不同的科学家合作关系构成的网络；基因调控网络可以看作是不同的基因通过调控与被调控关系构成的网络。这些真实网络的普遍存在，促使来自不同学科领域的科学家共同致力于复杂网络的研究。这些学科领域包括复杂性科学、数学、物理、生物和计算机等。复杂网络的研究可以使人们更好地了解现实世界的复杂系统，为设计具有良好性能的网络提供依据。同时复杂网络的理论成果将会广泛地应用到生物、计算机等各个学科领域。复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：大量的真实网络的实证研究，分析真实网络的统计特性；构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；研究网络上的动力学行为，如网络的鲁棒性和同步能力，网络的拥塞及网络上的传播行为等。1967年，美国哈佛大学社会心里学家Milgram做了一个实验，在美国将一封信通过熟人找熟人的方式传递到目标者，发现平均最短经过6人就可到达，这就是著名的“六度分离(six degree of separation)”现象，它揭示了社会网络的小世界特性。而在万维网中，平均只需点击19次超级链接，就可以从任意一个网页到达其它网页。近年来，随着大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络的研究进程大大加快。人们对社会系统、大型基础性设施和生物系统中大量的真实网络数据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现支配和影响这些复杂系统的动力学和演化规律的内在本质。复杂网络的理论及实证研究的发展将会对网络安全、网络控制、疾病传播的控制与防御、社会中人的行为动力学的研究和生物网络的演化机制研究等产生重要影响。1.2 复杂网络社团结构研究的现状随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区或“组构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元。发现这些网络中的社区有助于我们更加有效地理解和开发这些网络。在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如KL算法、谱平分法、随机游走算法和派系过滤等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法和基于边介数度量的分裂算法等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法、基于信息论的算法、基于PCA的算法和最大化模块度算法等。下面简要介绍一下几种具有代表性的算法。1970年，Kernighan和Lin提出一种试探优化法划分网络中的社区结构，简称K-L算法。它是一种基于贪婪算法原理将网络划分为两个大小已知的社区的二分法。其基本思想是为网络的划分引进一个增益函数Q，增益函数定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使Q值最大的划分方法。1990年，Pothen等基于图的Laplace矩阵的谱特征提出一种将网络划分为两个社区的二分法瞻目。该算法的理论基础是不为零的特征值所对应的特征向量的各元素中，同一个社区内的结点对应的元素是近似相等的。因此可以根据网络的Laplace矩阵的第二小特征值将其分为两个社区。2001年，Girvan和Newman提出了一种基于边介数的分裂算法，简称GN算法。该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径数目。该算法的复杂度非常高，2003年Tyler等在GN算法的基础上提出了一种新的算法圆1，它可以显著提高计算速度，但也降低了计算的准确性。GN算法是以网络中的每一个结点i为源结点，来计算它到其他结点的最短路径，并以这些最短路径经过每条边的次数作为该边的介数。而Tyler等人提出，以网络中某个结点集内的结点为源结点来计算边的介数也可以达到较好的效果。2004年，Newman把GN算法推广到了加权网络中。3 2003年，Wu和Huberman基于电阻网络的性质提出了W_H算法，其主要思路为将网络中每条边想象成电阻为单位值的导线，且在网络中任意选择的两个结点上加上单位值的电位差。Wu和Huberman认为，如果网络可以分解成两个社区，那么电位谱在连接两个社区的边的两端会产生一个较大的间隙。因此，首先确定电位谱的最大间隙处的某个电位值，然后根据每个结点处的电位是否大于该值而确定结点属于哪个社区。该算法的一个重要特点是可以用来确定包含指定结点的社区，而无须计算出所有的社区。2004年，Newman提出一种基于贪婪法思想的凝聚算法，并称这种算法为快速算法。该算法是在使得模块度不断增加的基础上进行，即每次合并沿着使模块度增多最大和减小最少的方向进行。算法总的复杂度为O(m+n)n)，对于稀疏网络则为O()，其中n为网络中结点的个数，m为网络中边的条数。在Newman快速算法的基础上，Clauset、Newman和Moore等人采用堆的数据结构来计算和更新网络的模块度，提出了一种新的贪婪算法，称为CNM算法。该算法的复杂度只有O(n)，已接近线性复杂性，可用来分析大型复杂网络数据。同样为了最大化网络的模块度，2006年Newman基于模块度矩阵提出一种划分网络中社区结构的谱算法，并于2008年把该算法推广到有向网络中。2005年，Pons和Latapy提出一种利用随机游走划分网络社区结构的算法，算法的初始条件为每个结点为一个单独的社区，然后逐步合并可使结点和它所在社区之间的平方距离均值达到最小的两个社区。每一步都要更新社区之间的距离，其中两个结点之间的距离对应于它们的相似度，即在一个离散的随机游走过程中，它们之间的方向转移概率。以上所述算法最终目的均是把网络划分为若干个相互分离的社区，但是现实中很多网络并不存在绝对的彼此独立的社区结构，相反它们是由许多彼此重叠且相互关联的社区构成。比如，每个人根据不同的分类方法都会属于多个不同的社区(如学校、家庭、不同的兴趣小组等)。在这种情况下，很难单独的将这些社区划分出来。因此，Palla等人提出了一种派系过滤算法(clique Percolation Method)来分析这种互相重叠的社区结构。尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。1.3本文的研究内容以及文章结构本课题主要研究复杂网络中的社区结构划分。首先，针对无权的复杂网络，提出了随机游走的概念，在此基础上提出一种有效的划分社区结构的算法。实验结果表明该算法是可行且有效的。最后把这种算法推广到加权的大型复杂网络中，并把算法应用实际的加权网络数据中，验证了推广算法的可行性和有效性。综上所述，本文主要研究内容共分为两个部分：第一部分提出了一种基于随机游走的复杂网络社区结构划分算法；第二部分把此算法推广到加权的复杂网络中。具体内容如下：第2章 介绍了一些复杂网络的图表示、度分布、平均最短路径和社区结构等基本概念和基本性质。介绍一些基本的网络拓扑模型及其性质，包括规则网络、随机图、小世界网络、无标度网络等。第3章 主要针对Internet 中的拓扑结构提出来一些模型。介绍复杂网络的社团结构及其搜索算法。大多数的实际网络都具有社团结构。也就是说，一个大的网络可以分成若干个字裙，在这些子群的内部的连接较为紧密，但是各个子群间的连接却较为稀疏。找到并且分析这些子群，有助于我们更好地理解网络的全局行为第4章 主要提出了基于图论的随机游走（random walk）算法，研究随机游走算法的基本原理，以及对随机游走算法的编译。第5章 主要介绍了random walk 算法对已知社团结构的复杂网络进行社团结构的划分，并比较划分社团结构的准确度；同时给出算法的复杂度的分析。第6章 主要介绍了在random walk算法基础上的改进，使random walk算法能够实现：对有权的复杂网络的社团结构的划分；减少算法的复杂度。第二章 复杂网络的基本概念以及网络拓扑的基本模型2.1复杂网络的基本概念近年来，人们在刻画复杂网络的统计特性上提出了许多概念和方法，其中有三个基本的概念：平均路径长度（average path length）、聚类系数（clustering coefficient）和度分布（degree distribution）。实际上，Watts和Strogatz提出小世界网络模型的初衷就是建立一个既具有类似于随机图的较少的平均路径长度，又具有类似于规则网络的较大的聚类系数的网络模型。另一方面，Barabasi和Albert 提出的无标度网络模型，则是基于许多实际网络的度分布具有幂律(power-law)形式的事实。在这里先介绍复杂网络的这几种性质，其他性质后面会陆续介绍。2.1.1网络的图表示一个具体网络可以抽象为一个由点集V和边集E组成的图G =（V，E）。节点数记为N = | V |，边数记为M = | E |。E中每条边都有V种的一堆点与之相对应。如果任意点对（i，j）和（j，i）对应同一条边，则该网络称为无向网络（），否则称为有向网络。如果给没调表都赋予相应的权值，那么该网络就被称为加权网络（），否则为无权网络。当然无权网络也可以看做每条边权值都为1的等权网络。此外，一个网络中还可能包含多种不同类型的节点。图2-1给出了几种不同类型的网络的例子。在图论中，没有重边和自环的图称为简单图（simple graph）4 。图2-1 不同类型网络的例子(a) 单一类型节点和边的无向网络 (b)不同类型节点和边的无向网络 (c)节点和边权重变化的无向网络 (d)有向网络2.1.2 平均路径长度网络研究中一般定义两节点i和j间的距离为连接两个节点的最短路径的边数，网络的直径为任意两点间的距离的最大值，记为D，即 （2-1）网络的平均路径长度L则定义为任意两个节点对之间距离的平均值，即 （2-2）其中N为网络节点数。网络的平均路径长度也成为网络的特征路径长度（characteristic path length）。它描述了网络中节点间的分离程度，即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，称之为“小世界效应”这一提法来源于著名的Milgram“小世界”试验4 。图2-2 一个简单网络的直径和平局路径长度2.1.3 聚类系数聚集系数C用来描述网络中节点的聚集情况，即网络有多紧密。比如在社会网络中，你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。一般的，假设网络中的一个节点i有条边将他和其他节点相连，这个节点就称为节点i的邻居。显然，在这个节点之间最多可能有(-1)/2条边。而这个节点间的实际存在的边数为和总的可能的边数(-1)/2之比就定义为节点i的聚类系数，即 （2-3）从几何特点上看，上式的一个等价定义为 （2-4）其中，与节点i相连的三元组是指包括节点i的三个节点，并且至少存在从节点i到其他两个节点的两条边（图2-3）。5图2-3 以节点i为顶点之一的三元组的两种可能形式2.1.4 精准度精准度是用来粗略的衡量社团发现算法对于划分复杂网络的社团结构的准确度的参数。以上所述算法最终目的均是把网络划分为若干个相互分离的社区，但是现实中很多网络并不存在绝对的彼此独立的社区结构，相反它们是由许多彼此重叠且相互关联的社区构成。给定一个由n个节点组成的复杂网络，其中每个节点v都赋予一个真实的标签来表示其属于的社团。对于社团划分的准确的计算如下所示，假设一个复杂网络已经分成数个社团，对于每个社团i，遍历i中所有的节点并找出每个节点最常发生的真实的标签，这个标签便被称作社团中节点v的预期的标签。而精确度的公式也如下所示： （2-6）其中 （2-7）2.1.5 复杂网络社团结构定义近几年来，复杂网络的研究正处于蓬勃发展的阶段，其思想已经充斥到科学和社会的每一个角落。随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质社团结构。也就是说，网络是由若干个“群(Group)或“团(Cluster)”构成的。每个群内的结点之间的连接非常紧密，而群之间的连接却相对比较稀疏，如图2-4所示。图中的空手道俱乐部网络包含两个社团，分别对应图中不同节点形状的部分。在这些社区内部，结点之间的联系非常紧密，而社区之间的联系就稀疏的多。图2-4 空手道俱乐部复杂网络的社团结构2.2网络拓扑基本模型和性质最简单的网络模型为规则网络，其特点是每个节点的近邻数目都相同，如一维链、二维晶格、完全图等。随机网络模型的提出是网络研究中的重大成果，但它仍不能很好的刻画实际网络的性质，人们又相继提出了一些新的网络模型。2.2.1 小世界模型实证结果表明，大多数的真实网络具有小世界性（较小的最短路径）和聚集性（相对较大的聚集系数）。然而，规则网络虽具有聚集性，平均最短路径却较大。随机图则正好相反，具有小世界性，但聚集系数却相当小。可见规则网络和随机网络并不能很好展现真实网络的性质，这说明现实世界既不是完全确定的也不是完全随机的。Watts和Strogatz在1998年提出了一个兼具小世界性和高聚集性的网络模型6，它是复杂网络研究中的重大突破。他们通过将规则网络中的每条边以概率p随机连接到网络中的一个新节点上，构造出一种介于规则网络和随机网络之间的网络（简称WS网络），它同时具有较小的平均路径长度和较大的聚集系数，而规则网络和随机网络则分别是WS网络在p为0和1时的特例。模型构造过程如图2-5所示!图2-5 WS小世界模型随机化重连过程2.2.2 无标度网络模型尽管小世界模型能很好的刻画现实世界的小世界性和高聚集性，但对小世界模型的理论分析表明其节点的度分布仍为指数分布形式。实证结果却表明对于大多数大规模真实网络用幂率分布来描述它们的度分布更加精确。幂率分布相对于指数分布其图形没有峰值，大多数节点仅有少量连接，而少数节点拥有大量连接，不存在随机网络中的特征标度，于是Barabasi等人称这种度分布具有幂率特征的网络为Scale-free网络。为解释Scale-free网络的形成机制，Barabasi和Albert提出了著名的BA模型6。他们认为以前的网络模型没有考虑真实网络的两个重要性质：增长性和择优连接性，前者意味着网络中不断有新的节点加入进来，后者则意味着新的节点进来后优先选择网络中度数大的节点进行连接。他们不仅给出了BA模型的生成算法并进行了模拟分析，而且还利用统计物理中的平均场方法给出了模型的解析解。结果表明：经过充分长时间的演化后BA网络的度分布不再随时间变化，度分布稳定为指数为3的幂律分布。BA模型的提出是复杂网络研究中的又一重大突破，标志着人们对客观网络世界认识的深入。之后，许多学者对这一模型进行了改进，如非线性择优连接、加速增长、重绕边的局域事件、逐渐老化、适应性竞争等等。需要注意的是，绝大多数而不是所有的真实网络都是Scale-free网络。如有的真实网络度分布为指数分布截断形式等等。2.2.3 模块性和等级网络为了研究网络的模块性，我们需要相应的工具和度量以确定一个网络是否是模块化的，并且能够清晰的辨识一个给定的网络中的模块以及模块之间的关系。当然，模块便是并不是一件容易的事，因为无标度性质和模块性看起来似乎是矛盾的。模块式如何构成的呢？近期研究表明，模体（motif）可能是复杂网络的基本模块7-9。网络的高聚类性表明网络在局部可能包含各种由高度连接节点组成的子图(subgraph)。子图描绘了从局部层次刻画一个给定网络的互联的特定模式。为理解这点，我们考虑了一个完全规则的放鸽子，他的子图报刊很多正方形而不是三角形（图2-6）。这些正方形子图反映了方格子的基本特征结构，而在有明显随机性连接的复杂网络中时难以找到这种明显的有序特征的。也就是说，复杂网络可能包含各种各样的子图，这些子图所占的比率明显高于同一网络的完全随机化形式中这些子图所占的比例。这些子图被称为模体。图2-6 子图和模体BA模型的提出是复杂网络研究中的又一重大突破，标志着人们对客观网络世界认识的深入。之后，许多学者对这一模型进行了改进，如非线性择优连接、加速增长、重绕边的局域事件、逐渐老化、适应性竞争等等。需要注意的是，绝大多数而不是所有的真实网络都是Scale-free网络。如有的真实网络度分布为指数分布截断形式等等。接下来的问题是：一个网络中的不同模体之间是如何相互作用的？经验表明，特定的模体类型聚集在一起形成大的模体簇，这可能也是大多数实际网络中的一个通有特性10。为了说明许多实际系统中同时存在的模块性、局部聚类和无标度拓扑特性，需要哪家社模块以某种迭代的方式生成一个等级网络（hierarchical network）。研究表明，一些网络（如新陈代谢网络）中的拓扑模块确实是按等级组织起来的。需要注意的是，ER随机图和BA无标度网络都不具有等级拓扑，在这两类网络中的节点系数C(k)与该节点的度k无关。这点并不奇怪，因为在这两类网络的构造过程中并未包含有利于模块涌现的机制。第3章 复杂网络中的社团结构网络社团结构的研究已经有很长的历史。它与计算机科学中的图形分割（graph partition）和社会学中的分级聚类（hierarchical clustering）有着密切的关系。，前者主要包括Kernighan-Lin算法和基于图的Laplace矩阵特征向量的谱平分法(Spectral Bisection Method)；而后者则以著名的GN(Girvan-Newman)算法为代表。3.1 分级聚类分级聚类是寻找社会网络中的社团结构的一类传统算法，它是基于各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群。根据往网络中添加边还是移除边，该类算法又可以分为两类：凝聚算法（agglomerative method）和分裂算法（division method）11。3.1.1 凝聚算法凝聚算法的基本思想是用某种方法计算出各节点对之间的相似性，然后从相似性最高的节点对开始，往一个节点数位n而边的数目为0的原始空网络中添加边。这个过程可以中止与任何一点，此时这个网络的组成就认为是若干个社团。从空图到最终图的整个算法的流程也可以用世系图或者树状图来表示，如图3-1所示。底部的各个圆代表了网络中的各个几点。当水平虚线从树的底端逐步上移，各个几点也逐步聚合称为更大的社团，当虚线移至顶部，即表示整个网络就总体的称为一个社团。在该树状图的任何一个位置用虚线断开，就对应着一种社团结构。图3-1 凝聚方法通常采用树状图来记录算法的结果基于一系列相似性度量标准额凝聚方法已经应用于许多不同的网络。一些网络本身就有很多相似性度量标准。比如，在电影演员合作网络中12-13，如果两个演员出现在同一部电影中，他们之间就有一条边相连，这样就可以用有多少电影演员同时出现在同一部电影中来度量节点的相似性14。而另外一些网络虽然其本身没有相似性的度量，但是可以利用相关系数、路径长度或者一些矩阵的方法来设计一些适当的度量，本文涉及的随机游走算法便可以算得上一种凝聚算法。3.1.2 分裂算法相反的，在分裂算法中，一般是从所关注的网络着手，试图找到已连接的相似性最低的节点对，然后移除连接他们的边。重复这个过程，就逐步把整个网络分成越来越小的各个部分。同样的，可以在任何情况下终止，并且把此状态的网络看做若干网络社团的集合。与凝聚方法类似，利用树状图来表示分裂方法的流程，可以更好地描述整个网络逐步分解为若干个越来越小的子群这一连续过程。3.2 迭代二分法计算机科学中的一个典型问题，是将一个网络分解成若干结点数基本相等的子网，使得不同子网中的结点之间的连接数最少，称为图分割。图分割问题(GPP)可应用于并行计算机的处理器合理分配进程。实际应用中，大多数图分割方法均基于迭代二分法：首先将图按要求分割成2个子图，然后再分别对这2个子图进行分割，如此迭代下去直至获得所要求的子图个数。我们介绍两个最具代表性的迭代二分法：一是Kernighan-Lin算法，该算法使用贪婪策略对社区内以及社区间的边数进行优化，从而达到改进网络的初始分解的目的；另一个是基于图的Laplace矩阵的特征向量的谱二分法(Spectral Bisection Method)。3.2.1 Kernighan-Lin 算法Kernighan-Lin算法是一种试探优化法。它基于贪婪算法原理将网络划分为两个规模已知的社区。其基本思想是为网络的划分引进一个增益函数Q，Q定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使Q值最大的划分方法。整个算法可描述如下：首先，将网络中的结点随机地划分为已知规模的两个社区。在此基础上，考虑所有可能的结点对，其中每个结点对的结点分别来自两个社区。对每个结点对，计算如果交换这两个结点的话可能得到的Q的增益，然后交换最大的Q对应的结点对，同时记录交换以后的Q值。规定每个结点只能交换一次。重复这个交换过程，直到某个社区内所有的结点都被交换一次为止。需要注意的是，在结点对交换的过程中，Q值并不一定总是单调增加的。不过，即使某一步的交换会使Q值有所下降，但是仍然可能在其后的步骤中出现一个更大的Q值。当交换完毕后，便找到上述交换过程中所记录的最大的Q值。这时对应的社区结构就认为是该网络实际的社区结构。Kernighan-Lin算法最大的缺陷是要求事先知道两个社区的规模，否则，就很可能不会得到正确的结果。这个缺陷使得它在实际网络分析中难以应用。而且，即使这个问题可以得到解决，它与所有的二分算法一样，仍然面临着如何事先知道网络中的社区数目，以及二分要重复到哪一步停止的问题3.2.2谱平分法一个有n个结点的无向图G的Laplace矩阵是一个维的对称矩阵L。其中，L的对角线上的元素是结点i的度，而其他非对角线上的元素则表示结点i和结点j的连接关系。如果这两个结点之间有边连接，则值为1，否则为0。L矩阵所有的行与列的和都为0，因此，该矩阵总有一个特征值为0，其对应的特征向量为l=(1，1，1)。可以从理论上证明，不为零的特征值所对应的特征向量的各元素中，同一个社区内的结点对应的元素是近似相等的。这就是谱平分法的理论基础。考虑网络社区结构的一种特殊情况：当一个网络中仅存在两个社区，此时该网络的Laplace矩阵L就对应了两个近似的对角矩阵块。对一个实对称矩阵而言，它的非退化的特征值对应的特征向量总是正交的。因此，除了最小特征值0以外，矩阵L其他特征值对应的特征向量总是包含正、负两种元素。这样，当网络由两个社区构成时，就可以根据非零特征值相应的特征向量中的元素对应网络的结点进行分类。其中，所有正元素对应的那些结点都属于同一个社区，而所有负元素对应的结点则属于另一个社区。因此，我们可以根据网络的Laplace矩阵的第二小的特征值将其分为两个社区。这就是谱平分法的基本思想。当网络的确是分成两个社区时，用谱平分法可以得到非常好的效果。但是，当网络不满足这个条件时，谱平分法的优点就不能得到充分体现。事实上，第二小特征值可以作为衡量谱平分法效果的标准：它的值越小，平分的效果就越好。也称为图的代数连接度(Algebraic Connectivity)。一般情况下，计算一个矩阵的全部特征向量的时间复杂度为。但是在大多数情况下，实际网络的Laplace矩阵是一个稀疏矩阵，因此，可以用Lanczos方法快速计算主要的特征向量。该方法的时间复杂度大致为，其中，m表示网络中边的条数。这样，计算的速度可以得到很大程度的提高。但是，如果不能很快将从其它特征值中分离出来，该算法就可能在一定程度上有所减慢。换句话说，当网络很明显地分成两个社区时，该算法的速度非常快，否则该算法就未必很有效。3.3 其他经典算法3.3.1 GN（Girvan-Newman）算法GN 算法是一种分裂方法，它通过迭代从网络中移除介数(Betweenness)最大的边将整个网络分解为各个社区。边的介数定义为网络中经过该边的最短路径的数目。它为区分一个社区内部边和外部边连接提供了一个度量准则。GN算法的基本流程如下：(i) 计算网络中的所有边的介数；(ii) 找到介数最高的边并将它从网络中移除；(iii) 重复步骤(ii)，直到每个节点就是一个退化社区为止。缺点：在不知道社区数目的情况下，此算法也不能确定迭代的合适步数。3.3.2 Newman快速算法由于GN 算法的时间复杂度较大，所以对大规模的复杂网络的分析效果并不理想。Newman 在GN 算法的基础上提出了一种快速算法，它是基于贪婪算法思想的一种凝聚算法。此算法总的时间复杂度为。整个算法完成后可得到一个社区结构分解的树状图，再通过选择在不同位置断开可得到不同的网络社区结构，在这些社区结构中，选择一个对应着局部最大的Q值，就得到最好的网络社区结构。3.3.3Radicchi算法该算法与GN 算法相同，都是基于去边，但不是根据边介数选择要去除的边，而是引进了边聚集系数的新指标。整个算法的运行时间为。显然，对于稀疏图，其计算速度要比GN算法快一个数量级。Radicchi 等考虑网络中的三角环(即边数为3 的闭合路径)。若一个三角环包含一条连接不同社区的边，则该三角环中的另两条边中的某一条仍然连接这两个社区的可能性将很大。但是由于连接不同社区的边非常稀少，故包含一条给定的连接不同社区的边的三角环不可能很多.因此，将一条边的边聚集系数定义为包含该边的三角环所占比例： （3-1）其中，分别表示节点i 和j 的度，表示网络中实际包含该边的三角环的个数。上式中的分母表示包含该边的最大可能的三角环的个数。Radicchi 算法每一步去除的是网络中边聚集系数最小的边，每次去除后，再重新计算每一条边的边聚集系数，如此进行下去，直至网络中不存在任何边。Radicchi 算法的不足是该算法依赖于网络中的三角环，如果网络中三角环很少，那么该算法将失去意义。实证研究表明，社会网络中三角环的数量比较大，而在非社会网络中，三角环的数量则相对较少。这意味着Radicchi 算法更加适合于社会网络。第四章 基于随机游走的社团发现算法本章主要介绍一种基于图论的随机游走（random walk）算法15-16，主要介绍了该随机游走算法的基本原理，以及随机游走算法的编译实现方式。4.1 随机游走算法的基本原理在上一章节对各种社团发现算法的介绍和比较后，我们在此提出一种完全基于随机游走来实现社团划分的算法。该算法的主要实现原理是基于此种方式，即在以任意节点i 为起点进行有限步数的随机游走，在有限的步数内，相比于在不同的社团间的随机游走，该随机游走是有更大的可能性是停留在同一个社团内部的。我们通过记录在每次随机游走过程中的轨迹来作为节点间属于同一个社团的证据。正式介于此类原理，我们提出了这种更简单，更直接的划分复杂网络的社团结构的随机游走算法。4.1.1 随机游走算法的相似度矩阵获取随机游走的基本思想是进行多次一段较短步数的随机游走，并且把在同一次随机游走过程中经历的节点作为他们同属于一个社团的证据。这个信息在经过所有的随机游走过程后被补充完整，并被用来作为一个基本的信息去划分复杂网络的社团结构，算法的基本过程在图4-1中显示。算法的过程中，我们首先定义的矩阵S，把矩阵中的每一个元素Sij都赋值为0。在考虑算法的随机游走的步数时，我们可以根据我们要处理的复杂网络的半径以及节点数n来自己给出随机游走的步数（随机游走的步数一般不会超过10）。在随机游走算法的过程中，我们从节点i开始进行随机游走，随机游走即从节点i的所有邻居节点中等概率的找到它的一个邻居节点，作为随机游走的下一个节点。在每一次随机游走过程中，我们都会用一个集合C来存储我们这一次随机游走过程中所遍历的节点i（集合C中的数据是不重复的，即使我们随机游走的过程中经过多次节点i，我们也只在集合C中记录一次）。根据得到的集合C，我们随机的选择集合C中不相等的元素i，j，来作为相似度矩阵S的行号和列号，即Sij。与此同时，Sij中的元素对应加1。以此遍历复杂网络中的所有节点，得到n个集合C，并最终得出矩阵S的值。在完成矩阵S后，矩阵的每个元素Sij表示节点i和节点j同属于一次随机游走的次数，即同属于一个社团的可能性的大小。Sij值越大，表示i，j属于一个社团的可能性便越大。图4-1 随机游走算法矩阵S的获取4.1.2 随机游走算法的矩阵融合现在我们通过随机游走得到了一个相似度矩阵S，我们下一步的工作便是将相似度矩阵进行融合，在融合的过程中不断得到新的社团结构。在融合矩阵的过程中，把每次融合的节点数进行记录到新的集合C中，在矩阵融合结束后，集合C中记录的便是复杂网络最终的社团结构的划分。在融合矩阵的过程中，我们使用的是与Johnson 描述的凝聚算法相类似的一种技术。这种方式的普遍观念是根据相似度矩阵中的元素的相似度的大小来进行融合。融合的方式为从最大的相似度开始融合，以后依次递减类推，在融合结束后得出结果。融合矩阵的算法在图4-2中给出。图4-2 随机游走算法相似度矩阵S的融合在矩阵融合的过程中，相似度矩阵S的尺寸在每一次的融合过程中不断的减少。矩阵在相应行（列）融合的过程中也在不断地进行变化。而在融合的过程中，几种不同的方式可供我们选择，有最大值，最小值以及平均值的方式，在这里我们经验性的选取平均值来作为融合结果最好的值（在下一小节我们进行讨论），根据相应的算法，其复杂度可以为也可以为O(n)，具体介绍将在下一章具体介绍。4.1.3 矩阵元素融合方式在此我们提醒读者关于我们讨论的在融合社团过程中，为相似矩阵计算的新的距离的方法。在融合矩阵之前，我们首先应该了解那种算法方式是最有效率的。如果我们假设社团i和社团j要被融合，让作为新的新的社团结构到某个社团k的距离。在这里我们注意到一下几种公式： （4-1） （4-2） （4-3）其中平均路径长度就是我们在上一小节中介绍的相似度矩阵融合过程中所使用的融合公式。4.2 随机游走算法的代码编译过程4.2.1 随机游走算法的相似度矩阵的获取在算法实现过程中，读取流量文件.csv，生成所有节点的哈希表以及所有边的哈希表。点与边的哈希表中元素的定义如图4-3。图4-3 算法中对于点和边的哈希表中元素的定义同时我们使用qsort函数来获取按边的起点的序号排列的新的边的哈希表。 qsort(h_edges,edge_num,sizeof(struct strc_edge),comp);获得新的边的哈希表之后，我们在每次随机游走过程中，以节点i作为一次随机游走的起点，每次从对应的边的哈希表中找到以节点i作为起点的边，在这些边中获得相应边的终点，即节点i的邻居节点，从这些节点中等概的选取一个节点j作为随机游走过程中下一次的节点。将随机游走过程中的所有节点的编号不重复的存入数组C中。其次，第一，随机游走算法是基于大型复杂网络的社团划分，为了以后更好地应用于大型复杂网络中，以及减少算法的复杂度方面；第二，所得到的相似度矩阵式系数矩阵。所有我们采用带行指针数组的链表来存储矩阵S。矩阵定义如图4-4图4-4 算法中对于矩阵的定义最终通过每次随机游走获得的集合C，在已知的链表中进行相对应的处理，得到相似度矩阵S。（相应的代码在最后给出。）4.2.2 随机游走算法的相似度矩阵融合通过上一小节，我们得到了需要的相似度矩阵S，我们现阶段的工作便是将相似度矩阵进行融合。首先我们遍历已知矩阵的所有元素获取相对应的最大元素，得到对应的行号Maxrow和列号Maxcol，如图4-5所示图4-5 获取矩阵元素最大值的行号、列号在得到相应的行号Maxrow和列号Maxcol后，在对应的两行，即Maxrow行与Maxcol行之间进行元素的融合；对应的两列，即Maxrow列和Maxcol列之间进行元素的融合。在融合后删除Maxcol行以及Maxcol列。在此，需要注意的是，由于矩阵的融合过程中由于对于行、列删除后，我们的系数矩阵S，仍然默认为矩阵，只是对应的Maxcol行以及Maxcol列的所有元素为0，但这与我们在矩阵每次融合过程中，矩阵尺寸不断减少是不矛盾的。在每次融合的过程中，我们定义了另外一个带行指针数组的链表来G存储我们融合过程中结果，即每次融合社团i和社团j之后，带行指针数组的链表G相应的改变，将Maxcol中的链表移动到到Maxcol后，删除Maxcol中的链表。如图4-6所示。图4-6 记录矩阵融