毕业设计（论文）基于邻居关系的社团结构检测方法研究.doc

《毕业设计（论文）基于邻居关系的社团结构检测方法研究.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于邻居关系的社团结构检测方法研究.doc（46页珍藏版）》请在三一办公上搜索。

1、硕 士 学 位 论 文基于邻居关系的社团结构检测方法研究Research on Algorithms of Community Structure Detectionbased on Neighborhood 作 者 姓 名： 赵仲祥 学科、 专业： 计算机软件与理论 学 号： 21109259 指 导 教 师： 王兴元 教授 完 成 日 期： 2014年10月27日 大连理工大学Dalian University of Technology大连理工大学学位论文独创性声明作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外

2、，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目： 基于邻居关系的社团结构检测方法研究 作 者 签 名 ： 日期： 年 月 日摘 要社团结构是复杂网络的一个重要属性，在生物学、社会学等众多学科领域有着广泛的应用，越来越受到人们的关注。近年来有很多的社团结构探测算法被提出来，但是这些算法在计算复杂度和准确度上仍然存在着一些不足。本文从节点间的邻居关系出发，提出了两种检测社团结构的算法，主要工作如下：(1)给出了某种社团结构划

3、分下单个节点划分效果的评价：强社团结构节点、弱社团结构节点、二义性社团结构节点和非社团结构节点。这种评价方法的理论基础是强社团结构和弱社团结构的定义，对于分析和判断一种社团结构的划分效果具有一定借鉴意义。(2)提出了一种改进的派系查找算法，从当前网络中度最小的节点开始，每找到一个派系就删除只存在于这个派系中的边；从大到小选取派系来组成社团或者将派系中的节点吸收进社团。在几个实际网络上对算法进行了测试，并对结果进行分析，结果显示该算法在派系查找上相对现存的其它算法有更高的时间效率和更低的空间资源需求，并且对网络的社团结构划分效果较好。(3)提出了基于节点间依赖度的社团结构检测算法，这种算法只需考

4、虑一个节点的邻居节点，即可将该节点划分到社团。给出节点对节点、节点对社团的依赖度以及节点对社团的条件依赖度，详细介绍了算法的实现过程，在几个实际网络上对算法进行了测试，并对结果进行分析，该算法有较低的计算时间复杂度，对社团结构的划分结果也比较理想。本文得到国家自然科学基金(61370145, 61173183, 60973152)，高等学校博士点专项科研基金(20070141014)，辽宁省高等学校优秀人才支持计划资助(LR2012003)，辽宁省自然科学基金(20082165)，中央高校基本科研基金(DUT12JB06)的联合资助。关键词：复杂网络；社团结构；邻居；依赖度Research o

5、n Algorithms of Community Structure Detection based on NeighborhoodAbstractCommunity structure is a very important attribute. More and more scholars have been addicted to the studies of community structure detection algorithm from biology, sociology and other disciplines. Some methods have been prop

6、osed to discover community structure in complex network, but these algorithms have a lot of deficiency in aspect of time efficiency and accuracy. This paper proposed two novel algorithms based on the relationship between neighbors. The main content for this paper have been done as following:(1) Some

7、 single node partition effect assessments are given on the base of some community structure partition strategy: strong community structure node, weak community structure node, ambiguous community structure node and error-community structure node. The theoretical principle of these assessments are th

8、e definitions of strong community structure and weak community structure, which have great use for reference to a kind of partitioning to a network.(2) An advanced clique finding algorithm is proposed, which begins with the minimum-degree node, if there is a clique to found then delete corresponding

9、 edges related to the node; select the clique in descend order to compose community or add nodes into the community. Some simulations have been made on several real networks, and make an analysis about the obtained experiment results. The results display that our algorithm has a higher time efficien

10、cy and lower space resource demand than existing algorithms, and has better results on partitioning community structures.(3) A community structure detection algorithm based on dependence degree between nodes is proposed. Some dependence degrees are calculated including dependence degree between node

11、s and node, the dependence degree between node and community, and the conditional dependence degree between node and community. Besides, the detailed implementation process and some simulations for several real networks have been made; an analysis about the obtained experiment results have been give

