The Design And Implementation Of Parallel Algorthm For Dynamic Community Detection And Evolution Analysis

In recent years,community detection has been hot issue in complex networks.A community is formed by vertices which belong to the same network and connect densely.The connections between communities are sparse.At present,various community detection algorithms have been proposed.However,changes in network structure are often neglected when taking static community detection,which also can not track the evolution of communities in dynamic network.Additionally,it is inefficient for the serial algorithms to mine and analyse community structure when mining for large-scale graphs with increasing amounts of data.Therefore,it is important for practical application to research parallel algorithm for dynamic community detection and evolution analysis.This paper conducts the design and implementation of dynamic community detection and evolution analysis based on Spark,which mainly includes the following parts:Firstly,this paper presents a parallel dynamic community detection algorithm based on increment under Spark framework named PIDCDS,which maximizes the total permanence of all vertices in the network to discover community structure.For parallel computation on GraphX,PIDCDS adopts a specialized permanence as the metric of community partition.At each time step,only permanence metric of incremental vertices will be computed to produce a new community structure.This algorithm can not only guarantee the accuracy of the result,but also reduce the amount of computation.Meanwhile,our experiments show that PIDCDS could obtain better stability and detect community similar to the real structure through comparison with the FacetNet dynamic community detection algorithm.Additionally,when comparing the running time of different scales of network on PIDCDS,it can be drawn that the algorithm performs well and holds a slow growth of executing time as the number of vertices and edges in a network increases.The larger number of cores will also accelerate our PIDCDS to some extent.When detecting communities in dynamic network through PIDCDS,this paper proposes a parallel dynamic community evolution algorithm.The algorithm designs the skeletal structure of a community and gets key vertices.Besides,it constructs the bipartite graph with communities as vertices and determines community evolution according to the distribution of key vertices in the bipartite graph.Then good results of event evolution analysis are received when the input of the parallel dynamic community evolution algorithm is the dynamic network formed by text data.Finally,this paper constructs a parallel graph mining system based on Spark and OSGI.A variety of algorithms are integrated into the system using the component technology and users can analyse large-scale social networks through the workflow pattern.