Notes from a Medium-Sized Island [entries|archive|friends|userinfo]

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Apr. 2nd, 2005|02:55 pm]

Well, I finally got some realistic-looking results for this class project.

So here's my exciting graph:

On the x-axis is the parameter σ, ranging from 0 to 1, and on the y-axis is δ, ranging from 0 at the bottom to 0.3 at the top. The two orange lines are notable values of δ, 0.125 and 0.25. The random graph model is the following:

(Phase I) Start with a one-vertex (undirected) graph. At every time step, add a vertex, and randomly do one of the following three things according to the probability listed:

  • (probability δσ) add two "half-edges" to the graph, one each to each of two vertices chosen uniformly from the current graph
  • (probability δ(1-σ)) add a real edge between two uniformly chosen vertices.
  • (probability (1-δ)) do nothing.

Do the add-vertex-and-maybe-connect-stuff routine N times for some very large N.

(Phase II) Choose a random permutation of all the half-edges. Pick two off this list at a time, and connect them, forming a real edge. Now we have an ordinary graph without any funny postponed half-edges lying around.

Okay, so what the graph represents is whether a "giant component" forms, i.e. a connected component of size on the order of the number of vertices. Anything shaded gray or black is "yes". What was previously known was that for σ=0, a giant component forms if δ > 1/8, and for σ=1, one forms if δ > 1/4. What platypuslord and I have been working on for the project (among some other things) is figuring out what goes on in the middle.

Which, well, is what the picture is. It's generated from some black black generating-functions magic, and I'm really ecstatic that it seems to agree with the (σ,δ) = (1,1/4) point (and doesn't do anything to violate the (0,1/8) point, but that's more to be expectde) since that suggests that for all of the opportunities I've had to get the theory and the hacking wrong, apparently I may have not taken any of them.

The thing that surprised me is that there seems to be another phase shift in the middle, a discontinuity of the derivative of the giant-component/no-giant-component boundary. The best I can explain it is that it happens because the giant component forms for different reasons as you move from low σ to high. For σ below that critical point, the giant component forms already during phase I (this is the gray stuff) and above it, no giant component appears during phase I, but one does (for sufficiently high δ) during phase II.

The noise on the bottom and right are just numerical innacuracy --- I'm solving all the numerical integration by hand in a completely stupid way, since I couldn't yet get Mathematica to do what I want. Code is in the directory http://www.cs.cmu.edu/~jcreed/kleinberg/ if anyone cares.

[User Picture]From: combinator
2005-04-02 10:47 pm (UTC)
Cool use of generating functions. What motivates this random graph model? It seems kind of, well, random.
(Reply) (Thread)
[User Picture]From: jcreed
2005-04-02 11:25 pm (UTC)
Well for a bit of history:

You can imagine just considering a uniform random graph on some large number of vertices N and a number of edges δN for a parameter N. That is, of the set of all graphs with N vertices and δN edges, pick one uniformly randomly. For this you could ask, well, what do I need to crank δ up to to get a giant component? I don't happen to know the answer, but this is the simplest model I could think of, and I think the answer is known.

But this paper says, hey, what effect might the idea of a graph growing over time have on this threshold? Their model was, every time step add a vertex, and then add an edge with probability δ. This gives you the same number of edges as before, but it's skewed towards "older" vertices having more connections. What's the threshold here? If δ > 1/8, there is a giant component.

To make a fair comparison to an "ungrown" graph, they don't use the uniform model above, but one where the distribution of degrees of the vertices is forced to be the same. For this model, δ needs to be > 1/4 for a giant component to form.

So "grown" graphs more easily form a giant component.

So we tried to come up with a model that interpolated between these two, to see what happens to that threshold. It was pretty much Dan that figured out how to do this. Another way of phrasing the model is like this:

Generate a "grown" graph as described in the paper cited above. Now take a σ fraction of the edges, chop them in half, and randomly reattach them. If σ=0, obviously we've ended up with the model in the paper. If σ=1 then it turns out we get the "fair ungrown" model. For σ in between, we get something in between.
(Reply) (Parent) (Thread)
[User Picture]From: combinator
2005-04-03 12:00 am (UTC)
One other thing: I have tried to get rid of your numerical instability and have been unable in doing anything other than tweaking it slightly. But in the process, I see that in "solve", your integration engine, the function you integrate appears to include its integral up to that point, which I have no idea how to deal with. (I suppose this has something to do with the recursive nature of the generating function?)
(Reply) (Thread)
[User Picture]From: jcreed
2005-04-03 12:59 am (UTC)
Oh, I suppose to be accurate I should call it "solving a differential equation numerically".

Where the diff. eq. is

g' = (huge mess of stuff involving g and x)
(Reply) (Parent) (Thread)