14.15J Problem Set 1 Solutions

Massachusetts Institute of Technology Departments of Electrical Engineering & Computer Science and Economics 6.207/14.15 Networks Spring 2018 Problem Set 1 Solutions Problem 1.1 [P7.3, Newman] Consider an undirected, connected tree of n vertices. A particular edge in the tree joins vertices 1 and 2 and divides the tree into two disjoint regions of n1 and n2 vertices (also see Figure in Newman). Argue that the closeness centralities C1 and C2 of the two vertices, defined according to Equation (7.29) in Newman, are related by 1 n1 1 n2 + = + . n C2 n C1 (1) Solution: From the definitions in Newman, we have the following: C1 = P n j d1j C2 = P n j d2j (2) We can simplify C2 as follows: n C2 = P j d2j n P j∈R1 (1 + d1j ) + j∈R2 (d1j − 1) n P = n1 − n2 + j d1j =P Taking 1 C2 and substituting in C1 gives the desired relation: P n1 − n2 + j d1j 1 = n P C2 n1 n2 j d1j = − + n n n 1 n1 n2 = − + n n C1 1 (3) (4) Problem 1.2 [P7.4, Newman] Consider an undirected, connected tree of n vertices. Consider a particular vertex in the tree that has degree k. Naturally, its removal would divide the tree into k disjoint trees with sizes being n1 , . . . , nk where n1 + · · · + nk = n − 1 and n1 , · · · , nk ≥ 1. (a) Show that the unnormalized betweenness centrality x of the vertex, as defined in Eq. (7.36) in Newman, is x = n2 − k X n2m . (5) m=1 Consider a special case of connected tree, a line graph of n nodes: imaging placing n nodes on a line next to each other and connecting only immediate neighbors, i.e. other than two end nodes all nodes connect to their neighbors of left and right, while end nodes connect to only one neighbor (also see Figure in Newman). (b) Using (a) or otherwise, calculate the betweenness of the vertex that is i hops away from one of the end vertex in the line graph for i ≥ 1. Solution: (a) From the definitions in Newman, we have: x= X nis,t (6) gs,t X s,t = 1 (7) s∈Regioni t∈Regionj i6=j = X X 1− s,t = n2 − 1 (8) s,t in some region k X m=1 2 n2m (9) (b) We can think of our line graph in terms of two regions, where region 1 contains all vertices before vertex i (vertices 1 to i − 1) and region 2 contains all vertices after vertex i (vertices i + 1 to n). Using the result from (a), the betweenness, xi of vertex i can be written as:   xi = n2 − (i − 1)2 + (n − i)2 = n2 − (i2 − 2i + 1 + n2 − 2ni + i2 ) = 2i(n + 1) − 2i2 − 1 (10) (11) (12) (13) Problem 1.3 In many graphs, average path length and diameter are close to each other in value. But there are graphs in which they are very different. (a) Describe an example of a graph where the diameter is more than three times as large as the average path length. (b) Describe how you could extend your construction to produce graphs in which the diameter exceeds the average path length by as large a factor as you like (that is, for every number c, can you produce a graph in which the diameter is more than c times as large as the average path length). Solution: (a) Consider the below graph, with diameter 4: 3 The average path length of our graph is given by: P average path length = = n(n−1) 2 i6=j dij (n+3)(n+2) 2 (14) ∗ 1 + (n − 1) ∗ 2 + (n − 1) ∗ 3 + (n − 1) ∗ 4 + 3 ∗ 1 + 2 ∗ 2 + 1 ∗ 3 (n+3)(n+2) 2 (15) = n(n−1) + 9n + 2 (n+3)(n+2) 2 1 (16) In particular, for n = 40, we have: average path length = 1.26 4 < 3 diameter < 3 (b) Consider the following graph, with diameter c + 1: 4 (17) (18) (19) The average path length of our graph is given by: P i6=j dij (n+c)(n+c−1) 2 n(n−1) + 2 = Pc+1 m=2 (n − 1)m + (n+c)(n+c−1) 2 Pc−1 k=1 (c (20) − k)k (21) From (23), we can see that the average path length approaches 1 as n → ∞. This tells us that avg. diamter → c + 1 as n → ∞. This path length construction allows us to produce graphs where the diameter exceeds the average path length by any factor. Problem 1.4 You are given an adjacency matrix of a network graph (p4-data.mat on the class website, under HW1). You can use the below python code to load the adjacency matrix. Using this, compute the following metrics of the associated graph: (a) Clustering coefficient. (b) Degree distribution. Plot the corresponding probability mass function. (c) Average path length. 5 (d) Diameter. Solution: (a) Let t be the number of triangles, and let r be the number of connected triples. The overall clustering coefficient is: C= 3t 3(467) = = 0.4989 r 2808 (b) The degree distribution should resemble the following: 6 (22) (c) The average path length is 2.6411 (d) The diameter of our graph is 5. The diameter is the maximum shortest path between any two nodes in the graph. Problem 1.5 Consider an undirected graph of n = 2m nodes with the following properties: 1. nodes 1, . . . m − 1 are fully connected, 2. nodes m + 1, . . . 2m are fully connected, 3. nodes m − 1, m, m + 1 are connected, 4. there are no other edges. Answer the following questions. (a) Write some code to construct the adjacency matrix, say A, from some value m, for this graph. Explicitly compute and write down the adjacency matrix for m = 3. (b) Let D denote the diagonal matrix with ith diagonal entry being degree of node i. Compute the first and second eignvalues of matrix L = AD−1 for m = 5, 10, 15, 20. Consider a linear dynamical system over this graph with each node having a real value associated with it. Let xi (0) be the initial value associated with node i at iteration 0, for 1 ≤ i ≤ 2m. Let x(0) = [xi (0)]0 ∈ R2m the vector of these initial values. The vector is updated iteratively as follows: at iteration k + 1, k ≥ 0, x(k + 1) = Lx(k). (c) Assume that initial vector x(0) is such that ( 1, 1 ≤ i ≤ m xi (0) = 0, m + 1 ≤ i ≤ 2m. (23) (24) For m = 5, 10, plot the values of x1 (k), xm+1 (k) and x2m (k) for k = 1, 10, 20, 50, 100. 7 (d) Based on answers of (c), do you observe any peculiar behavior in x(k)? Can you explain it using the structure of L? Solution: (a) The adjacency matrix should be of the form (in this case, m = 3): ⎛ ⎞ 0 1 0 0 0 0 ⎜1 0 1 0 0 0⎟ ⎟ ⎜ ⎜0 1 0 1 0 0⎟ ⎟ ⎜ (25) ⎜0 0 1 0 1 1⎟ ⎟ ⎜ ⎝0 0 0 1 0 1⎠ 0 0 0 1 1 0 (b) The first eigenvalue λ1 , is always 1. The second eigenvalue λ2 , with respect to m, is: m λ2 5 0.9465 10 0.9887 15 0.9952 20 0.9974 8 (26) (c) 9 (d) From (c) we see that the convergence rate of our system: x(k + 1) = AD−1 x(k) (27) is inversely proportional to the value of the second largest eigenvalue, λ2 and m. Problem 1.6 Romeo and Juliet are in love. Romeo positively reacts to Juliet; he loves her more if she shows him more love and he loves her less when she shows less. Juliet is a fickle lover; she loves Romeo more when he loves her less and vice versa. We want to model their love affair as a dynamical system in order to predict what will happen to them in the future. To do so, let x(k) be the amount of love Romeo has for Juliet (measured in love units!), and let y(k) be the amount of love Juliet has for Romeo. A simple dynamical system representing their interactions is given by: for some real numbers a and b, the love at time k + 1 is given by x(k + 1) = x(k) + ay(k) y(k + 1) = bx(k) + y(k). 10 (28) Assume that, initially x(0), y(0) > 0. Answer the following questions: (a) Determine the signs of a and b to reflect the behavior of Romeo and Juliet. (b) For what ranges of parameters a and b will Romeo’s and Juliet’s love fizzle away regardless of where they start? (c) For what ranges of parameters a and b will Romeo and Juliet be forever caught in a cycle of love and hate? (d) Both Romeo and Juliet were burnt before from loving someone else that does not love them. As a result, their love tomorrow discounts their own love today by a factor of 0.5. Rewrite the model and answer (a)-(b). (e) What happens if both Romeo’s and Juliet’s love increases by one unit every single time regardless of the actions of the other? Answer questions (a)-(b). Solution: (a) For the condition, Romeo positively reacts to Juliet: a ≥ 0 For the condition, Juliet negatively reacts to Romeo: b ≤ 0 (b) We can write our dynamical system as:      x(k + 1) 1 a x(k) = y(k + 1) b 1 y(k) (29) For love to fizzle away regardless of starting point, all eigenvalues of our matrix A must satisfy |λi | < 1. This means, we must have det(A − λI) = 0: 1−λ a b 1−λ =0 (30) (1 − λ)2 − ab = 0 (31) √ 1. If ab < 0, then solutions to (29) are λ1,2 = 1 ± i −ab, so |λi | > 1 2. If ab = 0, then solutions to (29) are λ1 = λ2 = 1. 11 Therefore, for no range of parameters, within the constraints of question 1, does love fizzle away, regardless of starting point. (c) For Romeo and Juliet to be forever caught in a cycle of love/hate, the dynamical system must oscillate, which requires the eigenvalues to be complex. We have complex eigenvalues when ab < 0. This means we must have a > 0, b < 0. (d) For our new model, we have: x(k + 1) = 0.5x(k) + ay(k) y(k + 1) = bx(k) + 0.5y(k) (32) (33) Solving a) and b) again: 1. Again, we need a ≥ 0, b ≤ 0. 2. Similarly to b) our system is:      x(k + 1) 0.5 a x(k) = y(k + 1) b 0.5 y(k) (34) and we must satisfy |λi | < 1. Similarly to b), we can solve for our eigenvalues by setting det(B − λI) = 0, where B is our new coefficient matrix. This gives us: (0.5 − λ)2 − ab = 0 If ab < 0: √ λ1,2 = 0.5 ± i −ab q √ |λi | = 0.52 + ( −ab)2 √ = 0.25 − ab < 1 if ab > −3/4 (35) (36) (37) (38) (39) If ab = 0: |λ1 | = |λ2 | = 0.5 < 1 (40) Love fizzles away, regardless of starting point, for: a = 0, b ≤ 0 a ≥ 0, b = 0 −3/4 < ab < 0 12 (41) (42) (43) (e) Our new model is: x(k + 1) = x(k) + ay(k) + 1 y(k + 1) = bx(k) + y(k) + 1 (44) (45) Solving a) and b) again: 1. Again, we need a ≥ 0, b ≤ 0. 2. Our new system can be written as:        x(k + 1) 1 a x(k) 1 = + y(k + 1) b 1 y(k) 1 (46) and we must satisfy |λi | < 1. However, as established in b) originally, our system does not admit |λi | < 1 for any a, b where a ≥ 0, b ≤ 0. 13