Extended navigability of small world networks: exact results and new insights.
By Cécile Caretta Cartozo, P. De Los Rios. 2009
35 citations recorded by the source corpus.
Navigability of networks, that is, the ability to find any given destination vertex starting from any other vertex, is crucial to their usefulness. In 2000 Kleinberg showed that optimal navigability could be achieved in small world networks provided that a special recipe was used to establish long range connections, and that a greedy algorithm, that ensures that the destination will be reached, is used. Here we provide an exact solution for the asymptotic behavior of such a greedy algorithm as a function of the system's parameters. Our solution enables us to show that the original claim that only a very special construction is optimal can be relaxed depending on further constraints, such as, for example, cost minimization, that must be satisfied.
Subfields: Molecular Biology, Statistical and Nonlinear Physics, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Molecular Biology
In Statistical and Nonlinear Physics
- Marc Barthelemy
- Santo Fortunato
- Olaf Sporns
- Alessandro Vespignani
- Mark Newman
- Geoff Boeing
- Alex Arenas
- Renaud Lambiotte
In Network Science & Complex Systems
Citations in the corpus
- Spatial Networks (2010, background): “For the interested reader, we also note that a detailed study of the d = 1 case is done in [335], that exact asymptotic results were obtained in [74], and that the ‘greedy’ paths connecting a source to the target were studied in [295] by defining a greedy connectivity.”