The evolution of navigable small-world networks

Abstract

Small-world networks, which combine randomized and structured elements, are seen as prevalent in nature. Several random graph models have been given for small-world networks, with one of the most fruitful, introduced by Jon Kleinberg, showing in which type of graphs it is possible to route, or navigate, between vertices with very little knowledge of the graph itself. Kleinberg's model is static, with random edges added to a fixed grid. In this paper we introduce, analyze and test a randomized algorithm which successively rewires a graph with every application. The resulting process gives a model for the evolution of small-world networks with properties similar to those studied by Kleinberg.

References in corpus (4)

• Emergence of scaling in random networks
• Renormalization group analysis of the small-world network model
• Identity and Search in Social Networks
• How Do Networks Become Navigable?

Cited by in corpus (5)

• Growing homophilic networks are natural navigable small worlds
• Networks become navigable as nodes move and forget
• Adaptive Dynamics of Realistic Small-World Networks
• Double Clustering and Graph Navigability
• A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity