Complex-Systems -     Project 2B - Solved

Complex Networks
In the present project you will try to analyse the behaviour of real networks and of the Watts-Strogatz model.

1. Real Networks
In the webpage https://snap.stanford.edu/data/index.html of the Stanford Network Analysis Project there several examples of real networks: for instance there are examples of social networks, communication networks, citation networks, collaboration networks, road networks etc...

For each network it is possible to download a text file with a list of the connections of each node of the network.

i)            Choose two undirected networks from the list, trying to pick up (using the heuristics given in Lecture 8) one scale-free and one non scale-free. Try to explain the heuristics of your choice.

ii)           For each of the networks determine the adjacency matrix A.

iii)         Calculate the average clustering coefficient of each network (Hint: the clustering coefficient can be written in terms of A3. In order to optimize the computing time one could use a fast matrix multiplication algorithm, like the Strassen algorithm, or by using sparse matrix multiplication).

iv)         Estimate the degree distribution of the networks and plot the probability mass functions pm (pm := P(K = m), where K is the degree of the node). Plot a log-log plot as well. Discuss your findings.

v)           Calculate the average degree of the neighbors of a randomly chosen node in one network of your choice. Compare the result with the average degree of the network. Can you observe the friendship paradox, i.e. on average, your friends have more friends than you do?

vi)         (BONUS PART) Consider a general graph G(V,E) with no isolated vertices. Pick a random vertex v1 ∈ V by first picking uniformly at random a vertex v0 ∈ V , and then by choosing uniformly at random v1 among the neighbors of v0. Show that:

E(kv1) ≥ E(kv0)

where we denote with kv the degree of the vertex v ∈ V .

vii)       (BONUS PART) Assume first that the degree distribution is Poisson. Estimate with the method of Maximum likelihood the parameter λ of the distribution. Then, perform a goodness of fit test for testing the hypothesis of being the data Poisson distributed.

viii)      (BONUS PART) Assume then that the degree distribution is a power law. Estimate with the method of Maximum likelihood the slope and the intercept of the log of the degree distribution Then, perform a goodness of fit: can we reject the hypothesis of the network being scale-free?

If you are more picky from a statistical point of view, you might want to estimate the tail exponent with a more refined methodology. From the paper Scale-Free Networks Well Done, you can use a non-parametric estimator as the Hill’s estimator (formula B7), or the smooth Hill’s estimator (formula B9) with optimal κ estimated by bootstraping (Appendix C).

2. Watts-Strogatz model
Consider the Watts-Strogatz model introduced in Lecture 8 (see the paper Collective dynamics of small-world network for a formal definition of the random graph). We recall that a realization of a Watts-Strogatz random graph WS(N,2r,p) can be obtained following the algorithm:

1.    N nodes arranged in a circle.

2.    Each node is linked to its 2r neighbors on the circle, r clockwise, r anticlockwise.

3.    Going through each node one after the other, each edge going clockwise is rewired towards a randomly chosen other node with probability p, with duplicate edges forbidden.

Each vertex i on the circle can be seen as a point in {1,2,,...,N}. We use the following metric for measuring distances between two points i and j on the circle:

 

i)         Let us take three realizations of a WS graph with different p: in particular let us take N = 500, r = 5 and p ∈ {0.2,0.4,1}.

•    For each of the graphs derive and plot the empirical degree distributions pˆm(p). Can you say a priori how much is pm, for k ∈ {1,2,3,4}?

•    (BONUS PART) We try now to derive an analytical expression for pm(p) := Pp(K = m). Since r of the initial 2r (with p = 0) connections of each vertex are left untouched by the construction of the WS graph, the degree of each vertex i, can be written as ki = r + ni, with ni ≥ 0. The quantity ni can also written as ni := Ai + Bi, where Ai ≤ r have been left in place, each one with probability 1 − p, and the other Bi = ni − Ai = ki − m − Ai links have been reconnected from other nodes towards i, each with probability of order p/N, for N large. Show that for large N (assuming valid the Poisson approximation of a Binomial distribution) we have:

 , for m ≥ r.

(1)

•    Draw the three degree distributions pm(p) of the previous point and discuss their agreement with pˆm(p).

•    By using the expression in (1), show that

 

which is a Poisson distribution for the variable K−r. Draw this Poisson degree distribution and discuss its agreement with the empirical pˆm(1) obtained in the first bullet. Draw also the Poisson degree distribution for an Erdos-Renii random graph with the same average distribution of a WS(500,10,1). Discuss your findings.

ii)       For a graph WS(N,2r,0) (i.e. the probability of rewiring p is zero), prove that the clustering coefficient C0 is:

 

iii)     For a general graph WS(N,2r,p), with p 6= 0, the calculation of the clustering coefficient Cp is a bit more involved. However, it can be proven that:

                                                                                    Cp = C0(1 − p)3                                                                                                    (2)

Could you explain the probabilistic intuition behind (2)? (Hint: which is the probability that a triangle existing at p = 0 is present after the rewiring?)

iv)      We want to find the mean shortest path distance ` of the Watts-Strogatz graph. Let us denote with `(i,j) the distance   between two vertices i and j belonging to a WS(N,r,p). Hence:

 

A mean-field treatment of the model showed that this quantity can be approximated by:

 

with

 

By using the identity  , show that for N large enough, there is a regime of the parameter p where the WS graph has small world properties (i.e. ` ∼ log(N))