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: