Deep Community Detection

Abstract

A deep community in a graph is a connected component that can only be seen after removal of nodes or edges from the rest of the graph. This paper formulates the problem of detecting deep communities as multi-stage node removal that maximizes a new centrality measure, called the local Fiedler vector centrality (LFVC), at each stage. The LFVC is associated with the sensitivity of algebraic connectivity to node or edge removals. We prove that a greedy node/edge removal strategy, based on successive maximization of LFVC, has bounded performance loss relative to the optimal, but intractable, combinatorial batch removal strategy. Under a stochastic block model framework, we show that the greedy LFVC strategy can extract deep communities with probability one as the number of observations becomes large. We apply the greedy LFVC strategy to real-world social network datasets. Compared with conventional community detection methods we demonstrate improved ability to identify important communities and key members in the network.

15 pages, 13 figures, journal submission and supplementary file (Figures 11-13), to appear in IEEE Transactions on Signal Processing

References in corpus (7)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Graph spectra and the detectability of community structure in networks
• A Classification for Community Discovery Methods in Complex Networks

Cited by in corpus (13)

• Revealing Multiple Layers of Hidden Community Structure in Networks
• Trust from the past: Bayesian Personalized Ranking based Link Prediction in Knowledge Graphs
• Bias-Variance Tradeoff of Graph Laplacian Regularizer
• Incremental Method for Spectral Clustering of Increasing Orders
• iSIRA: Integrated Shift-Invert Residual Arnoldi Method for Graph Laplacian Matrices from Big Data
• Can GAN Learn Topological Features of a Graph?
• Comparing Graph Spectra of Adjacency and Laplacian Matrices
• Revisiting Spectral Graph Clustering with Generative Community Models
• Steering Macro-Scale Network Community Structure by Micro-Scale Features
• Hidden Community Detection in Social Networks
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• First-order bifurcation detection for dynamic complex networks
• Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications