ISSN 0005-1179, Automation and Remote Control, 2017, Vol. 78, No. 1, p. 92. c Pleiades Publishing, Ltd., 2017.
Original Russian Text c R.P. Agaev and P.Yu. Chebotarev, 2017, published in Avtomatika i Telemekhanika, 2017, No. 1, 106–120.

INTELLECTUAL CONTROL SYSTEMS

Models of latent consensus1

arXiv:1612.05201v1 [math.OC] 15 Dec 2016

R. P. Agaev and P. Yu. Chebotarev
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
Received January 16, 2016

Abstract—The paper studies the problem of achieving consensus in multi-agent systems in the case
where the dependency digraph Γ has no spanning in-tree. We consider the regularization protocol that
amounts to the addition of a dummy agent (hub) uniformly connected to the agents. The presence
of such a hub guarantees the achievement of an asymptotic consensus. For the “evaporation” of the
dummy agent, the strength of its influences on the other agents vanishes, which leads to the concept
of latent consensus. We obtain a closed-form expression for the consensus when the connections of
the hub are symmetric; in this case, the impact of the hub upon the consensus remains fixed. On
the other hand, if the hub is essentially influenced by the agents, whereas its influence on them tends
to zero, then the consensus is expressed by the scalar product of the vector of column means of the
Laplacian eigenprojection of Γ and the initial state vector of the system. Another protocol, which
assumes the presence of vanishingly weak uniform background links between the agents, leads to the
same latent consensus.
Keywords: consensus, multi-agent system, decentralized control, regularization, eigenprojection, DeGroot’s iterative pooling, PageRank, Laplacian matrix of a digraph.

1. INTRODUCTION
In networked multi-agent systems (MAS) consensus is asymptotically reached for any initial state
if and only if 0 is a simple eigenvalue of the Laplacian matrix of the weighted dependency digraph.
An equivalent condition is the presence of a spanning in-tree in this digraph [1, 2]. Suppose that these
conditions are violated. Is it still possible to associate with the system a certain “most natural” consensus
achievable under a minimal or even infinitesimal transformation of the system?
In this paper, we propose two approaches to the determination of such a consensus, which can be
referred to as a latent consensus. At the first approach, the system is supplemented by a dummy agent
called a hub with a vanishingly weak uniform influence on the agents, which guarantees the achievement of
an asymptotic consensus. At the second approach, the system is supplemented by uniform and vanishingly
weak “background” links between the existing agents. It turns out that both approaches lead to the same
latent consensus. If the additional links are not vanishingly weak, then in both cases, consensus is the
average of the initial states (opinions) with weights equal to the column means of the parametric matrix
of spanning in-forests of the dependency digraph. When the strength of the additional links tends to zero,
the weights of the agents’ states converge to the column means of the matrix of maximum in-forests. The
closed-form expressions for the latent consensus in both continuous and discrete networked multi-agent
systems involve the eigenprojection of the Laplacian matrix of the dependency digraph.
A basically different approach to solving the same problem is achieving consensus not due to a small
change in the structure of relations, but due to a minimal appropriate correction of the initial state. This
approach is realized by the method of orthogonal projection on the consensus subspace [3, 4]. Its results
are generally different from those of the methods of eigenprojection presented in this paper.
1

The work of the second author was supported by the Russian Science Foundation (project 16-11-00063 granted to IRE
RAS).
92

MODELS OF LATENT CONSENSUS

93

The concept of latent consensus requires a discussion. The consensus problem admits two interpretations. In the first one, we synthesize a coordination protocol for a technical multi-agent system, e.g.,
averaging the speeds of drones flying in a flock. In the second interpretation, we model smooth or iterative convergence of opinions of the respondents (or experts) due to their influences on each other.
In the first interpretation, there are no unreported connections between agents: just those included in
the protocol matter. In contrast, the second interpretation allows for the presence of background, latent
“public opinion” affecting agents along with their interactions specified explicitly. This “public opinion”
can be simulated in two ways: (1) by rather weak uniform pairwise connections between agents and (2)
by introducing a special “invisible” agent uniformly affecting all real agents and experiencing, in turn,
their influence. Consensus achievable in these models in the case where the explicit links do not guarantee
its existence can be called a latent consensuses, which justifies the use of this term.
Returning to the first interpretation, i.e., to a technical system, the introduction of a dummy hub can
be seen as the assumption of the existence of a “center” with weak uniform influences on the agents. An
alternative, i.e., adding weak background pairwise interactions, can hardy be recommended as a tool to
ensure consensus, as it would dramatically increase the computational complexity for systems with large
and relatively sparse matrices of influences. On the other hand, in virtue of the results of this paper,
the latter approach does not give anything new, since it leads to the same consensus as the addition of
a dummy hub.
Stabilization by the addition of weak interactions can be treated as an embodiment of the idea of low
gain feedback [5]. This approach has been used as applied to consensus problems, e.g., for system with
general linear dynamics [6, 7] and with delay [1]. As distinct from these works, which studied the means
to achieve consensus, in the present case of the simplest dynamics, asymptotic consensus is guaranteed by
the presence of a spanning in-tree in the dependency digraph, while the object of interest is the functional
relationship of the consensus with the invariants of the digraph. The latter is the subject of this paper.
The paper is organized as follows. In sections 3 and 4, we obtain expressions for the consensus
in systems with a dummy agent (“hub”) that weakly influences the existing agents and, in turn, is
experiencing their impact. In Section 5, we study protocols with weak “background” links between agents.
Section 6 contains an example used to compare the methods of regularization based on the addition of
vanishingly weak links with the method of orthogonal projection. Finally, in Section 7 we obtain closedform expressions for the consensus in weak links regularization protocols applied to DeGroot’s iterative
pooling process.
2. NOTATION AND AUXILIARY RESULTS
Consider the continuous protocol of consensus seeking in a multi-agent system [1, 8]
ẋi (t) = −

n
X

aij (xi (t) − xj (t)) ,

i = 1, . . . , n,

(1)

j=1

where xi (t) is the characteristic to be adjusted of agent i.
With the dependency matrix A = (aij )n×n of protocol (1) we associate the weighted dependency
digraph Γ with vertex set {1, . . . , n} that for every element aij > 0 of A has an arc (i, j) with weight
wij = aij . Thus, arcs in Γ are drawn in the direction of dependency: from each dependent vertex / agent
i to every vertex / agent j affecting i; the weight wij of arc (i, j) reflects the strength of this influence.
The Laplacian matrix of the weighted digraph Γ is defined [9] by
L = diag(A1) − A,

(2)

where 1 = (1, . . . , 1)T , diag(v) being the operator transforming a vector v to the diagonal matrix with v
| {z }
n

on the diagonal. The class of Laplacian matrices of weighted digraphs coincides with the class of square
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

94

AGAEV, CHEBOTAREV

matrices with nonpositive off-diagonal entries and zero row sums. In what follows, the term Laplacian
matrix will refer to an element of this class.
It is easy to verify that matrix (2) appears in the matrix representation of the model (1):
ẋ(t) = −L x(t),

(3)

where x(t) = (x1 (t), . . . , xn (t))T .
Now recall the necessary notation of matrix theory. Suppose that A ∈ Cn×n is any square matrix,
R(A) and N (A) being the range and the null space of A, respectively. Let ν = ind A be the index of A,
i.e., the smallest k ∈ {0, 1, . . .} such that rank Ak+1 = rank Ak (by definition, we assume A0 ≡ I, where
I is the identity matrix of order n).
The eigenprojection of matrix A, corresponding to the eigenvalue 0 (or simply the eigenprojection
of A) is a projection (i.e., an idempotent matrix) A⊢ such that R(A⊢ ) = N (Aν ) and N (A⊢ ) = R(Aν ).
Such a matrix A⊢ is always unique.
Proposition 1. If x(t) is a solution to the system of equations (3), then
lim x(t) = L⊢ x(0).

t→∞

Proposition 1 follows from the forest consensus theorem (Theorem 1 in [10]).
Lemma 1 ([9]). The eigenprojection L⊢ coincides with the normalized matrix J¯ = (J¯ks ) of maximum
in-forests of the dependency digraph Γ:
fks
,
J¯ks =
f

k, s = 1, . . . , n,

where f is the total weight 2 of all maximum in-forests of digraph Γ, fks being the total weight of those
of them that have k belonging to a tree with root (sink!) s.
In the subsequent proofs, we make use of the following lemma.
Lemma 2 ( [11]). L⊢ = limτ →∞ (I + τ L)−1 .
Now we introduce some additional notation3 : 0 = (0, . . . , 0)T , E = n1 11T , 1′ = [1T 1]T , I ′ and E ′ are
| {z }
n

two matrices of order n + 1: the identity matrix and matrix with entries
L0 =

!

L 0
0T 0

,

I0 =

I

0

0T 0

!

1
n+1 ,

respectively;

.

The proofs of the main results of this paper rely on the following lemma.
Lemma 3. If for matrices A and C, AC = A and C 2 = C hold, δ > 0, and the real parts of the eigenvalues of δI + A are positive, then
−1

lim e−(A+δC)t = (I − C) I + δ−1 A

t→∞
2
3

.

The weight of a digraph (e.g., of an in-forest) is the product of the weights of all its arcs.
Square brackets will denote row vectors and row representations of block matrices whose entries (blocks) are separated
with spaces rather than commas.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

MODELS OF LATENT CONSENSUS

95

The proof of Lemma 3 and the other statements are given in the Appendix.
We will also use the following result.
Lemma 4. If for Laplacian matrices A and C, AC = A and C 2 = C hold, then (A + δC)⊢ =
−1
= (I − C) I + δ−1 A
for any δ > 0.
The proof of this lemma is based on Lemma 3 and Lemma 5.

Lemma 5. For any Laplacian matrix L, it holds that L⊢ = limt→∞ e−Lt .
3. CONSENSUS PROTOCOLS WITH A SYMMETRIC HUB
Consider the following protocols of consensus seeking:
ẏ(t) = −(L0 + Hδ,v ) y(t),

(4)

where y(t) = (y1 (t), . . . , yn+1 (t))T , Hδ,v = δHI + Hv , δ > 0,
HI =

!

I

−1

0T

0

and

Hv =

!

0n×n 0
−v T s

(5)

P

are Laplacian matrices of order n + 1, v = (v1 , . . . , vn )T , and s = ni=1 vi .
Every protocol (4) is obtained from (3) by adding an (n + 1)st agent that influences the n agents of the
system with intensity δ and is subjected to their influences whose intensities are given by the vector v.
This supplementary agent (and the corresponding vertex of the dependency digraph) will be called a
hub 4 . The motivation for the introduction of a hub is to assure the presence of a spanning in-tree in the
dependency digraph (which guarantees asymptotic consensus) due to hub’s uniform weak influences on
the agents.
The eigenprojection (L0 + Hδ,v )⊢ has a simple representation which provides an expression for the
consensus by means of Proposition 1.
h

1
Lemma 6. (L0 + Hδ,v )⊢ = 1′ s+δ
v T I + 1δ L

−1

i

δ .

Theorem 1. In the
with a hub that uniformly influences the agents, the consensus is
h system (4)
−1 i
1
1
T
′
δ y(0).
limt→∞ y(t) = 1 s+δ v I + δ L
Now consider a hub whose links are symmetric: vi = δ, i = 1, . . . , n. Then v = δ1 and s = δn. Using
Lemmas 6 and 2, we obtain:
"



1
1
(L0 + Hδ, δ1 ) = 1
1T I + L
n+1
δ
⊢

′

lim (L0 + Hδ, δ1 )⊢ = 1′

δ→+0

1 h T¯ i
1 J 1 .
n+1

−1

#

1 ,

(6)
(7)

Eqs. (6) and (7) and Proposition 1 imply Proposition 2.
4

In [9], before Definition 3, we gave references to a number of publications that use this concept either explicitly or implicitly.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

96

AGAEV, CHEBOTAREV

Proposition 2. If y(t) satisfies (4) and v = δ1, then








n
1 X
lim y(t) = 1′
sδ yj (0) + yn+1 (0) ,
t→∞
n + 1 j=1 j

n
1 X
J¯·j yj (0) + yn+1 (0) ,
lim lim y(t) = 1′
δ→+0 t→∞
n + 1 j=1

