Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks
Chen Avin (Ben Gurion University of the Negev);Zvi Lotker (Ben Gurion University of the Negev);Yinon Nahum (Weizmann Institute of Science);David Peleg (Weizmann Institute of Science)
Abstract
Consider a random preferential attachment model $G(p)$ for network evolution that allows both node and edge arrivals. Starting with an arbitrary nonempty graph $G_0$, at each time step, there are two possible events: with probability $p>0$ a new node arrives and a new edge is added between the new node and an existing node, and with probability $1-p$ a new edge is added between two existing nodes. In both cases, the involved existing nodes are chosen at random according to preferential attachment, i.e., with probability proportional to their degree. $G(p)$ is known to generate {\em power law networks}, i.e., the fraction of nodes with degree $k$ is proportional to $k^{-\beta}$. Here $\beta=(4-p)/(2-p)$ is in the range $(2,3]$.
Denoting the number of nodes of degree $k$ at time $t$ by $m_{k,t}$, we significantly improve some long-standing results. In particular, we show that $m_{k,t}$ is concentrated around its mean with a deviation of $O(\sqrt{t})$, which is independent of $k$. We also tightly bound the expectation $\ev{m_{k,t}}$ with an additive error of $O(1/k)$, which is independent of $t$. These new bounds allow us to tightly estimate $m_{k,t}$ for a considerably larger $k$ values than before. This, in turn, enables us to estimate other important quantities, e.g., the size of the $k$-rich club, namely, the set of all nodes with a degree at least $k$.
Finally, we introduce a new generalized model, $G(p_t, r_t, q_t)$, which extends $G(p)$ by allowing also \emph{time-varying} probabilities for node and edge arrivals, as well as the formation of new components. We show that the extended model can produce power law networks with any exponent $\beta$ in the range $(1,\infty)$. Furthermore, the concentration bounds established for $m_{k,t}$ in $G(p)$ also apply in $G(p_t, r_t, q_t)$.
