Phase transitions for random geometric preferential attachment graphs
From MaRDI portal
Publication:5262454
DOI10.1239/AAP/1435236988zbMATH Open1364.60019arXiv1311.3776OpenAlexW1804927206MaRDI QIDQ5262454FDOQ5262454
Authors: Jonathan H. Jordan, Andrew R. Wade 
Publication date: 15 July 2015
Published in: Advances in Applied Probability (Search for Journal in Brave)
Abstract: We study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barab'asi--Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barab'asi--Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence. Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors.
Full work available at URL: https://arxiv.org/abs/1311.3776
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Stochastic network models in operations research (90B15)
Cites Work
- Multivariate spatial central limit theorems with applications to percolation and spatial graphs
- Weak laws of large numbers in geometric probability
- Laws of large numbers in stochastic geometry with statistical applications
- The degree sequence of a scale-free random graph process
- The degree sequences and spectra of scale-free random graphs
- Graph colouring and the probabilistic method
- Title not available (Why is that?)
- A survey of random processes with reinforcement
- Degree sequences of geometric preferential attachment graphs
- A Geometric Preferential Attachment Model of Networks
- Title not available (Why is that?)
- On the size of a random sphere of influence graph
- High-Efficiency Estimation for the Positive Stable Laws
- Spatial preferential attachment networks: power laws and clustering coefficients
- Title not available (Why is that?)
- Degree distribution of the FKP network model
- A Geometric Preferential Attachment Model of Networks II
Cited In (11)
- Nonuniform distribution of nodes in the spatial preferential attachment model
- Random geometric graph: some recent developments and perspectives
- The age-dependent random connection model
- A Mecke-type formula and Markov properties for STIT tessellation processes
- Condensation phenomena in preferential attachment trees with neighbourhood influence
- Preferential attachment with location-based choice: degree distribution in the noncondensation phase
- Algorithms and Models for the Web-Graph
- Spatial Gibbs random graphs
- A Geometric Preferential Attachment Model of Networks II
- Quantitative two-scale stabilization on the Poisson space
- Geometric preferential attachment in non-uniform metric spaces
This page was built for publication: Phase transitions for random geometric preferential attachment graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262454)
