Study On The Parallel Overlapping Community Detection

Many complex systems in the real world can be represented as topological forms of complex networks.Community structure exists extensively in complex networks and there are much more intra-connections in the same community than inter-connections among different communities.The study of community structure will help to understand the structure and function of network,which is of great significance for the analysis and research of complex networks.Community detection is to find the underlying community structures in complex networks.Based on the research of existing overlapping community detection algorithms,this paper presents two parallel methods surrounding with measurement of nodes' importance and fuzzy community detection and local community detection,and can find overlapping nodes in large scale networks.Firstly,a stable overlapping community detection algorithm based on the importance and similarity of nodes is presented to solve the problem of no unique results caused by fuzzy c-means algorithm.The presented algorithm filters the nodes by nodes' importance and distance between nodes,the remained nodes naturally become the initial clustering centroids of fuzzy c-means algorithm avoiding the influence of random factors in the original algorithm.In the meantime,the similarity measure based on s-hops is introduced to enrich the information of similarity matrix.Thereafter,optimizing and implementing the algorithm in spark and verify its effectiveness.Secondly,aiming at the high time-consuming and poor scalability of community detection algorithms based on the global network,a parallel overlapping community detection algorithm based on k-core decomposition is presented in this paper.This algorithm quickly obtain the global and local node's importance by k-core decomposition and local clustering coefficient with the help of Spark and selects seed nodes according to certain mechanism.All the seed nodes can concurrently grow into a local community and the unassigned nodes can also be determined by the cumulative nodes' influence of local communities.The experimental results of artificial synthetic networks and real network datasets show that the presented algorithm can effectively discovery overlapping communities.At last,the prototype system of parallel overlapping community detection is designed and implemented in this paper.This system can not only transform different formats of network datasets,but also rapidly calculate network characteristics such as clustering coefficient,edge betweenness and shortest paths.But above all,this system can efficiently detect overlapping communities in the network and visualize the results of community division.