On the Permanence of Vertices in Network Communities

Abstract

Despite the prevalence of community detection algorithms, relatively less work has been done on understanding whether a network is indeed modular and how resilient the community structure is under perturbations. To address this issue, we propose a new vertex-based metric called "permanence", that can quantitatively give an estimate of the community-like structure of the network. The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon the following two factors: (i) the distribution of external connectivity of the vertex to individual communities and not the total external connectivity, and (ii) the strength of its internal connectivity and not just the total internal edges. In this paper, we demonstrate that compared to other metrics, permanence provides (i) a more accurate estimate of a derived community structure to the ground-truth community and (ii) is more sensitive to perturbations in the network. As a by-product of this study, we have also developed a community detection algorithm based on maximizing permanence. For a modular network structure, the results of our algorithm match well with ground-truth communities.

arXiv comment10 pages, 5 figures, 8 tables, Accepted in 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

References in corpus (14)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Maps of random walks on complex networks reveal community structure
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• An information-theoretic framework for resolving community structure in complex networks
• Limits of modularity maximization in community detection
• Spectral methods for network community detection and graph partitioning
• Robustness of community structure in networks
• Empirical Comparison of Algorithms for Network Community Detection

Cited by in corpus (4)

• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• On the evaluation potential of quality functions in community detection for different contexts
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures