Document Open Access Logo

Cluster Editing in Multi-Layer and Temporal Graphs

Authors Jiehua Chen, Hendrik Molter, Manuel Sorge, Ondrej Suchý

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.24.pdf
  • Filesize: 0.75 MB
  • 13 pages

Document Identifiers

Author Details

Jiehua Chen
  • Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland
Hendrik Molter
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
Manuel Sorge
  • Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland
Ondrej Suchý
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

Funding

JC and MS supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement number 631163.11, the Israel Science Foundation (grant no. 551145/14), and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement numbers 677651 (JC) and 714704 (MS). HM supported by the DFG, project MATE (NI 369/17). OS supported by grant 17-20065S of the Czech Science Foundation.

Cite AsGet BibTex

Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Cluster Editing in Multi-Layer and Temporal Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.24

Abstract

Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Cluster Editing
  • Temporal Graphs
  • Multi-Layer Graphs
  • Fixed-Parameter Algorithms
  • Polynomial Kernels
  • Parameterized Complexity

Metrics

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

Related Versions

References

  1. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation Clustering. Machine Learning, 56:89-113, 2004. Google Scholar
  2. Matteo Barigozzi, Giorgio Fagiolo, and Giuseppe Mangioni. Identifying the Community Structure of the International-Trade Multi-Network. Physica A, 390(11):2051-2066, 2011. Google Scholar
  3. N. Betzler, J. Guo, C. Komusiewicz, and R. Niedermeier. Average Parameterization and Partial Kernelization for Computing Medians. J. Comput. Syst. Sci., 77(4):774-789, 2011. Google Scholar
  4. Sebastian Böcker and Jan Baumbach. Cluster Editing. In Proc. of CiE '13, volume 7921 of LNCS, pages 33-44. Springer, 2013. Google Scholar
  5. Leizhen Cai and Junjie Ye. Dual Connectedness of Edge-Bicolored Graphs and Beyond. In Proc. of MFCS '14, volume 8635 of LNCS, pages 141-152. Springer, 2014. Google Scholar
  6. Yixin Cao and Jianer Chen. Cluster Editing: Kernelization Based on Edge Cuts. Algorithmica, 64(1):152-169, 2012. Google Scholar
  7. Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Cluster Editing in Multi-Layer and Temporal Graphs. CoRR, abs/1709.09100, 2018. Google Scholar
  8. M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Frank Dehne, Mike Fellows, Frances Rosamond, and Peter Shaw. Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover. In Proc. of IWPEC '04, volume 3162 of LNCS, pages 271-280. Springer, 2004. Google Scholar
  10. T.K. Dey, A. Rossi, and A. Sidiropoulos. Temporal Clustering. In Proc. of ESA '17, volume 87 of LIPIcs, pages 34:1-34:14. Schloss Dagstuhl, 2017. Google Scholar
  11. Martin Dörnfelder, Jiong Guo, Christian Komusiewicz, and Mathias Weller. On the Parameterized Complexity of Consensus Clustering. Theor. Comput. Sci., 542:71-82, 2014. Google Scholar
  12. Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger. Tight Bounds for Parameterized Complexity of Cluster Editing with a Small Number of Clusters. J. Comput. Syst. Sci., 80(7):1430-1447, 2014. Google Scholar
  13. J. Gramm, J. Guo, F. Hüffner, and R. Niedermeier. Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation. Theory Comput. Syst., 38(4):373-392, 2005. Google Scholar
  14. P. Holme. Modern temporal network theory: a colloquium. Eur. Phys. J. B, 88(9):234, 2015. Google Scholar
  15. Petter Holme and Jari Saramäki. Temporal networks. Phys. Rep., 519(3):97-125, 2012. Google Scholar
  16. Jungeun Kim and Jae-Gil Lee. Community Detection in Multi-Layer Graphs: A Survey. SIGMOD Rec., 44(3):37-48, 2015. Google Scholar
  17. Mikko Kivelä, Alex Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno, and Mason A. Porter. Multilayer networks. J. Complex Netw., 2(3):203-271, 2014. Google Scholar
  18. Christian Komusiewicz and Johannes Uhlmann. Cluster Editing with Locally Bounded Modifications. Discrete Appl. Math., 160:2259-2270, 2012. Google Scholar
  19. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. CoRR, abs/1710.04073, 2017. URL: http://arxiv.org/abs/1710.04073.
  20. Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math., 12(4):239-280, 2016. Google Scholar
  21. Vincenzo Nicosia and Vito Latora. Measuring and Modeling Correlations in Multiplex Networks. Phys. Rev. E, 92(3):032805, 2015. Google Scholar
  22. Andrea Tagarelli, Alessia Amelio, and Francesco Gullo. Ensemble-Based Community Detection in Multilayer Networks. Data Min. Knowl. Discov., 31(5):1506-1543, 2017. Google Scholar
  23. W. Tang, Z. Lu, and I. S. Dhillon. Clustering with Multiple Graphs. In Proc. of ICDM '09, pages 1016-1021. IEEE Computer Society, 2009. Google Scholar
  24. C. Tantipathananandh, T. Berger-Wolf, and D. Kempe. A Framework for Community Identification in Dynamic Social Networks. In Proc. of KDD '07, pages 717-726. ACM, 2007. Google Scholar
  25. C. Tantipathananandh and T. Y. Berger-Wolf. Finding Communities in Dynamic Social Networks. In Proc. of ICDM '11, pages 1236-1241. IEEE Computer Society, 2011. 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 Imprint Privacy Contact