Jason (jcreed) wrote,

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.
Tags: math

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded