图的代数连通度及其应用

论文总字数：20845字

摘 要

社团结构是复杂网络的重要特征，表现为社团内部节点之间的联系较为紧密，社团之间的节点联系较为疏松,它的研究一直以来是复杂网络中的热点问题之一。近年来，由于对社团划分算法的研究渐渐深入，越来越多的新型算法被发现。尤其是 “强弱社团结构”的定义以及模块度的概念的提出，将社团发现问题的定量化发展推广到了一个新的高度。但现实生活中，许多算法都有划分精度低或时间复杂度高的缺点，而网络的规模却越来越大，对算法的要求也越来越高。

本文做出以下工作：

（1）总结了三个常见的社团划分算法：第一是比较古老的Kernighan-Lin算法，第二是基于矩阵理论的谱平分法，第三是分裂算法中的经典Girvan-Newman算法，并对它们的优缺点进行了比较。

（2）基于分裂思想，提出了一种关于社团划分的分裂方法。方法的基本思想如下：对网络中的任意一点S，求出离它最远的节点T，再计算它们之间的最短路径，可以认为这条最短路径有很大的概率经过连接社团与社团之间的边，去掉这些连接社团的边便可以分裂出一个个独立的社团。相比ＧＮ算法而言，该算法不需要遍历所有的节点，计算速度更快。并用一系列数据实验了该算法。

关键词 ：社团划分 ；分裂算法； 复杂网络

ABSTRACT

Community structure is one of the most important fretures in complex network.The notes in the same group contact are closely associated,and the connections between two different groups are spare. Its research has been one of the hottest issues of complex networks.In these years,with the in-depth research on algorithm,more and more new algorithms have been found.Especially community division algorithms reach a new level when the concepts of “defines of community structure”and “modularity” have been proposed.But in the real life,many algorithms have its disadvantges,and the network scale is bigger and bigger,the requirement of algortihm will be higher and higher.

This paper does the work as follows:

1. make a summing up of three algortihms: Kernighan-Lin algortihm, spectral bisection method and GN algortihms,and in this paper their advantages and disadvantages are compared.
2. Give a new algortihm based on division method.In this algortihm ,we start from the note S ,find the farest note T.we can consider that the shortest path between S and T has a hegher chance to go through the way between two communities.If wu cut all the way which connect two communities,the groph is divided into servel subgroph.Compared to GN algortihm,the new algortihm works faster .

Keywords: Community division； Division method ；Complex networks

目录

一种新型社团划分分裂算法 1

摘要： 2

ABSTRACT 3

第一章 绪论 5

1.1研究背景 5

1.2 研究现状及各类方法简介 5

1.3本文工作 6

1.4 论文组织结构 6

第二章 一些社团划分的方法 7

2.1 图论的基本知识 7

2.2社团划分算法 8

2.3 本章小结 14

第三章 一种改进的分裂算法。 14

3.1 基本思想 14

3.2具体的算法步骤 15

3.3算法截止条件 17

3.4 数据实验 17

3.5联系比较紧密的网络 18

3.6 足球队网络： 19

3.7本章小结 20

四．总结与展望 20

4.1总结 20

4.2 展望 20

附录： 21

致谢： 25

参考文献 26

第一章 绪论

1.1研究背景

近30年来，网络技术的发展日新月异，对网络结构的研究也越来越深入，人们发现许多网络都具有社团性质。社团性质表现为内部连接紧密，外部连接疏松，比如说同一个俱乐部之间的成员交往密切，而不同俱乐部之间的成员交往便比较疏松。

社团结构在实际生活中也有具体的应用，万维网可以看成是一系列的社团的组成，而在同一个社团间，人们往往有共同的爱好或者话题。在生物网络或者电路网络中，也有类似的结构，如一个蜂巢中的蜜蜂可以看成一个社团。

在真实世界中，许多复杂网络比如信息网络、生物网络、社会网络和技术网络等等都可以用图来加以刻画。因此可以用图论中的一些方法来着手复杂网络问题。在这些复杂网络中，可以自然而然地划分出一些联系比较紧密的节点组。这些节点组的存在，也被称作社团，而一般而言，社团内两个点之间比不同社团间的两个点联系更加紧密。这种性质的存在，有利于揭示网络的功能与结构，发现其隐藏信息。

随着时间的推移，人们对复杂网络的研究愈来愈额透彻，许多特征被人们发现。其中两个重要的特征就是无尺度特征^[1]以及小世界效应^[2]。“小世界”效应的一个重要运用即是世界上的任意两个人，只要通过五个人，就能把他们联系起来，而在复杂网络中体现为：网络中任意两个节点之间的最短距离的最大值较小。

将网络划分成社团，能更加精准地控制资源的分配。例在如互联网中划分社团，能快速地控制计算机病毒的爆发。人群中划分社团，可以有效防止瘟疫的流行。在并行计算中也涉及到社团划分的运用。因此将图形分割成几个社团，是一件有必要也是一件有意义的事。

1.2 研究现状及各类方法简介

社团结构的分析一直以来是复杂网络领域的热点之一，它与许多学科有着密切的联系，例如图形分割、层次聚类等。但“社团”这一概念在学术界并没有明确的定义，只是粗犷地认为每个群之间的联系相对紧密，而社团与社团之间的联系相对疏松。因此，一般而言想要找到这类问题的精确解是NP难题。

由于划分出网络的社团结构相当重要，学者对算法孜孜不倦的研究已有几十年历史。分类聚集是寻找社团结构的一种优秀算法，它关注各个节点之间的联系相似度与紧密性，从而将网络分割为几个子群。根据从网络中添加边还是从网络中移除边，该类算法又分为两类：一种是凝聚方法，另一种是分裂方法^[3]。而图形分割法也可以分为两大种，第一类是基于矩阵理论及特征值的谱平分法^[4]，第二类是试探优化法。 到目前为止，在许多学者的不懈努力下，有一些经典的算法可以很好的解决规模不大时的社团划分问题：例如基于贪婪思想的KL算法^[5]、谱平分法、GN算法^[6]等等。另外，还有2004年由纽曼等人提出的CNM算法、结合谱分析的凝聚算法以及堆结构贪婪算法，在2006年pons、Latapy提出的随机游走算法等等，这些都属于凝聚算法。

剩余内容已隐藏，请支付后下载全文，论文总字数：20845字