Adaptive Dynamic of Realistic Small World Networks
Venue
2009 European Conference on Complex Systems (to appear)
Publication Year
2009
Authors
Olof Mogren, Oskar Sandberg, Vilhelm Verendel, Devdatt Dubhashi
BibTeX
Abstract
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.
