Spatial preferential attachment networks: Power laws and clustering coefficients

Abstract

We define a class of growing networks in which new nodes are given a spatial position and are connected to existing nodes with a probability mechanism favoring short distances and high degrees. The competition of preferential attachment and spatial clustering gives this model a range of interesting properties. Empirical degree distributions converge to a limit law, which can be a power law with any exponent $\tau >2$. The average clustering coefficient of the networks converges to a positive limit. Finally, a phase transition occurs in the global clustering coefficients and empirical distribution of edge lengths when the power-law exponent crosses the critical value $\tau =3$. Our main tool in the proof of these results is a general weak law of large numbers in the spirit of Penrose and Yukich.

Published in at http://dx.doi.org/10.1214/14-AAP1006 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Asymptotic behavior and distributional limits of preferential attachment graphs
• Phase transitions for random geometric preferential attachment graphs
• Geometric preferential attachment in non-uniform metric spaces

Cited by in corpus (27)

• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Recurrence versus Transience for Weight-Dependent Random Connection Models
• The age-dependent random connection model
• Structures in supercritical scale-free percolation
• Percolation phase transition in weight-dependent random connection models
• The shape of shortest paths in random spatial networks
• Bootstrap percolation on geometric inhomogeneous random graphs
• Random spherical graphs
• Phase transitions for random geometric preferential attachment graphs
• Scale-free network clustering in hyperbolic and other random graphs
• Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds
• Weighted distances in scale-free preferential attachment models
• High Degree Vertices and Spread of Infections in Spatially Modelled Social Networks
• Recurrence and transience of symmetric random walks with long-range jumps
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Geometric evolution of complex networks
• Capacity of an associative memory model on random graph architectures
• Spatial Strength Centrality and the Effect of Spatial Embeddings on Network Architecture
• Diameter of P.A. random graphs with edge-step functions
• Distance evolutions in growing preferential attachment graphs
• The HyperKron Graph Model for higher-order features
• Scale-free percolation in continuum space: quenched degree and clustering coefficient
• Poisson Approximation and Connectivity in a Scale-free Random Connection Model
• Chemical distance in geometric random graphs with long edges and scale-free degree distribution
• The contact process on scale-free geometric random graphs
• Agglomeration in a preferential attachment random graph with edge-steps
• Rumours spread slowly in a small world spatial network