Advantage of overlapping clusters for minimizing conductance

Rohit Khandekar, Guy Kortsarz, Vahab Mirrokni

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

8 Scopus citations

Abstract

Graph clustering is an important problem with applications to bioinformatics, community discovery in social networks, distributed computing, etc. While most of the research in this area has focused on clustering using disjoint clusters, many real datasets have inherently overlapping clusters. We compare overlapping and non-overlapping clusterings in graphs in the context of minimizing their conductance. It is known that allowing clusters to overlap gives better results in practice. We prove that overlapping clustering may be significantly better than non-overlapping clustering with respect to conductance, even in a theoretical setting. For minimizing the maximum conductance over the clusters, we give examples demonstrating that allowing overlaps can yield significantly better clusterings, namely, one that has much smaller optimum. In addition for the min-max variant, the overlapping version admits a simple approximation algorithm, while our algorithm for the non-overlapping version is complex and yields worse approximation ratio due to the presence of the additional constraint. Somewhat surprisingly, for the problem of minimizing the sum of conductances, we found out that allowing overlap does not really help. We show how to apply a general technique to transform any overlapping clustering into a non-overlapping one with only a modest increase in the sum of conductances. This uncrossing technique is of independent interest and may find further applications in the future.

Original languageEnglish (US)
Title of host publicationLATIN 2012
Subtitle of host publicationTheoretical Informatics - 10th Latin American Symposium, Proceedings
PublisherSpringer Verlag
Pages494-505
Number of pages12
ISBN (Print)9783642293436
DOIs
StatePublished - Jan 1 2012
Event10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, Peru
Duration: Apr 16 2012Apr 20 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7256 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
CountryPeru
CityArequipa
Period4/16/124/20/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • dynamic programming
  • graph clustering
  • overlapping clustering
  • tree decomposition

Fingerprint Dive into the research topics of 'Advantage of overlapping clusters for minimizing conductance'. Together they form a unique fingerprint.

  • Cite this

    Khandekar, R., Kortsarz, G., & Mirrokni, V. (2012). Advantage of overlapping clusters for minimizing conductance. In LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings (pp. 494-505). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7256 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-29344-3_42