The influence of geometry on scale-free random graphs

This thesis investigates the influence of geometry on scale-free networks, focusing on Geometric Inhomogeneous Random Graphs (GIRGs) and related models.

Part I examines scaling and concentration of subgraphs in GIRGs. Our results reveal a phase transition in clique counts driven by the interaction between geometry and scale-free properties. For large values of the scale-free parameter $\tau$, we identify a geometric regime, where cliques primarily form between nearby vertices and grow linearly with graph size. When $\tau$ is small, a non-geometric regime emerges, dominated by cliques among high-degree vertices. This geometric/non-geometric distinction holds across various subgraph types, with broader results obtained through a mixed-integer linear programming approach that balances entropy and energy for vertex subsets with specific degrees and distances.

Part II addresses the challenge of identifying latent geometry in scale-free networks. We introduce weighted triangles as a novel network statistic that effectively detects geometric structure by discounting triangles among high-degree nodes. Unlike pure triangle counts, which fail in detecting geometry when $\tau$ is small, weighted triangles grow linearly in GIRGs but remain bounded in non-geometric models, providing a reliable geometric test. Empirical studies demonstrate its effectiveness on real-world networks, where we also apply weighted triangles to a community detection problem, achieving partial recovery of geometric communities and developing an estimator for community size.

Part III defines Spatial Random Intersection Graphs (SRIGs), an AB model with spatially embedded individuals and groups connected by radially decreasing probabilities. We derive connection probabilities, bounds on the degree distribution (showing it is not heavy-tailed), and analyze percolation. Our results reveal a percolation phase transition that depends on whether the connection function's support is bounded or unbounded, highlighting the importance of individual and group intensities in network connectivity.