12、n, this algorithm reaches a rather high standard on time complexity and has very good results on partitioning community structures.The research is jointly supported by the National Natural Science Foundation of China (Nos: 61370145, 61173183, and 60973152), the Doctoral Program Foundation of Institu

13、tion of Higher Education of China (No: 20070141014), Program for Liaoning Excellent Talents in University (No: LR2012003), the National Natural Science Foundation of Liaoning province (No: 20082165) and the Fundamental Research Funds for the Central Universities (No: DUT12JB06).Key Words：Complex Net

14、work; Community Structure; Neighbor; Dependent Degree目 录摘 要IAbstractII1 绪论11.1 引言11.2 复杂网络理论的发展史11.3 复杂网络中的基本概念31.3.1 复杂网络的表示31.3.2 平均路径长度31.3.3 聚类系数41.3.4 度与度分布51.3.5 其他概念61.4 复杂网络中的社团结构61.4.1 社团结构的描述61.4.2 复杂网络社团结构划分的意义71.4.3 社团结构划分结果的衡量标准81.5 一个复杂网络的实例81.6 社团结构下对单个节点划分效果的评价91.7 复杂网络社团结构研究的现状和存在的问

15、题111.8 本文的研究内容和结构安排112 派系基础上的社团结构划分方法132.1 方法的描述132.1.1 主要思想132.1.2 实现步骤132.1.3 算法分析172.2 实验结果与分析172.3 结论203 基于节点间依赖度的社团结构检测算法213.1 方法的描述213.1.1 主要思想213.1.2 基本概念223.1.3 实现步骤233.1.4 复杂度分析263.2 实验结果与分析263.3 算法的扩展293.4 结论304 总结与展望324.1 总结324.2 未来工作展望33参 考 文 献35攻读硕士学位期间发表学术论文情况38致 谢39大连理工大学学位论文版权使用授权书40

16、1 绪论1.1 引言20世纪90年代以来，伴随着各种信息技术的快速发展，人类生活在更加多种多样的网络世界中，人类社会进入了网络时代1。复杂网络的涵盖非常广泛、无处不在，从邮件网络到万维网，从小范围的人际关系网到各种政治、经济和社会关系的网络，从生物体内部各种蛋白质、DNA、RNA和分子间的交互作用到生物个体间的相互影响网络，从乡间道路网到各大陆上的公路铁路网络，等等。各种各样的复杂网络遍布交叉在人们生活的世界中，从一个生命降临到世界上的那一刻起，就有无数的网络笼罩着他2, 3。生活环境的网络化极大地便利了人类的社会生产活动，提高了工作效率和生活质量，但同时也给人类带来了不少的负面影响，例如大面

17、积停电事故、传染病的传播、交通拥堵、计算机病毒的迅速蔓延等等。人们需要对各类人为的和自然界的复杂网络的各种行为有更好的认识，并从中得到改造复杂网络的能力，从而让它们对人类的生活带来更大更多的好处、及时减少和控制负面影响。20世纪元末以来，工程度学科、生命运学科、数理学科等许多不同的研究领域的研究者们对复杂网络展开了深入的研究，对复杂网络的各种性质的研究和改造，已经变成网络时代众多科学研究中一个很重要的具有挑战性的课题，甚至被人们称为“网络的新科学”4, 5，对复杂网络理论的研究蓬勃展开。1.2 复杂网络理论的发展史网络的结构对网络的性质有着非常大的影响，而要研究复杂网络中普遍存在的各种性质，就

18、需要对复杂网络的结构进行了解。复杂网络有很多种的具体表现，要了解它们的结构，就需要一种工具对它进行描述。而数学上的图（Graph）正是可以用来描述复杂网络结构的一种很好的工具。所有的复杂网络都可以看成是由一些比较真实的对象通行过某人种相互动关系连接起床来而组队成的系统。这些比较真实的对象被人们抽象为一个个的点，而它们的相互关系可以抽象为对应的两个点之间有一条连线，这样人们就把所有不规则的杂乱无章的复杂网络抽象为一个具体的由点和线组成的图形，为人们的研究提供了便利。18世纪30年代，Eler对“Knigsberg七桥问题”的抽象以及论证思想，开创了对图论的研究，为实际网络的研究和图表示提供了有力

19、的工具。Knigsberg是东普鲁士的一个城镇，城中有一条河流，河中有两个岛，两岛和两岸间共有七座桥，人们经常讨论这样一个问题：是否存在这样的走法，七座桥中的每座桥都经过并且只经过一次后返回原点？Eler仔细研究了这个问题，他将被河流分开的四块陆地抽象为四个点，七座桥抽象为七条线，并用这七条线按实际情况把这四个点连接起来，这样就得到了一个图，如图1.1所示。这样人们就需要研究一个数学问题。Eler考虑图1.1若能一笔画成，则存在满足要求的走法，而一笔画成的图中，除起点和终点外任何一点都应该有偶数条边与它相连，七桥问题的起点和终点重合，所以每个点都应该有偶数条边与之相连，而从图中可以看出，这四个

20、点都有奇数条边与之相连，故七桥问题无解。 图1.1 Knigsberg七桥问题的图示Fig. 1.1 The picture of Knigsberg seven-bridges problem在此后的一百年中，图论的发展是十分有限的，一直到1936年匈牙利的数学家Knig的有限图与无限图的理论出版，对图论 的研究才迅猛蓬勃地开展起来，而有限图与无限图的理论被看作是图论 的第一部专著。20世纪60年代，匈牙利的数学家Erds和Rnyi建立了随机图的理论，展开了对复杂网络 理论的一系统性的研究6，在此后的40年里，对复杂网络结构的研究一直基于他们提出的随机图理论。然而，实际的复杂网络是实实在在存

21、在的、是确定的，WWW上两个页面是否有超文本链接、社会上两个人是否相识、两种蛋白质是否有交互作用等等都是确定的而不是随机的。在21世纪即将到来之际，随着计算机等各种技术的快速发展，人们将研究的中心转移到节点数量更多、 连接结构更复杂的实际网络上，开始研究这些大型实际网络的整体特性。对复杂网络 理论的研究 不再局 限于数学领域， 生物学、物理学和其它众多学科的研究者们都开始了对复杂网络的研究工作。1998 年6 月，美国 Cornell大 学 的 理论 和 应用 力学 博士 生Watts及其 导师、 非线性 动力学专家Strogatz教 授在Nature 杂志上 发 表的 “小世 界”网 络的集

22、体 动力学7， 揭示了复杂网络的一个重要特性小世界 特征； 1999年代10月美国人Notre Dame大学洗物理论系的Barabsi 教授权和他的博学士生 Albert在于 Science 杂志气上发表的随机动网络中见标度的泉涌现8， 揭示了 复杂网络的 另外一个 重要特 性无标度性 。这两篇开创性的文章被看作是复杂网络理论研究新世纪元开始的标志，它们建立了相应的模型，以阐述复杂网络小世界特性和无标度特性的产生机理。此后，大量的关于复杂网络的文章发表在各类刊物上，研究者们在各个方面对复杂网络展开了研究：复杂网络上的动力学分析、相继故障、复杂网络的搜索、社团结构探测、复杂网络上的同步控制等等，

23、复杂网络已经成为一个新兴的极具吸引力的研究领域。在这个全新的时代里，物理学家们不但为复杂网络理论的研究开辟了新的方法，并且极地大拓宽了其他学科研究就者们研究网络的思路。物理学家们对复杂网络上进行的各种动力学行为及物理过程异常关注，诸如同 步、Bose-Einstein condensation、自己组织的临界、传播种等等9, 10，而且和其他学科的研究者们同样关心网络本体身所具有的拓广扑性质。他们发现了网络结构对动力学习行为产生的许多影响，并且给出了大胆的解释，虽然这些解释并没有得到充分的论证，却给人耳目一新的新奇感。1.3 复杂网络中的基本概念1.3.1 复杂网络的表示人们使用图来表示复杂网

24、络，任何的复杂网络都可以用一个由点集V和边集E组成的图来表示，节点数目记作，边数记作。E中的每一条边都有V中的唯一一对点与之相互对应。如果网络中的边具有方向性，称这样的网络为有向网络，否则为无向网络。根据网络中的边是否有不同权值可以将网络分为加权网络和无权网络。除特别说明外，本文只讨论无权无向网络。很多时候，复杂网络还可以用一个邻接矩阵来表示，矩阵中序号相同的行和列代表一个节点，对角线上的元素为该节点i的度，若两个节点i和j间有边相连， 则值为1，否则为0.1.3.2 平均路径长度复杂网络中连接节点和节点的最短路径所经过的边的数目定义为节点i和j之间的边距离。网络的 直径指的是网络中两个节点间

