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 $μ= ρ/s_d$, where $s_d$ is the average dynamic shortest distance and $ρ$ 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 $μ$ scales with the system size $N$ as $N^{-δ}$, where $δ$ 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 $δ\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