【作者】 张磊；

【导师】 谢福鼎；

【作者基本信息】 辽宁师范大学 ， 软件与理论， 2009， 硕士

【摘要】 复杂网络可以用来描述现实社会中的实际网络,比如Internet,交通网,电子邮件联系网,电力网等常见的实体网络。它也可以表示包含大量个体和个体之间相互作用的系统,如恒星及星际气体中的化学反应,人与人之间的社会关系,物种之间的捕食关系,科学研究中的合作关系等。人们生活在一个充满着各种各样的复杂网络的世界中。这也使得对复杂网络的研究成为必要。由于复杂网络中节点众多,结构复杂,所以研究复杂网络非常困难。然而,复杂网络的社团结构性质可以帮助了解网络结构与分析网络特性,因此寻找网络中的社团结构具有极为重要的意义。从20世纪末开始,复杂网络的研究已渗透到生命科学、数理学科和工程学科、社会科学等众多不同的领域。对复杂网络的研究,已成为科学研究中一个极其重要的富有挑战性的课题。寻找复杂网络中的社团结构已经成为复杂网络研究的热点之一,本文正是对复杂网络中社团结构的发现方法进行研究。本文在详细研究已有的复杂网络社团结构发现算法的基础上,提出了两种新的社团发现方法:(1)在谱平分法的基础上,提出了一种新的复杂网络社团结构发现算法——基于谱平分法的社团划分方法。该算法对传统的SNN相似度矩阵进行改进,然后将改进后的矩阵与谱平分算法相结合来寻找网络中的社团结构。通过多个经典实例的验证,证明该方法对社团结构不明显的网络也具有较好的划分效果。并且与目前比较流行的社团发现算法进行比较可知,利用该算法划分得到的结果准确率较高。(2)将Wu-Huberman算法和贪婪算法的思想相结合,提出了一种新的社团发现方法——基于Wu-Huberman方法和贪婪算法相结合的聚类算法。该方法定义了一种新的局部模块度计算方法,并采用了新的距离衡量标准,即斜率距离来衡量社团之间的距离。通过实例验证可知,在社团数目未知的情况下,与已有的社团发现算法相比,该方法在计算速度上也有了明显的改善。更多还原

【Abstract】 Complex networks provide powerful tools to describe real networks in nature and society, such as the Internet, traffic system, Email communication system and cellular metabolism. They also indicate systems which include a large number of individuals interacting with each other, for instance, chemical reactions in stars and interstellar gases, the social relationships between different individuals, the food cycles in nature and the collaborations in science research. People live in the world which filled with kinds of complex networks. So it is necessary and significant to investigate the properties of complex networks. But it is difficult to study some of characteristics of complex network duo to the huge number of nodes and complicated structures in networks. The community structures in complex network are helpful to comprehend the structures of networks and analyze the specific properties of the whole network. Therefore, detection of community structure becomes very important and meaningful.Beginning at the end of 20th century, the research of complex network has been permeating through different areas, such as life science, mathematical science, engineering science, social science and so on. It becomes a very important and challenged subject in scientific research. Detecting community structure becomes one of the most popular issues in complex networks.Some classical detecting community structure algorithms are investigated in detail firstly, and then two new methods are proposed.(1) Based on the spectral bisection method, the paper gives a new algorithm for detecting the community structure in complex networks——a community partitioning algorithm based on spectral bisection method. This approach improves SNN similarity matrix and combines it with spectral bisection method to find the community structure. The experiments show the validity of the method. It also proves that the method is efficient to those networks with unobvious community structure. The result obtained here is compared with other popular ones. The conclusion is that the accuracy of the results calculated by this approach is much better than the known ones.(2) Based on Wu-Huberman method and greedy algorithm, this paper proposes a new clustering algorithm——a new clustering algorithm based on Wu-Huberman method and greedy algorithm. This method defines a new calculative formula of local modularity and a distance measure criterion named slope distance. The experiments show the validity of the algorithm. The result is that the speed calculated by this approach is much faster than the current ones.更多还原