Document Open Access Logo

Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size

Authors Jan Dreier , Philipp Kuinke , Peter Rossmanith

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2020.14.pdf
  • Filesize: 492 kB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
Keywords
  • Random Graphs
  • Preferential Attachment
  • Sparsity
  • Somewhere Dense

Metrics

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

Abstract

Preferential attachment graphs are random graphs designed to mimic properties of real word networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We prove various structural asymptotic properties of this graph model. In particular, we show that the size of the largest r-shallow clique minor in Gⁿ_m is at most log(n)^{O(r²)}m^{O(r)}. Furthermore, there exists a one-subdivided clique of size log(n)^{1/4}. Therefore, preferential attachment graphs are asymptotically almost surely somewhere dense and algorithmic techniques developed for structurally sparse graph classes are not directly applicable. However, they are just barely somewhere dense. The removal of just slightly more than a polylogarithmic number of vertices asymptotically almost surely yields a graph with locally bounded treewidth.

Cite As Get BibTex

Jan Dreier, Philipp Kuinke, and Peter Rossmanith. Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.14

Author Details

Jan Dreier
  • Department of Computer Science, RWTH Aachen University, Germany
Philipp Kuinke
  • Department of Computer Science, RWTH Aachen University, Germany
Peter Rossmanith
  • Department of Computer Science, RWTH Aachen University, Germany

References

  1. Réka Albert, Hawoong Jeong, and Albert-László Barabási. Internet: Diameter of the world-wide web. Nature, 401(6749):130, 1999. Google Scholar
  2. Agnes Backhausz et al. Limit distribution of degrees in random family trees. Electronic Communications in Probability, 16:29-37, 2011. Google Scholar
  3. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  4. Hans L Bodlaender, Fedor V Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M Thilikos. (Meta) kernelization. Journal of the ACM (JACM), 63(5):44, 2016. Google Scholar
  5. Béla Bollobás and Oliver Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5-34, 2004. Google Scholar
  6. Béla Bollobás, Oliver Riordan, Joel Spencer, and Gábor Tusnády. The degree sequence of a scale-free random graph process. Random Structures & Algorithms, 18(3):279-290, May 2001. Google Scholar
  7. Béla Bollobás and Oliver M Riordan. Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet, pages 1-34, 2003. Google Scholar
  8. Fan Chung and Linyuan Lu. The average distances in random graphs with given expected degrees. Proc. of the National Academy of Sciences, 99(25):15879-15882, 2002. Google Scholar
  9. Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Formal Models and Semantics, pages 193-242. Elsevier, 1990. Google Scholar
  10. Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D. Sullivan. Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. J. Comput. Syst. Sci., 105:199-241, 2019. URL: https://doi.org/10.1016/j.jcss.2019.05.004.
  11. R. Diestel. Graph Theory. Springer, Heidelberg, 2010. Google Scholar
  12. Sander Dommers, Remco van der Hofstad, and Gerard Hooghiemstra. Diameters in preferential attachment models. Journal of Statistical Physics, 139(1):72-107, 2010. Google Scholar
  13. Jan Dreier and Peter Rossmanith. Motif counting in preferential attachment graphs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India, volume 150 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.13.
  14. K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O-J. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th ICALP, volume 80 of LIPIcs, pages 63:1-63:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.63.
  15. Matthew Farrell, Timothy D Goodrich, Nathan Lemons, Felix Reidl, Fernando Sánchez Villaamil, and Blair D Sullivan. Hyperbolicity, degeneracy, and expansion of random intersection graphs. In International Workshop on Algorithms and Models for the Web-Graph, pages 29-41. Springer, 2015. Google Scholar
  16. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. JACM, 64(3):17, 2017. Google Scholar
  17. Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 253-266. ACM, 2018. URL: https://doi.org/10.1145/3196959.3196970.
  18. Michał Karoński, Edward R Scheinerman, and Karen B Singer-Cohen. On random intersection graphs: The subgraph problem. Combinatorics, Probability and Computing, 8(1-2):131-159, 1999. Google Scholar
  19. Jon Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. In Proceedings of the 32nd Symposium on Theory of Computing, pages 163-170, 2000. Google Scholar
  20. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010. Google Scholar
  21. Stanley Milgram. The small world problem. Psychology Today, 2(1):60-67, 1967. Google Scholar
  22. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-827, 2002. Google Scholar
  23. Michael Molloy and Bruce Reed. A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3):161-180, 1995. Google Scholar
  24. Tamás F Móri. The maximum degree of the Barabási-Albert random tree. Combinatorics, Probability and Computing, 14(3):339-348, 2005. Google Scholar
  25. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity. Springer, 2012. Google Scholar
  26. Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R Wood. Characterisations and examples of graph classes with bounded expansion. European Journal of Combinatorics, 33(3):350-373, 2012. Google Scholar
  27. J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics, 29(3):760-776, 2008. Google Scholar
  28. Erol Peköz, Adrian Röllin, and Nathan Ross. Joint degree distributions of preferential attachment random graphs. Advances in Applied Probability, 49(2):368-387, 2017. Google Scholar
  29. Erol A Peköz, Adrian Röllin, Nathan Ross, et al. Degree asymptotics with rates for preferential attachment random graphs. The Annals of Applied Probability, 23(3):1188-1218, 2013. Google Scholar
  30. Satu Elisa Schaeffer. Graph clustering. Computer science review, 1(1):27-64, 2007. Google Scholar
  31. Remco van der Hofstad. Random graphs and complex networks, volume 1. Cambridge University Press, 2016. Google Scholar
  32. Duncan J Watts and Steven H Strogatz. Collective dynamics of ‘small-world’networks. nature, 393(6684):440, 1998. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact