How Many Nodes are Effectively Accessed in Complex Networks?

Abstract

The measurement called accessibility has been proposed as a means to quantify the efficiency of the communication between nodes in complex networks. This article reports important results regarding the properties of the accessibility, including its relationship with the average minimal time to visit all nodes reachable after $h$ steps along a random walk starting from a source, as well as the number of nodes that are visited after a finite period of time. We characterize the relationship between accessibility and the average number of walks required in order to visit all reachable nodes (the exploration time), conjecture that the maximum accessibility implies the minimal exploration time, and confirm the relationship between the accessibility values and the number of nodes visited after a basic time unit. The latter relationship is investigated with respect to three types of dynamics, namely: traditional random walks, self-avoiding random walks, and preferential random walks.

8 pages and 7 figures

References in corpus (11)

• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Identification of influential spreaders in complex networks
• Critical phenomena in complex networks
• Spatial Growth of Real-world Networks
• Congestion and centrality in traffic flow on complex networks
• Failure and avalanches in complex networks
• Diffusion Processes on Power-Law Small-World Networks
• Chain motifs: The tails and handles of complex networks
• Avalanches of Activation and Spikes in Neuronal Complex Networks
• Random Walks on Complex Networks

Cited by in corpus (8)

• Spreading dynamics in complex networks
• Understanding the spreading power of all nodes in a network: a continuous-time perspective
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• Concentric Network Symmetry
• Topological characterization of world cities
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• A framework for evaluating complex networks measurements
• Malleability of complex networks