Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT 331 Fall 2023 Project

The giant component of random graphs

In a large random graph, there tends to be one very large connected component of the graph, and several small connected components. In this project, we will explore the size of this “giant” component as a function of the number of vertices V and the number of edges E. For reference see the Wikipedia article or the paper by Bela Bollobas “The evolution of random graphs” (there is a link on the class webpage).

(1) Write a script that builds a random graph with V vertices and E edges. The input should be V and E and the output is the adjacency graph (it is probably a good idea to use sparse matrices). To define the graph, choose random pairs of vertices and check to see if that edge has already been chosen; if not add it to the graph. Continue until E edges have been chosen. Find the size of the largest connected component of the graph.

(2) The total number of possible edges on V vertices is N = V (V − 1)/2. Take values of s > 0 and set E = sN; this is roughly the same as choosing edges with probability s. Write code that takes in a value of s and returns the size of the largest connected component in a random graph with V vertices and E = sN edges.

(3) We are most interested in what happens when the probability of choosing an edge is about 1/V . Using the code from the previous step, take various values of V (say 100, 500, 1000, 5000, 10000), take various values of s close to 1/V , and compute the size of the largest component.

More precisely, take t going from 0 to 4 in steps of .01 and set s = t/V . Compute the size of the largest component in the graph with V vertices where edges are chosen at random with probability s. Redo this 20 times for each value of V and s. Plot the results in a single figure. The x-axis should show the values of t and the y-axis the percentage of vertices in the largest component. Each value of V should be a separate curve. Your figure should look something like the figure listed in the extra reading below this project on the class website.

(4) For various values of V , take E = floor(V/2) and compute the size of the largest component (this corresponds to taking s = 1 above). What is the prediction given in Bollobas’ paper for how large this component is? Is this supported by the results of your experiments? Plot your results as a function of n. Do a log-log plot of your results. Does this plot look linear? If so, what is its approximate slope?