有向网络上社团检测算法的研究

发布时间：2018-07-12 08:13

本文选题：社团检测 + 有向网络　；参考：《西安理工大学》2017年硕士论文

【摘要】：社团结构是复杂网络研究的热点,近些年来提出了许多社团检测算法,但目前提出的大多数算法主要适用于无向网络的社团结构挖掘,对于有向网络这些算法往往难以取得较好的社团检测效果。另外,大规模数据量的产生使得传统的社团检测算法不能满足计算效率以及数据存储等方面的需求。因此,寻找大规模有向网络的社团检测算法对于社团的研究具有重要的意义。本文主要工作如下:(1)对复杂网络的理论基础、社团的概念以及Hadoop技术进行了详细的介绍,分析了一些具有代表性的社团检测算法并指出其各自的优缺点;深入研究了社团检测的研究现状和所面临的问题。(2)研究基于相似度的有向网络社团检测算法,该算法利用网络的方向信息指导节点相似度的计算,从而把有向网络的拓扑结构信息转化为代数值,然后利用相似度改进CNM算法,结合CNM算法本身的优点提高了算法的准确性和适用性。(3)针对传统社团检测算法在单机环境下不能有效处理大规模网络的局限性,使用MapReduce分布式编程模型对本文的算法进行并行化,使得大规模网络数据的社团检测得以实现。基于相似度的有向网络社团检测算法利用相似度改进CNM算法,使得算法与网络的拓扑结构相关,并且利用方向信息指导相似度的计算,使得有向网络社团检测得以实现。在单机和分布式环境下分别进行实验,结果表明本文的算法具有较高的准确性,对大规模网络数据的处理具有高效性。
[Abstract]:Community structure is a hot topic in the research of complex networks. In recent years, many community detection algorithms have been proposed, but most of the algorithms proposed at present are mainly suitable for community structure mining in undirected networks. For directed networks, these algorithms are often difficult to achieve better community detection results. In addition, because of the large amount of data, the traditional community detection algorithm can not meet the needs of computing efficiency and data storage. Therefore, it is of great significance to find a large-scale directed network community detection algorithm for community research. The main work of this paper is as follows: (1) the theoretical basis of complex network, the concept of community and Hadoop technology are introduced in detail, and some representative community detection algorithms are analyzed and their advantages and disadvantages are pointed out. The current situation and problems of community detection are deeply studied. (2) the similarity based directed network community detection algorithm is studied, which uses the direction information of the network to guide the node similarity calculation. Then the topological structure information of the directed network is transformed into the algebraic value, and then the similarity is used to improve the CNM algorithm. Combined with the advantages of CNM algorithm, the accuracy and applicability of the algorithm are improved. (3) aiming at the limitation of traditional community detection algorithm can not effectively deal with large-scale networks in a single computer environment, The algorithm is parallelized by MapReduce distributed programming model, which makes the community detection of large-scale network data possible. Similarity based directed network community detection algorithm using similarity to improve the CNM algorithm, make the algorithm related to the network topology, and use direction information to guide the similarity calculation, so that the directed network community detection can be realized. Experiments are carried out in single computer and distributed environment. The results show that the proposed algorithm has high accuracy and high efficiency for large-scale network data processing.
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】