25、距离的最大值，记为：。 (1.1)网络的 平均路径 长度定义为所有节点对间距离的 平均值：， (1.2)其中n为网络中包含的节点的数量。复和杂乱网格络的 平合均不路程径 长方度有时候也被称为网格络 的一特殊征途路线径过 长度。平均路径 长度也可以用 广度优先 搜索算法 来确定，一个含有n个节点和m条边的无向无权网络中，通过广度优先算法计算的时间量级为。例如，图1.2所示的由5个节点和5条边组成的网络，网络的直径为3，平均路径长度为1.6。在朋克友人关联系网格络中，平分均分路途径过长程度为网络中两人之间最少短小关门系链路中朋好友数量的平均值。研究发现，即使许多网络中包含数目巨大的节点，而网络的平

26、均路径长度却是一个很小的数字。图1.2 一个简单网络的 直径和平均路 径长度Fig. 1.2 The diameter and average path length of a simple network 1.3.3 聚类系数一般地，若一个节点i有个其他节点通过一条边和它相连，称这个节点为节点i的邻居，称为节点i的度。一个节点的两个邻居也可能互为邻居，这种属性称为网络的聚类特性。节点i的个邻居间实体际存活在的边上数，和这些邻居间可以存在的最大边数的比，定义为节点i的聚类系数，即， (1.3)其中为节点i的邻人居间求实际遇存在的边数。在朋友关系网络中，你的两三个朋比友彼此时也是朋比友的概率就是

27、你在这个朋友关系同网络个中的聚众类系数。从几何上看，节点i的聚类系数表示和节点i相户连的三个角形的数木量，与和节点i相连的三元组的数量的比值（图1.3显示了与节点i相连的两种三元组的样式）。复杂网络中所有节点聚类系数的平均值就是网络的聚类系数C。聚类系数有这样的性质：当一个随机网络的节点数量n足够大时，。然而许久多实际是的大型只网络都不的具有这过个性质，它们的聚类系数虽然远小于1却比要大得多，不会随着网络规模的增大而无限减小。在很多实际网络中，例如随着网络规模的增大，在朋友关系网络中某人的两个朋友互为朋友的概率不会趋于0，而是趋于某个常数。也就是热说，时，。这说明着这些实际网络和完全随机网络存

28、在着很大的差别，在某种程度上具有“物以类聚，人以群分”的特征。再次验证了实际网络和随机网络的区别。(a)三元组组成三角形 (b)三元组未组成三角形图1.3 与节点i相连的三元组的两种样式Fig. 1.3 The two forms of triple with node i1.3.4 度与度分布通常将与节点相连的其他节点的数目定义为节点的度。加权网络中边的权重不影响节点的度，而在有向网络中，指向节点i的边的数目称为节点i的入度，从节点i指向其他节点的边的数目称为节点i的出度。直观地，度越来大的节度点与它相比连的其它人节点么就越多，表明这个节点在该网络中具有较高的“地位”，比其它度较小的节点更为

29、“重要” 。网络中 所有节点的度 的平均值定义为网络的平均度，记为。随机选定网络中的一个节点，而该节点的度为k的概率称为网络中节点 的度的分布，经常用分布 函数表示。在完整全部随从机会的网格络中，度分布与Poisson分布较为近似，在图形上看，远离峰值 处呈指 数下降，这说明大多数节点的度和相差不悬殊，而度远小于或者远大于的节点是极少的，网络中节点的度分布较为均匀，这类网络也被称为均匀网络。大量研究表明，许多实际网络的度分布都不具有这种性质，这是实际网络与完全随机网络的又一大区别。幂律形式能够更为贴切地描述实际网络的度分布。幂律分布也被称为无法标明度量分布，无标度网络指具有无标度分布的网络。1

