%0 Book Section %1 statphys23_1029 %A Dorogovtsev, S.N. %A Mendes, J.F.F. %A Samukhin, A.N. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K ensembles networks random statistical statphys23 topic-11 %T Simple vs. multiply connected networks %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=1029 %X The problem of the structural organization of an equilibrium random graph without multiple connections is among the basic problems of the statistical mechanics of networks. The point is that the theory of an equilibrium random network with multiple connections can be reduced to the classic non-network problem of the distribution of balls among boxes. In contrast, the problem of the network without multiple connections is irreducible to simple non-network problems. ``Thermally'' equilibrium ensembles of networks with independent vertices may be formed under the generalized preferential attachement rule. We assume the new edges between vertices can be introduced, and, at the same time, some verices removed. Probability of the appearence of new edge between vertices with degrees $q$ and $q^\prime$ is $f(q)f(q^\prime)$. Then vertex degree distrubution is: $$ \Pi(q) \Pi_c(q)x_c^q \,\,\, , \Pi_c(q)=1q!\prod_r=0^q-1f(r)\, . $$ Here $x_c$ is some growing function of $q=2L/N$, $L$ and $N$ are the numbers of edges and vertices, resp. For some $f(q)$, $\Pi_c(q)$ becomes a slowly decaying function. For example, if $f(q)?q+1-\gamma$, $Pi_c(q)?q^-\gamma$. If at some $q=q_c$ we have $x_c=1$, then the degree distribution decays slower then any exponent. But, what happens, if $q>q_c$? We have found that if $q>q_c$, the highly interconnected core emerges in the simple graph. This core contains: $$ N_h=N(\barq-q_c)Q(q) N^2/3łn^-1/3N $$ vertices. A finite fraction of the total number of edges are inside of the core. Also, a finite fraction of all edges connect the core vertices to the rest of the network. In contrast, in multiple networks with $q>q_c$, $N(q-q_c)$ edges are connected to a single hub, some of which are self-connecting loops. For fat-tailed $\Pi_c(q)$, the degree distribution of a simple graph is given by the following expression: $$ \Pi(q)=\Pi_c(q)B^(q/Q)-(1/2)(q/Q)^2\,, $$ with (assuming $\Pi_c(q) q^-\gamma)$: $$ B\sim(\barq-q_c)^2Q^4-2\gammałnłeft\barq-q_c) Q^2-\gamma\right $$ and: $$ Q łeft(Nq-q_c\right)^1/3łeft\vertłnłeftN^2-\gamma (q-q_c)^5-\gamma\right\right\vert^1/3\, . $$ At $q=q_c$, the degree distribution of the network is equal to $\Pi_c(q)$, but with a size-dependent cut-off. In the simple graphs with with a convergent second moment $m_2c=\sum_qq^2 \Pi_c(q)<ınfty$: $$ \Pi(q,N)=\Pi_c(q)\expłeft(-q^22aN\right)\,\,\, , a1 $$ In the simple networks with $2<\gamma<3$: $$ \Pi(q,N) q^-\gamma\expłeft(-bq^2N^2/(5-\gamma)\right) , b 1 . $$ In both cases we have Gaussian cut-off, but with different size dependencies. If $m_2c<ınfty$ (in particular, if in a scale-free network $\gamma>3$), then the cutoff degree is $q_cut N^1/2$. This square-root law fails if $m_2c=ınfty$, i.e., in particular, when exponent $2<\gamma<3$. Here we have $q_cut(N) N^1/(5-\gamma)$. Note the difference from the multiple networks, where the cutoff degree is $q_cut(N) N^1/(\gamma-1)$ for $2<\gamma<3$.

