Exploring complex networks by walking on them.

We carry out a comparative study of the problem of a walker searching several typical complex networks. The search efficiency is evaluated for various strategies. Having no knowledge of the global properties of the underlying networks and the optimal path between any two given nodes, it is found that the best search strategy is the self-avoiding random walk. The preferentially self-avoiding random walk does not help in improving the search efficiency further. In return, topological information of the underlying networks may be drawn by comparing the results of the different search strategies.

• Publication year

  2004

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2004-06-08

• Fields of study

  Mathematics, Physics, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.71.016107arXiv cond-mat/0406177PMID 15697658
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Scaling properties of random walks on small-world networks.

  2003cited by this paper
• Random walks on complex networks.

  2003cited by this paper
• Optimal network topologies for local search with congestion

  2002cited by this paper
• Hierarchical Organization of Modularity in Metabolic Networks

  2002cited by this paper
• Scale-free networks from varying vertex intrinsic fitness.

  2002cited by this paper
• Specificity and Stability in Topology of Protein Networks

  2002cited by this paper
• A Model of Large-Scale proteome Evolution

  2002cited by this paper
• Growing scale-free networks with tunable clustering.

  2001cited by this paper
• Statistical mechanics of complex networks

  2001cited by this paper
• Lethality and centrality in protein networks

  2001cited by this paper
• Evolution of networks

  2001cited by this paper
• Highly clustered scale-free networks.

  2001cited by this paper
• Scaling of random spreading in small world networks.

  2001cited by this paper
• Dynamical and correlation properties of the internet.

  2001cited by this paper
• Evolution of the social network of scientific collaborations

  2001cited by this paper
• The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes.

  2001cited by this paper
• Exploring complex networks

  2001cited by this paper
• Infection dynamics on scale-free networks.

  2001cited by this paper
• Search in Power-Law Networks

  2001cited by this paper
• Growing scale-free networks with small-world behavior.

  2001cited by this paper
• Pseudofractal scale-free web.

  2001cited by this paper
• Scientific collaboration networks. I. Network construction and fundamental results.

  2001cited by this paper
• Adaptive random walks on the class of Web graphs

  2001cited by this paper
• Connectivity of growing random networks.

  2000cited by this paper
• Complexity and fragility in ecological networks

  2000cited by this paper
• Epidemic spreading in scale-free networks.

  2000cited by this paper
• Bose-Einstein condensation in complex networks.

  2000cited by this paper
• Breakdown of the internet under intentional attack.

  2000cited by this paper
• Error and attack tolerance of complex networks

  2000cited by this paper
• The fractal properties of Internet

  2000cited by this paper
• Competition and multiscaling in evolving networks

  2000cited by this paper
• Random spread on the family of small-world networks.

  2000cited by this paper
• Small world patterns in food webs.

  2000cited by this paper
• Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality.

  2000cited by this paper
• Network robustness and fragility: percolation on random graphs.

  2000cited by this paper
• Relaxation properties of small-world networks

  2000cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Emergence of scaling in random networks

  1999cited by this paper
• Internet: Diameter of the World-Wide Web

  1999cited by this paper
• On power-law relationships of the Internet topology

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Random Walks and Random Environments: Volume 1: Random Walks

  1995cited by this paper

• Biased random walks on networks with stochastic resetting.

  2025cites this paper
• Who leads the chain? Deciphering the trajectory of global value network in technology-intensive manufacturing and innovation effects

  2025cites this paper
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics.

  2025cites this paper
• Synchronization detection using spatial ordinal partitions in networks.

  2025cites this paper
• Network classification through random walks

  2025cites this paper
• Fast and Robust Flocking of Protesters on Street Networks

  2024cites this paper
• Signal propagation in complex networks

  2023cites this paper
• Multi-Objective Optimization of Transport Processes on Complex Networks

  2023cites this paper
• An integrative dynamical perspective for graph theory and the study of complex networks

  2023cites this paper
• Efficient network exploration by means of resetting self-avoiding random walkers

  2023cites this paper
• An integrative dynamical perspective for graph theory and the analysis of complex networks.

  2023cites this paper
• Estimating high-order brain functional network via signed random walk for mild cognitive impairment identification

  2022cites this paper
• Unexpected advantages of exploitation for target searches in complex networks.

  2022cites this paper
• Random walks on weighted networks: a survey of local and non-local dynamics

  2021cites this paper
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula

  2021cites this paper
• The self-adaptive routing strategy to alleviate packet loss in finite buffer networks

  2021cites this paper
• Identifying the essential nodes in network pharmacology based on multilayer network combined with random walk algorithm

  2020cites this paper
• NC-MOPSO: A network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020cites this paper
• NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020cites this paper
• A comparative analysis of knowledge acquisition performance in complex networks

  2020cites this paper
• Evidence of power-law behavior in cognitive IoT applications

  2020cites this paper
• Impact of structural balance on Self-Avoiding Pruning Walk

  2019cites this paper
• Markov chain approach to anomalous diffusion on Newman–Watts networks

  2019cites this paper
• Module partition of complex mechanical products based on weighted complex networks

  2019cites this paper
• Dynamics on complex networks: modeling the form to shape the substance

  2019cites this paper
• Routing optimization considering real-time traffic condition and travel distance

  2019cites this paper
• Centrality in Networks: Finding the Most Important Nodes

  2019cites this paper
• Resilience analytics: coverage and robustness in multi-modal transportation networks

  2018cites this paper
• A O ] 1 8 Ju l 2 01 8 Reactive random walkers on complex networks

  2018cites this paper
• Efficient Crowd Exploration of Large Networks

  2018cites this paper
• Efficient sampling of complex network with modified random walk strategies

  2018cites this paper
• Reactive random walkers on complex networks

  2018cites this paper
