Community Detection And Evolution Analaysis Technique In Large-scale Complex Networks

With the advent of mobile Internet era,the network has become increasingly popular,especially social networks, with people contacted with other people or things more or less through them, and they have produced massive data. The study of complex network is of great value to advertising, precision marketing, content recommendation and user behavior prediction. Community discovery and evolution is the research hotspots in complex network analysis, and has been widely concerned by scholars, a lot of research results has been put forward.For community detection, with the increasing of network data, traditional community detection algorithms have been unable to deal with large-scale networks effectively and accurately. Based on the GraphX distributed computing model, this thesis proposed a parallel algorithm for discovering communities in large-scale complex networks. The experiments are conducted on several real and synthetic network datasets and results demonstrate that the algorithm proposed in this thesis can effectively deal with the problem of partitioning the large-scale networks. In particularly, it only takes about four minutes to handling more than one million nodes for community discovery. In addition, the time cost is reduced to 1/20 comparing with the parallel algorithm based on Hadoop. The accuracy is improved by 3%when comparing to the traditional community discovery algorithms.For community evolution, along with the traditional event framework more and more relaxed, the count of events mined out by these frameworks increases, but the count of redundant events also increases. Meanwhile, these frameworks do not take into account with the overlapping and concomitance between events. In order to overcome the problem of traditional frameworks, this thesis puts forward the concept of weak event, and redefines all events, and new constraints of events are given. A lot of experiment on real dynamic networks and simulation dynamic networks data sets show that the new framework can effectively deal with weak events which the traditional community evolution framework can not handle with. The number of strong events mined out by the framework proposed in this thesis is 22.9% more than traditional frameworks,and event detection accuracy is about 4%higher than traditional event frameworks.The main work of this thesis includes:(1) Firstly, it introduces the research background and significance of complex network community discovery and evolution, the current research status and latest achievements of community discovery and evolution at home and abroad.(2) According to the modularity idea, this thesis proposed multi-community selection model combining with graph theory, approximation optimization theory, and new increment of modularity updating method is designed. The algorithm first calculates the modularity among all nodes in the network,and then selects all communities with the maximum increment of modularity to merge, finally using new modularity incremental update method update increment of modularity. Parallel algorithm is designed combined with GraphX.(3) According to event framework, weak event is defined in this thesis, such as weak expand, weak split, weak merge and weak shrink, to solve the problem that traditional event framework cannot deal with these weak events which occur with other event at the same time in a period of time. In order to find out all of the traditional events and weak events, this paper proposed the concept of community overlap, community subjection .etc. Based on the above theories, a community evolution analysis method based on weak event is proposed.(4) Finally, realization of the above algorithm is given. Experiment is implemented on the simulation complex networks and real complex networks, with comparing to a number of algorithms to verify the accuracy and efficiency of the proposed algorithm in this thesis.