Optimal subgraphs in geometric scale-free random graphs
- 1 August 2026
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 36 (4) , 3266-3294
Abstract
Geometric scale-free random graphs are popular models for networks that exhibit 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.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- On the Distances Within Cliques in a Soft Random Geometric GraphJournal of Statistical Physics, 2024
- Geometric inhomogeneous random graphsTheoretical Computer Science, 2019
- Scale-Free Percolation in Continuum SpaceCommunications in Mathematics and Statistics, 2018
- Cliques in Hyperbolic Random GraphsAlgorithmica, 2017
- PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite2016
- Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks2005
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- Subgraph counts in random graphs using incomplete u-statistics methodsDiscrete Mathematics, 1988
- A Method for Detecting Structure in Sociometric Data1977
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976