Power-law and log-periodic degree tails for a family of probability generating function equations arising in evolving networks

Abstract

For a fixed integer $j\ge 1$ and $0<p<1$, we study the probability generating function (pgf) equation \[ (1+2p)\,g(x)=2p\,x^{j}+g\bigl(x-px+px^{2}\bigr),\qquad 0\le x\le1 , \] which governs the limiting degree distribution $\{p_k\}$ of a family of evolving network models. The cases $j=1$ and $j=2$ are the treelike fast-growth model of Feng and Hu and the homogeneous evolving network of Feng, Li and Hu. We prove that for every $j$ the equation has a unique pgf solution, of mean $2j$, and we determine its coefficient tail exactly: \[ p_k=k^{-1-ρ}\,Ψ_j(\log_λk)+o\bigl(k^{-1-ρ}\bigr), \] where $\hat{I}»=1+p$, $\ddot{I}=\log (1+2p)/\log (1+p)$ is independent of $j$, and $\hat{I}{¨}_j$ is continuous, strictly positive and $1$-periodic, with explicit Fourier coefficients. This resolves two conjectures of Feng and coauthors: (1) the power-law order $p_k=\hat{I}˜(k^{-1-\ddot{I}})$ and (2) its refinement to the multiplicatively periodic form $p_k\sim \hat{I}{¨}_j({\log }_{\hat{I}}»k)k^{-1-\ddot{I}}$. The periodic factor is genuinely non-constant for $p$ near $1$, and, for the two network models, for all $p$ outside a discrete set. Consequently, $p_k$ is asymptotic to no constant multiple of $k^{-1-\ddot{I}}$. Our method is a self-contained local analysis of the supercritical Galton-Watson process with offspring law $1+\mathrm{Bernoulli}(p)$, inspected at an independent geometric time. This time-changed process solves the equation observed by Feng and coauthors. The main results of this paper were obtained by the multi-agent system Eureka and have subsequently been verified by the authors.

21 pages

Topics & keywords