基于Spark的大规模复杂网络社区发现算法的设计与实现

发布时间：2018-07-21 09:30

【摘要】：现实生活存在着许多复杂系统,这些系统往往以一种复杂网络的形式展现或者可以转换为复杂网络形式。这些网络大多呈现出大小不一的社团结构(社区),所谓社团结构就是社团内部的点之间联系紧密,社团之间联系较为稀疏的一种图的节点归属划分。目前,现实中的社交网络的用户量早已达到亿级别,并且每天呈现爆炸式的数量增长。因此,在大规模复杂网络中发现社团结果在网络结构的理论研究和网络分析实际应用中具有重要意义。本课题基于Spark分布式计算框架进行大规模复杂网络的研究,主要有以下几方面工作:本课题通过对社团发现算法SHRINK研究,结合边图概念提出了一种新的重叠社团发现算法LinkSRHINK算法。该算法结合了基于密度社团发现算法,基于模块度优化算法和基于层次划分算法,拥有社团发现结果唯一确定、可以准确发现网络结构中的中心点和孤立点和社团结构避免过度重叠的优点。此外,L inkSHRINK算法还提出一个新颖概念:社团重叠度,从而可以发现具有不同重叠度的社团结构。实验表明,该算法在真实网络和人工生成网络上表现都优于经典的重叠社团发现算法。由于LinkSHRINK算法无法在大规模网络中正常运行,本课题通过采用图抽样和基于Spark分布式计算框架并行化LinkSHRINK从而提出新算法PLinkSHRINK算法较好地解决该问题。作为对比算法,本课题还实现了基于Hadoop平台并行LinkSRHINK的算法:MLinnkSRHINK算法。实验证明PLinkSHRINK算法的性能优于MLinkSRHINK算法和单机版的LinkSHRINK算法。最后,本课题基于分布式计算框架设计提出了一个高效便捷的大规模图挖掘系统BDAP。该系统集成了相应的图属性计算和社团发现算法,采用工作流模式与用户交互,方便用户使用。
[Abstract]:There are many complex systems in real life. These systems are often displayed in the form of a complex network or can be converted into complex network forms. Most of these networks present a community structure of different sizes. The so-called community structure is a close link between the points within the community and a relatively sparse type of association. At present, the user of social networks in reality has already reached hundreds of millions of users, and presents an explosive number of increase every day. Therefore, the discovery of community results in large-scale complex networks is of great significance in the theoretical research of network structure and the practical application of network analysis. This topic is based on Spark distributed computing. The framework of large-scale complex network research, mainly in the following aspects: this topic through the community discovery algorithm SHRINK research, combined with the concept of edge graph proposed a new overlapping community discovery algorithm LinkSRHINK algorithm. This algorithm is based on the density community discovery algorithm, based on modularity optimization algorithm and hierarchy based The L inkSHRINK algorithm also presents a new concept: the overlap degree of the community, so that the community structure with different overlapping degrees can be found. The experiment shows that the algorithm is true. The performance of real network and artificial generation network is better than classical overlapping association discovery algorithm. Because LinkSHRINK algorithm can not run normally in large-scale network, this topic proposes a new algorithm PLinkSHRINK algorithm to solve the problem by using graph sampling and parallel LinkSHRINK based on Spark distributed computing framework. In contrast, this topic also implements a parallel LinkSRHINK based algorithm based on Hadoop platform: MLinnkSRHINK algorithm. The experiment proves that the performance of the PLinkSHRINK algorithm is superior to the MLinkSRHINK algorithm and the single machine version LinkSHRINK algorithm. Finally, a efficient and convenient large-scale graph mining system BDAP. is proposed based on the distributed computing framework design. The system integrates corresponding graph attribute calculation and community discovery algorithm, and uses workflow mode to interact with users to facilitate users.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP301.6

【相似文献】