Fork me on GitHub

Adaptive Dynamics of Realistic Small-World Networks

Synthetic Graph Generated after Official Population Data from Statistics Sweden.

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.

Fulltext: PDF
Bibtex: click here
Published in: European Conference on Complex Systems, 2009, p12, Warwick UK
Authors: Olof Mogren, Oskar Sandberg, Vilhelm Verendel, Devdatt Dubhashi

Olof Mogren, Department of Computer Science and Engineering, Chalmers University of Technology

LinkedIn Twitter Atom/RSS Feed