Exploring complex networks by walking on them

Abstract

We carry out a comparative study on the problem for a walker searching on 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-avoid random walk. The preferentially self-avoid 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.

arXiv comment5 pages, 5 figures

References in corpus (29)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Lethality and centrality in protein networks
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Network robustness and fragility: Percolation on random graphs
• Evolution of the social network of scientific collaborations
• Dynamical and correlation properties of the Internet
• Breakdown of the Internet under intentional attack
• Search in Power-Law Networks
• Connectivity of Growing Random Networks
• Growing Scale-Free Networks with Tunable Clustering
• Bose-Einstein condensation in complex networks
• Optimal network topologies for local search with congestion
• Pseudofractal Scale-free Web
• Highly clustered scale-free networks
• Growing Scale-Free Networks with Small World Behavior
• The Fractal Properties of Internet
• Relaxation Properties of Small-World Networks
• Random spread on the family of small-world networks
• Scaling Properties of Random Walks on Small-World Networks
• Scaling of random spreading in small world networks
• Adaptive Random Walks on the Class of Web Graph
• Random Walks on Complex Networks

Cited by in corpus (39)

• The structure and dynamics of multilayer networks
• Mathematical Formulation of Multi-Layer Networks
• Random walks and diffusion on networks
• Random Walks on Multiplex Networks
• Centrality in Interconnected Multilayer Networks
• Cycles and clustering in bipartite networks
• Biased random walks on complex networks: the role of local navigation rules
• A spectrum of routing strategies for brain networks
• Random walk centrality in interconnected multilayer networks
• Exploring Complex Networks through Random Walks
• Characteristic times of biased random walks on complex networks
• Efficient exploration of multiplex networks
• Extreme events and event size fluctuations in biased random walks on networks
• Ring structures and mean first passage time in networks
• The Web of Connections between Tourism Companies in Elba: Structure and Dynamics
• Walks on weighted networks
• Walks on Apollonian networks
• A comparative analysis of knowledge acquisition performance in complex networks
• Reactive random walkers on complex networks
• An integrative dynamical perspective for graph theory and the study of complex networks
• Exploring complex networks by means of adaptive walkers
• Weak ties: Subtle role of information diffusion in online social networks
• Diffusive capture processes for information search
• Smart random walkers: the cost of knowing the path
• Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks
• Optimal exploration of random walks with local bias on networks
• Efficient Crowd Exploration of Large Networks: The Case of Causal Attribution
• Random Walk Access Times on Partially-Disordered Complex Networks: an Effective Medium Theory
• Efficient network exploration by means of resetting self-avoiding random walkers
• Generating multi-scaling networks with different types of nodes
• Unexpected advantages of exploitation for target searches in complex networks
• Multiple predator based capture process on complex networks
• Local search on protein residue networks
• Improving Resource Location with Locally Precomputed Partial Random Walks
• Resource location based on precomputed partial random walks in dynamic networks
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks