Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks

author: Yinon Nahum, Faculty of Mathematics and Computer Science, Weizmann Institute of Science
published: Oct. 9, 2017,   recorded: August 2017,   views: 986

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography


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)$.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: