Overlapping community detection via constrained PARAFAC: A divide and conquer approach

Fatemeh Sheikholeslami, Georgios B. Giannakis

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

4 Scopus citations

Abstract

The task of community detection over complex networks is of paramount importance in a multitude of applications. The present work puts forward a top-to-bottom community identification approach, termed DC-EgoTen, in which an egonet-tensor (EgoTen) based algorithm is developed in a divide-and-conquer (DC) fashion for breaking the network into smaller subgraphs, out of which the underlying communities progressively emerge. In particular, each step of DC-EgoTen forms a multi-dimensional egonet-based representation of the graph, whose induced structure enables casting the task of overlapping community identification as a constrained PARAFAC decomposition. Thanks to the higher representational capacity of tensors, the novel egonet-based representation improves the quality of detected communities by capturing multi-hop connectivity patterns of the network. In addition, the top-to-bottom approach ensures successive refinement of identified communities, so that the desired resolution is achieved. Synthetic as well as real-world tests corroborate the effectiveness of DC-EgoTen.

Original languageEnglish (US)
Title of host publicationProceedings - 17th IEEE International Conference on Data Mining, ICDM 2017
EditorsGeorge Karypis, Srinivas Alu, Vijay Raghavan, Xindong Wu, Lucio Miele
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages127-136
Number of pages10
ISBN (Electronic)9781538638347
DOIs
StatePublished - Dec 15 2017
Event17th IEEE International Conference on Data Mining, ICDM 2017 - New Orleans, United States
Duration: Nov 18 2017Nov 21 2017

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
Volume2017-November
ISSN (Print)1550-4786

Other

Other17th IEEE International Conference on Data Mining, ICDM 2017
CountryUnited States
CityNew Orleans
Period11/18/1711/21/17

Keywords

  • Community detection
  • Constrained PARAFAC
  • Egonet subgraphs
  • Overlapping communities
  • Tensor decomposition

Fingerprint Dive into the research topics of 'Overlapping community detection via constrained PARAFAC: A divide and conquer approach'. Together they form a unique fingerprint.

  • Cite this

    Sheikholeslami, F., & Giannakis, G. B. (2017). Overlapping community detection via constrained PARAFAC: A divide and conquer approach. In G. Karypis, S. Alu, V. Raghavan, X. Wu, & L. Miele (Eds.), Proceedings - 17th IEEE International Conference on Data Mining, ICDM 2017 (pp. 127-136). (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2017-November). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDM.2017.22