Characterizing network topology using first-passage analysis

Abstract

Understanding the topological characteristics of complex networks and how they affect navigability is one of the most important goals in science today, as it plays a central role in various economic, biological, ecological and social systems. Here, we apply First Passage analysis tools to investigate the properties and characteristics of random walkers in networks with different topology. Starting with the simplest two-dimensional square lattice, we modify its topology incrementally by randomly reconnecting links between sites. We characterize these networks by First Passage Time from a significant number of random walkers without interaction, varying the departure and arrival locations. We also apply the concept of First Passage Simultaneity, which measures the likelihood of two walkers reaching their destination together. These measures, together with the site occupancy statistics during the processes, allowed to differentiate the studied networks, especially the random networks from the scale-free networks, by their navigability. We also show that small world features can also be highlighted with the proposed technique.

arXiv comment17 pages and 9 figures

References in corpus (17)

• Emergence of scaling in random networks
• Maps of random walks on complex networks reveal community structure
• Universal Behavior of Load Distribution in Scale-free Networks
• Geometry-controlled kinetics
• The dynamical foundation of fractal stream chemistry: The origin of extremely long retention times
• Global mean first-passage times of random walks on complex networks
• First-passage times for random walks in bounded domains
• First passages in bounded domains: When is the mean first passage time meaningful?
• First passages for a search by a swarm of independent random searchers
• Laplacian Spectra as a Diagnostic Tool for Network Structure and Dynamics
• Mean first-passage time for random walks on undirected networks
• Assessing diversity in multiplex networks
• Quantifying instabilities in Financial Markets
• Origin of the hub spectral dimension in scale-free networks
• Crossover from anomalous to normal diffusion in porous media
• Response to targeted perturbations for random walks on networks
• Random Walks on Complex Networks