Adaptive Dynamic of Realistic Small World Networks

Continuing in the steps of Jon Kleinberg’s and others celebrated work on decentralized search, we conduct an experimental analysis of destination sampling, 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 unevenly 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.

• Algorithms and Theory