Spring 2020 Proj 3 MAT 331
Project 3: Giant component of a random graph
Due: 11:59pm, Tuesday, May 19
Collaboration Policy: You can discuss topics related to programming or graphs with your class-
mates or others. You may also do research on the internet or from books (this is certainly not
required). But you must design and write your own algorithms and write your own report. In
particular, you should understand how your code works and be able to justify your design choices.
Introduction
In this project you will explore the “giant component” of a random graph. Recall that the vertices of
an (undirected) graph G can be partitioned into sets called connected components, such that every
pair of vertices in each set can be joined by a path consisting of edges of the graph, and no pair
of vertices from different sets can be joined by such a path (see the figure below). The number,
size, and structure of the connected components are important properties of graphs that arise when
modeling networks.
You will investigate the relationship between the connected components (particularly the size
of the largest one - the giant component) in a random graph and the number of edges in the graph.
With few edges, all the connected components are small and there are many of them. As the number
of edges increases, eventually it is becomes very likely that almost all vertices in the graph can be
joined by a path (with just a few outlying islands of vertices). But between these two extremes
there is a transition point when the graph starts to have one large component, and many smaller
ones. You will empirically explore this transition point.
Programming tasks [70 pts]
(1) [20 pts] Write code that generates a random graph G with n vertices, where each edge appears
with probability p. This means that two distinct vertices are connected to each other with an
edge with probability p. You can choose how you want to represent the graph G. (Note that
this is model is somewhat different than the rand_graph function we wrote in lecture, though
it has similar properties).
(2) [5 pts] Plot visual representations of random graphs for various values of n up to 50, and
various values of p. You can use the package networkx or some other way of plotting.
(3) [20 pts] Write a function that takes in a graph G and returns a list of the connected com-
ponents. For instance, for the graph in the figure below, the list of the connected components
is:
[[0, 1, 2, 3, 4, 5], [6, 7, 8, 9], [10]].
Page 1 of 4
Spring 2020 Proj 3 MAT 331
Figure 1: A graph with 3 connected components.
Test out your code on some of the graphs you generated in the previous part.
Hint: In Lecture on Tuesday 5/5 we write code to determine whether a graph is connected. You
can modify this a bit to generate a list of connected components.
(4) [10 pts] Write a function that takes in a graph and outputs the size of the giant component
(measured in number of vertices). Test this for a random graph with n = 50 and p = 1/50.
(5) [15 pts] You will now see what happens to the size of the giant component of random graphs
for p near 1/n. If p = 1/n, then the number of edges hitting a vertex v (the degree of v) is around
1. Compute the size of the giant component for random graphs with n = 10, 50, 100, 200, and
p = t/n where t ranges from 0 to 4 in steps of size 0.25. Do 10 trials for each of the possible (n, p)
values and take the average of the size of the giant component over those 10 trials. Generate
a plot of your results, with one curve for each of the possible values of n. Make the x-axis the
value of pn (which is the average degree of a vertex), and the y-axis the value of the size of
giant component divided by n.
From this plot, you should see the emergence of a giant component as p increases from below
1/n to above this threshold.
It may be helpful to optimize your code from part (3) so that the above experiments don’t take
too long (also see Extra Credit (6a) below).
(6) Extra Credit [Up to 8 pts] You may choose at most one of the following to work on for
extra credit.
(a) Optimize your code from part (3) so that you can compute the list of connected components
efficiently for random graphs with n vertices and p = 1/n, for larger n than were studied
in part(5). The number of points you get will depend on how efficient your algorithm is.
Page 2 of 4
Spring 2020 Proj 3 MAT 331
Hint: You may want to change the way you represent the graph. Since a random graph with
n vertices and p = 1/n is relatively sparse, it may be faster to use a representation other
than an adjacency matrix. For instance, you could use adjacency lists: for each vertex,
store a list of the vertices that it neighbors. For reference, on my newish MacBook Pro,
with this optimization, I can find connected components for n = 2000, p = 1/2000 in about
3 seconds. You will receive most of the 8 points if you achieve a similar level of efficiency.
(b) Do experiments and create a plot as in part (5), but this time instead of computing the size
of giant component, compute the ratio of the size of the giant component to the size of the
second largest component.
This quantity should also experience a transition around p = 1/n; below this threshold
the giant component isn’t much bigger than the second largest component, while above the
threshold, the giant component gets much bigger than the second largest component.
(Note that sometimes the whole graph will be connected, so there will be no second largest
component. However, when p > 0 for our random graphs, this is not very likely, so it
doesn’t really matter. You can define the ratio to be some large number, like n, if the graph
is connected).
Written report [30 pts]
• Describe the algorithm that you used to compute connected components in (3). How do you
think the running time would scale with the number of vertices n and the number of edges in
the input graph?
• Interpret the results about the size of the giant component you computed in (5). What kind
of transition occurs around p = 1/n? What do you think would happen if you were able to
test random graphs with very large n?
• What are some other questions about properties of random graphs that you could explore in
a similar fashion?
What to turn in
You will submit everything on Blackboard. Include the following:
• A .ipynb notebook file named code_firstname_lastname.ipynb with all your code from the
Programming tasks section. Make sure to clearly separate the various parts. Also, test this
notebook by restarting it and running from the beginning; this should produce no errors.
Page 3 of 4
Spring 2020 Proj 3 MAT 331
• A pdf file named report_firstname_lastname.pdf with your work from theWritten report
section. The exact format of this report is up to you. It can be hand-written (legibly) and
then scanned (legibly) into a pdf document. Or it can be be made on a computer. It must
be in pdf form (it is generally easy to convert other forms such as .doc to pdf).
Page 4 of 4