Subnets of scale-free networks are not scale-free: Sampling properties of networks

Footnotes

• ↵ ‡ To whom correspondence should be addressed. E-mail: m.stumpf{at}imperial.ac.uk.

• Author contributions: M.P.H.S., C.W., and R.M.M. designed research, performed research, and wrote the paper.

• Abbreviation: PGF, probability-generating function.

• ↵ ∥ For the subnet, we have the PGF \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;G^{{^\ast}}(s)={{\sum^{{\infty}}_{k=0}}}P^{{^\ast}}(k;p)s^{k}={{\sum^{{\infty}}_{k=0}}}{{\sum_{i{\geq}k}}}P(i)(ps)^{k}(1-p)^{i-k} \left \left(\begin{matrix}i\\ k\end{matrix}\right) \right .\;\end{equation*}\end{document} Summing first over k (0 ≤ k ≤ i), and remembering P(0) = 0 (for scale-free networks), we get \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;G^{{^\ast}}(s)={{\sum^{{\infty}}_{i=1}}}P(i)[(1-p)+ps]^{i}.\;\end{equation*}\end{document} Note that G*(1) = ΣP(i) = 1, as it should.

  ↵ ∥ The subsequent sample will, however, contain orphan nodes, given by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}P^{{^\ast}}(0)=G^{{^\ast}}(0)={{\sum^{{\infty}}_{i=1}}}P(i)(1-p)^{i}\end{equation*}\end{document}. If we redefine P*(0) ≡ 0 by discarding such orphans, we have the subnet defined by Eq. 5, where the renormalization constant C is required to compensate for the deletion of the orphan nodes: C[1 – P*(0)] = 1 or \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;C^{-1}={{\sum^{{\infty}}_{i=1}}}P(i)[1-(1-p)^{i}]=1-G(1-p).\;\end{equation*}\end{document}

• ↵ †† The negative binomial distribution has the PGF G(s) = [1 + (m/k)(1 – s)]^–k, where m represents the distribution`s mean value and k characterizes the distribution's “clumpiness” (the variance is given by σ²/m ² = 1/m + 1/k). This widely studied distribution includes the Poisson distribution (the degree distribution of classical random graphs) as the special case k → ∞ and the exponential or geometric as k = 1. The subnet PGF is obtained, via Eq. 4, by substituting 1 – p(1 – s) for s in G(s), to get G*(s) = [1 + (mp/k)(1 – s)]^–k. Thus, the subnet has an identical PGF to the full distribution, excepting only that the mean is reduced to mp (the clumping parameter k is unaltered). The proof for the binomial distribution is even more trivial.

• ↵ ‡‡ For Eq. 1 with γ = 2, the PGF of the subnet is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}G^{{^\ast}}(s)=C{{\sum^{{\infty}}_{k=1}}}k^{-2}[1-p+ps]^{k}\end{equation*}\end{document}, with C given by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}C{{\sum^{{\infty}}_{k=1}}}k^{-2}[1-(1-p)^{k}]=1\end{equation*}\end{document}. Defining u = 1 – p + ps, whence dG*(s)/ds = pdG*/du, we have the degree distribution given by k!P*(k) = p^k (d^kG*(u)/du^k )_{u = 1 – p}. For small p « 1, consider first \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}pdG^{{^\ast}}/du=Cp{{\sum^{{\infty}}_{k=1}}}u^{k-1}/k=-(Cp/u){\mathrm{ln}}(1-u)\end{equation*}\end{document}. This exact result gives P*(1) = –[Cpln(p)]/(1 – p). Further differentiation gives exact, but increasingly complicated, expressions for P*(k > 1). Thus, P*(2) = [Cp/(1 – p)][1 + pln(p)/(1 – p)]. For larger k, P*(k > 2) = [Cp/k(k – 1)][1 + O(p)]. Finally, we can calculate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}C^{-1}=p{\int _{0}^{{\infty}}}\{xe^{x}dx/[(e^{x}-1)(e^{x}-1+p)]\}{\simeq}p[1-{\mathrm{ln}}(p)-(1/2)p{\mathrm{ln}}(p)+(1/4)p{\ldots}]\end{equation*}\end{document}.

• ↵ §§ By method analogous to those in the previous note, we can obtain, for small p, the analytic results: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;P^{{^\ast}}(1)=1+p\hspace{.167em}{\mathrm{ln}}(p)/[2{\zeta}(2)]+p \left \left[\frac{1}{2}-\frac{1}{4{\zeta}(2)}\right] \right +{\ldots},\;\end{equation*}\end{document} \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;P^{{^\ast}}(2)=-p({\mathrm{ln}}(p))/[2{\zeta}(2)]-\frac{1}{2}p+{\ldots},\;\end{equation*}\end{document} \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}\;P^{{^\ast}}(k>2)=p/[{\zeta}(2)k(k-1)(k-2)]+{\ldots},\;\end{equation*}\end{document} \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*} {\mathrm{and}}{\;}C^{-1}=p \left \left[{\zeta}(2)+\frac{1}{2}p\hspace{.167em}{\mathrm{ln}}(p)+p \left \left(\frac{1}{2}{\zeta}(2)-\frac{3}{4}\right) \right +{\ldots}\right] \right .\;\end{equation*}\end{document}

• Copyright © 2005, The National Academy of Sciences