复杂网络环境下的社区发现技术研究

发布时间：2018-05-05 10:02

本文选题：复杂网络 + 社区发现　；参考：《北京交通大学》2017年硕士论文

【摘要】：近年来,随着互联网及其上虚拟网络的规模日趋庞大,拓扑结构也越来越复杂。在这种复杂的网络结构中,个体偏好和群体关系具有很大的应用价值,而社区发现技术,是挖掘个体偏好及群体关系的基础性方法,得到了研究者的广泛关注。但是,当前的社区发现算法存在需要人为设定一些参数以获得准确的社区结构的问题,还有一些经典的社区发现算法无法挖掘网络重叠社区,这些问题都影响到复杂网络环境下社区发现的准确性。针对以上问题,本论文以复杂网络为研究环境,重点对社区属性以及重叠社区进行了分析研究,提出了一种能够适用于复杂网络的预处理模型以及一种重叠社区发现算法。论文的研究工作得到了国家自然科学基金项目(No.61172072、61271308)、北京市自然科学基金项目(No.4112045)和高等学校博士学科点专项科研基金(No.20100009110002)的支持。本论文的主要工作包括以下两个方面:(1)以马尔科夫聚类算法为基础,提出复杂网络社区的预处理模型。该预处理模型能够从复杂网络中分析出节点的重要性信息,得到网络中的中心节点,并能够根据得到的网络边结构信息,对已知的网络拓扑结构进行边权赋值。结合中心节点与边权赋值结果,进而得到预处理网络。该预处理网络中包含社区发现算法所需的先验性信息,因此能够降低人为设定参数对社区发现算法准确性的影响。(2)提出了一种基于随机游走的多标签重叠社区发现算法(Multi-Label Propagation algorithm based on Random Walk,简称 RW-MLP 算法)。本论文中,RW-MLP算法结合随机游走的全局性优势,利用经过预处理得到的网络结构信息,构建标签矩阵并进行标签传播,最后根据标签得到社区划分结果。RW-MLP算法在保证社区划分全局性的同时,起到了减小随机性、平衡社区规模的作用。本论文还分别在人工网络数据集与实际网络数据集上对预处理模型和RW-MLP算法进行了测试。数值计算结果表明,预处理模型能够得到准确的网络结构信息,并且能够提高社区发现算法的划分结果准确性,同时相对于其他重叠社区发现算法,RW-MLP算法的准确性也有了显著提高。
[Abstract]:In recent years, with the growing scale of the Internet and its virtual network, the topology is becoming more and more complex. In this complex network structure, individual preference and group relationship have great application value, and community discovery technology, as the basic method of mining individual preference and group relationship, has been widely concerned by researchers. However, the current community discovery algorithms need to set some parameters artificially in order to obtain accurate community structure, and some classical community discovery algorithms can not mine overlapping communities. These problems affect the accuracy of community discovery in complex network environment. Aiming at the above problems, this paper takes complex network as the research environment, focuses on the analysis of community attributes and overlapping communities, and proposes a preprocessing model and an overlapping community discovery algorithm that can be applied to complex networks. The research work of this paper has been supported by the National Natural Science Foundation Project No. 61172072N 61271308, Beijing Natural Science Foundation Project No. 4112045) and the Special Research Foundation for doctoral subject points in Colleges and Universities No. 20100009110002). The main work of this thesis includes the following two aspects: 1) based on Markov clustering algorithm, the preprocessing model of complex network community is proposed. The preprocessing model can analyze the importance information of nodes from complex networks and obtain the central nodes in the network. According to the information of the network edge structure, the model can assign the known network topology with edge weights. The preprocessing network is obtained by combining the evaluation results of center node and edge weight. The pre-processing network contains the priori information needed for the community discovery algorithm. Therefore, it can reduce the effect of artificial setting parameters on the accuracy of community discovery algorithm. (2) A multi-label overlapping community discovery algorithm based on random walk is proposed, which is called Multi-Label Propagation algorithm based on Random Walk, for short RW-MLP algorithm. In this paper, the RW-MLP algorithm combines the global advantage of random walk, using the network structure information obtained by preprocessing, the label matrix is constructed and propagated. Finally, according to the label, the RW-MLP algorithm can reduce the randomness and balance the community size while ensuring the overall community division. In this paper, the preprocessing model and RW-MLP algorithm are tested on the artificial network data set and the actual network data set respectively. The numerical results show that the preprocessing model can obtain accurate network structure information and improve the accuracy of community discovery algorithm. At the same time, the accuracy of RW-MLP algorithm is improved significantly compared with other overlapping community discovery algorithms.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】