Realistic searches on stretched exponential networks

Abstract

We consider navigation or search schemes on networks which have a degree distribution of the form $P(k) \propto \exp(-k^γ)$. In addition, the linking probability is taken to be dependent on social distances and is governed by a parameter $λ$. The searches are realistic in the sense that not all search chains can be completed. An estimate of $μ=ρ/s_d$, where $ρ$ is the success rate and $s_d$ the dynamic path length, shows that for a network of $N$ nodes, $μ\propto N^{-δ}$ in general. Dynamic small world effect, i.e., $δ\simeq 0$ is shown to exist in a restricted region of the $λ-γ$ plane.

Based on talk given in Statphys Guwahati, 2008