A novel approach to study realistic navigations on networks

Abstract

We consider navigation or search schemes on networks which are realistic in the sense that not all search chains can be completed. We show that the quantity $\mu =\rho /s_d$, where $s_d$ is the average dynamic shortest distance and $\rho$ the success rate of completion of a search, is a consistent measure for the quality of a search strategy. Taking the example of realistic searches on scale-free networks, we find that $\mu$ scales with the system size $N$ as $N^{-\delta }$, where $\delta$ decreases as the searching strategy is improved. This measure is also shown to be sensitive to the distintinguishing characteristics of networks. In this new approach, a dynamic small world (DSW) effect is said to exist when $\delta \approx 0$. We show that such a DSW indeed exists in social networks in which the linking probability is dependent on social distances.

Text revised, references added; accepted version in Journal of Statistical Mechanics

References in corpus (2)

• Network reachability of real-world contact sequences
• Search in Complex Networks : a New Method of Naming

Cited by in corpus (2)

• Efficiency of navigation in indexed networks
• Realistic searches on stretched exponential networks