Ensemble-based algorithms to detect disjoint and overlapping communities in networks

Tanmoy Chakraborty, Noseong Park, V. S. Subrahmanian

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

10 Scopus citations

Abstract

Given a set AL of community detection algorithms and a graph G as inputs, we propose two ensemble methods EnDisCo and MeDOC that (respectively) identify disjoint and overlapping communities in G. EnDisCo transforms a graph into a latent feature space by leveraging multiple base solutions and discovers disjoint community structure. MeDOC groups similar base communities into a meta-community and detects both disjoint and overlapping community structures. Experiments are conducted at different scales on both synthetically generated networks as well as on several real-world networks for which the underlying ground-truth community structure is available. Our extensive experiments show that both algorithms outperform state-of-the-art non-ensemble algorithms by a significant margin. Moreover, we compare EnDisCo and MeDOC with a recent ensemble method for disjoint community detection and show that our approaches achieve superior performance. To the best of our knowledge, MeDOC is the first ensemble approach for overlapping community detection.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
EditorsRavi Kumar, James Caverlee, Hanghang Tong
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages73-80
Number of pages8
ISBN (Electronic)9781509028467
DOIs
StatePublished - Nov 21 2016
Externally publishedYes
Event2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States
Duration: Aug 18 2016Aug 21 2016

Publication series

NameProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

Other

Other2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
Country/TerritoryUnited States
CitySan Francisco
Period8/18/168/21/16

Funding

Parts of this work were funded by ARO Grants W911NF-16-1-0342, W911NF1110344, W911NF1410358, by ONR Grant N00014-13-1-0703, and Maryland Procurement Ofce under Contract No. H98230-14-C-0137

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Sociology and Political Science
  • Communication

Fingerprint

Dive into the research topics of 'Ensemble-based algorithms to detect disjoint and overlapping communities in networks'. Together they form a unique fingerprint.

Cite this