●  Solution Problem 1

a)  The network is directed because the adjacency matrix is not sym- metric.                                                                  (2 marks)[Unseen]

b)  The network is shown in Figure 1. (4 marks)[Unseen]

Figure 1: The directed network with adjacency matrix A.

c)  The network contains two weakly connected components formed re- spectivelly by the nodes {1, 2} and {3, 4}.                                        (2 marks)[Unseen]

d)  The network contains one strongly connected component formed by the nodes {3, 4}.                                                   (2 marks)[Unseen]

e)  The network does not have any out-component.  (2 marks)[Unseen]

f)  The in-degree sequence is fiven by {1, 0, 1, 1} the out-degree sequence is given by {0, 1, 1, 1}.

(4 marks) [Unseen]

g)  The in-degree distribution is given by Pin (0) = 1/4, Pin (1) = 3/4Pin (k) =

0 for k = 2, 3.

(2 marks) [Unseen]

The out-degree distribution is given by Pout (0)  =  1/4, Pout (1)  = 3/4Pout (k) = 0 for k = 2, 3.

(2 mark2) [Unseen]

h)  The eigenvector centrality x can be found as following.

Given the initial guess x(0)  =  1 given by

╱  1  、

x(0)  =   !(!)  1(1)   │(│)

．  1  !

let us is calculate the result of the iteration

xn  = Axn _ 1 .

We have

(1)

(2)

╱ 0 x(1)  =  !(!) 0(0) ．  0

╱  0

x(2)  =  !(!) 0

．

╱ 0

x(3)  =  !(!) 0 ．  0

Therefore

for every n > 3.

It follows that

╱  0  、

x(n)  =   !(!) 1(0)   │(│)

(2 marks)[Unseen]

╱  0  、

x =   !(!) 1(0)   │(│)

(2 marks)[Unseen]

i)  The result of point  h)  is expected because nodes  1  and  2  are  in an in-component of the network and therefore have zero eigenvector centrality.   Nodes 3 and node 4 instead have the same eigevcetor centrality because they form a dimer.                (2 marks)[Unseen]

–  Solution Problem 2

a)  The undirected network of N nodes with smallest diameter is the complete graph, formed by N nodes each one connected to all the others. The diameter of this network is D = 1. (2 marks)[Unseen] This network has the small-world distance property. In fact

lN   = lN   = 0.                               (5)

(3 marks)[Bookwork]

b)  The undirected network of N nodes which is connected and has the largest diameter is the (open) linear chain of N nodes that has di- ameter D = N · 1.                                              (2 marks)[Unseen] This network does not have the small-world distance property.  In fact

lN   = lN   = o.                              (6)

(3 marks)[Bookwork]

c)    i)  The degree distribution P(k) of the Poisson network with average degree (k）= c = 4 is given by

P (k) = ck e_c .                                      (7)

(1 marks)[Bookwork] The generating function G(x) is given by

→

G(x) =       P (k)xk  = e_c+cx .                           (8)

k=0

(2 marks)[Bookwork] The first and second moment of the Poisson degree distribution can be obtained by differentiating the generating function G(x). In particular we have

(k）    =     │x=1  = c    (k(k · 1)）    =     │x=1  = c2 .

(9)

(2 marks)[Bookwork]

It follows that

(b）=                   = c = 4.                             (10)

(1 marks)[Bookwork]

ii)  Using the result of point i) we get

Nd  ~ (k） ╱ 、d _ 1  = (k）d                                (11)

(2 marks)[Bookwork]

Therefore

Nd  ~ 4d .                                          (12)

(1 marks)[Unseen]

iii)  Since at distance d = 0 from the random node there is only one node (the node itself) we have

Nd  ~ 4d                                                               (13)

for 0 < d.                                                       (1 marks)[Unseen]

The total number of nodes Nd<e  at distance 0 < d < 1 from any random node of the Poisson network is given by

e                  4e+1  · 1

Nd<e  =       4d  =    4 · 1   .                             (14)

d=0

(2 marks)[Unseen]

Therefore we have

N =  ┌4e+1 · 1┐                                 (15)

(1 marks)[Unseen]

iv)  By imposing that all the nodes of the network are found at dis- tance d < 1 from a random node we have

N = Nd<e  =  ┌4e+1 · 1┐ (1marks)

3N = 4e+1 · 1(1mark)

3N + 1 = 4e+1(1mark)

1 =  ln [3N + 1] · 1.(1mark)                    (16)

v)  Using Eq.  (16) and considering the leading term for N > 1 we have

ln[3N]      ln N

2 ln 2       2 ln 2 .

(4 marks) [Unseen]

vi)  The local clustering coefficient Ci of a generic node i of a Poisson network can be estimated to be

Number of triangles passing through node i

Ci      =                                ki (ki  · 1)/2

~

pki (ki · 1)/2

ki (ki · 1)/2

(18)

where ki  is the degree of node i and p = (k）/N is the probability of a link between any two nodes of the network.        (2 marks) [Bookwork]

In fact each node i belongs in average to pki (ki · 1)/2 triangles since any pair of its neighbor is connected with probability p.  (2 marks) [Bookwork]

●  Solution Problem 3

a) The average number of links i  added to node i in timestep t is given by

N                             N

i  =       π (i,r)  =        .

r=1                    r=1

(19)

(2 marks) [Unseen]

Using

N

L   =           kj

j=1

N

ki      =         Air

r=1

we get

(20)

i  = 

(21)

(4 marks) [Unseen]

b)Since initially the number of links is m0  = 1 and at each time we add

two links we have L = 1 + 2t.                                     (1 mark) [Unseen]

Since initially we have n0  = 2 nodes and at each time we add a node we

have N = 2 + t.

c)The average degree (k）is given by

=       =

(1 mark) [Unseen]

(22)

(4 marks) [Bookwork]

d)In the mean-field approximation, the degree ki (t) of node i at time t satisfies the following differential equation

 = i  = 

(23)

(2 marks)[Bookwork] In the limit t > 1, we have(j kj  = 2L ~ 4t. Therefore we can write the dynamical mean-field equation for the degree ki (t) of node i, getting

dki          2ki          ki

=                          =

dt        4t       2t ,

with initial condition ki (ti ) = 2.

This equation has solution

ki (t) = 2 ╱ 、1/2 .

(24)

(2 marks)[Bookwork]

(25)

(2 marks)[Bookwork]

e) The probability P(ki (t) > k) that a random node has degree ki (t) > k , in the mean-field approximation can be calculated as follows

P (ki (t) > k) = P ╱2 ╱   、 (1/2)  > k\ = P ╱ti  < t ╱  、 2 \ = ╱  、 2 . (26)

(3 marks)[Bookwork] Therefore, the degree distribution P (k) is given by

P (k) =  = ·  ╱  、 2  = ╱  、 3 .                   (27)

(3 marks)[Bookwork]

f) The master equation for Nk (t) reads

Nk (t + 1) = Nk (t) + Nk _ 1 (t)(1 · δk,2) · Nk (t) + δk,2

(28)

(3 marks)[Bookwork]

g) Assuming Nk (t) ~ (t + n0 )P (k) for large t

1 we get

P (k) = P (k · 1)(1 · δk,2) · P (k) + δk,2 .

(29)

giving

P (k) = P (k · 1)

for k > 2 and

P (2) = 1

Solving these equations we get

(3 marks)[Bookwork]

(30)

(31)

(3 marks)[Bookwork]

P (k) =

12

k(k + 1)(k + 2) .

(32)