1 Measures and Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Network Statistics & Measurement Error . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Structure of Real-world Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Models of Network Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5 Network Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6 Spreading Phenomena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Tutorial 1
Measures and Metrics
1.1
A network consists of n nodes in a ring, where n is odd:
All the nodes have the same closeness centrality. What is it, as a function of n?
1.2
Calculate the closeness centrality of each of the nodes in this network:
2
1.3
Consider an undirected tree of n nodes. A particular edge in the tree joins nodes 1 and 2 and divides the
tree into two disjoint regions of n1 and n2 nodes as sketched here:
Show that the closeness centralities C1 and C2 of the two nodes are related by
1 n1 1 n2
+ = + .
C1 n C2 n
1.4
Consider the following two studies:
a) A survey of heterosexual couples in the city of San Francisco recorded, among other things, the
ethnicity of their interviewees and calculated the fraction of couples whose members were from each
possible pairing of ethnic groups. The fractions were as follows:
Assuming the couples interviewed to be a representative sample of the edges in the undirected
network of relationships for the community studied, and treating the nodes as being of four types —
black, Hispanic, white, and other — calculate the numbers er and ar defined below for each type.
Hence, calculate the modularity of the network with respect to ethnicity.
3
er = the fraction of edges that join nodes of type r,
ar = the fraction of ends of edges attached to nodes of type r.
b) A 2016 article on the website [Link] described the results of a study by Eitan Hersh
and Yair Ghitza of political alignment among couples in the United States. Hersh and Ghitza
estimated the fractions of opposite-sex partners with each combination of major-party alignment
(which in the US means Democratic, Independent, or Republican) to be as follows:
Assuming these results to be representative of the network of relationships, calculate the modularity
of the network with respect to political persuasion.
c) From your results, what do you conclude about homophily in these two studies?
4
Tutorial 2
Network Statistics & Measurement
Error
2.1
Suggest some potential sources of error in measurements of the structure of the following networks:
a) A scientific coauthorship network assembled from a database of papers.
b) A web network of web pages at a single university, assembled by using an automated web crawler.
c) A metabolic network.
d) A social network of who is friends with whom at a large company, assembled using questionnaires.
e) A network representation of an electrical power grid.
2.2
The false positive rate β is the probability of erroneously observing an edge where none exists. Arguably a
more useful measure, however, is the false discovery rate, which is the probability that an actual observed
edge is itself a false positive, which is not the same thing.
Suppose we measure a network once, producing an observed adjacency matrix O with elements Oij . Then
the standard false positive rate within the independent edge model is β = P (Oij = 1|Aij = 0, α, β, ρ). (It
does not matter which pair of nodes i, j we look at. By hypothesis, all pairs have the same false positive
rate.)
The probability that an observed edge is a false positive, on the other hand, is given by P (Aij = 0|Oij =
1, α, β, ρ). Using Bayes’ rule, we can write this probability as:
P (Aij = 0|α, β, ρ)
P (Aij = 0|Oij = 1, α, β, ρ) = P (Oij = 1|Aij = 0, α, β, ρ) .
P (Oij = 1|α, β, ρ)
a) Show that
P (Oij = 1|α, β, ρ) = P (Oij = 1|Aij = 1, α, β, ρ)P (Aij = 1|α, β, ρ)
+P (Oij = 1|Aij = 0, α, β, ρ)P (Aij = 0|α, β, ρ).
5
b) Hence, show that the probability of an observed edge being a false positive is
β(1 − ρ)
P (Aij = 0|Oij = 1, α, β, ρ) = .
αρ + β(1 − ρ)
c) Calculate the value of this probability for the reality mining example.
d) You should find that the probability you calculate is considerably larger than the false negative rate
β. Explain briefly why this is.
2.3
For some networks, observations of edges are reliable but observations of non-edges are not. Academic
coauthorship networks provide an example. If we observe a paper written by two particular individuals,
then it is a safe bet that they did actually coauthor a paper. But if we do not observe such a paper, then
it does not guarantee that no such paper exists. We might just not have found it, or it might be written
but not published yet.
Derive an error model for edge probabilities, and adapt it to this case (reliable edges but unreliable
non-edges).
6
Tutorial 3
Structure of Real-world Networks
3.1
Suppose that a network has a degree distribution that follows the exponential (or geometric) form pk =
Cak , where C and a are positive constants and a < 1.
a) Assuming the distribution is properly normalized, find C as a function of a.
b) Calculate the fraction P of nodes that have degree k or greater.
c) Calculate the fraction W of ends of edges that are attached to nodes of degree k or greater.
d) Hence show that the Lorenz curve (plot of W vs. P ) for this degree distribution is given by
1 − 1/a
W =P − P log P.
log a
e) Show that the value of W is greater than one for some values of P in the range 0 ≤ P ≤ 1. What
is the meaning of these “unphysical” values?
3.2
A particular network is believed to have a degree distribution that follows a power law for nodes of degree
10 or greater. Among a random sample of nodes in the network, the degrees of the first 20 nodes with
degree 10 or greater are:
16 17 10 26 13
14 28 45 10 12
12 10 136 16 25
36 12 14 22 10
Estimate the exponent α of the power law and the error on that estimate.
3.3
Here are plots of the cumulative distribution function of degrees in two undirected networks:
a) One of these networks is approximately scale-free; the other is not. Which is which and how can
you tell?
7
b) For the scale-free network give an estimate of the exponent α of the degree distribution.
c) If there are m edges in the scale-free network, then there are 2m ends of edges. Approximately what
fraction of the highest-degree nodes have half of all the edge-ends?
8
Tutorial 4
Models of Network Formation
4.1
Consider the following variant of the Barabási–Albert model. Nodes are added one by one to a growing
undirected network, each node having initial degree c. The c edges emanating from a newly added node
connect to previously existing nodes i with probability proportional to ki + a, where ki is i’s (undirected)
degree and a is a constant.
a) Given that c edges are added to the network with each node, what is the mean degree of a node in
the network in the limit of large network size?
b) Derive the master equation that gives the fraction of nodes pk having degree k in the limit of large
network size. If necessary, give an additional rate equation to cover any special-case value of k.
c) Show that the fraction of nodes with degree c in the limit of large network size is
2c + a
pc ≈ .
2c + a + c(c + a)
4.2
Consider a model network similar to the model of Barabási and Albert, in which undirected edges are
added between nodes according to a preferential attachment rule, but suppose now that the network does
not grow—it starts off with a given number n of nodes and neither gains nor loses any nodes thereafter.
In this model, starting with an initial network of n nodes and some specified arrangement of edges, we
add at each step one undirected edge between two nodes, both of which are chosen at random in direct
proportion to degree k. Let pk (m) be the fraction of nodes with degree k when the network has m edges.
a) Show that when the network has m edges, the probability that node i will get a new edge upon the
addition of the next edge is ki /m.
b) Write down a master equation giving pk (m + 1) in terms of pk−1 (m) and pk (m). Be sure to give the
equation for the special case of k = 0 also.
c) Eliminate m from the master equation in favor of the mean degree c = 2m/n and take the limit
n → ∞ with c held constant to show that pk (c) satisfies the differential equation
dpk
c = (k − 1)pk−1 − kpk .
dc
9
P∞ k
d) Define a generating function g(c, z) = k=0 pk (c)z and show that it satisfies the partial differential
equation
∂g ∂g
c + z(1 − z) = 0.
∂c ∂z
e) Show that g(c, z) = f (c − c/z) is a solution of this differential equation, where f (x) is any differen-
tiable function of x.
f) The particular choice of f depends on the initial conditions on the network. Suppose the network
starts off in a state where every node has degree one, which means c = 1 and g(1, z) = z. Find the
function f that corresponds to this initial condition and hence find g(c, z) for all values of c and z.
g) Show that, for this solution, the degree distribution as a function of c takes the form
(c − 1)k−1
pk (c) = ,
ck
except for k = 0, for which p0 (c) = 0 for all c.
Note that this degree distribution decays exponentially in k, implying that preferential attachment does
not, in general, generate a power-law degree distribution if the network is not also growing.
10
Tutorial 5
Network Robustness
5.1
Consider a site percolation process in which nodes are removed uniformly at random from a random 4-
regular network (i.e., a configuration model where all nodes have degree 4). You can assume the network
is large.
a) Give an expression for the size S of the giant percolation cluster as a fraction of total network size.
b) Find the critical occupation probability ϕc .
c) Find the value of ϕ at which S = 1. This implies that the giant cluster fills the whole network. How
can this happen, given that the most it can fill is the whole of the giant component?
5.2
Consider a (uniform) bond percolation process with edge occupation probability ϕ on a random graph
with Poisson degree distribution and mean degree c, in the limit of large network size n.
a) Write down an equation whose solution gives the probability u that a node is not connected to the
giant percolation cluster via a particular one of its edges.
b) In terms of u, write down an expression for the probability that a node is not in the giant cluster
given that it has degree k.
c) Hence, or otherwise, write down an expression in terms of u, c, and k for the probability that a
node has degree k given that it is not in the giant cluster.
d) Thus, show that the mean degree of nodes not in the giant cluster is cu.
5.3
In the “acquaintance immunization” scheme, instead of vaccinating people at random, we ask people to
nominate a friend then we vaccinate the friend. Because one’s friends tend to be the popular people, this
has the beneficial effect of vaccinating people with many contacts.
Consider an acquaintance immunization process on an arbitrary network, in which a fraction f of
the population are chosen uniformly at random and then each of them nominates one of their friends
uniformly at random to receive the vaccination.
11
a) Show that the expected number of nominations received by individual i is f κi , where κi is the sum
of the reciprocals of the degrees of i’s neighbors in the network:
X Aij
κi = .
kj
j
b) Hence argue that the probability that an individual is not vaccinated, i.e., the probability that the
corresponding network node is occupied in the sense of percolation, is e−f κi when n is large.
c) Between two nodes with the same degree, of which one has high-degree neighbors and one has low-
degree neighbors, which is more likely to be vaccinated? Is this a good thing or a bad thing as far
as preventing disease is concerned?
5.4
Suppose we know the contact network over which a disease is spreading and we are given a certain
“budget” for vaccinating nodes, meaning we can vaccinate a specified number r of nodes. Our goal is to
minimize the number of people who catch the disease.
a) Suppose that after removing our r nodes the network consists of a set of k percolation clusters with
sizes s1 . . . sk . If the disease starts at a single randomly chosen node in the network and spreads to
all nodes in the same percolation cluster as that node (or doesn’t spread if the node itself has been
vaccinated), show that the expected number I of nodes that get infected is
k
1 X 2
I= sm .
n
m=1
Hence argue that the smallest possible value for the expected size of a disease outbreak is I =
(n − r)2 /nk when there are k clusters. All other things being equal, therefore, it’s better to allocate
the vaccinations so as to divide the network into the largest number of clusters possible. In effect,
one should use the vaccinated nodes to create “firewalls” that divide up the network and prevent
the disease from spreading too far, no matter where it starts.
b) If you are allowed to remove just one node, which one should you remove to minimize the expected
size of an outbreak in this network:
c) If you are allowed to remove two nodes, which should they be? How about three?
12
Tutorial 6
Spreading Phenomena
6.1
Consider a variant of the SIR model in which people die of the disease rather than recovering. Assuming,
as in the ordinary model, that an individual makes contacts with others at a rate β per unit time, but
that those contacts are with living people only, write down a modified version of the SIR equations for
this variant of the model.
6.2
Consider an epidemic SIR outbreak (i.e., an outbreak that starts in the giant cluster of the corresponding
percolation process) on a configuration model network with exponential degree distribution pk = (1−a)ak
with a < 1. You can assume that the network is large.
a) Write an expression for the probability u in terms of ϕ (edge occupation probability) and a. u is
the average probability that a node is not connected to the giant percolation cluster via a specific
one of its edges.
b) Hence find an expression for the probability that a node is infected by the disease if it has degree k.
c) Evaluate this probability for the case a = 0.4 and ϕ = 0.9, for k = 0, 1, and 10.
6.3
Consider the SIR model on a configuration model network where all nodes have degree four (also known
as a random 4-regular graph).
a) What is the critical value ϕc of the transmission probability at the epidemic threshold?
b) When the transmission probability is ϕ = 12 , show that if an epidemic happens, the fraction S of
nodes infected is √
3 5−5
S= .
2
13
6.4
Consider an SI-type epidemic spreading on the giant component of a k-regular random graph, i.e., a
configuration model network in which all nodes have the same degree k. Assume that some number c of
nodes, chosen at random, are infected at time t = 0.
a) Show that the probability of infection of every node increases at short times as eβkt .
b) Show that within the first-order moment closure approximation ( dx dt ) the average probability of
i
infection x of every node is the same and give the differential equation it satisfies.
c) Hence show that
ceβkt
x(t) = .
n − c + ceβkt
d) Find the time at which the “inflection point” of the epidemic occurs, the point at which the rate of
appearance of new disease cases stops increasing and starts decreasing.
14