@incollection{statphys23_1029, abstract = {The problem of the structural organization of an equilibrium random graph without multiple connections is among the basic problems of the statistical mechanics of networks. The point is that the theory of an equilibrium random network with multiple connections can be reduced to the classic non-network problem of the distribution of balls among boxes. In contrast, the problem of the network without multiple connections is irreducible to simple non-network problems. ``Thermally'' equilibrium ensembles of networks with independent vertices may be formed under the generalized preferential attachement rule. We assume the new edges between vertices can be introduced, and, at the same time, some verices removed. Probability of the appearence of new edge between vertices with degrees $q$ and $q^\prime$ is $f(q)f(q^\prime)$. Then vertex degree distrubution is: $$ \Pi(q) \sim \Pi_{c}(q)x_{c}^{q} \,\,\, , \Pi_{c}(q)=\frac{1}{q!}\prod_{r=0}^{q-1}f(r)\, . $$ Here $x_{c}$ is some growing function of $\bar{q}=2L/N$, $L$ and $N$ are the numbers of edges and vertices, resp. For some $f(q)$, $\Pi_c(q)$ becomes a slowly decaying function. For example, if $f(q)?q+1-\gamma$, $Pi_{c}(q)?q^{-\gamma}$. If at some $\bar{q}=q_{c}$ we have $x_{c}=1$, then the degree distribution decays slower then any exponent. But, what happens, if $\bar{q}>q_{c}$? We have found that if $\bar{q}>q_{c}$, the highly interconnected core emerges in the simple graph. This core contains: $$ N_{h}=\frac{N(\bar{q}-q_{c})}{Q(\bar{q})} \sim N^{2/3}\ln^{-1/3}N $$ vertices. A finite fraction of the total number of edges are inside of the core. Also, a finite fraction of all edges connect the core vertices to the rest of the network. In contrast, in multiple networks with $\bar{q}>q_{c}$, $N(\bar{q}-q_{c})$ edges are connected to a single hub, some of which are self-connecting loops. For fat-tailed $\Pi_{c}(q)$, the degree distribution of a simple graph is given by the following expression: $$ \Pi(q)=\Pi_{c}(q)B^{(q/Q)-(1/2)(q/Q)^2}\,, $$ with (assuming $\Pi_{c}(q) \sim q^{-\gamma})$: $$ B\sim\frac{(\bar{q}-q_{c})^2}{Q^{4-2\gamma}}\ln\left[\frac{\bar{q}-q_{c})} {Q^{2-\gamma}}\right] $$ and: $$ Q \sim \left(\frac{N}{\bar{q}-q_{c}}\right)^{1/3}\left\vert\ln\left[\frac{N^{2-\gamma}} {(\bar{q}-q_{c})^{5-\gamma}}\right]\right\vert^{1/3}\, . $$ At $\bar{q}=q_{c}$, the degree distribution of the network is equal to $\Pi_{c}(q)$, but with a size-dependent cut-off. In the simple graphs with with a convergent second moment $m_{2c}=\sum_{q}q^2 \Pi_{c}(q)<\infty$: $$ \Pi(q,N)=\Pi_{c}(q)\exp\left(-\frac{q^2}{2aN}\right)\,\,\, , a\sim 1 $$ In the simple networks with $2<\gamma<3$: $$ \Pi(q,N) \sim q^{-\gamma}\exp\left(-\frac{bq^2}{N^{2/(5-\gamma)}}\right) , b \sim 1 . $$ In both cases we have Gaussian cut-off, but with different size dependencies. If $m_{2c}<\infty$ (in particular, if in a scale-free network $\gamma>3$), then the cutoff degree is $q_{cut} \sim N^{1/2}$. This square-root law fails if $m_{2c}=\infty$, i.e., in particular, when exponent $2<\gamma<3$. Here we have $q_{cut}(N) \sim N^{1/(5-\gamma)}$. Note the difference from the multiple networks, where the cutoff degree is $q_{cut}(N) \sim N^{1/(\gamma-1)}$ for $2<\gamma<3$.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Dorogovtsev, S.N. and Mendes, J.F.F. and Samukhin, A.N.}, biburl = {https://www.bibsonomy.org/bibtex/2ae4c0dd5389e5603a2ff3d24a1d2e8ba/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {35336e59684bbcafe328863142111759}, intrahash = {ae4c0dd5389e5603a2ff3d24a1d2e8ba}, keywords = {ensembles networks random statistical statphys23 topic-11}, month = {9-13 July}, timestamp = {2007-06-20T10:16:37.000+0200}, title = {Simple vs. multiply connected networks}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=1029}, year = 2007 }