节点重要度在社团划分中的应用研究

发布时间：2018-07-13 19:02

【摘要】：复杂网络中一些关键的核心节点对于网络中其他节点具有很大的影响力,因此找到这些关键的核心节点对于研究复杂网络的社团结构和节点的行为预测具有十分重要的意义。此外,复杂网络中很多的技术研究都是在社团划分的基础上进行的,因此对复杂网络社团划分的研究同样具有非常重要的意义。经过多年社团划分的研究,尽管出现了许多优秀的划分算法,但是在提高社团划分的准确度及降低算法的复杂度上仍然面临着挑战。针对现存算法准确度低复杂度高的问题,本文主要在如下几个方面进行研究和探索:(1)在划分社团之前,首先要准确找到社团中的核心节点,这涉及到节点重要度的评价。而当前节点重要度评价算法考虑的因素比较单一,不能准确找到社团的核心节点。本文考虑到邻居节点对节点自身重要度的影响,以及自身对邻居节点的影响,给出了节点重要度贡献矩阵,重要度贡献矩阵中将节点的K-shell值、邻居节点平均度及节点间的紧密度作为影响因素考虑在内。然后综合节点度和局部度中心节点等因素给出节点重要度的评价方法。(2)目前大多数的层次聚类算法划分社团的准确度都比较低,本文利用多个核心节点作为初始社团对复杂网络进行聚类,在计算节点与初始社团的相似度时,将初始社团中的节点重要度考虑在内,从而更加准确的计算出节点与初始社团的相似度,提高算法划分社团的准确度。最后对算法进行并行化分析,将其应用在分布式平台上,提高算法的运行效率。节点重要度的实验在两个简单直观、结构清晰的网络上进行,将其与单一的评价指标进行比较分析。社团划分的实验分别在真实网络和人工网络上进行,对其划分结果进行分析,同时将算法分别与其他节点重要度评价算法和层次聚类算法进行对比分析。并将并行化的算法在大规模的数据集上进行实验,验证算法的运行效率。实验结果表明,本文节点重要度评价算法能够准确有效的计算出节点的重要度,社团划分算法能够快速准确的划分出复杂网络的社团结构,算法并行化后能够快速的处理大规模复杂网络。
[Abstract]:Some key core nodes in complex networks have great influence on other nodes in the network, so it is very important to find these key core nodes to study the community structure and the behavior prediction of nodes in complex networks. In addition, many technical studies in complex networks are carried out on the basis of community division, so the study of community division in complex networks is also of great significance. After years of research on community partitioning, although there are many excellent partitioning algorithms, there are still challenges in improving the accuracy of community partitioning and reducing the complexity of the algorithm. Aiming at the problem of low accuracy and high complexity of existing algorithms, this paper mainly studies and explores the following aspects: (1) before dividing the community, we must first find the core nodes in the community accurately, which involves the evaluation of the importance of the nodes. However, the current node importance evaluation algorithm considers a single factor, and can not accurately find the core nodes of the community. In this paper, considering the influence of neighbor nodes on the importance degree of nodes and their own influence on neighbor nodes, the contribution matrix of importance degree of nodes is given, and the K-shell value of nodes is given in the contribution matrix of importance degree. The neighbor node average and the tightness between nodes are taken into account. Then the evaluation method of node importance is given by synthesizing node degree and local degree center node. (2) most hierarchical clustering algorithms have low accuracy in community division. In this paper, several core nodes are used as the initial community to cluster the complex network. When calculating the similarity between the nodes and the initial community, the importance of the nodes in the initial community is taken into account. Thus, the similarity between the nodes and the initial community can be calculated more accurately, and the accuracy of the algorithm can be improved. Finally, the parallelization analysis of the algorithm is carried out, and the algorithm is applied to the distributed platform to improve the efficiency of the algorithm. The experiment of node importance is carried out on two simple and intuitive networks with clear structure, which is compared with a single evaluation index. The experiments of community division are carried out on real network and artificial network respectively, and the results of classification are analyzed. At the same time, the algorithm is compared with other node importance evaluation algorithm and hierarchical clustering algorithm. The parallel algorithm is tested on a large scale data set to verify the efficiency of the algorithm. The experimental results show that the algorithm can calculate the importance of nodes accurately and effectively, and the community partition algorithm can quickly and accurately divide the community structure of complex networks. The parallel algorithm can deal with large scale complex networks quickly.
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP301.6

【参考文献】