2012 | OriginalPaper | Chapter
Advantage of Overlapping Clusters for Minimizing Conductance
Authors : Rohit Khandekar, Guy Kortsarz, Vahab Mirrokni
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.