《复杂网络上的社团结构探测研究》由会员分享，可在线阅读，更多相关《复杂网络上的社团结构探测研究（51页珍藏版）》请在金锄头文库上搜索。
1、湘潭大学 硕士学位论文 复杂网络上的社团结构探测研究 姓名：项炬 申请学位级别：硕士 专业：理论物理 指导教师：唐翌 20080516 I 摘 要 近年来复杂网络研究受到了来自物理以及其它学科的研究者的广泛关注， 成为当今 的一个研究热点。 大量研究已经表明在真实世界中各种不同的复杂网络具有许多共同的 结构特征，例如小世界性质、无标度性、社团结构等。我们对复杂网络的社团结构及其 探测方法进行了研究。在复杂网络中社团结构的存在意味着网络通常由若干个社团组 成，在这些社团内节点之间的连接相对紧密，而各个社团之间的连接则比较的稀疏。网 络的这种结构特征对网络的动力学有着重要影响， 并且在真实网络中这
2、些社团通常对应 着某种功能单元如社会网络中真实的社会分组、WWW 上内容相关的网页、或论文引用网 络中关于某个主题的论文。因此，探测分析网络的社团结构对我们认识和理解真实复杂 网络的结构以及功能有着重要意义。目前，已经有许多研究者投身到社团结构探测的研 究当中并提出了各种各样的算法以便能够快速而准确的找到网络中的社团， 但是探测算 法的时间复杂度和准确性之间的矛盾仍然是大规模复杂网络的社团结构分析面临的重 要问题。在本文中，我们系统分析了已有的社团探测算法，然后设计了一种改进社团探 测算法准确性的方案，并根据这个方案，提出了一类改进的社团探测算法。 本文共分为五章。在第一章我们对复杂网络的研究
3、进行了回顾，并介绍了本文的主 要研究内容。在第二章，我们介绍了复杂网络的主要结构特征，并系统介绍了复杂网络 的社团结构，包括社团的定义、社团结构探测、以及社团划分的评价。在第三章中我们 系统分析了已有的一些社团探测算法及其性能。同时，根据研究的需要我们研究了这些 算法如何扩展到加权网络，以及在考虑加权网络的内在边权之后算法的探测能力的变 化。 根据前一章的分析， 我们在第四章中首先设计了一个改进社团探测算法精度的方案， 然后据此提出了一类改进的 Girvan-Newman 算法， 并在计算机产生的具有已知社团结构 的网络以及一些真实网络上测试了这些算法。 测试的结果显示无论是在计算机产生的网
4、络上还是在真实网络上改进后的算法都要比原算法有更优异的表现。另外，我们还将改 进的算法扩展到了具有内在权重的网络；测试的结果显示同样是考虑了内在边权，改进 算法的权重版本要胜过原算法的权重版本。 这些结果说明我们对算法的进行改进的尝试 是成功的，同时也证实了我们的改进方案的可行性。第五章对本文的工作进行了总结， 并对本领域的研究进行了展望。 关键词：复杂网络；社团结构；Girvan-Newman 算法；边介数；边聚类系数 II Abstract Complex networks have recently received extensive attention from physics an
5、d other disciplines. A lot of experimental findings have uncovered that complex networks in various fields share many common structural properties such as small-world property, scale-free feature, community structure etc. In the thesis, we studied the detection and characterization of the community
6、structure in networks. The emergence of community structure in complex networks means that networks often consist of groups of vertices within which connections are dense while between which they are sparser. Such a property of networks may play an important role in dynamics of networks, on the othe
7、r hand, communities in networks often correspond such functional units as real social groupings in social networks, sets of pages on related topics on the WWW, or sets of related papers on a single topic in citation networks. Thus, detecting and analyzing these communities in networks will help us u
8、nderstand the structure and function of real complex networks more effectively. In order to detect communities in networks quickly and accurately, a variety of community detection algorithms have been proposed, but it is still an important problem how to deal with the conflict between the time-compl
9、exity and accuracy of algorithms. We analyzed the existing algorithms for detecting community structure in complex networks systematically. Then, we designed a scheme for improving the accuracy of community structure algorithms, and proposed a class of improved algorithm according to the scheme. The
10、 thesis consists of five chapters. In chapter one, we gave a brief review for complex networks, and then introduced the main content and organization of this thesis. In chapter two, we briefly presented some structural properties of real networks, and introduced community structure in complex networ
11、ks in detail, including definitions of communities, community structure detection and evaluation of partitions of networks into communities. In chapter three, we investigated some community detection algorithms as well as their performance, and because of the need of our studies we analyzed the exte
12、nsion of these algorithms to weighted networks as well as the change of these algorithms performance after considering intrinsic edge weight of networks. In chapter four, we firstly designed a scheme for improving the accuracy of community detection algorithms in networks based on the analysis in pr
13、evious chapter, and then proposed a class of improved Girvan-Newman algorithms according to the scheme. Testing these algorithms on both artificial and real-world networks, we find that our improved algorithms can discover communities of networks better than the original algorithm. In addition, our
14、improved algorithms were also extended to weighted case in order to make use of the information contained in intrinsic edge weight; our test results shown that the III weighted versions of our improved algorithms also outperform that of the original algorithm, as the intrinsic edge weight in network
15、s is considered. These results indicated that we really improve the performance of the Girvan-Newman algorithm successfully, and it is also proved that our scheme for improving detection algorithms is also applicable. In chapter five, we presented a conclusion for our work and some prospects for fut
16、ure work in this field. Key Words: complex network; community structure; Girvan-Newman algorithm; edge betweenness; edge-clustering coefficient 湘潭大学湘潭大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和
