大规模网络演化算法的研究与实现
发布时间：2018-09-12 14:05
【摘要】：随着互联网的飞速发展,互联网上的数据正以爆炸式的速度增长,互联网上由用户构成的各种网络的规模也飞速增长,大规模网络的时代已经到来。在分析大规模网络的时候,希望能够有一种快速、高效的方法分析复杂网络中随着时间改变社团结构的演化。尽管过去很多工作致力于静态社团发现算法,相对较少的工作发现动态网络中的社团结构,并且传统的静态社区发现算法直接用于动态社团发现普遍存在诸多缺点。为了解决动态网络中社团发现的问题,本文根据基于顶点的叫做持久力的度量,提出了一种增量式计算的动态社团发现新方法。该算法的中心思想利用动态网络短时平滑性假设,增量地分析动态网络中部分节点的社团归属,从而避免了对整个网络的节点全部重新计算社团归属,并且引入了一个叫做演化强度的新的度量来衡量增量计算过程中可能引入的误差以及网络拓扑结构发生突变导致的误差。同时,由于包含真实社团结构的动态网络数据很少,现有的人工合成方法的局限性,本文提出了一种新颖的包含真实社团结构的人工合成动态网络数据的方法,通过定义演化事件以及事件的演化率,我们能够得到更加真实的人工合成数据。除此之外,为了提供一种研究大规模动态网络中社团演化的途径,提出了基于Spark并行计算框架的动态社团发现算法,并通过不同规模的动态网络数据实验验证和分析了我们的并行算法。
[Abstract]:With the rapid development of the Internet, the data on the Internet is increasing at an explosive rate, and the scale of various networks made up of users on the Internet is also growing rapidly. The era of large-scale networks has arrived. When analyzing large-scale networks, it is hoped that there will be a fast and efficient way to analyze the evolution of community structures over time in complex networks. Although much work has been done in the past on static community discovery algorithms, relatively little work has been done to discover community structures in dynamic networks, and traditional static community discovery algorithms directly used in dynamic community discovery have many disadvantages. In order to solve the problem of community discovery in dynamic networks, a new dynamic community discovery method based on vertex called persistence is proposed in this paper. The central idea of this algorithm is to analyze the community ownership of some nodes in dynamic network incrementally by using the assumption of short-term smoothness of dynamic network, thus avoiding the recalculating of all nodes in the whole network. A new measure called evolutionary strength is introduced to measure the errors that may be introduced in the incremental computation process as well as the errors caused by the abrupt changes in the network topology. At the same time, due to the few dynamic network data containing real community structure and the limitations of existing artificial synthesis methods, this paper proposes a novel method of artificial synthesis dynamic network data containing real community structure. By defining evolutionary events and their evolution rates, we can obtain more realistic synthetic data. In addition, in order to provide a way to study community evolution in large-scale dynamic networks, a dynamic community discovery algorithm based on Spark parallel computing framework is proposed. The parallel algorithm is verified and analyzed by dynamic network data experiments of different scales.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
本文编号：2239241
[Abstract]:With the rapid development of the Internet, the data on the Internet is increasing at an explosive rate, and the scale of various networks made up of users on the Internet is also growing rapidly. The era of large-scale networks has arrived. When analyzing large-scale networks, it is hoped that there will be a fast and efficient way to analyze the evolution of community structures over time in complex networks. Although much work has been done in the past on static community discovery algorithms, relatively little work has been done to discover community structures in dynamic networks, and traditional static community discovery algorithms directly used in dynamic community discovery have many disadvantages. In order to solve the problem of community discovery in dynamic networks, a new dynamic community discovery method based on vertex called persistence is proposed in this paper. The central idea of this algorithm is to analyze the community ownership of some nodes in dynamic network incrementally by using the assumption of short-term smoothness of dynamic network, thus avoiding the recalculating of all nodes in the whole network. A new measure called evolutionary strength is introduced to measure the errors that may be introduced in the incremental computation process as well as the errors caused by the abrupt changes in the network topology. At the same time, due to the few dynamic network data containing real community structure and the limitations of existing artificial synthesis methods, this paper proposes a novel method of artificial synthesis dynamic network data containing real community structure. By defining evolutionary events and their evolution rates, we can obtain more realistic synthetic data. In addition, in order to provide a way to study community evolution in large-scale dynamic networks, a dynamic community discovery algorithm based on Spark parallel computing framework is proposed. The parallel algorithm is verified and analyzed by dynamic network data experiments of different scales.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
【参考文献】
相关期刊论文 前1条
1 王莉;程学旗;;在线社会网络的动态社区发现及演化[J];计算机学报;2015年02期
相关硕士学位论文 前1条
1 熊站营;基于增量和密度的动态网络社团检测算法[D];西安电子科技大学;2012年
，本文编号：2239241
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2239241.html
