On the permanence of vertices in network communities

Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Animesh Mukherjee, Sanjukta Bhowmick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationKDD 2014 - Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery
Pages1396-1405
Number of pages10
ISBN (Print)9781450329569
DOIs
StatePublished - 2014
Event20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014 - New York, NY, United States
Duration: Aug 24 2014Aug 27 2014

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014
CountryUnited States
CityNew York, NY
Period8/24/148/27/14

Keywords

  • community analysis
  • modularity
  • permanence

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'On the permanence of vertices in network communities'. Together they form a unique fingerprint.

  • Cite this

    Chakraborty, T., Srinivasan, S., Ganguly, N., Mukherjee, A., & Bhowmick, S. (2014). On the permanence of vertices in network communities. In KDD 2014 - Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1396-1405). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/2623330.2623707