基于MapReduce聚类算法的复杂网络分簇研究
发布时间：2018-10-31 18:12
【摘要】：现实世界中诸如交通运输网络、社交网络等复杂系统都可建模成是由若干个“社团”或“簇”构成复杂网络,揭示其社团结构以便深入了解网络结构与分析网络行为特性受到研究者广泛关注。社团分簇就是要找到复杂网络中存在的社团结构,进而提取各社团结构中所蕴含的重要信息,但近年来随着移动互联网、社交网络、物联网的等复杂网络节点不断增加,网络规模日益增大,传统单机模式下的社团分簇方法已经不能满足大规模复杂网络分析的需求,如何应对大规模复杂网络社团分簇日益成为当前的研究热点。本文针对复杂网络分簇问题,提出了基于MapReduce聚类算法的复杂网络分簇研究,具体工作如下:首先,针对复杂网络社团分簇问题,提出了一种基于邻域搜索聚类算法的复杂网络分簇方法,该算法通过邻域搜索策略控制选取聚类中心,克服了传统聚类算法选取聚类中心的随机性和局限性,从而实现较优的社团分簇结果,实验结果表明在相对规模较小的复杂网络中本文算法具有较高的检测准确率。其次,针对复杂网络规模不断增大,传统单机模式已经不能满足大规模网络社团分簇需要问题,提出将基于邻域搜索聚类算法的复杂网络分簇方法进行MapReduce化,该方法依次进行数据预处理、计算节点的最短路径、计算邻域密度、选取聚类中心节点并分簇,以实现MapReduce化后大规模复杂网络社团分簇处理。最后,设计并搭建基于Hadoop集群的实验平台,实验结果表明,随着复杂网络规模的增大,本文算法MapReduce并行化在执行速度上对比于单机具有明显的优势,体现出较高的准确率和可靠性。
[Abstract]:Complex systems in the real world, such as transportation networks and social networks, can be modeled as complex networks consisting of several "communities" or "clusters". In order to understand the network structure and analyze the characteristics of network behavior, researchers pay more and more attention to revealing its community structure. Community clustering is to find out the community structure in the complex network, and then extract the important information contained in the community structure. But in recent years, with the mobile Internet, social network, Internet of things and other complex network nodes increasing. With the increasing of network scale, the traditional single-machine community clustering method can not meet the needs of large-scale complex network analysis. How to deal with the large-scale complex network community clustering has become a hot research topic. In order to solve the complex network clustering problem, this paper proposes a complex network clustering research based on MapReduce clustering algorithm. The specific work is as follows: firstly, aiming at the complex network community clustering problem, In this paper, a new clustering method based on neighborhood search clustering algorithm is proposed. The clustering center selection is controlled by neighborhood search strategy, which overcomes the randomness and limitation of traditional clustering algorithm. The experimental results show that the proposed algorithm has a high detection accuracy in a relatively small complex network. Secondly, in view of the increasing scale of complex network and the fact that the traditional single-machine mode can no longer meet the needs of large-scale network community clustering, a new clustering method based on neighborhood search clustering algorithm is proposed for MapReduce. The method performs data preprocessing in turn, calculates the shortest path of nodes, calculates neighborhood density, selects cluster center nodes and clusters, so as to achieve large-scale complex network community clustering after MapReduce. Finally, the experimental platform based on Hadoop cluster is designed and built. The experimental results show that with the increase of the scale of complex network, the parallel algorithm MapReduce has obvious advantages over single computer in execution speed. It shows high accuracy and reliability.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5
本文编号：2303127
[Abstract]:Complex systems in the real world, such as transportation networks and social networks, can be modeled as complex networks consisting of several "communities" or "clusters". In order to understand the network structure and analyze the characteristics of network behavior, researchers pay more and more attention to revealing its community structure. Community clustering is to find out the community structure in the complex network, and then extract the important information contained in the community structure. But in recent years, with the mobile Internet, social network, Internet of things and other complex network nodes increasing. With the increasing of network scale, the traditional single-machine community clustering method can not meet the needs of large-scale complex network analysis. How to deal with the large-scale complex network community clustering has become a hot research topic. In order to solve the complex network clustering problem, this paper proposes a complex network clustering research based on MapReduce clustering algorithm. The specific work is as follows: firstly, aiming at the complex network community clustering problem, In this paper, a new clustering method based on neighborhood search clustering algorithm is proposed. The clustering center selection is controlled by neighborhood search strategy, which overcomes the randomness and limitation of traditional clustering algorithm. The experimental results show that the proposed algorithm has a high detection accuracy in a relatively small complex network. Secondly, in view of the increasing scale of complex network and the fact that the traditional single-machine mode can no longer meet the needs of large-scale network community clustering, a new clustering method based on neighborhood search clustering algorithm is proposed for MapReduce. The method performs data preprocessing in turn, calculates the shortest path of nodes, calculates neighborhood density, selects cluster center nodes and clusters, so as to achieve large-scale complex network community clustering after MapReduce. Finally, the experimental platform based on Hadoop cluster is designed and built. The experimental results show that with the increase of the scale of complex network, the parallel algorithm MapReduce has obvious advantages over single computer in execution speed. It shows high accuracy and reliability.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5
【参考文献】
相关期刊论文 前4条
1 李建中;王宏志;高宏;;大数据可用性的研究进展[J];软件学报;2016年07期
2 郭平;王可;罗阿理;薛明志;;大数据分析中的计算智能研究现状与展望[J];软件学报;2015年11期
3 李刘强;桂小林;安健;孙雨;;采用模糊层次聚类的社会网络重叠社区检测算法[J];西安交通大学学报;2015年02期
4 杨博;刘大有;金弟;马海宾;;复杂网络聚类方法[J];软件学报;2009年01期
，本文编号：2303127
本文链接：https://www.wllwen.com/kejilunwen/yysx/2303127.html
