Webwhompers

Chapter 2 of Six Degrees starts with an excellent introduction to random graphs. Have that handy before you continue.

Random graphs (and their dynamics) are based on the following assumptions:

• The graph we start with has many nodes but no edges.
• Edges are added randomly one at a time to the graph. (I.e., any pair of non-adjacent nodes is equally likely to be the next edge added to the existing graph.)
• Eventually, we end with a clique: every pair of nodes is adjacent.

Given the above framework, how does a graph evolve between the starting and ending points? That is a core question of random graph dynamics.

One of the most famous results in the dynamics of random graph describes the size of the largest connected component, also called the giant component. Read in Six Degrees the explanation of Figure 2.2 on p. 45. A similar figure labeled with our own terminology is below:

After you absorb Six Degrees, then consider what this means:

• By eyeballing the above figure, we can estimate that a random graph with average degree of 2 has a giant component with 75% of all nodes.
• Whether |V| is big or small doesn't matter at all: To connect a set of nodes into a giant component, just randomly add |V| edges and you have guaranteed that the average degree is at least 2, thus creating a giant component with 75% of all nodes.

Example: Suppose all links are deleted from the Web. Only the 30-70 billion link-less pages remain. If each author of each Web page added just one random link to each of his pages, then the resulting giant component would connect 75% of all Web pages into a giant component connected by undirected paths (which allow both forward and backward traversing of hyperlinks).