Document Open Access Logo

Correlation Clustering Generalized

Authors David F. Gleich, Nate Veldt, Anthony Wirth

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2018.44.pdf
  • Filesize: 473 kB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing β†’ Approximation algorithms
Keywords
  • Correlation Clustering
  • Approximation Algorithms

Metrics

Abstract

We present new results for LambdaCC and MotifCC, two recently introduced variants of the well-studied correlation clustering problem. Both variants are motivated by applications to network analysis and community detection, and have non-trivial approximation algorithms.
We first show that the standard linear programming relaxation of LambdaCC has a Theta(log n) integrality gap for a certain choice of the parameter lambda. This sheds light on previous challenges encountered in obtaining parameter-independent approximation results for LambdaCC. We generalize a previous constant-factor algorithm to provide the best results, from the LP-rounding approach, for an extended range of lambda.
MotifCC generalizes correlation clustering to the hypergraph setting. In the case of hyperedges of degree 3 with weights satisfying probability constraints, we improve the best approximation factor from 9 to 8. We show that in general our algorithm gives a 4(k-1) approximation when hyperedges have maximum degree k and probability weights. We additionally present approximation results for LambdaCC and MotifCC where we restrict to forming only two clusters.

Cite As Get BibTex

David F. Gleich, Nate Veldt, and Anthony Wirth. Correlation Clustering Generalized. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.44

Author Details

David F. Gleich
  • Department of Computer Science, Purdue University, West Lafayette, Indiana, USA
Nate Veldt
  • Department of Mathematics, Purdue University, West Lafayette, Indiana, USA
Anthony Wirth
  • School of Computing and Information Systems, The University of Melbourne, Parkville, Victoria, Australia

Funding

  • Gleich, David F.: D.F.G. is supported by the DARPA Simplex program, the Sloan Foundation, and NSF awards IIS-154648, CCF-1149756 and CCF-093937.
  • Veldt, Nate: N.V. supported by NSF award CCF-1149756.
  • Wirth, Anthony: A.W. is supported by the Melbourne School of Engineering.

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√ log n) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems. In STOC 05, pages 573-581. ACM, 2005. URL: http://dx.doi.org/10.1145/1060590.1060675.
  2. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):23, 2008. Google Scholar
  3. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation Clustering. Machine Learning, 56:89-113, 2004. Google Scholar
  4. Austin R. Benson, David F. Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295):163-166, 2016. URL: http://dx.doi.org/10.1126/science.aad9029.
  5. Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):360-383, 2005. Google Scholar
  6. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the Hardness of Approximating Multicut and Sparsest-cut. Computational Complexity, 15(2):94-114, June 2006. URL: http://dx.doi.org/10.1007/s00037-006-0210-9.
  7. Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In STOC 15, pages 219-228. ACM, 2015. Google Scholar
  8. Tom Coleman, James Saunderson, and Anthony Wirth. A Local-Search 2-Approximation for 2-Correlation-Clustering. In ESA 08, pages 308-319, 2008. URL: http://dx.doi.org/10.1007/978-3-540-87744-8_26.
  9. Bhaskar DasGupta, German A. Enciso, Eduardo Sontag, and Yi Zhang. Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems. In WEA 06, pages 253-264, 2006. Google Scholar
  10. Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172-187, 2006. Google Scholar
  11. Takuro Fukunaga. LP-based pivoting algorithm for higher-order correlation clustering. In Computing and Combinatorics, pages 51-62, Cham, 2018. Springer International Publishing. Google Scholar
  12. Ioannis Giotis and Venkatesan Guruswami. Correlation Clustering with a Fixed Number of Clusters. Theory OF Computing, 2:249-266, 2006. Google Scholar
  13. David F. Gleich, Nate Veldt, and Anthony Wirth. Correlation Clustering Generalized. arXiv, cs.DS, 2018. URL: http://arxiv.org/abs/1809.09493.
  14. S. A. Khot and N. K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into 𝓁₁. In FOCS 05, pages 53-62, October 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.74.
  15. Subhash Khot. On the Power of Unique 2-prover 1-round Games. In STOC 02, pages 767-775, 2002. URL: http://dx.doi.org/10.1145/509907.510017.
  16. Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang D. Yoo. Higher-Order Correlation Clustering for Image Segmentation. In NIPS 11, pages 1530-1538, 2011. URL: http://papers.nips.cc/paper/4406-higher-order-correlation-clustering-for-image-segmentation.pdf.
  17. P. Li, H. Dau, G. Puleo, and O. Milenkovic. Motif clustering and overlapping clustering for social network analysis. In INFOCOM 17, pages 1-9, May 2017. URL: http://dx.doi.org/10.1109/INFOCOM.2017.8056956.
  18. Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(026113), 2004. Google Scholar
  19. G. Puleo and O. Milenkovic. Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds. SIAM Journal on Optimization, 25(3):1857-1872, 2015. URL: http://dx.doi.org/10.1137/140994198.
  20. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In FOCS 00, pages 3-13, 2000. Google Scholar
  21. Anke van Zuylen and David P. Williamson. Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Mathematics of Operations Research, 34(3):594-620, 2009. URL: http://dx.doi.org/10.1287/moor.1090.0385.
  22. Nate Veldt, David F Gleich, and Anthony Wirth. A Correlation Clustering Framework for Community Detection. In WWW 18, pages 439-448. International World Wide Web Conferences Steering Committee, 2018. Google Scholar
  23. Anthony Ian Wirth. Approximation Algorithms for Clustering. PhD thesis, Princeton University, November 2004. Computer Science Technical Report 716. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact