Document Open Access Logo

Clustering in Hypergraphs to Minimize Average Edge Service Time

Authors Ori Rottenstreich, Haim Kaplan, Avinatan Hassidim

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.64.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Ori Rottenstreich
Haim Kaplan
Avinatan Hassidim

Cite As Get BibTex

Ori Rottenstreich, Haim Kaplan, and Avinatan Hassidim. Clustering in Hypergraphs to Minimize Average Edge Service Time. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.64

Abstract

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria which we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

Subject Classification

Keywords
  • Clustering
  • average cover time
  • hypergraphs
  • set cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ameer Ahmed Abbasi and Mohamed Younis. A survey on clustering algorithms for wireless sensor networks. Computer communications, 30(14):2826-2841, 2007. Google Scholar
  2. Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David J. Kriegman, and Serge J. Belongie. Beyond pairwise clustering. In IEEE CVPR, 2005. Google Scholar
  3. Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466(7307):761-764, 2010. Google Scholar
  4. Reid Andersen, David F. Gleich, and Vahab Mirrokni. Overlapping clusters for distributed computation. In ACM Web search and data mining, 2012. Google Scholar
  5. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1-3):89-113, 2004. Google Scholar
  6. Rafael Bru, Francisco Pedroche, and Daniel B. Szyld. Additive Schwarz iterations for Markov chains. SIAM Journal on Matrix Analysis and Applications, 27(2):445-458, 2005. Google Scholar
  7. Rafael Bru, Francisco Pedroche, and Daniel B. Szyld. Cálculo del vector PageRank de Google mediante el método aditivo de Schwarz. In Congreso de Métodos Numéricos en Ingeniería, 2005. Google Scholar
  8. Samuel Rota Bulò and Marcello Pelillo. A game-theoretic approach to hypergraph clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(6):1312-1327, 2013. Google Scholar
  9. Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233-235, 1979. Google Scholar
  10. Rami Cohen, Liane Lewin-Eytan, Joseph Naor, and Danny Raz. Near optimal placement of virtual network functions. In IEEE Infocom, 2015. Google Scholar
  11. A. J. Cole and D. Wishart. An improved algorithm for the Jardine-Sibson method of generating overlapping clusters. The Computer Journal, 13(2):156-163, 1970. Google Scholar
  12. David L. Davies and Donald W. Bouldin. A cluster separation measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(2):224-227, 1979. Google Scholar
  13. Ran Duan. A simpler scaling algorithm for weighted matching in general graphs. CoRR, abs/1411.1919, 2014. URL: http://arxiv.org/abs/1411.1919.
  14. Joseph C. Dunn. Well-separated clusters and optimal fuzzy partitions. Journal of cybernetics, 4(1):95-104, 1974. Google Scholar
  15. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449-467, 1965. Google Scholar
  16. Vladimir Estivill-Castro. Why so many clustering algorithms: a position paper. ACM SIGKDD explorations newsletter, 4(1):65-75, 2002. Google Scholar
  17. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998. Google Scholar
  18. Andreas Frommer and Daniel B. Szyld. Weighted max norms, splittings, and overlapping additive Schwarz iterations. Numerische Mathematik, 83(2):259-278, 1999. Google Scholar
  19. Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In ACM-SIAM SODA, 1990. Google Scholar
  20. David S. Johnson. Approximation algorithms for combinatorial problems. In ACM symposium on Theory of computing, 1973. Google Scholar
  21. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, IBM Thomas J. Watson Research Center, 1972. Google Scholar
  22. Marius Leordeanu and Cristian Sminchisescu. Efficient hypergraph clustering. In AISTATS, 2012. Google Scholar
  23. László Lovász. On the ratio of optimal integral and fractional covers. Discrete mathematics, 13(4):383-390, 1975. Google Scholar
  24. Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan. Clustering social networks. In Algorithms and Models for the Web-Graph, pages 56-67. Springer, 2007. Google Scholar
  25. Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14:849-856, 2002. Google Scholar
  26. Matthias Peiser et al. Allergic contact dermatitis: epidemiology, molecular mechanisms, in vitro methods and regulatory aspects. Cellular and Molecular Life Sciences, 69(5):763-781, 2012. Google Scholar
  27. Ori Rottenstreich, Isaac Keslassy, Yoram Revah, and Aviran Kadosh. Minimizing delay in network function virtualization with shared pipelines. IEEE Transactions on Parallel and Distributed Systems, 28(1):156-169, 2017. Google Scholar
  28. Amnon Shashua, Ron Zass, and Tamir Hazan. Multi-way clustering using super-symmetric non-negative tensor factorization. In ECCV, 2006. Google Scholar
  29. Daniel A. Spielmat and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. In IEEE Foundations of Computer Science, 1996. Google Scholar
  30. Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In ACM symposium on Theory of computing, 2001. Google Scholar
  31. Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416, 2007. Google Scholar
  32. Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In NIPS, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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