Description

AA 597: Networked Dynamics Systems
Prof. Mehran Mesbahi
Soowhan Yi
P1. The complement of graph G = (V,E), denoted by G¯, is a graph (V,E¯), where uv ∈ E¯ if and only if uw /∈ E. Show that
L(G) + L(G¯) = nI − 11T
First, by definition, degree matrix of complement of graph (n − 1)I − D(G). Assuming that the graph and the complement do not have self loop, complement graph would have a adjacency matrix(A(G¯)) that would make the adjacecny matrix of the graph ((A(G))) would become adjacency matrix of complete graph when (A(G¯)) is added, since the complement of a graph contains edges that would make the union of those graphs to become complete grapoh. Therefore adding their adjacency matrix would result in 11T − I.
L(G) + L(G¯) = D(G) − A(G) + D(G¯) − A(G¯)
= D(G) + D(G¯) − (A(G) + A(G¯))
= D(G) + (n − 1)I − D(G) − (A(G) + A(G¯))
= (n − 1)I − (11T − I) = nI − 11T
Conclude that for 2 ≤ j ≤ n,
λj(G¯) = n − λn+2−j(G)
Lets think about the laplacian of complete graph Kn, and its eigenvalues. Since the complete graph can be divided into some graph G and its complement, the laplacian of it would equal to L(G) + L(G¯). Therefore
L(Kn)vj = (L(G) + L(G¯))vj = (nI − 11T)vj
Since the Kn is connected, the eigenvectors are just multiple of ones (α1) for the very first eigenvalue which is 0. This is also applicable to G and G¯.
(nI − 11T)vj = (L(G) + L(G¯))vj = L(G)vj + L(G¯)vj = λj(G)vj + λj(G¯)vj
∴ n = λj(G) + λj(G¯)
If we were to sort the laplacian spectrum of G¯ in increasing order, then λj(G¯) = n−λn+2−j(G), assuming that the laplacian spectrum of G is already in increasing order.
P2. Show that for any graph G,λn(G) ≥ dmax(G)
According to Courant Fischer theorum, maxxTAx = λn, where A is a symmetric matrix with n×n and ||x|| = 1.
0 = λ1 0 0 ··· 0 

0
0
…
0 λ2 0 0 λ3 ···
··· 0 
0 



λn

Also using eigenvalue decomposition, we can say that L(G) = QΛQ−1, where Λ = 



and , where λ1 ≤ λ2 ≤ ··· ≤ λn. vi are eigenvectors corresponding to those eigenvalues. However, LG is symmetric and Q is eigenvectors of LG, and therefore Q has to be a orthogonal matrix and Q−1 = QT. Now we utilize above properties to solve the problem.
L(G) = QΛQ−1 = QΛQT xTL(G)x = xTQΛQTx Let y = QTx, and simplify xTL(G)x = xTQΛQTx = yTΛy
= λ1y12 + λ2y22 + λ3y32 ··· + λnyn2 ≤ λny12 + λny22 + λny32 ··· + λnyn2 = λnyty
∴ xTL(G)x ≤ λn(∵ yTy = xTQQTx = xTx = 1)
Now, let , where only ith vertex has the maximum degree in the graph and only ith component in x is 1, so that we can extract the maximum degree out from degree matrix.
xtL(G)x = xT(D(G) − A(G))x
= xT(D(G))x − xTA(G)x
= dmax(G) − Aii(G)
= dmax(G) ≤ λn(G)(∵ Aii = 0)
P3. Simulate the agreement protocol (3.2) for a graph on five vertices. Compare the rate of convegence of protocol as the number of edges increases. Does the convergence of the protocol alw3ays improve when the graph contains more edges? Provide an analysis to support your observation.

(a) Graph with 5 edges (b) Graph with 5 edges

(c) Graph with 6 edges (d) Graph with 6 edges

(a) Graph with 7 edges (b) Graph with 7 edges

(c) Graph with 8 edges (d) Graph with 8 edges

(a) Graph with 9 edges (b) Graph with 9 edges

(c) Graph with 10 edges (d) Graph with 10 edges

Figure 4: convergence vs number of edges
As we can see from above figures, we can see that the graphs with more edges are more converging with same number of nodes. Left hand side of above figures show the x and y coordinates seperately in time domain, and the right hand side shows in the x-y plane. I created random dense gnm graph, which we can specify number of nodes and edges, with 5 nodes and used 5 to 10 edges. As we can see from the last plot, we see that the λ2 is increasing as the probability of forming edge between two nodes is increasing. Also from above plots, we see that it converges faster with more edges. Therefore it always improves with more edges.
P4.
x˙i(t) = X (xj(t) − xi(t)),i = 1,··· ,n
j∈N(i)
How would one modify the agreement protocol (3.1) so that the agents converge to an equilibrium ¯x, where x¯ = α1 + d for some given d ∈ Rn and α ∈ R?
x˙i(t) = X (xj(t) − xi(t)) − ki(xi(t) − x¯(t))
j∈N(i)
I would introduce control term k like above. This way the ˙xi(t) would become zero whenxi(t) = ¯x(t), therefore reaching the equilibrium ¯x = α1+d. Control term k can be adjusted for control objectives, but, by introducing xi(t) − x¯(t), the agents are able to converge to ¯x = α1 + d. P5. The second-order dynamics of a unit paticle i in one dimension is

where pi and vi are, respectively the position and the velocity of the particle with repect to an ineartial frame, and vi is the force and/or control term acting on the particle. Use a setup, inspired by the agreement protocol, to propose a control law −ui(t) for each vertex such that: (1) the control input for particle i relies only on the relative posistion and velocity information with respect to its neighbors; (2) the control input to each particle results in an asymptotically cohesive behavior for the particle group, that is, the position of the particle remain close to each other; and (3) the control input to each particle results in having a particle group that evolves twith the same velocity. Simulate you r proposed control law.
(1) For control input, we are only allowed to use position and velocity information.
(2) their position can be different but asymptotically at the same position, meaning as long as their positions are close to each other, they can travel at a high speed.
(3) After all, the velocity should converge to same or similar value.
Therefore I would put a bit of penalty on having different position from average of neighboring nodes, and larger penalty on having different velocity from neighboring nodes.
ui(t) = kp X (pi − pj) + kv X (vi − vj)
j∈N(i)
def get_input(x, G):
k_p = 0.5 k_v = 0.9
u = np.array(np.zeros((x.shape[0],1)))
for i in G.nodes():
for j in G.neighbors(i): j∈N(i)
u[i] += k_p *(x[i,0] – x[j,0]) + k_v *(x[i, 1] – x[j, 1])
return u

(a) position trajectory (b) velocity trajectory
Here, we see that their trajectories are not converging, not even in asymptotical manner. Proper tuning for those gains would achieve those design objectives.
P6. Write a code that implements the consensus protocol ˙x = −L(G)x, where L(G) is the Laplacian matrix of the graph, from arbitrary (random) initial conditions. Use networkX or something similar to run the consensus dynamics on a cycle, path, star, and complete graphs. Find the second smallest eigenvalues of these graphs and see if the convergence properties of consensus can be matched to these second smallest eigenvalues. Then explore the convergence as a function the number nodes in these graphs- again using networkX or something similar, choose graphs of sizes 5, 10, 20, and 50 for your computational experiments.
def get_xdot(positions, t, L_G):
num = int(len(positions)/2) positions = positions.reshape(num, 2) return (-np.matmul(L_G,positions)).reshape(num*2)
def main(): num = 50
graphs = [nx.cycle_graph(num),nx.path_graph(num), nx.star_graph(num), nx.complete_graph(num)] graph = nx.complete_graph(num)
graph, positions = random_graphs_init(graph) t = np.linspace(0,10,101)
L_G = nx.laplacian_matrix(graph).toarray()
trajectory = sp.integrate.odeint(get_xdot, np.reshape(positions, 2*len(graph)), t, args=(L_G, ))
From below graphs, we can see that positions of nodes converge to 2 different numbers because I am using x and y coordinates to show this convergence. Plot below would be more helpful for visualization. But we can see that the position is converging to the agreement. The first 4 plots show the convergence of each x and y position, and the last 4 plots show that the convergence in 2 d plane.
Also we can see from figure 2, that λ2 is growing for all the graphs when number of nodes are increased. All the plots are included in next page.

(a) cycle graph (b) path graph

(c) star graph (d) complete graph

(a) cycle graph (b) path graph

(c) star graph (d) complete graph

Figure 8: convergence vs number of nodes