Organization of complex networks without multiple connections

S. N. Dorogovtsev, J. F. F. Mendes, A. M. Povolotsky, A. N. Samukhin

Published 2005-05-08, updated 2005-09-23Version 2

We find a new structural feature of equilibrium complex random networks without multiple and self-connections. We show that if the number of connections is sufficiently high, these networks contain a core of highly interconnected vertices. The number of vertices in this core varies in the range between $const N^{1/2}$ and $const N^{2/3}$, where $N$ is the number of vertices in a network. At the birth point of the core, we obtain the size-dependent cut-off of the distribution of the number of connections and find that its position differs from earlier estimates.