Scale-free networks generated by random walkers

2004/04/05 by Jari Saramäki, Jari Saramaki, Kimmo Kaski · 3 citations
Mathematics · Physics and Astronomy · #Cluster analysis #Clustering coefficient #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Degree (music) #Exponent #Graph #Mathematics #Mechanism (biology) #Node (physics) #Physics #Preferential attachment #Random graph #Random walk #Random walker algorithm #Scale (ratio) #Scale-free network #Simple (philosophy) #Simple random sample #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.1016/j.physa.2004.04.110

published as Physica A 341, 80-86 (2004) · 10 pages, 3 figures

arxiv created 2004/04/05 · openalex publication_date 2004/06/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present a simple mechanism for generating undirected scale-free networks using random walkers, where the network growth is determined by choosing parent vertices by sequential random walks. We show that this mechanism produces scale-free networks with degree exponent gamma=3 and clustering coefficients depending on random walk length. The mechanism can be interpreted in terms of preferential attachment without explicit knowledge of node degrees.

Citations

• Community structure in social and biological networks
• Structural transitions in scale-free networks
• Emergence of scaling in random networks
• Hierarchical organization in complex networks
• Efficient Immunization Strategies for Computer Networks and Populations
• Growing scale-free networks with small-world behavior
• Statistical mechanics of complex networks
• Evolution of networks

Cited by

• Exact solution for the time evolution of network rewiring models
• Modelling citation networks
• Link-space formalism for network analysis