A.V. Proskurnikov, R. Tempo / Annual Reviews in Control 43 (2017) 65–79 67
which is neither left by the agents nor can acquire new members.
Hence the size of the group, denoted by n ≥ 2, remains unchanged.
2.2. Basic notions from graph theory
Social interactions among the agents are described by weighted
(or valued) directed graphs. We introduce only basic definitions
regarding graphs and their properties; a more detailed expo-
sition and examples of specific graphs can be found in text-
books on graph theory, networks or SNA, e.g. Harary, Norman,
and Cartwright (1965) , Tutte (1984) , Wasserman and Faust (1994) ,
Easley and Kleinberg (2010) , Jackson (2008) and Bullo (2016) . The
reader familiar with graph theory and matrix theory may skip
reading the remainder of this section.
Henceforth the term “graph” strands for a directed graph (di-
graph), formally defined as follows.
Definition 1 (Graph) . A graph is a pair G = (V, E) , where V =
{ v
1
, . . . , v
n
} and E ⊆V × V are finite sets. The elements v
i
are called
vertices or nodes of G and the elements of E are referred to as its
edges or arcs .
Connections among the nodes are conveniently encoded by the
graph’s adjacency matrix A = (a
ij
) . In graph theory, the arc ( i, j )
usually corresponds to the positive entry a
ij
> 0. In multi-agent
control ( Ren & Beard, 2008; Ren & Cao, 2011 ) and opinion forma-
tion modeling it is however convenient
1
to identify the arc ( i, j )
with the entry a
ji
> 0.
Definition 2 (Adjacency matrix) . Given a graph G = (V, E) , a non-
negative matrix A = (a
ij
)
i, j∈ V
is adapted to G or is a weighted adja-
cency matrix for G if ( i, j ) ∈ E when a
ji
> 0 and (i, j) ∈ E otherwise.
Definition 3 (Weighted graph) . A weighted graph is a triple G =
(V, E, A ) , where ( V, E ) is a graph and A is a weighted adjacency
matrix for it.
Any graph ( V, E ) can be considered as a weighted graph by as-
signing to it a binary adjacency matrix
A = (a
ij
)
i, j∈ V
, a
ij
=
1 , ( j, i ) ∈ E
0 , otherwise .
On the other hand, any nonnegative matrix A = (a
ij
)
i, j∈ V
is adapted
to the unique graph G[ A ] = (V, E[ A ] , A ) . Typically, the nodes are in
one-to-one correspondence with the agents and V = { 1 , ... , n } .
Definition 4 (Subgraph) . The graph G = (V, E) contains the graph
G
= (V
, E
) , or G
is a subgraph of G, if ∅ = V
⊆V and E
⊆( V
×
V
) ∩ E .
Simply speaking, the subgraph is obtained from the graph by
removing some arcs and some nodes.
Definition 5 (Walk) . A walk of length k connecting node i to
node i
is a sequence of nodes i
0
, . . . , i
k
∈ V, where i
0
= i, i
k
= i
and adjacent nodes are connected by arcs: (i
s −1
, i
s
) ∈ E for any
s = 1 , . . . , k . A walk from a node to itself is a cycle . A trivial cy-
cle of length 1 is called a self-loop ( v, v ) ∈ E . A walk without self-
intersections ( i
p
= i
q
for p = q ) is a path .
It can be shown that in a graph with n nodes the shortest walk
between two different nodes (if such a walk exists) has the length
≤ n − 1 and the shortest cycle from a node to itself has the length
≤ n .
1
This definition is motivated by consensus protocols and other models of opinion
dynamics, discussed in Sections 3 –6 . It allows to identify the entries of an adjacency
matrix with the influence gains, employed by the opinion formation model.
(a)
3
1
2
4
(b)
Fig. 1. Examples of graphs: (a) a directed tree with root 4; (b) a cyclic graph of
period 4.
a
b
Fig. 2. A quasi-strongly connected graph (a) and one of its directed spanning trees
(b).
Definition 6 (Connectivity) . A node connected by walks to all
other nodes in a graph is referred to as a root node. A graph is
called strongly connected or strong if a walk between any two nodes
exists (and hence each node is a root). A graph is quasi-strongly
connected or rooted if at least one root exists.
The “minimal” quasi-strongly connected graph is a directed tree
( Fig. 1 a), that is, a graph with only one root node, from where
any other node is reachable via only one walk. A directed span-
ning tree in a graph G is a directed tree, contained by the graph
G and including all of its nodes ( Fig. 2 b). It can be shown ( Ren &
Beard, 2008 ) that a graph has at least one directed spanning tree if
and only if it is quasi-strongly connected. Nodes of a graph with-
out directed spanning tree are covered by several directed trees, or
spanning forest ( Chebotarev & Agaev, 2002 ).
Definition 7 (Components) . A strong subgraph G
of the graph G
is
called a strongly connected (or strong) component , if it is not
contained by any larger strong subgraph. A strong component that
has no incoming arcs from other components is called closed .
Any node of a graph is contained in one and only one strong
component. This component may correspond with the whole
graph; this holds if and only if the graph is strong. If the graph
is not strongly connected, then it contains two or more strong
components, and at least one of them is closed . A graph is quasi-
strongly connected if and only if this closed strong component is
unique; in this case, any node of this strong component is a root
node.
Definition 7 is illustrated by Fig. 3 , showing two graphs with
the same structure of strong components. The graph in Fig. 3 a has
the single root node 4, constituting its own strong component, all
other strong components are not closed. The graph in Fig. 3 b has
two closed strong components {4} and { 5 , 6 , . . . , 10 } .
2.3. Nonnegative matrices and their graphs
In this subsection we discuss some results from matrix theory,
regarding nonnegative matrices ( Berman & Plemmons, 1979; Gant-
macher, 20 0 0; Horn & Johnson, 1985; Meyer, 20 0 0 ).
Definition 8 (Irreducibility) . A nonnegative matrix A is irreducible
if G[ A ] is strongly connected.