Finding communities in sparse networks

Abstract

Spectral algorithms based on matrix representations of networks are often used to detect communities but classic spectral methods based on the adjacency matrix and its variants fail to detect communities in sparse networks. New spectral methods based on non-backtracking random walks have recently been introduced that successfully detect communities in many sparse networks. However, the spectrum of non-backtracking random walks ignores hanging trees in networks that can contain information about the community structure of networks. We introduce the reluctant backtracking operators that explicitly account for hanging trees as they admit a small probability of returning to the immediately previous node unlike the non-backtracking operators that forbid an immediate return. We show that the reluctant backtracking operators can detect communities in certain sparse networks where the non-backtracking operators cannot while performing comparably on benchmark stochastic block model networks and real world networks. We also show that the spectrum of the reluctant backtracking operator approximately optimises the standard modularity function similar to the flow matrix. Interestingly, for this family of non- and reluctant-backtracking operators the main determinant of performance on real-world networks is whether or not they are normalised to conserve probability at each node.

arXiv comment11 pages, 4 figures

References in corpus (18)

• The structure and function of complex networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Comparing community structure identification
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Hierarchical modularity in human brain functional networks
• Spectral redemption: clustering sparse networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Phase transition in the detection of modules in sparse networks
• Spectra and eigenvectors of scale-free networks
• Stochastic Block Models and Reconstruction
• Spectra of random graphs with arbitrary expected degrees
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Improving the performance of algorithms to find communities in networks
• Spectral community detection in sparse networks

Cited by in corpus (5)

• Community detection in networks: A user guide
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Multi-resolution community detection in massive networks
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Characterizing several properties of high-dimensional random Apollonian networks