Networks, 2nd Edition

Networks, 2nd Edition Mark Newman Solutions to Exercises (Chapter 6 to 18) No Solutions for Chapter 1 to 5 6Mathematics of networks

Exercise6.1:

a) Undirected

b) Directed, approximately acyclic

c) Planar, tree, directed or undirected depending on the

representation

d) Undirected, approximately planar

e) Directed or undirected depending on the network

f) Citation networks, food webs

g) The web, the network of who says they're friends with

whom

h) A river network, a plant or a tree or their root system

i) A road network, the network of adjacencies of countries

j) Any aliation network, recommender networks, key-

word indices

k) A web crawler

l) Draw data from a professionally curated index such as the

Science Citation Index or Scopus, or from an automated citation crawler such as Google Scholar

m) A literature search

n) Questionnaires or interviews

o) An appropriate map

Exercise6.2:The maximum number of edges is

n 2

because there are

n 2

distinct places to put an edge and each can have only one edge in a simple network. The minimum isn1 because we require that the network be connected andn1is the minimum number of edges that will achieve thissee the discussion at the top of page 123.Exercise6.3:The matrices are as follows: a)A © ­ ­ ­ ­ «

0 1 0 0 1

0 0 1 0 0

1 0 0 0 1

0 1 1 0 0

0 0 0 0 0

ª ® ® ® ® ¬ b)B © ­ ­ ­ «

1 0 1 0 0

0 1 1 0 0

0 0 0 1 0

0 1 1 1 1

ª ® ® ® ¬ c)B T B © ­ ­ ­ ­ «

0 0 1 0 0

0 0 1 1 1

1 1 0 1 1

0 1 1 0 1

0 1 1 1 0

ª ® ® ® ® ¬

Exercise6.4:

a)kA1 b)m 1 2 1 T A1 c)NA 2 d) 1 6 TrA 3

Exercise6.5:

a) A 3-regular graph has three ends of edges per node, and

hence3nends total. But the total number of ends of edges is also equal to2m, which is an even number. Hencen must be even.

b) A tree withnnodes hasmn1edges. Hence the

average degree is2m�n2¹n1º�n<2.

c) The connectivity of A and C must be at leasty, because if

there areypaths from B to C andx>ypaths from A to B, then there are at leastypaths all the way from A to C.On the other hand the connectivity of A and C cannot be

greater thanyby the same argument: if there were more

thanypaths from A to C and more thanypaths from B to A, then there would be more thanypaths from B to C (via A). Hence the connectivity of A and C must be exactlyy.

Exercise6.6:Let the eigenvector element at the central node

bex1. By symmetry the elements at the peripheral nodes all have the same value. Let us denote this valuex2. Then the

1 1 / 4

Networks(2ndEdition)

eigenvalue equation looks like this:

© ­ ­ ­ ­ ­ ­ «

0 1 1 1

1 0 0 0

1 0 0 0

1 0 0 0

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

ª ® ® ® ® ® ® ¬ © ­ ­ ­ ­ ­ ­ « x1 x2 x2 x2

:

:

:

ª ® ® ® ® ® ® ¬

© ­ ­ ­ ­ ­ ­ « x1 x2 x2 x2

:

:

:

ª ® ® ® ® ® ® ¬ ; whereis the leading eigenvalue. This implies that¹n1ºx2 x1andx1x2. Eliminatingx1andx2from these equations we nd that p n1. The equationx1x2then implies thatx1andx2have the same sign, which means that this must be the leading eigenvalue (by the PerronFrobenius theorem see the discussion on page 160 and the footnote on page 161).

Exercise6.7:

a) Total ingoing edges rÕ i1 k in i ; Total outgoing edges rÕ i1 k out i

:

b)1: : :rfrom nodes r1: : :nis equal to the total number of edges running to nodes1: : :rminus the number originating at nodes 1: : :r. In other words, it is equal to the dierence of the

two expressions above:

Number of edges rÕ i1

k in i k out i

:

c)r1must attach to nodes in the range1: : :rand hence the number of edges outgoing from noder1can be no greater than the total number from nodesr1: : :nto nodes1: : :r. Thus k out r1

rÕ i1

k in i k out i

:

Similarly, all edges ingoing at nodermust originate from nodes in the ranger1: : :nand hence the total number ingoing at nodercan be no greater than the total number from nodesr1: : :nto nodes1: : :r. Thus k in r rÕ i1

k in i k out i

:

Noting that the total number of edges ism Í n i1 k in i

Í n i1 k out i , this can also be written as k in r nÕ ir1

k out i k in i

:

Exercise6.8:The total number of edges attached to nodes of

type 1 isn1c1. The total number attached to nodes of type 2 is n2c2. But each edge is attached to one node of each type and hence these two numbers must be equaln1c1n2c2.

Exercise6.9:The network contains an expansion of UG, and

hence is nonplanar by Kuratowski's theorem:

(The ve-fold symmetric appearance of the network might lead one at rst to hypothesize that it contains an expansion of K5, but upon reection we see that this is clearly impossible, since every node has degree 3, whereas every node in K5has de- gree 4. Thus if the network is to be nonplanar it must contain an expansion of UG.)

Exercise6.10:The edge connectivity is two. To prove this we

display two edge-independent paths and a cut set of size two

thus:BABA

This constitutes a proof because the existence of two indepen- dent paths proves that the connectivity must be at least two, while the existence of the cut set proves that the connectivity can be no greater than two.

Exercise6.11:

a)n1,m0,f1.b)n!n

n1,m!m

m1,f!f

f.c)n!n

n,m!m

m1,f!f

f1.d)fnm2. Clearly it is true for case (a), which can be conveniently used as a starting point for in- duction. The relation is also preserved by (b) and (c). And any connected planar graph can be built up by adding its nodes and edges one by one, i.e., by a combination of moves (b) and (c). Hence by inductionfnm2is true for all such graphs.e) for the outside face that extends to innity, and each edge has two sides. Therefore the number of edgesm

2 2 / 4

Solutions to exercises times two is at least as great asf1times three, or f2m�31. Substituting this inequality into the rela- tion from part (d) we getm3n3, and combining this with the relation for the average degreec2m�nwe get c6 6 n

<6:

Exercise6.12:

a)stotof lengthris»A r ¼st and each has weight r . Thus the sum of the weights for paths of lengthris»¹Aº r ¼stand the sum for paths of all lengths (including length zero) is Zst 1Õ r0

»¹Aº

r ¼st»¹IAº 1

¼st:

b)jj<1�1, where1is the largest eigenvalue ofA(which is always positive, a consequence of the PerronFrobenius theorem).c) @logZst @log

Zst @Zst @

Zst Õ r r r1 »A r ¼st

1 Zst Õ r r»¹Aº r

¼st:

Letmbe the number of paths fromstotof length`st.Then the leading terms inZstand the sum above are Zst Õ r

»¹Aº

r ¼stm `s t O¹ `s t1 º; Õ r r»¹Aº r ¼stm`st `s t O¹ `s t1

º:

Substituting into the previous result we then get @logZst @log

m`st `s tO¹ `s t1 º m `s tO¹ `s t1 º

`stO¹º:

Taking the limit!0then gives the required result.

Exercise6.13:

• k

in i incoming edges at nodeiand the sum of the trophic levels at their other ends is Í jAi jxj. Thus the average trophic level is¹1�k in i º Í jAi jxjand the result follows.b)k in i 0and soxiis undeter- mined. We can x this by articially settingk in i 1for autotrophs (or indeed setting it to any nonzero value).Then the equation forxican be rewritten in vector form as xD 1 Ax1; whereDis the matrix with the in-degrees down the diag- onal or 1 for nodes with zero in-degree, and1is the vector ¹1;1;1; : : :º. Rearranging this expression then gives the required result.7Measures and metrics

Exercise7.1:

• »A1¼i

Í jAi jkikand henceA1k1.

• xof Katz centralities is given by

x¹IAº 1 1¹IA 2 A 2

: : :º1:

Noting, as above, thatA1k1for the regular graph, this then becomes x¹1k 2 k 2

: : :º1

1 1k ; and hencexi1�¹1kºfor alli.c) obvious choices.

Exercise7.2:Starting at any node, there is one node at dis-

tance 0, two at distance 1, two at distance 2, and so forth up to a maximum distance of 1 2 ¹n1º. So the mean distance is 2 n ¹n1º�2 Õ k1 k 2 n

1 8 ¹n 2 1º n 2 1 4n

:

And the closeness is the reciprocal of this, or4n�¹n 2 1º.

Exercise7.3:

a) verse direction. We write the series asx Í 1 k0 ¹Aº k 1, then Ax1A 1Õ k0 ¹Aº k 111 1Õ k1 ¹Aº k 1

1Õ r0 ¹Aº k

1x:

Alternatively, we can rearrange the denition ofxaccord- ing to Eq. (7.7) asx¹IAº 1 1and then expand the matrix inverse as a geometric series.b)we can neglect terms in the series beyond the rst two to getx'1A1which implies that the centrality of nodeiisxi1ki, which is linear in the degrees. Hence in this limit the Katz centrality is, apart from additive and multiplicative constants, the same as the degree centralityhigher degree implies higher Katz centrality.c)1as a linear combination of the eigen- vectorsvrof the adjacency matrix1 Í kc kv kfor some choice of coecientsc

• (For a directed network, we use

the right eigenvectors.) Then ¹Aº k

1¹Aº

k Õ r crvr Õ r cr¹rº k vr;

3 3 / 4

Networks(2ndEdition) whereris the eigenvalue corresponding to eigenvec- torvr. Summing overkwe now have x 1Õ k0 ¹Aº k 1 Õ r cr 1Õ k0 ¹rº k vr Õ r crvr 1r ; so long asr<1. Now as we take the limit!1�1, all terms in the sum remain nite except the term inr1, which diverges. Hence this term dominates in the limit andxbecomes proportional to the leading eigenvectorv1.

Exercise7.4:Every node in this network is symmetry-

equivalent, so we only have to calculate the closeness of one of them. Starting at any node there is one node at distance 0, three at distance 1, and the remaining six are at distance 2. So the mean distance is¹0312º�10 3 2 and the closeness centrality is the reciprocal 2 3 .

Exercise7.5:The vectorxof PageRank scores is given by

Eq. (7.11) to bex¹IAD 1 º 1

• In this network, how-

ever, all out-degrees are 1 and henceDD 1 Iand x¹IAº 1 1¹IA 2 A 2

: : :º1:

(The central node has out-degree zero but, as discussed in Sec- tion 7.4, we conventionally set the out-degree to one to avoid dividing by zero, and this change has no eect on the PageR- ank values.) But recall now that the matrix element»A d ¼i j counts the number of paths of lengthdfromjtoiand hence n ¹dº i

Í j»A d ¼i j»A d 1¼iis the number of paths of lengthd from all nodes to nodei. Since the network is a directed tree, however, there is at most one path between each pair of nodes, and hencen ¹dº i is also the number of nodes that have distance exactlydfromi. Thus, if the central node is node 1, then n ¹dº 1

Õ i

did; wheremnis the Kronecker delta. Now the PageRank of the central node is x1 1Õ d0

d

A d 1

1

1Õ d0

d n ¹dº 1

1Õ d0

d Õ i

did

Õ i 1Õ d0

d

did Õ i

di

:

Exercise7.6:LetL1andR1be the sums of the distances from

node 1 to nodes in the left and right shaded regions and simi- larly forL2andR2with node 2. Then we note that the distance from node 2 to any node in the left shaded region is 1 greater than the corresponding distance from node 1 to the same node and henceL2L1n1. SimilarlyR1R2n2. Adding these two expressions gives

L1R1n1L2R2n2:

Noting that the closeness centralities are given byC1n�¹L1 R1ºandC2n�¹L2R2º, we then recover the required result.

Exercise7.7:

a) est path between any pair of nodes. The particular node of interest lies on the shortest path between every pair of nodes except pairs where both members fall in the same disjoint region. There are Í in 2 i such pairs, andn 2 pairs in total, soxn 2

Í in 2 i .b)ith node divides the line graph into two disjoint regions of sizesn1i1andn2ni.Applying the formula we then nd that the betweenness of theith node is2¹ni1ºi1.

Exercise7.8:

a) b) r 3 4 .c) have degrees 4 and 5 respectively, so their cosine similar- ity is

2 p 45

1 p 5

:

Exercise7.9:

a) three of the others, so the entire network is a 3-core. In the second network, however, there is one node with only two neighbors. Removing this node and then iteratively removing all subsequent nodes with two or fewer neigh- bors, we end up removing the entire network. Hence there is no 3-core in the second network, despite its close similarity to the rst.b) components then there are three such components in this

network:

(Depending on who you ask, a single node may or may not be considered a strongly connected component.) c) cients of the nodes are 0, 1, 1 3 , 1, and 2 3 .d)erandardened on page 205 of the book, we havee1 3 10 ,e2 1 2 ,a1 2 5 , anda2 3 5 .Then the modularity is Qe11a 2 1 e22a 2 2

7 25

:

• / 4