【作者】 刘微；

【导师】 谢福鼎；

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

【摘要】 现实中存在的大量复杂系统都可以用各种各样的网络进行刻画。复杂网络是复杂系统的抽象表示,由节点和边组成。网络中的节点代表现实中的不同个体,边则代表这些个体之间的关系。复杂网络理论的研究不仅仅属于数学范畴,而是涉及到了从物理学到生物学,从工程技术到管理学和社会科学等众多领域的研究,并且受到越来越多的重视和关注。人类社会的日益网络化也需要人们对各种人工的和自然的复杂网络有更加深刻的认识和了解。复杂网络已成为网络时代科学研究中的一个极其重要的具有挑战性的课题,甚至被称为“网络的新科学”。更为重要的是,有越来越多的研究表明,许多看上去各不相同的网络之间都存在着非常惊人的相似之处,社团结构就是其中之一。发现网络中的社团结构,对于了解网络结构和分析网络特性都有着非常重要的意义。社团结构的分析在生物学领域、物理学领域、计算机图形领域和社会学领域等众多不同领域中都有着非常广泛的应用。因此,如何利用网络中的各种信息准确的分析社团结构,是一个值得研究的问题。本文正是通过对社团性质的深入研究,开展了如下的研究工作。一种基于共享邻居数的社团结构发现算法。该方法首先选取度最大的节点作为社团的初始节点。其次,计算已知社团与其邻居节点之间的共享邻居数。最后,根据共享邻居数的大小,找到与社团连接最强的节点,并且利用局部模块度判断是否将该点加入到已知社团中去,进而达到发现社团结构、实现网络聚类的目的。为了验证该算法的有效性和可行性,将该方法应用于三个典型的复杂网络,取得了较好的实验结果。基于局部信息的社团结构发现算法。通过定义边的聚类系数和基于局部信息,提出了一个寻找复杂网络中社团结构的算法。该方法首先在网络的剩余节点中寻找度最大的节点作为社团的初始节点。然后利用该节点的边聚类系数和该点的度数值,判断与社团相连的其他节点是否可以加入到节点所在的社团中。最后得到了复杂网络的社团结构。通过对三社团网络和空手道俱乐部网络的实验,证明了该方法的可行性和有效性。更多还原

【Abstract】 Many complex systems in the world can be modeled by a variety of complex networks. Complex networks which composed by the nodes and edges are the abstract representation of complex systems. The nodes represent different individuals, and the edges reflect the relationship between these individuals. The study of complex networks gets more and more attention in Mathematics, Physics, biology, engineering, management, science and etc.. The growing network of human society also needs to understand the variety of artificial and natural complex networks well. Complex network has become an extremely important and challenge issue in scientific research of the network age, and even called“the new science of networks”.More and more research shows that many different networks have very remarkable similarities. One of them is community structure. Detecting community structure in network is more significance for understanding the network structure and analyzing the network properties. There are very extensive applications for analyzing community structure in biology, physic, computer graph, society and many different fields. So, it is Worthwhile to analysis community structure accurately with variety information of network.By researching deeply in community structure, the following work has been introduced in this dissertation.An algorithm for detecting community structure based on shared neighbors is proposed. First, the node with maximum degree is chosen as the first node in the community. Then, this algorithm calculates the numbers of shared neighbors between the community and its neighbors. Finally, the shared neighbors are compared to find the closest node with the community. At the same time, the local modularity will be used to decide whether this node can be added into the community. Doing so, the algorithm will detect the community structure and cluster the network. It is tested in three typical networks, and the results prove the viability and effective of this algorithm.An algorithm for detecting structure in complex network based on local information is proposed. Based on the local information, an algorithm is proposed for discovering the communities in complex networks by introducing the definition of the edge cluster coefficient. To obtain the community structures in the networks, the node with maximum degree in remainder network is first found. And then, some edge cluster coefficients and nodes’degrees are computed to decide whether the nodes connected with the community can be added into the community. At last, the community structure is detected. It is tested at the three group network and the Zachary network, the results show the validity and effective of this algorithm.更多还原