A Parallel Algorithm to Find Overlapping Community Structure in Directed and Weighted Complex Networks

摘要

Based on the BSP (Bulk Synchronous Parallel) computing framework, this paper proposes a parallel algorithm to find overlapping community structure in directed and weighted complex networks. The algorithm is composed of four parts, job distribution, finding natural communities, passing information in cluster and merging the similar natural communities. The main idea of the algorithm is finding the local maxima of a modularity function by local, iterative search to ensure that each vertex in network at least belongs to one natural community. By iteratively merging the similar natural communities we get a series of schemes and choose the scheme which results in the maximum modularity as the best scheme. By using Hama which is a pure BSP computing framework, we conduct experiments in several real networks. The results show the algorithm can give an original scheme very fast and give the best scheme with high accuracy.