Deep Community Detection

DOI10.1109/TSP.2015.2458782zbMATH Open1394.94727arXiv1407.6071OpenAlexW1647709314MaRDI QIDQ4580886FDOQ4580886

Authors: Pin-Yu Chen, Alfred O. III Hero 

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1407.6071

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Detection theory in information and communication theory (94A13) Applications of graph theory to circuits and networks (94C15)

Cited In (3)

• iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
• High-Speed and Noise-Robust Embedding of Hypergraphs Based on Double-Centered Incidence Matrix
• Title not available (Why is that?)

This page was built for publication: Deep Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580886)