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.


  1. W.Willinger, R.Govindan, S.Jamin, V.Paxon, and S.Shenker, Scaling phenomena in the Internet: Critically examining criticality, PNAS 99, 2573 (2002).
  2. S.N.Dorogovtsev, Lectures on Complex Networks, Oxford University Press, Oxford, 2010.
  3. 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.

Presentation Material

Back to TERANET 2011 Homepage