On consensus-based community detection

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

Abstract

We consider networks in which every node updates its value in discrete time by taking a weighted average of the values of the nodes it interacts with. Using an objective function that quantifies the efficiency with which clusters of interacting nodes converge to consensus internally, we formulate an optimization problem that identifies distinct communities in the network. The optimal community detection problem is combinatorial in nature and intractable in general, and we use convex relaxations to reformulate the problem as a semidefinite program. We demonstrate the utility of our algorithm by applying it to some benchmark graphs from the network science literature.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Conference on Decision and Control
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1577-1582
Number of pages6
Volume2016-February
ISBN (Print)9781479978861
DOIs
StatePublished - Feb 8 2016
Event54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan
Duration: Dec 15 2015Dec 18 2015

Other

Other54th IEEE Conference on Decision and Control, CDC 2015
CountryJapan
CityOsaka
Period12/15/1512/18/15

Keywords

  • Clustering
  • community detection
  • consensus
  • convex relaxation
  • dynamical systems
  • graph partitioning
  • optimization
  • semidefinite programming
  • social networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'On consensus-based community detection'. Together they form a unique fingerprint.

  • Cite this

    Fardad, M. (2016). On consensus-based community detection. In Proceedings of the IEEE Conference on Decision and Control (Vol. 2016-February, pp. 1577-1582). [7402435] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2015.7402435