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 (14)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Efficient Behavior of Small-World Networks
• Assortative mixing in networks
• Classes of behavior of small-world networks
• Search in Power-Law Networks
• Identity and Search in Social Networks
• Network reachability of real-world contact sequences
• Path finding strategies in scale-free networks
• Search in weighted complex networks
• Search in Complex Networks : a New Method of Naming
• Navigation in a small world with local information
• Distribution of infected mass in disease spreading in scale-free networks

Cited by in corpus (4)

• Frozen states and active-absorbing phase transitions of the Ising model on networks
• Efficiency of navigation in indexed networks
• Funnelling effect in networks
• Realistic searches on stretched exponential networks