首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28