Navigation in a small world with local information

Abstract

It is commonly known that there exist short paths between vertices in a network showing the small-world effect. Yet vertices, for example, the individuals living in society, usually are not able to find the shortest paths, due to the very serious limit of information. To theoretically study this issue, here the navigation process of launching messages toward designated targets is investigated on a variant of the one-dimensional small-world network (SWN). In the network structure considered, the probability of a shortcut falling between a pair of nodes is proportional to $r^{-\alpha }$, where $r$ is the lattice distance between the nodes. When $\alpha =0$, it reduces to the SWN model with random shortcuts. The system shows the dynamic small-world (SW) effect, which is different from the well-studied static SW effect. We study the effective network diameter, the path length as a function of the lattice distance, and the dynamics. They are controlled by multiple parameters, and we use data collapse to show that the parameters are correlated. The central finding is that, in the one-dimensional network studied, the dynamic SW effect exists for $0\le \alpha \le 2$. For each given value of $\alpha$ in this region, the point that the dynamic SW effect arises is $M{L}^{\prime }\sim 1$, where $M$ is the number of useful shortcuts and $L^{\prime }$ is the average reduced (effective) length of them.

10 pages, 5 figures, accepted for publication in Physical Review E

References in corpus (2)

• The structure and function of complex networks
• The effect of aging on network structure

Cited by in corpus (13)

• Spatial Networks
• Phase transitions in Ising model on a Euclidean network
• Effect of the nature of randomness on quenching dynamics of Ising model on complex networks
• Two-dimensional small-world networks: navigation with local information
• Susceptible-Infected-Recovered model on Euclidean network
• Phase transition of a one-dimensional Ising model with distance-dependent connections
• Complex Networks: effect of subtle changes in nature of randomness
• Ordering kinetics with long-range interactions: interpolating between voter and Ising models
• A novel approach to study realistic navigations on networks
• Funnelling effect in networks
• Efficiency of navigation in indexed networks
• Realistic searches on stretched exponential networks
• Navigation in non-uniform density social networks