Exploring Complex Graphs by Random Walks

Abstract

We present an algorithm to grow a graph with scale-free structure of {\it in-} and {\it out-links} and variable wiring diagram in the class of the world-wide Web. We then explore the graph by intentional random walks using local next-near-neighbor search algorithm to navigate through the graph. The topological properties such as betweenness are determined by an ensemble of independent walkers and efficiency of the search is compared on three different graph topologies. In addition we simulate interacting random walks which are created by given rate and navigated in parallel, representing transport with queueing of information packets on the graph.

Latex, 4 figures

Cited by in corpus (7)

• Analysis of weighted networks
• Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations
• Quantifying the sensing power of crowd-sourced vehicle fleets
• Information Super-Diffusion on Structured Networks
• Simulating Network Influence Algorithms Using Particle-Swarms: PageRank and PageRank-Priors
• Gaussian Networks Generated by Random Walks
• Deep Social Collaborative Filtering