Community detection based on first passage probabilities

Abstract

Community detection is of fundamental significance for understanding the topology characters and the spreading dynamics on complex networks. While random walk is widely used and is proven effective in many community detection algorithms, there still exists two major defects: (i) the maximal length of random walk is too large to distinguish the clustering information if using the average step of all possible random walks; (ii) the useful community information at all other step lengths are missed if using a pre-assigned maximal length. In this paper, we propose a novel community detection method based on the first passage probabilities (FPPM), equipped with a new similarity measure that incorporates the complete structural information within the maximal step length. Here the diameter of the network is chosen as an appropriate boundary of random walks which is adaptive to different networks. Then we use the hierarchical clustering to group the vertices into communities and further select the best division through the corresponding modularity values. Finally, a post-processing strategy is designed to integrate the unreasonable small communities, which significantly improves the accuracy of community division. Surprisingly, the numerical simulations show that FPPM performs best compared to several classic algorithms on both synthetic benchmarks and real-world networks, which reveals the universality and effectiveness of our method.

References in corpus (27)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection in networks: A user guide
• Detecting causal associations in large nonlinear time series datasets
• Random walks and diffusion on networks
• Spectral redemption: clustering sparse networks
• Modern hierarchical, agglomerative clustering algorithms
• Mixture models and exploratory analysis in networks
• Detecting communities in large networks
• Distance, dissimilarity index, and network community structure
• Community Detection as an Inference Problem
• Local structure can identify and quantify influential global spreaders in large scale social networks
• Community Detecting By Signaling on Complex Networks
• Unveiling the Multi-fractal Structure of Complex Networks
• Homophily on social networks changes evolutionary advantage in competitive information diffusion
• Spectral community detection in sparse networks