Complex network research focuses on large-scale network structures such as social systems, cell biology, neurology, etc. The goal is to bserve real-world network properties and model the observed properties under random mechanisms.
Erdos-Renyi (1959) random graph G(n,p) connects two pairs of nodes with a probability p=c/n where c is a constant. It has two important properties: (a) when c is less than 1, composed of small components all of which have O(logn) (b) when c is greater than 1, a.a.s. (asymptotically almost surely), a unique giant component containing theta(n) nodes appears, which is called the phase transition.
Stanley Milgram's 6-degree separation states that not only there exist a short path in a society, it is possible for individuals to find such a path using only local information.
Small world networks by Watts and Strongatz uses grids (to guarantee clusters) and makes short cuts in the network uniformly random. This leads to preserving small-world properties (i.e., short distance and high clustering). The prevailing need for this model is that Erdos-Renyi random graph does not support the notion of clusters.
Extended model by Kleinberg is a variant of the small-world model. Rather than making shortcuts that are uniformly random, Kleinberg assumes shortcuts follow a particular distance distribution, rho(v,w)^-alpha, and showed that (a) alpha=2, decentralized algorithm exists that is of O(log^2 n). (b) Otherwise, there does not exist any poly-logarithmic decentralized algorithm.
Further readings:
1. J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
2. J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
No comments:
Post a Comment