Random walk attachment graphs

DOI10.1214/ECP.V18-2518zbMATH Open1298.05289arXiv1303.1052OpenAlexW2160694264MaRDI QIDQ743050FDOQ743050

Authors: Chris Cannings, Jonathan H. Jordan 

Publication date: 22 September 2014

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Abstract: We consider the random walk attachment graph introduced by Saram"{a}ki and Kaski and proposed as a mechanism to explain how behaviour similar to preferential attachment may appear requiring only local knowledge. We show that if the length of the random walk is fixed then the resulting graphs can have properties significantly different from those of preferential attachment graphs, and in particular that in the case where the random walks are of length 1 and each new vertex attaches to a single existing vertex the proportion of vertices which have degree 1 tends to 1, in contrast to preferential attachment models. AMS 2010 Subject Classification: Primary 05C82. Key words and phrases:random graphs; preferential attachment; random walk.

Full work available at URL: https://arxiv.org/abs/1303.1052

Recommendations

• Preferential attachment random graphs with general weight function
• The cover time of the preferential attachment graph
• Recency-based preferential attachment models
• Scale-free property for degrees and weights in a preferential attachment random graph model
• Preferential attachment with choice

zbMATH Keywords

random walkrandom graphspreferential attachment

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Cited In (6)

• Random-walk models of network formation and sequential Monte Carlo methods for graphs
• Transient and slim versus recurrent and fat: random walks and the trees they grow
• Compressibility of random walker trajectories on growing networks
• On a random walk that grows its own tree
• Modeling random walkers on growing random networks
• Network model with scale-free, high clustering coefficients, and small-world properties

This page was built for publication: Random walk attachment graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743050)