• A spectrum of routing strategies for brain networks

  2018cites this paper
• Navigated Random Walks on Amazon Book Recommendation Network

  2017cites this paper
• Traffic congestion and the lifetime of networks with moving nodes.

  2017cites this paper
• The structure and dynamics of multiplex networks

  2017cites this paper
• Effects of packet retransmission with finite packet lifetime on traffic capacity in scale-free networks

  2017cites this paper
• Ανάλυση, μοντελοποίηση και προσομοίωση αναζήτησης σε σύνθετα δυναμικά δίκτυα

  2017cites this paper
• Optimizing Network Discovery with Clever Walks

  2017cites this paper
• Linear and nonlinear approaches to unravel dynamics and connectivity in neuronal cultures

  2017cites this paper
• Communication dynamics in complex brain networks

  2017cites this paper
• Check-in based routing strategy in scale-free networks

  2017cites this paper
• MADM-based smart parking guidance algorithm

  2017cites this paper
• Module partition of complex mechanical products based on weighted complex networks

  2017cites this paper
• Multiple-predators-based capture process on complex networks

  2016cites this paper
• Efficient packet navigation method on scale-free networks with finite and diversiform node delivery capacity

  2016cites this paper
• Community detection in networks using self-avoiding random walks

  2016cites this paper
• Random walks and diffusion on networks

  2016cites this paper
• Network exploration using true self-avoiding walks.

  2016cites this paper
• An optimal path finding strategy in networks based on random walk

  2016cites this paper
• Enhancing traffic capacity of scale-free networks by employing hybrid routing strategy

  2015cites this paper
• Theoretical knock-outs on biological networks.

  2015cites this paper
• Resource location based on precomputed partial random walks in dynamic networks

  2015cites this paper
• Biased random walks on multiplex networks

  2015cites this paper
• Random walk centrality in interconnected multilayer networks

  2015cites this paper
• Efficient exploration of multiplex networks

  2015cites this paper
• The Role of Accessibility in the Static and Dynamic Risk Computation

  2015cites this paper
• Mathematical Foundations: Complex Networks and Graphs (A Review)

  2015cites this paper
• Mathematical Model II: Dynamic Intentional Risk

  2015cites this paper
• Towards the Implementation of the Model

  2015cites this paper
• Exploring highly-efficient routing strategy on scale-free networks with limited and diverse node capacity

  2015cites this paper
• Efficient packet transportation on complex networks with nonuniform node capacity distribution

  2015cites this paper
• Intentional Risk and Cyber-Security: A Motivating Introduction

  2015cites this paper
• Mathematical Model I: Static Intentional Risk

  2015cites this paper
• Coverage maximization under resource constraints using proliferating random walks

  2015cites this paper
• The Random Walk Value for Ranking Spatial Characteristics in Road Networks

  2014cites this paper
• The structure and dynamics of multilayer networks

  2014cites this paper
• Blind and myopic ants in heterogeneous networks.

  2014cites this paper
• Supplementary Information for “ Navigability of Interconnected Networks under Random Failures ”

  2014cites this paper
• An incremental optimal routing strategy for scale-free networks

  2014cites this paper
• Analysis of Brownian Particles for finding the shortest path in networks

  2014cites this paper
• Coverage maximization under resource constraints using a nonuniform proliferating random walk.

  2013cites this paper
• ENHANCING TRAFFIC CAPACITY OF TWO-LAYER COMPLEX NETWORKS

  2013cites this paper
• Dynamic Source Routing Strategy for Two-Level Flows on Scale-Free Networks

  2013cites this paper
• Impact of the Network Structure on Transmission Dynamics in Complex Networks

  2013cites this paper
• A Local Routing Strategy on Weighted Scale-Free Networks

  2013cites this paper
• Probability routing strategy for scale-free networks

  2013cites this paper
• Research on the Adaptive-absorption Search Strategy on Scale-free Networks ⋆

  2013cites this paper
• Analysis of network traffic flow dynamics based on gravitational field theory

  2013cites this paper
• Local search on protein residue networks

  2013cites this paper
• Ranking in interconnected multilayer networks reveals versatile nodes

  2013cites this paper
• Improving resource location with locally precomputed partial random walks

  2013cites this paper
• Resource Location Mechanisms for Complex Networks Based on Random Walks

  2013influential citation
• Characteristic times of biased random walks on complex networks

  2013cites this paper
• Mathematical Formulation of Multilayer Networks

  2013cites this paper
• Navigability of interconnected networks under random failures

  2013cites this paper
• Parameter estimation and topology identification of uncertain fractional order complex networks

  2012cites this paper
• Resource location based on partial random walks in networks with resource dynamics

  2012cites this paper
• Integrating local and partial network view for routing on scale-free networks

  2012cites this paper
• Search for Directed Networks by Different Random Walk Strategies

  2012cites this paper
• Local-Based Semantic Navigation on a Networked Representation of Information

  2012cites this paper
• AN EFFICIENT WEIGHTED ROUTING STRATEGY FOR SCALE-FREE NETWORKS

  2012cites this paper
• Traffic Dynamics on Complex Networks: A Survey

  2012cites this paper
• A model of self‐avoiding random walks for searching complex networks

  2012influential citation
• Reconstruction, mobility, and synchronization in complex networks

  2012cites this paper
• Smart random walkers: the cost of knowing the path.

  2012cites this paper
• Exploring complex networks by means of adaptive walkers

  2012cites this paper
• When Feedbacks Matter: Epidemics, Synchronization, and Self-regulation in Complex Networks

  2011cites this paper
• Reducing Search Lengths with Locally Precomputed Partial Random Walks

  2011cites this paper
• Routing in scale-free networks based on expanding betweenness centrality

  2011cites this paper