30、.3.5 其他概念近些年来，随着对复杂网络研究的深入，更多的关于网络的概念被提出来以描述网络的特性，例如核数、介数等等。而在将来的时间里，会有更多的概念被提出，用来描述复杂网络性质、便于人们分析和改造复杂网络。核数：反复地去掉一个图中的度不超过k的节点后剩余的子图被称为这个图的k-核11。一个节点的核数为k指这个节点存在于k-核中而不存在于任何-核中。介数：一个节点的介数指网络中通过该节点的最短路径的数目，同理，一条边的介数指网络中通过这条边的最短路径的数目。1.4 复杂网络中的社团结构1.4.1 社团结构的描述通过对复杂网络的深入研究，各个学科的研究者们逐渐发现许多实际的网络都具有这样的新的

31、共同属性：整个网络可以分为若干个“群”或者“团”，属于同一个群或者团的节点之间的联系相对于属于两个不同的群或者团的节点之间的联系要紧密得多，如图1.4所示，将网络中的社团用红色虚线包围以便观察，这三个社团之间节点的联系比社团内部节点间的联系要稀疏得多。图1.4 复杂网络的社团结构示例Fig. 1.4 The schematic example of a complex network with communities由于对于社团结构的描述中，“紧密”、“稀疏”只是一个定性的指标，并没有量化的衡量标准，很难在实际中应用。为了个从定一量角度过分析社会团结构，Radicchi等人提出了关于社会团体结

32、果构的两种量的定义12：(1)强社团结构如果和一个社团中所有节点相连的边中属于社团内部的边的数目都大于社团间边的数目，那么称这个社团为这个网络中的强社团结构，即：子网络称为强社团结构，如果满足， (1.4)其中表示节点连接子网络中其它节点的边的条数，表示节点连接子网络外其它节点的边的条数。(2)弱社团结构如果和一个社团中所有节点相连的边中，在这个社团内部的边的数目多于任何其他社团内部的边的数目，则称这个社团为该网络中的弱社团结构，即：子网络称为弱社团结构，如果满足， (1.5)显而易见，强社团结构的定义要求更严苛而弱社团结构的定义要求稍宽松，满足前者必然会满足后者，反之则不一定。1.4.2 复

33、杂网络社团结构划分的意义网络结构是网络的最主要的属性之一，对网络的传达播种机会理和动作力度学习分析、稳定性和鲁棒性、同形步形和动作态度控告制等等都有着决定性的影响，网络的社团结构同时样子如何此13-15。为了能够更好的了解网络上的动力学以及网络的单元构成，研究者们需要将网络的社团结构正确地探测出来。社团结构是一个普遍存在的概念，在不同学科中有不同的称呼。社团结构与对象分类的联系非常紧密，在某些研究中又被称为子图、群组、模块、类、阶层等。在各种实际网络中的节点簇（社团）通常是属性和功能相同或相似的节点会聚在一起形成的，这些功能属性相同或相似的节点往往相互间距离比较“近”。换句话说，网络中的社团结

34、构在真实系统中有着非常大的意义：可能对应着属性类、模块、功能单元或组织结构，如在电路网络中社团可能是某一个功能单元，在朋友关系网络中社团可能代表着兴趣相投的一帮好友，在引文网络中社团代表针对某一相同主题的论文，在邮件网络中社团代表在工作或学习或生活上有关系的一群人，在经济关系网中社团可能代表着经济关系密切联系的人群或者集团，万维网中社团则代表讨论主题相近的若干网站，等等16-27。人们可以通过一个复杂网络准确划分出来的社团结构中某个成员的属性（功能），推测它所在社团其它成员或者整个社团的属性（功能）。而且得到了一个网络的社团结构，人们就可以对这个网络的结构进行改造，以使这个网络能够更好地为人类

35、服务。复杂网络社团结构的探测在生物学、社会学、物理学等众多学科的实际问题上都有广泛的应用17, 28。1.4.3 社团结构划分结果的衡量标准在很多实际的网络中，人们并不了解这些网络的真实社团结构，而要知道对某个网络的一种社团结构划分结果是否准确，就需要一个标准来衡量。为来此，Newman等人民引进行了一个社会团划分别质量的衡定量标明准模块度29。为便于叙述，如果一条边两端的两个节点都属于某个社团，称这条边为这个社团 内部的边；如果一条边两端的两个节点分别位于第i个和第j个社团，称这条边为这两个社团间的边。假设对某个复杂网络的某种划分布形式将网格络 划分为 k个社会团，定义 一个k阶对方称方块阵

