基于复杂网络的社区发现算法研究与实现

发布时间：2018-01-15 15:42

本文关键词：基于复杂网络的社区发现算法研究与实现　出处：《南京理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：近年来,随着互联网(Internet)的不断发展普及,各种网络应用平台如雨后春笋般出现,人们已经生活在充满各种各样复杂网络的环境中。因此,社会网络分析已经成为各界学者关注的重要话题。而在复杂网络数据集上进行相关分析,并发现存在于网络数据中的关键性规律和信息,已经成为研究复杂网络的主要手段和目的。在复杂网络中,人相当于节点,人与人之间的联系相当于节点之间的边。人们通过大量研究发现,在复杂网络中都普遍存在社区结构。社区结构代表着具有相似属性或扮演相似角色的节点集合。通常情况下,社区内部的节点之间具有更加紧密的联系。通过对社区结构的研究,可以对复杂网络内部结构与属性进行深入的研究与探索,从而发现其隐含规律并对其行为进行预测。因此,对社区结构的发现与研究,已经成为计算机领域的重要研究课题之一。本文将对复杂网络,社区结构,社区发现算法,社会网络分析等话题进行分析与研究,主要包括以下几个方面的内容:(1)针对现有社区发现算法存在的低准确度问题,本文提出了一种基于中心节点的社区发现算法。通过各节点度数及节点间相似度寻找社区的中心节点,然后利用局部模块度对各个社区进行优化,并根据节点吸引力将孤立节点和重叠社区节点尽量归入其社区,最终获得整个复杂网络的社区结构。(2)针对基于中心节点的社区发现算法在进行社区划分时每个节点默认在复杂网络中担任相同角色,在模块度计算时权值相同,从而导致不同节点无法体现其自身在网络中所承担的角色与价值的问题。本文引入PageRank算法的基本思想,提出核心子团的概念。为了体现出不同节点在网络中所担任的不同角色,本文还提出加权局部社区贡献度的概念,并在此基础上提出一种基于核心子团的社区发现算法。在找到个社区中心节点的基础上,通过节点度等特征找到该社区的核心子团,然后利用加权局部模块度对各个社区进行优化,并对未被划分社区的特殊节点进行社区优化,从而获得整个网络的社区划分。(3)本文提出的两种算法在复杂网络应用中具有一定的优势,通过在复杂网络数据集上进行社区划分实验,并与相关社区发现算法进行准确度和运行时间对比。最终可以发现,本文中的社区发现算法具有一定的优越性。
[Abstract]:In recent years, with the continuous development and popularization of Internet, a variety of network application platforms have sprung up, people have been living in a variety of complex network environment. Social network analysis has become an important topic of concern to scholars from all walks of life, and related analysis is carried out on the complex network data set, and the key laws and information that exist in the network data are found. It has become the main means and ends to study complex networks. In complex networks, people are equivalent to nodes, and the connections between people are equivalent to the edges between nodes. Community structures are common in complex networks. Community structures represent sets of nodes that have similar attributes or play similar roles. Through the study of community structure, the internal structure and attributes of complex network can be deeply studied and explored. Therefore, the discovery and study of community structure has become one of the important research topics in the field of computer. Community discovery algorithm, social network analysis and other topics for analysis and research, mainly including the following aspects of the content: 1) the existing community discovery algorithm for the low accuracy problem. In this paper, we propose a community discovery algorithm based on the central node. We find the central node of the community through the degree of each node and the similarity between the nodes, and then optimize each community by using the local module degree. And according to the node attraction, the isolated nodes and overlapping community nodes are classified into their communities as far as possible. Finally, the community structure of the whole complex network is obtained. 2) for the community discovery algorithm based on the central node, each node plays the same role in the complex network by default. The weight value is the same when the module degree is calculated, which leads to the problem that different nodes can not reflect their own role and value in the network. In this paper, the basic idea of PageRank algorithm is introduced. In order to reflect the different roles played by different nodes in the network, this paper also proposes the concept of weighted local community contribution. On this basis, a community discovery algorithm based on the core cluster is proposed. Based on finding a community central node, the core sub-cluster of the community is found by the node degree and other characteristics. Then the weighted local module degree is used to optimize each community, and the special nodes that are not divided into communities are optimized. In order to obtain the community partition of the whole network.) the two algorithms proposed in this paper have some advantages in the application of complex network, through the community partition experiment on the complex network data set. Finally, we can find that the community discovery algorithm in this paper has some advantages.
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】