Random walk attachment graphs

DOI10.1214/ECP.V18-2518MaRDI QIDQ743050zbMATH OpenOpenAlexFDO

Authors Chris Cannings, Jonathan H. Jordan

Publication date 22 September 2014

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

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

zbMATH Keywords

preferential attachmentrandom graphsrandom walk

Mathematics Subject Classification ID

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

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.

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

Cited in

(10)

• On a random walk that grows its own tree
• Modeling random walkers on growing random networks
• Compressibility of random walker trajectories on growing networks
• 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
• Network model with scale-free, high clustering coefficients, and small-world properties
• Recurrence, transience and degree distribution for the tree builder random walk
• Renewal structure of the tree builder random walk
• Structural results for the tree builder random walk
• Random friend trees

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)