Document Open Access Logo

Building Large k-Cores from Sparse Graphs

Authors Fedor V. Fomin, Danil Sagunov , Kirill Simonov

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.35.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Danil Sagunov
  • St. Petersburg Department of V.A. Steklov Institute of Mathematics, Russia
  • JetBrains Research, St. Petersburg, Russia
Kirill Simonov
  • Department of Informatics, University of Bergen, Norway

Funding

The research leading to these results has received funding from the Research Council of Norway via the project "MULTIVAL" (grant no. 263317).

Cite As Get BibTex

Fedor V. Fomin, Danil Sagunov, and Kirill Simonov. Building Large k-Cores from Sparse Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.35

Abstract

A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than k connections within the network leave it, so the remaining users form exactly the k-core. In this paper we study the question of whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the k-core construction problem is the following Edge k-Core optimization problem. We are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices by adding at most b edges. 
The previous studies on Edge k-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when k = 3, W[1]-hard when parameterized by k+b+p (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the k-core has to be constructed from a sparse graph with some additional structural properties. Our results are  
- When the input graph is a forest, Edge k-Core is solvable in polynomial time; 
- Edge k-Core is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; 
- Edge k-Core is FPT parameterized by the treewidth of the graph plus k. This improves upon a result of Chitnis and Talmon by not requiring b to be small.  Each of our algorithms is built upon a new graph-theoretical result interesting in its own.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • k-core
  • vertex cover
  • treewidth

Metrics

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

Related Versions

References

  1. J. Ignacio Alvarez-Hamelin, Mariano G. Beiró, and Jorge Rodolfo Busch. Understanding edge connectivity in the internet through core decomposition. Internet Mathematics, 7(1):45-66, 2011. URL: https://doi.org/10.1080/15427951.2011.560786.
  2. J. Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems 18 (NIPS), pages 41-50, 2005. Google Scholar
  3. José Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. K-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks & Heterogeneous Media, 3(2):371-393, 2008. Google Scholar
  4. Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: The anchored k-core problem. In ICALP '12, volume 7392 of Lecture Notes in Computer Science, pages 440-451, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_40.
  5. Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: The anchored k-core problem. SIAM J. Discrete Math., 29(3):1452-1475, 2015. URL: https://doi.org/10.1137/14097032X.
  6. Moira Burke, Cameron Marlow, and Thomas M. Lento. Feed me: motivating newcomer contribution in social network sites. In Proceedings of the 27th International Conference on Human Factors in Computing Systems (CHI), pages 945-954. ACM, 2009. URL: https://doi.org/10.1145/1518701.1518847.
  7. Rajesh Chitnis, Fedor V Fomin, and Petr A Golovach. Preventing unraveling in social networks gets harder. In Proceedings of the 27h AAAI Conference on Artificial Intelligence (AAAI), pages 1085-1091. AAAI Press, 2013. Google Scholar
  8. Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized complexity of the anchored k-core problem for directed graphs. Inf. Comput., 247:11-22, 2016. URL: https://doi.org/10.1016/j.ic.2015.11.002.
  9. Rajesh Chitnis and Nimrod Talmon. Can we create large k-cores by adding few edges? In Proceedings of the 13th International Computer Science Symposium in Russia (CSR), volume 10846 of Lecture Notes in Computer Science, pages 78-89. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-90530-3_8.
  10. M.S.Y. Chwe. Structure and Strategy in Collective Action 1. American Journal of Sociology, 105(1):128-156, 1999. Google Scholar
  11. M.S.Y. Chwe. Communication and Coordination in Social Networks. The Review of Economic Studies, 67(1):1-16, 2000. Google Scholar
  12. Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2020. URL: http://arxiv.org/abs/2001.06867.
  13. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  14. Reinhard Diestel. Graph theory. Springer Publishing Company, Incorporated, 2018. Google Scholar
  15. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 11(2):1-20, 2014. Google Scholar
  16. Paul Erdős and Tibor Gallai. Gráfok előírt fokszámú pontokkal. Matematikai Lapok, 11:264-274, 1960. Google Scholar
  17. Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, and Saket Saurabh. Editing to connected f-degree graph. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), volume 47 of LIPIcs, pages 36:1-36:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.36.
  18. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, March 1987. URL: https://doi.org/10.1007/bf02579200.
  19. Christos Giatsidis, Fragkiskos Malliaros, Dimitrios Thilikos, and Michalis Vazirgiannis. Corecluster: A degeneracy based graph clustering framework. In Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2014. Google Scholar
  20. Petr A. Golovach. Editing to a graph of given degrees. In Proceedings of the 9th International Symposium Parameterized and Exact Computation (IPEC), volume 8894 of Lecture Notes in Comput. Sci., pages 196-207. Springer, 2014. Google Scholar
  21. Petr A. Golovach. Editing to a connected graph of given degrees. Inf. Comput., 256:131-147, 2017. Google Scholar
  22. Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Finding even subgraphs even faster. J. Comput. Syst. Sci., 97:1-13, 2018. Google Scholar
  23. Michael A. Henning and Anders Yeo. Tight lower bounds on the matching number in a graph with given maximum degree. Journal of Graph Theory, 89(2):115-149, 2018. URL: https://doi.org/10.1002/jgt.22244.
  24. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12(3):415-440, August 1987. URL: https://doi.org/10.1287/moor.12.3.415.
  25. H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, November 1983. URL: https://doi.org/10.1287/moor.8.4.538.
  26. Junjie Luo, Hendrik Molter, and Ondřej Suchỳ. A parameterized complexity view on collapsing k-cores. In 13th International Symposium on Parameterized and Exact Computation, 2019. Google Scholar
  27. Luke Mathieson and Stefan Szeider. Editing graphs to satisfy degree constraints: A parameterized approach. J. Comput. Syst. Sci., 78(1):179-191, 2012. Google Scholar
  28. T.C. Schelling. Micromotives and Macrobehavior. WW Norton, 2006. Google Scholar
  29. Amitabha Tripathi and Sujith Vijay. A note on a theorem of erdős & gallai. Discrete Mathematics, 265(1-3):417-420, April 2003. URL: https://doi.org/10.1016/s0012-365x(02)00886-5.
  30. Stefan Wuchty and Eivind Almaas. Peeling the yeast protein network. Proteomics, 5(2):444-449, 2005. Google Scholar
  31. Fan Zhang, Wenjie Zhang, Ying Zhang, Lu Qin, and Xuemin Lin. OLAK: an efficient algorithm to prevent unraveling in social networks. Proceedings of the VLDB Endowment, 10(6):649-660, 2017. Google Scholar
  32. Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding critical users for social network engagement: The collapsed k-core problem. In Procedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 245-251. AAAI Press, 2017. Google Scholar
  33. Zhongxin Zhou, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Chen Chen. K-core maximization: An edge addition approach. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 4867-4873. ijcai.org, 2019. URL: https://doi.org/10.24963/ijcai.2019/676.
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