Optimization-driven evolution of networks
Sergey Dorogovtsev
University of Aveiro, Aveiro, Portugal
Ioffe Institute, St.Petersburg, Russia.
Abstract: Most popular models of growing networks are based on the preferential attachment (actually, self-organization) mechanism, which readily leads to heavy-tailed degree distributions. Due to their simplicity these models are widely used to mimic evolution of real-world networks. The problem is that it is usually difficult to find a reason for the preferential attachment itself, and so these models were criticized as "not explanatory". Optimization is a tempting mechanism for the explanation of the network evolution, but, the optimization-driven models are difficult for analysis and simulations. We discuss a set of optimization-driven processes, global and partial optimization, Metropolis-like-algorithm evolution, and the resulting network architectures. The optimization-driven evolution can produce unusual critical phenomena. We describe the so-called "explosive percolation'' phase transition in processes of this sort. This remarkable transition was originally reported to be discontinuous, but we show that this is actually a second order transition though with unique features.
References:
- W.Willinger, R.Govindan, S.Jamin, V.Paxon, and S.Shenker, Scaling phenomena in the Internet: Critically examining criticality, PNAS 99, 2573 (2002).
- S.N.Dorogovtsev, Lectures on Complex Networks, Oxford University Press, Oxford, 2010.
- R.A. da Costa, S.N.Dorogovtsev, A.V.Goltsev, J.F.F.Mendes, "Explosive Percolation" Transition is Actually Continuous, Phys. Rev. Lett. 105, 255701 (2010); arXiv:1009.2534.