Description
One can use the igraph library (https://igraph.sourceforge.net/) to
generate all kinds of networks and measure various properties of a
given network. The library has R, Python, Ruby and C interfaces. You
can choose one of these languages to program and generate the following
networks, although R is preferred.
Submission: Please submit a zip file containing your codes and report
to “ee232e.spring2016@gmail.com”. The zip file should be named as
“HW1_UID1_UID2_…_UIDn.zip” where UIDx are student ID numbers
of team members. If you had any questions you can send an email to
the same address.
1. Create random networks
(a) Create three undirected random networks with 1000 nodes,
and the probability p for drawing an edge between two arbitrary
vertices 0.01, 0.05 and 0.1 respectively. Plot the degree
distributions.
(b) Are these networks connected or disconnected? What are the
diameters of these networks?
(c) Try to numerically find a value pc (to three significant figures),
so that when p < pc the generated random networks
are disconnected, and when p pc the generated random
networks are connected.
(d) Can you analytically derive the value of pc?
1
2. Create a network with a fat-tailed degree distribution
(a) Create an undirected network with 1000 nodes, whose degree
distribution is proportional to x
−3
. Plot the degree distribution.
What is the diameter?
(b) Is the network connected? Find the giant connected component
(GCC) and use fast greedy method to find the community
structure. Measure the modularity. Why is the modularity
so large?
(c) Try to generate a larger network with 10000 nodes whose
degree distribution is proportional to x
−3
. Compute the modularity.
Is it the same as the smaller network’s?
(d) You can randomly pick a node i, and then randomly pick a
neighbor j of that node. Measure and plot the degree distribution
of nodes j that are picked with this process.
3. Creates a random graph by simulating its evolution
(a) Each time a new vertex is added it creates a number of links
to old vertices and the probability that an old vertex is cited
depends on its in-degree (preferential attachment) and age.
Produce such an undirected network with 1000 nodes. Plot
the degree distribution.
(b) Use fast greedy method to find the community structure.
What is the modularity?
4. Use the forest fire model to create a directed network
(a) This is a growing network model, which resembles how the
forest fire spreads by igniting trees close by. Plot the in and
out degree distributions.
(b) Measure the diameter.
(c) Measure the community structure and modularity.
2