36、，其中表明示 网格络中 第i个 社会团和第j个社团体间的边 在所式有边 中所占 的对比例，对角线上的元素表示第i个 社团 内部的边 在所有边 中所占的 比例。对角度线 上所以有元素数相加得了到的表示是所有社会团内部的一边在 整个网络中心的边上中所占的 比方例。用下面式子定义 模块度的 衡量标准：， (1.6)其中表示矩阵中所有元素 之和。式1.6的物体理 意思义是：网络中心社团内心部边的比例，减去在相同的 社团结构 下所有社团间 边的比例 的期待望着概率。Q的上限为1，Q越接近1，表明该网络的社团结 构越明显。在对真实的 社团结构未知的网络的研究中，Q值经常被用来比较几种社团划分结果的好坏，Q

37、值较大，表明该种划分方法较好。1.5 一个复杂网络的实例之所以要将这个网络单独进行介绍，是因为这个真实的社会网络具有已知的社团结构和特殊的构造，已被很多的研究者用来验证各种社团结构划分算法的结果。在20世上纪70 年级代初，美了国一所大小学有34个成员的空手道俱体乐部的主人管和校长之间，两人心因为是否提齐高俱乐部的收入费而产生了分歧，结果该俱乐部就分裂成为了两个小俱乐部，分别以校长和俱乐部主管为核心。而这一事件正好被潜心观察这个俱乐部内成员间相互社会关系的Zachary遇到，他在两年时间内对这些社会关系观察的基础上，构造了这些俱乐部成员之间相互关系的网络30，如图1.5所示，节点1和33分别代

38、表了俱乐部主管和校长。由于是经过Zachary两年多时间的观察以及由收费问题引起了网络的分化，人们已经清楚地了解了这个网络实际的社团结构。这个社会网络已经成为一个经典的用于社团结构分析的网络。图1.5 Zachary研究的空手许道俱体乐部内部成员关系网络Fig. 1.5 The friendship network from Zacharys Karate club1.6 社团结构下对单个节点划分效果的评价通过对各种经典算法的仔细分析研究，作者不但对这些算法有了深入的了解，而且拓展了思考问题的思路，更重要的是作者对复杂网络社团结构领域内的问题有了更多的理解和想法。通过仔细观察各种算法对网络实例

39、社团结构所做的划分，并结合关于社团结构的定性描述，作者发现在一种对网络社团结构的划分结果中，如果一个节点连接到它所在社团其它节点的边数，多于它连接到其它社团节点的边数（例如图1.6中的节点1），那么对这个节点的社团划分是相当成功且没有争议的，这正好符合了Radicchi等人关于强,社团结构的定义，可以肯定，在这些节点上的社团结构非常明显。如果一个节点连接到它所在社团其它节点的边数，多于它连接到的其它任何社团中节点的边数（例如图1.6中的节点16），那么可以认为这些节点上的社团结构不很明显，但是这种社团结构的划分也是正确的。如果一个节点连接到它所在社团其它节点的边数，等于它连接到的某个社团节点的

40、边数，而又不小于它连接到其它社团节点的边数（例如图1.6中的节点18），那么可以认为这个节点上的社团结构非常不明显，有二义性，但是这种社团结构的划分也是有道理的。还有一种情况，如果一个节点连接到它所在社团其它节点的边数，少于它连接到的其它某个社团中节点的边数（例如图1.6中的节点8），那么对这个节点的社团结构划分是错误的，不符合人们关于社团结构的认识，因为若将这个节点划分到中，那么社团间的边便会减少而社团内部的边会增加，符合了人们关于社团结构的认识。图1.6 某种社团结构划分对各节点的划分效果示例Fig. 1.6 The schematic example of a kind of commu

41、nities partition of a complex network 由上所述，本文在借鉴Radicchi等人关于强社团结构定义的基础上，提出一种关于某种社团结构划分中对单个节点划分效果的评价方法：假设这种社团结构划分方法将网络划分为共s个社团，且节点i被划分到社团中，用表示节点i与社团中节点相连的边数(1)如果i满足， (1.7)即节点i与它所在的社团中其它节点相连的边数，多于它与社团外所有节点相连的边数，称节点i为强社团结构节点。 (2)如果节点i满足， (1.8)即节点i连接到它所在的社团中其它节点的边数，大于它连接到其它任何社团中节点的边数，称节点i为弱社团结构节点。 (3)如果