P
where sδj and J¯·j = ni=1 J¯ij are the jth column sums of matrices (I + 1δ L
respectively.

−1

and L⊢ = J¯ = (J¯ij )n×n ,

By Proposition 2, the weight of the initial state yn+1 (0) of a hub with symmetric links is (n + 1)−1 ,
irrespective of δ.
Corollary 1. 1. If the system (3) has an asymptotic consensus expressed by the scalar product of the
vectors x(0) and (v1 , . . . , vn )T , then the asymptotic consensus in the system (4) with v = δ1 and δ → +0
is the scalar product of the vectors y(0) and (n + 1)−1 (nv1 , . . . , nvn , 1)T .

Pn
¯
2. If the initial state of the hub satisfies the equality yn+1 (0) = n1
i,j=1 Jij yj (0) , then this equality
also expresses the asymptotic consensus in the protocol (4) with v = δ1 and δ → +0.
3. The coincidence of the asymptotic consensuses of systems (3) and (4) in item 1 takes place if and
only if yn+1 (0) satisfies the equality in item 2.
The proof of Corollary 1 is obvious.
According to Proposition 1 and Lemma 1, the consensus in protocols (4) is the weighted average of
the initial states of the agents (including the hub), where the weight of the state of agent j is the specific
weight of spanning in-trees with sink j in the dependency digraph whose Laplacian matrix is L0 + Hδ,v .
By Theorem 1 and the matrix forest theorem [12] this weight can also be found by averaging (with weights
specified by v) the specific (1/δ)-weights5 of the forests, converging to j from all the vertices of Γ.
Let the links of the hub be symmetric, i.e., v = δ1. According to Proposition 2, for any Γ and δ → ∞,
1 Pn+1
the consensus equals n+1
j=1 yj (0), the arithmetic mean of the initial states of all agents, including the
hub. As δ → +0, to determine the weight of the initial state of agent j ≤ n, the average specific weight
n
J¯·j /n of the maximum forests converging to vertex j in Γ must be taken with the coefficient n+1
, and
−1
the initial state of the hub with weight (n + 1) . Such a consensus cannot be termed “latent”, as it
essentially depends on the initial state of the hub added to the system, which is an external parameter.
4. A HUB SUBORDINATE TO THE AGENTS
According to Proposition 2, a symmetric hub in protocols (4) outwardly affects the consensus with an
average strength: the weight of its initial state is (n + 1)−1 . The constancy of this weight, even when the
strength of hub’s links goes to zero, may seem strange. The reason is as follows. If a symmetric hub very
weakly depends on the agents, then the influence of its initial state is though weak, but rather stable.
So the resulting coefficient (n + 1)−1 of its influence can be treated as a manifestation of the principle of
“little strokes fell great oaks”.
Therefore, if our aim is to ensure consensus without arbitrary external influences, then the links of the
hub should be set in a different way. Consider the protocols (4), where
δ/s → +0 as δ → +0.
5

(8)

By “b-weight” of a weighted digraph we mean the product of its arc weights, each multiplied by b.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

MODELS OF LATENT CONSENSUS

97

Thereby, we consider the process, in which the influence δ of the hub on the agents becomes vanishingly
small not only in itself, but also compared to their influence s on the hub. This “makes the hub forget”
its initial state, so that its impact on the agents becomes a translation of their own average influence (a
kind of “public opinion”).
A counterpart of Eq. (7) for this case is the following statement.
Lemma
7. Under (8) and the existence of ṽ = limδ→+0 1s v, it holds that limδ→+0 (L0 + Hδ, v )⊢

= 1′ ṽ TJ¯ 0 .
Along with Lemma 7, Proposition 1 implies Theorem 2.

Theorem 2. Under the conditions of Lemma 7, for protocols (4) we have:


1. lim lim y(t) = 1′ ṽ TJ¯ 0 y(0);
δ→+0 t→∞

2. If v = ns 1, then lim lim y(t) = 1′
δ→+0 t→∞

1

T¯
n1 J



0 y(0) = 1′

1
n

Pn

¯

j=1 J·j yj (0),

P
where J¯·j = ni=1 J¯ij .

Consensus in item 2 of Theorem 2 can legitimately be termed latent: it takes place for a wide class
of protocols (4) with a hub subordinate (in accordance with (8)) to the agents and uniformly, but
infinitesimally affecting them. This consensus equals the weighted average of the initial states of n agents
with weights equal to the column means of J¯ = L⊢ . Herewith, due to Lemma 1 the weight of the initial
state of agent j is the average (over i) specific weight of the maximum in-forests in Γ, where j is a sink
accessible from i. It is easily seen that this weight equals the probability to access sink j from a randomly
chosen vertex in the model of motion along maximum in-forests chosen with probabilities proportional
to their weights.
5. PROTOCOLS WITH WEAK BACKGROUND LINKS BETWEEN THE AGENTS
Now we turn to a different method of regularization. Consider the protocols of consensus seeking in
which the initial dependency digraph Γ is supplemented by the complete digraph of “background links”
with uniform arc weights:
ẋ(t) = −(L + δK) x(t),

(9)

where δ > 0 and K = I − E (K is the Laplacian matrix of the complete digraph with arc weights 1/n).
First, in the same way as before, we study a more general type of regularization. Let v be a distribution
P
vector on the set of agents, i.e., vi ≥ 0 (i = 1, . . . , n) and ni=1 vi = 1. Set
ẋ(t) = −(L + δD) x(t),

(10)

where δ > 0, D = I − V, and V = 1v T . D is Laplacian; δvi is the influence of agent i on any other.
Lemma 8. In the above notation,
−1
1. (L + δD)⊢ = 1v T I + 1δ L ;
¯
2. limδ→0 (L + δD)⊢ = 1v TJ.
Proposition 1 and Lemma 8 imply Theorem 3.
Theorem 3. If x(t) is a solution to the system of equations (10), then
−1

1. limt→∞ x(t) = 1v T I + 1δ L x(0);
¯
2. limδ→+0 limt→∞ x(t) = 1v TJx(0).
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

98

AGAEV, CHEBOTAREV

Observe that with v = n1 1 we have 1v T = E and D = K, and so Corollary 2 holds true.
Corollary 2. If x(t) is the solution to the system of equations (9), then
−1
1
δ
δ
;
j=1 sj xj (0), where sj are the column sums of (I + δ L
Pn ¯
1 Pn
¯
¯
limδ→+0 limt→∞ x(t) = 1 n j=1 J·j xj (0), where J·j = i=1 Jij , j = 1, . . . , n.

1. limt→∞ x(t) = 1 n1
2.

Pn

Thus, in the protocols with additional uniform background links (9), consensus is determined by
−1
averaging the column entries of (I + 1δ L , which is the parametric matrix of in-forests [12] of digraph Γ.
Furthermore, if the arc weights of the added complete digraph tend to zero, then consensus is determined
by the column means of the matrix of maximum in-forests.
Comparing items 2 of Theorem 2 and Corollary 2 we come to the following conclusion: the latent
consensus of the protocol with uniform background links coincides with that of the protocol with hub
uniformly subordinate to the agents.
6. PROTOCOLS OF EIGENPROJECTION AND ORTHOGONAL PROJECTION
The same purpose, i.e., to develop a concept of latent consensus for the case where classical protocols
give no consensus, can be achieved in another way. This can be done by means of the method of
orthogonal projection [3, 4]. As distinct from the protocols of a dummy hub (Section 4) and background
links (Section 5), where the dependency digraph Γ is supplemented by additional links, in the method
of orthogonal projection, the link structure is preserved, while the initial state is subject to a minimum
¯
necessary correction. The resulting consensus has the form JSx(0),
where S is the projection onto
the consensus subspace of the system determined by L. This consensus generally differs from those of
protocol (9) and the other protocols (4) studied in this work.
It should be noted that if the dependency digraph contains an in-tree, then all versions of latent
¯
consensus coincide with the ordinary consensus Jx(0).
The problem of revealing the specific features of two different concepts of latent consensus requires
special consideration. In this section, we just provide an example that demonstrates a difference between
them.
Example 1. For the multi-agent system with Laplacian matrix


1 −1


−3
L=

 0

3
0



0.75 0.25



0

0

0




;
0 0.8 0.2 



 0.75 0.25

J¯ = 


0
0

0

0 0.8 0.2





0

4

0.5690 −0.1437


 −0.1437
S≈

 0.4598

0.1149



0


,
1 −1 


0

0 −4

0

we find:

0

0.9521
0.1533

0.4598

0.1149




;
0.5096 −0.1226 


0.1533

0.0383 

0.0383 −0.1226

0.9693



¯ ≈ 1· 0.3908 0.1303 0.3831 0.0958 ;
Porthog. projection = JS


Peigenprojection = E J¯ = 1· 0.375 0.125 0.4 0.1 .

The two systems of weights obtained for this example do not differ considerably, however, they differently order the weights of the first and the third agents. The second order may look more rational, since
agent 3 influences agent 4 stronger than agent 1 influences 2. On the other hand, a number of examples demonstrate that the method of orthogonal projection gives more “rewards” to more homogeneous
components.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

MODELS OF LATENT CONSENSUS

99

7. REGULARIZATION FOR DISCRETE CONSENSUS PROTOCOLS
Discrete protocols of consensus seeking can be obtained by replacing differentials with finite differences
in the continuous protocols.
7.1. Protocols with the addition of a hub
Consider DeGroot’s iterative pooling process [13]:
xk+1 = P xk ,

k = 0, 1, . . . ,

(11)

where xk ∈ Rn and P is a row-stochastic matrix. If P is not regular 6 (i.e., P has at least two eigenvalues
of modulus 1), then asymptotic consensus is not generally achieved.
As regularized extensions of P, consider the matrices
Qδ,v =

(1 − δ)P δ1
vT

0

!

,

where 0 < δ ≤ 1 and v is a distribution vector. Qδ,v is regular, since vi > 0 implies that the ith column
of Q2δ,v is positive.
Consider the protocols
y k+1 = Qδ,v y k ,

k = 0, 1, . . . ,

(12)

where y k ∈ Rn+1 . These are the counterparts of the continuous protocols (4). Let γ = δ−1 − 1.
Lemma 9. In the above notation,
 T
−1 
1
1. (I ′ − Qδ,v )⊢ = 1′ 1+δ
v I + γ(I − P )
δ ;




2. limδ→+0 (I ′ − Qδ,v )⊢ = 1′ v T (I − P )⊢ 0 .

Since L = I − P is Laplacian, Lemma 1 and the matrix forest theorem are applicable to L. The
following Theorem 4 relies on Lemma 9.
Theorem 4. If {y k } satisfies (12), then denoting J¯ = (I − P )⊢ we have:


−1

1
v T I + γ(I − P )
1. lim y k = 1′ 1+δ
k→∞





2. lim lim y k = 1′ v TJ¯ 0 y 0 ;
3.

δ→+0 k→∞
If v = n1 1,

then lim lim y k = 1′
δ→+0 k→∞

1
n



δ y0 ;

Pn

¯ 0
j=1 J·j yj ,

P
where J¯·j = ni=1 J¯ij .

In item 3 of Theorem 4, we obtain the already familiar to the reader latent consensus: if a hub is
subordinate to the agents and infinitesimally influences them, then consensus is determined by averaging
the initial agents’ states with the weights equal to the column means of J¯ = (I − P )⊢ .
7.2. Adding background links: regularization of PageRank type
Now for DeGroot’s process (11), where P is not regular, consider the protocols
xk+1 = ((1 − δ)P + δV )xk ,
6

k = 0, 1, . . . ,

A stochastic matrix is regular iff it is SIA (Stochastic, Indecomposable, Aperiodic).
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

(13)

100

AGAEV, CHEBOTAREV

where δ ∈ ]0, 1], V = 1v T , and v is a distribution. Such a regularization is used7 in the PageRank
method [14, 15] (see also [16, 17]). The asymptotic behavior of the protocols (13) is determined by
Theorem 5.
Theorem 5. If a sequence {xk } satisfies (13), then with J¯ = (I − P )⊢ it holds that:
−1

1. lim xk = 1v T I + γ(I − P )
k→∞

¯ 0;
2. lim lim xk = 1v TJx
3.

δ→+0 k→∞
If v = n1 1,

x0 , where γ = δ−1 − 1;

¯ 0 = 1 1 Pn J¯·j x0 , where J¯·j = Pn J¯ij .
then lim lim xk = E Jx
i=1
j=1
j
n
δ→+0 k→∞

Item 1 of Theorem 5 is equivalent to Eq. (7.0.1) in [15].
The main conclusion is as follows: item 3 provides the same latent consensus as the models considered
above do.
Finally, one can notice that item 3 along with Theorem 2′ in [11] (interpreting the matrix J¯ = (I −P )⊢ )
characterizes the limit of iterative regularization for an arbitrary stochastic matrix in [16].
8. CONCLUSION
In this paper, we studied two types of regularization models for the problem of coordination in multiagent systems. In the models of the first type, the system is supplemented by a dummy agent, “hub”
(a personalized common “background”), which uniformly, but very weakly influences the agents and,
in turn, depends on them. In the models of the second type, we assume the presence of very weak
background links between the initial agents. The paper presents the asymptotic properties of these
models. It is demonstrated that in their framework, the concept of latent consensus makes sense. It is
the limit consensus as the intensity of the supplemented weak links goes to zero. The latent consensus for
the models of both types (wherein both discrete and continuous) turns out to be the same. This sonsensus
can be found by averaging the initial states of the agents with the weights equal to the column means
of the eigenprojection of the Laplacian matrix L of the dependency digraph (for continuous models) or
matrix I − P, where P is the stochastic dependency matrix (for discrete models). An interpretation of
these weights is given by Lemma 1 stating the coincidence of the eigenprojection of the Laplacian matrix
of a dependency digraph and the normalized matrix of its maximum in-forests.
APPENDIX
Proof of Lemma 3. We need one more lemma.
Lemma A.1. Suppose that A and C satisfy the conditions of Lemma 3. Then for any δ ∈ R it holds
that (A + δC)m = (A + δC)(A + δI)m−1 , m = 1, 2, . . . .
Proof of Lemma A.1. For m = 1 we obtain a trivial identity. For m = 2 we have
(A + δC)2 = A2 + δA + δCA + δ2 C = A(A + δI) + δC(A + δI) = (A + δC)(A + δI),

(A.1)

i.e., the desired statement holds true. Let it be true for m = k > 1. Now we prove it for m = k + 1. Due
to the induction hypothesis and (A.1), we obtain
(A + δC)k+1 = (A + δC)(A + δC)(A + δI)k−1 = (A + δC)(A + δI)k .
7

T

T

The iterations of the PageRank method have the form of π k+1 = π k ((1 − δ)P + δV ), k = 0, 1, . . . , where π 0 is a
distribution. The result is the distribution π ∞ = limk→∞ π k (with generally unequal components) not depending on π 0 .
T
π ∞ coincides with any row of limk→∞ ((1 − δ)P + δV )k .
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

MODELS OF LATENT CONSENSUS

101

Lemma A.1 is proved.
Now we use the series representation of the matrix exponent:
e−(A+δC)t =

∞
X
(−t)k (A + δC)k

k!

k=0

=I−

t(A + δC) t2 (A + δC)2 t3 (A + δC)3
+
−
+ ...
1!
2!
3!

By Lemma A.1 we have
−(A+δC)t

e

!

t2 (A + δI) t3 (A + δI)2
tI
−
+
+ ... .
= I − (A + δC)
1!
2!
3!

(A.2)

Since by the conditions of Lemma 3 A + δI is invertible, (A.2) can be rewritten in the form
−(A+δC)t

e

!

t(A + δI) t2 (A + δI)2
−I + I −
+
− ...
1!
2!

−1

= I + (A + δC)(A + δI)

−1

= I + (A + δC)(A + δI)



−(A+δI)t

e



(A.3)

−I .

Since the real parts of the eigenvalues of A + δI are positive, limt→∞ e−(A+δI)t = 0 holds. From (A.3)
we obtain
lim e − (A + δC)t = I −(A+ δC)(A+ δI) − 1 = I −(A+ δI +δC − δI)(A+ δI) − 1

t→∞

−1

= I −I +δ(I −C)(A+ δI) − 1 = (I −C) I +δ − 1 A

.

Lemma 3 is proved.
Proof of Lemma 4. Since A is Laplacian, its spectrum lies in the right half-plane bounded by the
vertical axis [18, proposition 9], therefore, the real parts of the eigenvalues of δI + A are positive. Thereby
the condition of Lemma 3 are fulfilled, thus, so does its conclusion. Comparing it with that of Lemma 5
(whose proof is given below) and having in mind that A + δC is a Laplacian matrix, we obtain the desired
statement. Lemma 4 is proved.
Proof of Lemma 5. All the solutions of the equation ẋ(t) = −L x(t) satisfy the identity [19, Eq. (43)
of Chapter 5] x(t) = e−Lt x(0), from which in the case of existence of the limit at t → ∞, it follows
that limt→∞ x(t) = limt→∞ e−Lt x(0). Comparing the last expression with Proposition 1 and taking into
account the arbitrariness of x(0), one has L⊢ = limt→∞ e−Lt . Lemma 5 is proved.
Proof of Lemma 6. Set A := L0 + Hv , C := HI . It can be easily checked that AC = A andC 2 = C. By

Lemma 4, (L0 + Hδ,v )⊢ = (I ′ − HI )(I ′ + 1δ L0 + 1δ Hv )−1 . Since I ′ + 1δ L0 + 1δ Hv = I ′ + 1δ L0 I ′ + 1δ Hv ,
we have


1
(L0 + Hδ,v )⊢ = (I ′ − HI ) I ′ + Hv
δ

I

′ 
= 0(n+1)×n 1  1

−1 

vT
s+δ
#
"


1 −1
′ 1
T
=1
δ .
v I+ L
s+δ
δ

Lemma 6 is proved.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1



−1
1
I ′ + L0
δ



1 −1
0
0
 I + δ L

δ 
T
0
1
s+δ

2017

102

AGAEV, CHEBOTAREV

Proof of Lemma 7. From Lemmas 6 and 2 one derives:
"





#

1
1 −1
δ
lim (L0 + Hδ, v ) = lim 1
vT I + L
δ→+0
δ→+0
s+δ
δ


h
i
1 T¯ δ
1
′
v J
= lim 1
= 1′ ṽ TJ¯ 0 .
δ→+0
1 + δ/s s
s
⊢

′

Lemma 7 is proved.
Proof of Lemma 8. 1. For
A = L and C =
D, the conditions of Lemma 4 are fulfilled, therefore,
−1
−1
= 1v T I + 1δ L .
(L + δD)⊢ = (I − D) I + 1δ L
−1
¯ Lemma 8 is proved.
2. Using Lemma 2 we obtain lim (L + δD)⊢ = lim 1v T I + 1 L
= 1v TJ.
δ→0

δ

δ→0

Proof of Lemma 9. Set
P0 =

!

P 0
0T 0

, P1 =

0n×n δ1
0T 0

!

, P2 =

!

0n×n 0
vT 0

, and Iˆ = I ′ − I0 .

Then Qδ,v = (1 − δ)P0 + δP1 + P2 . Using (5), (4), and the notation L0 := (1 − δ)(I0 − P0 ) (L0 is a
Laplacian matrix!), we obtain
I ′ − Qδ,v = (1 − δ)(I0 − P0 ) + δ(I0 − P1 ) + (Iˆ − P2 )
= (1 − δ)(I0 − P0 ) + δHI + Hv = L0 + δHI + Hv = L0 + Hδ,v .
Now the desired statement is derived from Lemma 6 (with substitution L = (1 − δ)(I − P )) and Lemma 2.
Lemma 9 is proved.
Proof of Theorem 4. Since Qδ,v is a regular stochastic matrix, the limit of its powers coincides
[20, 21] with the eigenprojection of I ′ − Qδ,v . Thus, limk→∞ y k = limk→∞ Qkδ,v y 0 = (I ′ − Qδ,v )⊢ y 0 , and
the theorem follows from Lemma 9. Theorem 4 is proved.
Proof of Theorem 5. 1. Since the stochastic matrix (1 − δ)P + δV is regular, the limit of its powers
coincides [20, 21] with the eigenprojection of I − (1 − δ)P − δV = (1 − δ)(I − P ) + δ(I − V ) = L + δD,
where L := (1 − δ)(I − P ) is a Laplacian matrix and D = I − V (see (10)). Therefore, by Lemma 8 the
−1
required limit of the powers equals E I + 1δ L , which implies item 1 of Theorem 5.
2. The desired statement (along with item 3) also follows from Lemma 8 in view of the fact that
the eigenprojection is preserved under the multiplication of a matrix by a nonzero scalar. Theorem 5 is
proved.
REFERENCES
1. Olfati-Saber, R. and Murray, R.M., Consensus Problems in Networks of Agents with Switching Topology and
Time-delays, IEEE Trans. Automat. Control, 2004, vol. 49, no. 9, pp. 1520–1533.
2. Mesbahi, M. and Egerstedt, M., Graph Theoretic Methods in Multiagent Networks. Princeton: Princeton University Press, 2010.
3. Agaev, R.P. and Chebotarev, P.Yu., The Projection Method for Reaching Consensus and the Regularized
Power Limit of a Stochastic Matrix, Automat. Remote Control, 2011, vol. 72, no. 12, pp. 2458–2476.
4. Agaev, R.P. and Chebotarev, P.Yu., The Projection Method for Continuous-Time Consensus Seeking, Automat.
Remote Control, 2015, vol. 76, no. 8, pp. 1436–1445.
5. Lin, Z., Low Gain Feedback. London: Springer, 1999.
6. Seo, J.H., Shim, H. and Back, J., Consensus of High-Order Linear Systems Using Dynamic Output Feedback
Compensator: Low Gain Approach, Automatica, 2009. vol. 45, no. 11, pp. 2659–2664.
AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

MODELS OF LATENT CONSENSUS

103

7. Su, H., Chen. M.Z., Lam, J. and Lin, Z., Semi-Global Leader-Following Consensus of Linear Multi-Agent
Systems with Input Saturation via Low Gain Feedback, IEEE Trans. Circuits and Systems I: Regular Papers,
2013, vol. 60, no. 7, pp. 1881–1889.
8. Ren, W. and Cao Y. Distributed Coordination of Multi-Agent Networks: Emergent Problems, Models, and
Issues. London: Springer, 2011.
9. Chebotarev, P. and Agaev, R., Forest Matrices around the Laplacian Matrix, Linear Algebra and its Applications, 2002, vol. 356, pp. 253–274.
10. Chebotarev, P. and Agaev, R., The Forest Consensus Theorem, IEEE Trans. Automat. Control, 2014, vol. 59,
no. 9, pp. 2475–2479.
11. Agaev, R.P. and Chebotarev, P.Yu., The Matrix of Maximum Out Forests of a Digraph and its Applications,
Automat. Remote Control, 2000, vol. 61, no. 9, pp. 1424–1450.
12. Chebotarev, P.Yu. and Shamis, E.V., The Matrix-Forest Theorem and Measuring Relations in Small Social
Groups, Automat. Remote Control, 1997, vol. 58, no. 9, pp. 1505–1514.
13. DeGroot, M.H., Reaching a Consensus, J. Amer. Statistical Association, 1974, vol. 69, no. 345, pp. 118–121.
14. Brin, S. and Page, L., The Anatomy of a Large-Scale Hypertextual Web Search Engine, Computer Networks
and ISDN Systems, 1998, vol. 30, pp. 107–117.
15. Langville, A.N. and Meyer, C.D., Google’s PageRank and Beyond: The Science of Search Engine Rankings.
Princeton: Princeton Univ. Press, 2006.
16. Polyak, B.T. and Tremba, A.A., Regularization-Based Solution of the PageRank Problem for Large Matrices,
Automat. Remote Control, 2012, vol. 73, no. 11., pp. 1877–1894.
17. Ishii, H. and Tempo, R., The PageRank Problem, Multiagent Consensus, and Web Aggregation: A Systems
and Control Viewpoint, IEEE Control Syst. Magazine, 2014, vol. 34, no. 3, pp. 34–53.
18. Agaev, R.P. and Chebotarev, P.Yu., Spanning Forests of a Digraph and Their Applications, Automat. Remote
Control, 2001, vol. 62, no. 3, pp. 443–466.
19. Gantmacher, F.R., The Theory of Matrices. New York: Chelsea, 1959.
20. Meyer, C.D., Jr., The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains, SIAM
Review, 1975, vol. 17, no. 3, pp. 443–464.
21. Rothblum, U.G., Computation of the Eigenprojection of a Nonnegative Matrix at Its Spectral Radius, Stochastic Systems: Modeling, Identification and Optimization II, ser. Mathematical Programming Study, R. J.B. Wets, Ed. Amsterdam: North-Holland, 1976, vol. 6, pp. 188–201.

AUTOMATION AND REMOTE CONTROL

Vol. 78

No. 1

2017

