2024/04/23 by Riccardo Michielan, Michielan, Riccardo, Clara Stegehuis +3
Computer Science · Mathematics · Physics and Astronomy · #05C60 #05C80 #05C82 #90C11 #Advanced Graph Theory Research #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2404.14972
openalex publication_date 2024/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Geometric scale-free random graphs are popular models for networks that exhibit as heavy-tailed degree distributions, small-worldness and high clustering. In these models, vertices have weights that cause the heavy-tailed degrees and are embedded in a metric space so that close-by groups of vertices tend to cluster. The interplay between the vertex weights and positions heavily affects the local structure of the random graph, in particular the occurrence of subgraph patterns, but the dependencies in these structures and weights make them difficult to analyze. In this paper we investigate subgraph counts using a divide et impera strategy: first counting the number of subgraphs in specific classes of vertices; then computing which class yields maximum contribution. Interestingly, the scaling behavior of induced and general subgraphs in such geometric heavy-tailed random graphs is closely related to the solution of a mixed-integer linear program which also shows that subgraphs appear predominantly on vertices with some prescribed degrees and inter-distances. Finally, we derive precise asymptotics for trees and Hamiltonian subgraphs.