Two takes on preferential attachment graphs

I recently read a paper from STOC 2011 by Doerr, Fouz, and Friedrich on rumor spreading in preferential attachment graphs: Social networks spread rumors in sublogarithmic time, and it cites a 2004 paper by Bollob´s and Riordan from Combinatorica on The diameter of a scale-free random graph (i.e. a preferential attachment graph). The latter paper has a characterization of the graph growth process which is fun and geometric, so I thought it might make a good topic for a post.

So what is a preferential attachment graph? The graph has parameters {m} (number of edges to add each time) and {n} (total number of nodes). We start out with a single vertex with {m} self-loops. Then we add nodes one at at time. Each node gets added with {m} edges, and the trick is in how we add the edges. The process goes like this:

 
 for i = 2 to n 
   add vertex i 
   for t = 1 to m 
      d <- degrees of vertices 
      d(i) <- d(i) + 1 
      pick vertex j with probability d(j)/sum(d) 
      add edge (i,j) 
 

The idea is that we add each vertex {i} and then add {m} edges one at a time, with the destination of the edge chosen proportional to the degree of the destination. Since we already know the edge will have one end at vertex {i}, the degree {d(i)} gets incremented before selecting the destination. This produces a few more loops.

The problem is that this process, while easy to code up and simulate, is rather annoying to analyze, since it goes in this sequential way and things are kind of messy. So what Bollob´s and Riordan do is to look at a different way of generating the same random graph. They prove that the two processes are equivalent in their paper, but here I’ll just show what it looks like graphically.

As Doerr et al. note, it’s easier to think of this first for {m = 1}. Pick points {n} points {\{(x_i,y_i)\}} in the unit square {[0,1]\times[0,1]}:

Then reorder the pairs so {x_i < y_i} (this is equivalent to reflecting the points to the triangle above the line {y = x}) and reorder them so that {y_1 < y_2 < \cdots < y_n}:

Note that we could have just picked {n} points in this triangle, but it’s more clear to define it step by step. Now let {y_0 = 0} and let {I_j = (y_{j-1},y_j)}. For each {i}, if {x_i \in I_j} for some {j} then draw an edge from {i} to {j}. So what we can do is work our way vertically through the field. Since each point we encounter has a {x_i < y_i} it is in some interval {I_j} for {j \le i}. This is what it looks like as it grows, where a node is red if it got a self-loop from the edge selection process:

Ok but what about for larger {m}? It’s a little trickier and less pretty to plot, but you generate {mn} points {\{x_{i,k},y_{i,k}\}} uniformly in {[0,1] \times [0,1]}, and reorder so that in each pair {x_{i,k} < y_{i,k}} and the {y_{i,k}}‘s are in ascending order:

\displaystyle  y_{1,1} < y_{1,2} < \cdots < y_{1,m} < y_{2,1} < \cdots < y_{n,m},

and set {y_{0,m} = 0}. The intervals are now {I_j = (y_{j-1,m},y_{j,m})}. Now for each {i} and {k = 1, 2, \ldots, m}, add the edge {(i,j)} if {x_{i,k} \in I_j}. Maybe next time I’ll try to graph this in a non-ugly way.

Advertisements

2 thoughts on “Two takes on preferential attachment graphs

  1. Very cute! 🙂
    I am curious now — what is an example of a theorem that is easier to prove because you look at the graph this way?

  2. Bollobás and Riordan get results showing the intervals satisfy some properties that hold w.h.p. for large n. So we can think of the graph as kind of having static edge probabilities rather than worrying about this dynamic graph growing process blah blah.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s