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 (number of edges to add each time) and (total number of nodes). We start out with a single vertex with self-loops. Then we add nodes one at at time. Each node gets added with 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 and then add 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 , the degree 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 . Pick points points in the unit square :

Then reorder the pairs so (this is equivalent to reflecting the points to the triangle above the line ) and reorder them so that :

Note that we could have just picked points in this triangle, but it’s more clear to define it step by step. Now let and let . For each , if for some then draw an edge from to . So what we can do is work our way vertically through the field. Since each point we encounter has a it is in some interval for . 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 ? It’s a little trickier and less pretty to plot, but you generate points uniformly in , and reorder so that in each pair and the ‘s are in ascending order:

and set . The intervals are now . Now for each and , add the edge if . Maybe next time I’ll try to graph this in a non-ugly way.