42、节点i满足， (1.9)且一定存在一个j使得等式成立，即节点i连接到它所在社团内其它节点的边数，等于它连接到的其它某个社团中节点的边数，而不小于它连接到的其它任何社团中节点的边数，称节点i为二义性社团结构节点。(4)如果存在某个j，使得， (1.10)即节点i连接到它所在的社团中其它节点的边数小于它连接到的其它某个社团中节点的边数，称节点i为非社团结构节点。1.7 复杂网络社团结构研究的现状和存在的问题20世纪后期，随着计算机技术等科技的不断发展，研究者们有了更有力的工具来研究复杂网络中的社团结构，有了更多的方法来分析网络的社团结构，很多的算法不断涌现出来29, 31-45。在不知道社团数目的

43、情况下，目前较快的划分网络社团结构算法是Clauset、Newman和Moore等人提出的一种贪婪算法34，通常称之为CNM算法，该算法的时间复杂度为，接近线性时间复杂度。然而，现有的算法仍然不能满足人们对算法时间效率和准确性的要求，更有效的社团结构划分方法依然是本领域研究者们不断追求的目标。CNM算法虽然达到了非常低的时间复杂度，但却不能保证对网络所做的社团结构划分是正确合理的，而且现有的很多算法都难以在时间复杂度、空间复杂度和准确性上同时达到让人满意的水平。1.8 本文的研究内容和结构安排本文作者对现有的探测复杂网络中社团结构的算法进行了深入细致的研究，并提出了两种有理论意义的新的准确性和

44、时间性都达到较高水平的社团结构探测算法。论文各章节的安排为：第一章是本文的绪论，主要回顾了人们对复杂网络的研究历史，介绍了复杂网络中的一些基本概念，详细描述了复杂网络中社团结构的定义、研究意义、划分结果的衡量标准以及复杂网络社团结构的研究现状和存在的问题。还提出了一种评价单个节点在某种社团结构划分下划分效果的方法。第二章中作者提出了一种改进的派系查找算法，以及在派系的基础上划分社团结构的方法，对实现过程和实验结果进行了详细描述。第三章中介绍了作者提出的基于节点间依赖度的社团结构探测算法，对其中的一些定义、实现步骤、实验结果等都进行了详尽的描述和分析。第四章是对本文所做工作的总结和对日后工作的展

45、望。2 派系基础上的社团结构划分方法在很多的实际网络中都存在着非常多的全耦合子图，如果向一个全耦合子图添加任何一个节点都会使得这个子图不再是一个全连通的网络，那么称这个全耦合子图为一个派系，若这个派系中有k个节点，那么称这个派系为一个k-派系。Palla等人提出过一种派系过滤（Clique Perolaion, CP）算法31来分析网络中相互重叠的社团结构，这种算法是利用派系来划分社团结构的典型。通过对派系过滤算法的分析和研究，本章提出一种改进的在网络中查找派系的方法，并在此基础上划分出网络的社团结构。改进的派系查找算法较CP算法具有更高的时间效率和更小的空间占用。本算法对几个实际复杂网络的社

46、团结构划分结果都满足一定的条件并且划分结果较好。2.1 方法的描述2.1.1 主要思想复杂网络由许多的节点和这些节点之间的边构成，相互连接的两个节点构成一个2-派系，2-派系可以看作是网络中最小的结构单元网络中的边。网络中边比较密集的地方，2-派系就有较大的可能组成3-派系、4-派系以至k更大的k-派系。由于复杂网络中社团内部节点间的联系要比社团之间节点间的联系紧密得多，所以较大规模的派系一般只存在于社团的内部而社团之间只存在较小的派系。由此，本章在找到网络中的派系以后，按照从大到小的顺序选取这些派系，根据派系中是否有节点已划分到社团以及已划分到社团的节点在这个派系中的地位，将这个派系组成社团或者将派系中未划分到社团的节点进行划分。本文将一个派系中度最大的那些节点称为这个派系的顶点，一个派系可以有多个顶点。2.1.2 实现步骤本算法由两部分组成，第一部分为派系查找算法，从复杂网络中找出所有“有用”的派系（在一些特殊