Adaptive Dynamics of Realistic Small-World Networks

Abstract

Continuing in the steps of Jon Kleinberg's and others celebrated work on decentralized search in small-world networks, we conduct an experimental analysis of a dynamic algorithm that produces small-world networks. We find that the algorithm adapts robustly to a wide variety of situations in realistic geographic networks with synthetic test data and with real world data, even when vertices are uneven and non-homogeneously distributed. We investigate the same algorithm in the case where some vertices are more popular destinations for searches than others, for example obeying power-laws. We find that the algorithm adapts and adjusts the networks according to the distributions, leading to improved performance. The ability of the dynamic process to adapt and create small worlds in such diverse settings suggests a possible mechanism by which such networks appear in nature.

References in corpus (7)

• Emergence of scaling in random networks
• The structure and function of complex networks
• How Do Networks Become Navigable?
• The evolution of navigable small-world networks
• Neighbor selection and hitting probability in small-world graphs
• Networks become navigable as nodes move and forget
• Double Clustering and Graph Navigability