Description
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
