Teoria ed Esercizi, Sistemi Ibridi

Chapter 3: The agreement protocol

The factorization lemma and related concepts

The factorization lemma comes from Nguyen and Mesbahi [179]. However, similar points of view have been explored in the theory of random walks; see the book by Woess [248]. For a detailed convergence analysis of the agreement problem and repeated averaging, see also Olshevsky and Tsitsiklis [187].

Graph products is the subject of the book by Imrich and Klavar [121], where the Cartesian product of graphs and the corresponding factorization results are discussed. For the extension of the protocol to the case where the state of each agent is constrained to a convex set, see [173]. We also refer the reader to the notes and references for Chapter 4 for pointers to various extensions of the agreement protocol, particularly, when the underlying graph or digraph is allowed to be time-varying.

Suggested reading

The suggested readings for this chapter are Ren and Beard [204] on the agreement protocol, and Chapter 8 of Meyer [159], which provides a lucid introduction to the theory of non-negative matrices and Markov chains.

Exercises

Exercise 3.1

Simulate the agreement protocol (3.2) for a graph on five vertices. Compare the rate of convergence of the protocol as the number of edges increases. Does the convergence of the protocol always improve when the graph contains more edges? Provide an analysis to support your observation.

Exercise 3.2

Consider the digraph and the following symmetric protocol:

ẋ(t) = 1/2 {L(D) + L(D)^T} x(t).

Does this protocol correspond to the agreement protocol on a certain graph? What are the conditions on the digraph such that the resulting symmetric protocol converges to the agreement subspace?

Exercise 3.3

The reverse of is a digraph where all directed edges of D have been reversed. A disoriented digraph is the graph obtained by replacing the directed edges of the digraph with undirected ones. Prove or disprove:

• The digraph is strongly connected if and only if its reverse is strongly connected.
• A digraph contains a rooted out-branching if and only if its reverse digraph contains one.
• If the disoriented graph of is connected, then either the digraph or its reverse contains a rooted out-branching.
• A digraph is balanced if and only if its reverse is balanced.

Exercise 3.4

The Kronecker product of two matrices, A and B, denoted by A ⊗ B, is the matrix:

[a_ij] ⊗ [b_kl] = [a_ijb_kl].

Suppose that the state of each vertex in the agreement protocol (3.1) is in ℝ^s, for some positive integer s. For example, x_i might be the position of a particle along a line, that is, s = 1. How would the compact form of the agreement protocol (3.2) be modified for the case when s ≥ 2? Hint: use Kronecker products.

Exercise 3.5

How would one modify the agreement protocol (3.1) so that the agents converge to an equilibrium where x̄ = α1 + d for some given α ∈ ℝ and d ∈ ℝⁿ?

Exercise 3.6

The second-order dynamics of a unit particle in one dimension is:

d/dt [p_i(t), v_i(t)] = [0, 1; 0, 0][p_i(t), v_i(t)] + [0, 1]u_i(t),

where p_i and v_i are, respectively, the position and the velocity of the particle with respect to an inertial frame, and u_i is the force and/or control term acting on the particle. Use a setup, inspired by the agreement protocol, to propose a control law u_i(t) for each vertex such that:

• The control input for particle i relies only on the relative position and velocity information with respect to its neighbors.
• The control input to each particle results in an asymptotically cohesive behavior for the particle group, that is, the positions of the particles remain close to each other.
• The control input to each particle results in having a particle group that evolves with the same velocity.

Simulate your proposed control law.

Exercise 3.7

How would one extend Exercise 3.6 to particles in three dimensions?

Exercise 3.8

Consider the uniformly delayed agreement dynamics over a weighted graph, specified as:

ẋ_i(t) = Σ_j∈Ni w_ij (x_j(t-τ) - x_i(t-τ)), for some τ > 0.

Show that this delayed protocol is stable if:

τ < π/(2λ_n(G)),

where λ_n(G) is the largest eigenvalue of the corresponding weighted Laplacian. Conclude that, for the delayed agreement protocol, there is a trade-off between faster convergence rate and tolerance to uniform delays on the information-exchange links.

Exercise 3.9

A matrix M is called essentially non-negative if there exists a sufficiently large μ such that M + μI is non-negative, that is, all its entries are non-negative. Show that e^tM for an essentially non-negative matrix M is non-negative when t ≥ 0.

Exercise 3.10

The averaging protocol for agents, with state x_i, i = 1, 2, ..., n, is the discrete-time update rule of the form:

x(k + 1) = Wx(k), k = 0, 1, 2, ...,

where x(k) = [x₁(k), x₂(k), ..., x_n(k)]^T and W is a stochastic matrix. Derive the necessary and sufficient conditions on the spectrum of the matrix W such that the process steers all the agents to the average value of their initial states.

Exercise 3.11

Consider vertex i in the context of the agreement protocol (3.1). Suppose that vertex i (the rebel) decides not to abide by the agreement protocol, and instead fixes its state to a constant value. Show that all vertices converge to the state of the rebel vertex when the graph is connected.

Exercise 3.12

A geometric graph on the unit square is generated by placing n points on the unit square and having (v_i, v_j) ∈ E(G) when ||x_i - x_j|| ≤ ρ, where x_i is the coordinate of vertex i and ρ is a given threshold distance for the existence of a link between a pair of vertices. Compute the Laplacian for such graphs on hundred nodes and various values of ρ. What is your estimate on how λ₂(G) grows as a function of ρ?

Exercise 3.13

Show that a balanced digraph is weakly connected if and only if it is strongly connected.

Exercise 3.14

Show that if graphs G₁ and G₂ are connected, then their Cartesian product G = G₁ × G₂ is connected.

Exercise 3.15

Prove Lemma 3.22.

Exercise 3.16

Consider a network of processors, where each processor has been given an initial computational load to process. However, before the actual processing occurs, the processors go through an initialization phase, where they exchange certain fractions of their loads with their neighbors in the network. Specifically, during this phase, processor i adopts the update protocol:

p_i(k + 1) = p_i(k) - Σ_j∈Ni w_ij(p_i(k) - p_j(k)), k = 0, 1, 2, ...,

that is, it sends a fraction w_ij of its load imbalance with its neighbors to each of them. What is the necessary and sufficient condition on the weights w_ij in (3.24) such that this initialization phase converges to a balanced load for all processors when the network is (1) a path graph, (2) a cycle graph, or (3) a star graph?

Exercise 3.17

Given two square matrices A and B, show that:

A ⊗ B = A ⊕ B = e^A ⊗ e^B,

and use this to provide an alternate (shorter) proof for Lemma 3.26.

Exercise 3.18

Let the disagreement vector be:

δ(t) = I - 1/n 1 1^T x(t).

Find the matrix M such that:

δ̇(t) = M δ(t),

under the assumption that ẋ(t) = -L(G)x(t) for some graph G.

Notation

Graph theory notation

• G: undirected graph; also referred to as graph
• D: directed graph; also referred to as digraph
• D̄: graph obtained after removing the orientation of the directed edges of D; also referred to as disoriented digraph
• G̅: complement of undirected graph G
• G°: oriented version of graph G
• V (G) or V (D): vertex set; when necessary, also denoted by V
• ∂S: boundary of vertex set S (with respect to an underlying graph)
• cl S: closure of vertex set S (with respect to an underlying graph)
• v_i: i-th vertex; also used for denoting the i-th entry of vector v
• E(G) or E(D): edge set; when necessary, also denoted by E
• e = {v_i, v_j}: edge in a graph; also denoted by (v_i, v_j)
• v_i ∼ v_j: edge {v_i, v_j} is present in the graph
• dist(i, j): the length of the shortest path between vertices v_i and v_j
• G \ e: graph G with edge e removed
• G + e: graph G with edge e added
• N_i: set of agents adjacent to i
• N(i, t): set of agents adjacent to i at time t
• d(v): degree of vertex v
• d_in(v): in-degree of vertex v in G
• d_min(G): minimum vertex degree in G
• d_max(G): maximum vertex degree in G
• δ̅_in(D): maximum (weighted) in-degree in D
• diam(G): diameter of G
• A(G): adjacency matrix of G
• A(D): in-degree adjacency matrix of D
• Δ(G): degree matrix of G
• Δ(D): in-degree matrix of D
• L(G): graph Laplacian of G
• L_e(G): edge Laplacian of G
• L_in(D): in-degree Laplacian of D
• L_o(D): out-degree Laplacian of D
• Line graph of G: graph whose vertex set is the set of edges of G
• D(D): incidence matrix of D
• C_n: cycle graph on n vertices
• P_n: path graph on n vertices
• K_n: complete graph on n vertices
• S_n: star graph on n vertices
• G(n, p): set of random graphs on n vertices, with edge probability p
• G(n, r): set of random geometric graphs on n vertices, with edge threshold distance r
• G × G: Cartesian product of two graphs G₁ and G₂

Linear algebra notation

