复杂网络社团结构识别算法研究

发布时间：2018-11-20 17:53

【摘要】：自然界中,复杂网络系统随处可见。不管是人们可以感知的经济系统、引文网络系统、食物链网络系统,还是人们不可感知的生物化学系统,这些复杂网络系统都拥有着各自的属性和联系。为了充分地研究这些复杂网络系统,学者们抽象出一种模型—复杂网络。近年来,复杂网络的崛起引起了相关领域专家们的高度关注,也迅速成为他们研究的重点内容。学者们通过进一步地研究和分析,发现不同的现实网络模型却有着相同的特性。社团结构是描述复杂网络的一个关键特征,也是网络中最普通且最关键的一个拓扑属性。研究社团结构不仅具有重要的理论意义,而且具有实际应用价值。社团结构可以帮助人们更好地认识和了解网络的拓扑结构、复杂网络的功能模块、节点之间的隐藏关系,也可以预测网络系统的变化趋势。在复杂网络的社团结构识别过程中,模块度度量和其衍生出的度量指标起了很重要的作用,并催生了一大批重要的社团识别算法。但这种通过一般模块度优化方法来获取复杂网络的社团结构存在分辨率问题,影响了模块度优化方法的准确性和应用广度。针对模块度优化时所产生的分辨率问题,本文将提出应用增强模块度优化方法,从而有效地避免分辨率问题。由于社团结构的划分和聚类算法的思想类似,可以探索使用数据挖掘的方法和理论来研究复杂网络的社团结构问题。因此,本文将已成熟的聚类算法应用到复杂网络社团识别问题上。本文的主要工作如下:(1)基于增强模块度社团识别算法:首先,该算法应用随机游走理论把无向无权网络通过预处理转化为无向有权网络,预处理后的网络社团之间的连边权值小,社团内部中连边的权值大。然后,使用CNM算法对实际网络进行划分,并使用无向有权网络的模块度公式来衡量划分结果的好坏。本文提出了一种将随机游走理论与CNM算法结合的社团识别算法,其划分结果表明这种算法可以有效地避免模块度优化时所产生的分辨率问题。将该算法应用到人工网络或社团结构较为显著的现实网络中,识别出的社团效果较好。(2)基于聚类算法思想的社团结构识别算法:基于边的信息中心度,本文提出了节点亲密度的概念,并构建了节点亲密度矩阵。然后,采用聚类思想对节点亲密度矩阵进行聚类,从而形成了一种基于聚类思想的社团结构发现新算法。鉴于聚类算法对初始值选取敏感,本文制订了一些选取规则,有效地避免了此类问题。最后,通过经典网络模型证明了该算法的有效性。
[Abstract]:In nature, complex network systems can be found everywhere. Whether it is the economic system, the citation network system, the food chain network system or the biochemistry system that people can not perceive, these complex network systems all have their own properties and connections. In order to fully study these complex network systems, scholars abstract a model-complex network. In recent years, the rise of complex networks has attracted the attention of experts in related fields, and has quickly become the focus of their research. Through further research and analysis, scholars find that different real network models have the same characteristics. Community structure is a key feature in describing complex networks, and it is also the most common and key topological attribute in networks. The study of community structure not only has important theoretical significance, but also has practical application value. Community structure can help people better understand the topology of network, the function module of complex network, the hidden relationship between nodes, and predict the change trend of network system. In the process of community structure recognition in complex networks, modularity metric and its derived metrics play an important role, and give birth to a large number of important community recognition algorithms. However, the community structure of complex networks obtained by the general modular optimization method has the problem of resolution, which affects the accuracy and application breadth of the modular degree optimization method. Aiming at the resolution problem caused by modularity optimization, this paper proposes an enhanced modularity optimization method, which can effectively avoid the resolution problem. Because the division of community structure is similar to the idea of clustering algorithm, the method and theory of data mining can be used to study the problem of community structure in complex networks. Therefore, this paper applies the mature clustering algorithm to the complex network community recognition problem. The main work of this paper is as follows: (1) based on the enhanced modular degree community recognition algorithm: firstly, the algorithm applies random walk theory to transform the undirected unauthorized network into an undirected weighted network by preprocessing. After pretreatment, the weight of the connected edges is small and the weight of the connected edges in the communities is large. Then, the actual network is divided by CNM algorithm, and the module degree formula of undirected weighted network is used to measure the result of partition. In this paper, a community recognition algorithm based on random walk theory and CNM algorithm is proposed. The partition results show that this algorithm can effectively avoid the resolution problem caused by modularity optimization. The algorithm is applied to artificial network or real network with obvious community structure. (2) Community structure recognition algorithm based on clustering algorithm: edge based information center degree. In this paper, the concept of node affinity is proposed and the node affinity matrix is constructed. Then, the cluster idea is used to cluster the node affinity matrix, and a new community structure discovery algorithm based on clustering theory is formed. Since the clustering algorithm is sensitive to the selection of initial values, this paper formulates some selection rules to effectively avoid this kind of problem. Finally, the effectiveness of the algorithm is proved by classical network model.
【学位授予单位】：兰州理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】