大规模复杂网络社区发现与社区进化分析技术研究

发布时间：2018-09-05 21:20

【摘要】：随着移动互联时代的到来,网络日益得以普及,各种社交网络平台的兴起,人们或多或少通过网络与其他人或物发生着联系,形成复杂的关系网络,产生了海量的网络数据。复杂网络的研究对广告投放、精准营销、内容推荐、用户行为预测等具有极大的价值,而社区发现与社区进化作为复杂网络分析中的研究热点,自提出以来,一直受到学者们的广泛关注,提出了大量的研究成果。对于社区发现,随着网络规模增大,传统社区发现算法已无法有效和高效地处理大规模网络数据,本文结合GraphX图计算框架,提出了新的大规模复杂网络社区并行发现算法。实验表明本文算法能够有效的处理大规模复杂网络数据,百万级以上节点处理时间约为4分钟,是Hadoop平台下并行发现算法运行时间的1/20,社区识别准确率比传统社区发现算法提高了 3%。对于社区进化,随着传统事件框架限制条件越来越宽松,挖掘出的事件虽然增多,但同时也挖掘出了大量冗余事件,而且这些框架没有考虑到事件的重叠性和伴随性。为了克服传统事件框架的问题,本文基于事件框架,提出了弱事件的概念,并对传统事件框架进行了改进,重新定义了各种事件,并给出了新的限制条件,最后提出了适用于弱事件挖掘的框架。实验表明本文社区演化框架发现事件比传统框架多22.9%,事件准确率提高了 4%,解决了弱社区挖掘问题。本文主要工作包括:(1)介绍了复杂网络社区发现及社区进化的研究背景与意义,并介绍了当前社区发现与社区进化方向的国内外研究现状及最新成果。(2)根据模块度思想,结合图论、网络性质及近似优化理论,提出多社区选择模型,并设计了新的模块度增量更新方法,算法首先计算出所有节点间的模块度增量,然后选取网络中所有具有最大模块度增量的社区进行合并,最后利用新的模块度增量更新方法,更新与合并社区相关的模块度增量,再结合GraphX设计了并行处理算法。(3)根据事件框架定义,提出了“弱扩张”、“弱收缩”、“弱分裂”、“弱合并”等新的事件,以解决在一段时间内社区结构同时发生多种事件的情况。为了能够准确的发现这些事件,提出了社区重叠度、社区隶属度、事件发现准确率等新概念。根据以上理论提出了基于弱事件的社区进化分析方法。(4)给出了上述算法的具体实现,并将本文所提的分别在仿真复杂网络和真实复杂网络数据上,同多个算法进行了对比,验证了本文所提算法的准确性和高效性,全面的分析了本文算法及对比算法的优劣之处。
[Abstract]:With the arrival of the era of mobile interconnection, the network is becoming more and more popular. With the rise of various social network platforms, people are more or less connected with other people or things through the network, forming a complex relationship network, and producing massive network data. The research of complex network has great value for advertising, accurate marketing, content recommendation, user behavior prediction, etc. Community discovery and community evolution have been the research focus of complex network analysis since they were put forward. It has been widely concerned by scholars and a large number of research results have been put forward. For community discovery, with the increase of network size, the traditional community discovery algorithm can not deal with large-scale network data effectively and efficiently. In this paper, a new parallel discovery algorithm for large-scale and complex network communities is proposed based on the GraphX graph computing framework. Experiments show that the algorithm can deal with large-scale complex network data effectively, and the processing time of multi-level nodes is about 4 minutes. It is 1 / 20 of the running time of parallel discovery algorithm based on Hadoop, and the accuracy of community recognition improves by 3% compared with traditional community discovery algorithm. For community evolution, with the loosening of the constraints of traditional event frameworks, the number of excavated events increases, but at the same time a large number of redundant events are mined, and these frameworks do not take into account the overlap and concomitant of events. In order to overcome the problem of traditional event framework, this paper proposes the concept of weak event based on event framework, and improves the traditional event framework, redefines all kinds of events, and gives new limiting conditions. Finally, a framework for weak event mining is proposed. The experiments show that the community evolution framework in this paper finds more events 22. 9 more than the traditional framework, and the accuracy of the event is improved by 4%, and the mining problem of weak communities is solved. The main work of this paper is as follows: (1) the research background and significance of complex network community discovery and community evolution are introduced, and the current research status and latest achievements of community discovery and community evolution at home and abroad are introduced. (2) according to modularity, Combined with graph theory, network properties and approximate optimization theory, a multi-community selection model is proposed, and a new modular degree increment updating method is designed. The algorithm first calculates the modularity increment among all nodes. Then all the communities with the largest modular degree increment in the network are selected to merge. Finally, the modular degree increment related to the merged community is updated by using the new modular degree increment updating method. The parallel processing algorithm is designed with GraphX. (3) according to the definition of event frame, new events such as "weak extension", "weak contraction", "weak splitting" and "weak merging" are proposed. To address multiple events that occur at the same time within the community structure. In order to find these events accurately, some new concepts, such as community overlap degree, community membership degree and event discovery accuracy rate, are proposed. Based on the above theory, a method of community evolution analysis based on weak event is proposed. (4) the realization of the above algorithm is given, and the simulation data of complex network and real complex network are compared with other algorithms. The accuracy and efficiency of the proposed algorithm are verified, and the advantages and disadvantages of the algorithm and the contrast algorithm are analyzed.
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】