• ℝⁿ: Euclidean space of dimension n
• ℝ⁺ⁿ: nonnegative orthant in ℝⁿ
• R^m×n: space of real m×n matrices
• Sⁿ: space of symmetric n×n matrices over reals
• Sⁿ₊: space of (symmetric) positive semidefinite matrices
• I: identity matrix; also denoted as I_n if the dimension is clear from the context
• 0_m×n: zero matrix; also denoted as 0 if the dimension is clear from the context
• M^-1, M^†: respectively, inverse and pseudo-inverse of M
• M^T, M^-T: respectively, transpose and inverse transpose of M
• N(M): null space of M
• R(M): range space of M
• [A]_ij: i-th row, j-th column of matrix A
• det(M): determinant of (square) matrix M
• rank M: rank of M
• trace M: trace of M
• e^M: matrix exponential of square matrix M
• M ⊗ M: Kronecker product of two matrices M₁ and M₂
• L_[i,j]: matrix obtained from L by removing its i-th row and j-th column
• diag(M): vector comprised of the diagonal elements of M
• Diag(v): diagonal matrix with the vector v on its diagonal
• Diag([v₁, ..., v_n]): diagonal matrix with elements v₁ to v_n
• M > 0 (M: a symmetric matrix): M is positive definite
• M ≥ 0 (M: a symmetric matrix): M is positive semidefinite
• λ_i(M): i-th eigenvalue of M; M is symmetric and its eigenvalues are ordered from least to greatest value
• v_i: i-th entry of the vector v; also used for denoting vertex i in a graph
• ρ(M): spectral radius of M, that is, the maximum eigenvalue of M in magnitude
• span{x}: span of vector x, that is, the subspace generated by scalar multiples of x
• ⟨x, y⟩: inner product between two vectors x and y
• x^*: complex conjugate transpose for complex-valued vector x
• 1_n: vector of all ones of dimension n
• 1^⊥: subspace orthogonal to span{1}
• ||x||: 2-norm of vector x unless indicated otherwise

Other notation

• dist: distance function
• j: √-1
• |z|: modulus of complex number z
• ⍺: product of s_i
• Σ: sum of s_i
• ≈: approximately equal to
• ≪: much less than
• ∈: belongs to
• {1, 2, ..., n}: set of integers from 1 to n
• ℙ(V): power set of V, that is, the set of its subsets
• arg min f: argument of the function f that minimizes it over its domain or constraint set
• arg max f: argument of the function f that maximizes it over its domain or constraint set
• R[x]: set of polynomials over the reals with indeterminants x
• O(f(n)): g(n) = O(f(n)) if g(n) is bounded from above by some constant multiple of f(n) for large enough n
• Ω(f(n)): g(n) = Ω(f(n)) if g(n) is bounded from below by some constant multiple of f(n) for large enough n

Graph theory exercises

Exercise 2.1

Show that the number of edges in any graph is half the sum of the degrees of its nodes. Conclude that the trace of L(G) is always an even number and that the number of odd degree nodes in any graph has to be even.

Exercise 2.2

The degree sequence for a graph is a listing of the degrees of its nodes; thus K₃ has the degree sequence 2, 2, 2. Is there a graph with the degree sequence 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6? How about with the degree sequence 1, 1, 3, 3, 3, 3, 5, 6, 8, 9?

Exercise 2.3

Alkanes are chemical compounds that consist of carbon (C) and hydrogen (H) atoms, where each carbon atom has four bonds and each hydrogen atom only one. The graph of the alkane is obtained by denoting each atom by a vertex and drawing an edge between a pair of vertices if there is a bond between the corresponding atoms. Show that an alkane with n carbon atoms assumes the chemical formula C_nH_2n+2, indicating that for any alkane with n carbon atoms there are 2n + 2 hydrogen atoms. Show that the graph of an alkane is a tree. Draw two realizations of C₄H₁₀.

Exercise 2.4

A graph is k-regular if the degree of every vertex is k; thus K₃ is 2-regular. What is the relationship between k in a k-regular graph and the number of nodes in the graph G other than n ≤ k ≤ n - 1?

Exercise 2.5

Let G be a graph on n vertices with c connected components. Show that rank L(G) = n - c.

Exercise 2.6

Show that any graph on n vertices with more than (n-1)(n-2)/2 edges is connected.

Exercise 2.7

The complement of a graph G, denoted by G̅, is a graph where uv ∈ E̅ if and only if uv ∉ E. Show that L(G) + L(G̅) = nI - 1 1^T. Conclude that λ_j(G) = n - λ_n+2-j(G).

Exercise 2.8

The list adjacency of a graph is an array, each row of which is initiated by a vertex in the graph and lists all vertices adjacent to it. Given the list adjacency of a graph, write an algorithm (in your favorite language) that checks whether the graph is connected.

Exercise 2.9

Recall that Cheeger’s inequality states that:

2φ(G) ≥ λ₂(G) ≥ φ(G)²/2d_max(G),

where φ(G) is the isoperimetric number of G that can be used as a robustness measure of G to edge deletions. Construct a maximally robust graph consisting of n vertices and n-1 edges. Explain how would you do this and, in particular, give the value of φ(G) for this maximally robust graph.

Exercise 2.10

The line graph of G is a graph whose vertex set is the set of edges of G and there is an edge between these vertices if the corresponding edges in G are incident on a common vertex. What is the relationship between the automorphism groups of a graph and its complement and its line graphs?

Exercise 2.11

Show that any graph on n vertices that has more than n - 1 edges contains a cycle.

Exercise 2.12

Show that the graph and its complement cannot both be disconnected.

Exercise 2.13

Show that for a graph G, Δ(G) - A(G) = D(G). Conclude that the graph Laplacian is independent of the orientation given to G for constructing D(G). Is the edge Laplacian independent of the orientation given to G?