A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part II
Anton V. Proskurnikova,b,c,∗, Roberto Tempod
a

b

Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands
Institute of Problems of Mechanical Engineering of the Russian Academy of Sciences (IPME RAS), St. Petersburg, Russia
c
ITMO University, St. Petersburg, Russia
d
CNR-IEIIT, Politecnico di Torino, Torino, Italy

arXiv:1701.06307v2 [cs.SY] 6 Mar 2017

Abstract
In recent years, we have observed a significant trend towards filling the gap between social network analysis
and control. This trend was enabled by the introduction of new mathematical models describing dynamics of
social groups, the advancement in complex networks theory and multi-agent systems, and the development of
modern computational tools for big data analysis. The aim of this tutorial is to highlight a novel chapter of
control theory, dealing with applications to social systems, to the attention of the broad research community.
This paper is the first part of the tutorial, and it is focused on the most classical models of social dynamics
and on their relations to the recent achievements in multi-agent systems.
Keywords: Social network, opinion dynamics, multi-agent systems, distributed algorithms.
1. Introduction
The 20th century witnessed a crucial paradigm
shift in social and behavioral sciences, which can
be described as “moving from the description of social bodies to dynamic problems of changing group
life” [1]. Unlike individualistic approaches, focused on
individual choices and interests of social actors, the
emerging theories dealt with structural properties of
social groups, organizations and movements, focusing
on social relations (or ties) among their members.
A breakthrough in the analysis of social groups
was enabled by introducing a quantitative method
for describing social relations, later called sociometry [2, 3]. The pioneering work [2] introduced an
important graphical tool of sociogram, that is, “a
graph that visualizes the underlying structure of a
group and the position each individual has within
it” [2]. The works [2, 3] also broadly used the term
“network”, meaning a group of individuals that are
“bound together” by some long-term relationships.
Later, the term social network was coined, which deI
The paper is supported by Russian Science Foundation
(RSF) grant 14-29-00142 hosted by IPME RAS.
∗
Corresponding author
Email address: anton.p.1982@ieee.org (Anton V.
Proskurnikov)

Preprint submitted to Annual Reviews in Control

notes a structure, constituted by social actors (individuals or organizations) and social ties among them.
Sociometry has given birth to the interdisciplinary
science of Social Network Analysis (SNA) [4–7], extensively using mathematical methods and algorithmic tools to study structural properties of social networks and social movements [8]. SNA is closely
related to economics [9, 10], political studies [11],
medicine and health care [12]. The development of
SNA has inspired many important concepts of modern network theory [13–15] such as e.g. cliques and
communities, centrality measures, small-world network, graph’s density and clustering coefficient.
On a parallel line of research, Norbert Wiener introduced the general science of Cybernetics [16, 17]
with the objective to unify systems, control and information theory. Wiener believed that this new science should become a powerful tool in studying social
processes, arguing that “society can only be understood through a study of the messages and communication facilities which belong to it” [17]. Confirming
Wiener’s ideas, the development of social sciences in
the 20th century has given birth to a new chapter
of sociology, called “sociocybernetics” [18] and led to
the increasing comprehension that “the foundational
problem of sociology is the coordination and control
of social systems” [19]. However, the realm of social
March 8, 2017

very young, and its contours are still blurred. Without aiming to provide a complete and exhaustive survey of this novel area at its dawn, this tutorial focuses on the most “mature” dynamic models and on
the most influential mathematical results, related to
them. These models and results are mainly concerned
with opinion formation under social influence.
This paper, being the first part of the tutorial, introduces preliminary mathematical concepts and considers the four models of opinion evolution, introduced in 1950-1990s (but rigorously examined only
recently): the models by French-DeGroot, Abelson,
Friedkin-Johnsen and Taylor. We also discuss the
relations between these models and modern multiagent control, where some of them have been subsequently rediscovered. In the second part of the tutorial more advanced models of opinion evolution, the
current trends and novel challenges for systems and
control in social sciences will be considered.
The paper is organized as follows. Section 2 introduces some preliminary concepts, regarding multiagent networks, graphs and matrices. In Section 3 we
introduce the French-DeGroot model and discuss its
relation to multi-agent consensus. Section 4 introduces a continuous-time counterpart of the FrenchDeGroot model, proposed by Abelson; in this section
the Abelson diversity problem is also discussed. Sections 5 and 6 introduce, respectively, the Taylor and
Friedkin-Johnsen models, describing opinion formation in presence of stubborn and prejudiced agents.

systems has remained almost untouched by modern
control theory in spite of the tremendous progress in
control of complex large-scale systems [20–22].
The gap between the well-developed theory of SNA
and control can be explained by the lack of mathematical models, describing social dynamics, and tools
for quantitative analysis and numerical simulation of
large-scale social groups. While many natural and
engineered networks exhibit “spontaneous order” effects [23] (consensus, synchrony and other regular
collective behaviors), social communities are often
featured by highly “irregular” and sophisticated dynamics. Opinions of individuals and actions related
to them often fail to reach consensus but rather exhibit persistent disagreement, e.g. clustering or cleavage [19]. This requires to develop mathematical models that are sufficiently “rich” to capture the behavior of social actors but are also “simple” enough to
be rigorously analyzed. Although various aspects of
“social” and “group” dynamics have been studied in
the sociological literature [1, 24], mathematical methods of SNA have focused on graph-theoretic properties of social networks, paying much less attention to
dynamics over them. The relevant models have been
mostly confined to very special processes, such as e.g.
random walks, contagion and percolation [14, 15].
The recent years have witnessed an important tendency towards filling the gap between SNA and dynamical systems, giving rise to new theories of Dynamical Social Networks Analysis (DSNA) [25] and
temporal or evolutionary networks [26, 27]. Advancements in statistical physics have given rise to a new
science of sociodynamics [28, 29], which stipulates
analogies between social communities and physical
systems. Besides theoretical methods for analysis of
complex social processes, software tools for big data
analysis have been developed, which enable an investigation of Online Social Networks such as Facebook
and Twitter and dynamical processes over them [30].
Without any doubt, applications of multi-agent
and networked control to social groups will become a
key component of the emerging science on dynamic
social networks. Although the models of social processes have been suggested in abundance [19, 29, 31–
33], only a few of them have been rigorously analyzed from the system-theoretic viewpoint. Even less
attention has been paid to their experimental validation, which requires to develop rigorous identification methods. A branch of control theory, addressing problems from social and behavioral sciences, is

2. Opinions, Agents, Graphs and Matrices
In this section, we discuss several important concepts, broadly used throughout the paper.
2.1. Approaches to opinion dynamics modeling
In this tutorial, we primarily deal with models of
opinion dynamics. As discussed in [19], individuals’ opinions stand for their cognitive orientations towards some objects (e.g. particular issues, events
or other individuals), for instance, displayed attitudes [34–36] or subjective certainties of belief [37].
Mathematically, opinions are just scalar or vector
quantities associated with social actors.
Up to now, system-theoretic studies on opinion dynamics have primarily focused on models with realvalued (“continuous”) opinions, which can attain continuum of values and are treated as some quantities of
interest, e.g. subjective probabilities [38, 39]. These
2

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 (digraph), formally defined as follows.

models obey systems of ordinary differential or difference equations and can be examined by conventional
control-theoretic techniques. A discrete-valued scalar
opinion is often associated with some action or decision taken by a social actor, e.g. to support some
movement or abstain from it and to vote for or against
a bill [29, 40–45]. A multidimensional discrete-valued
opinion may be treated as a set of cultural traits [46].
Analysis of discrete-valued opinion dynamics usually
require techniques from advanced probability theory
that are mainly beyond the scope of this tutorial.
Models of social dynamics can be divided into two
major classes: macroscopic and microscopic models.
Macroscopic models of opinion dynamics are similar
in spirit to models of continuum mechanics, based on
Euler’s formalism; this approach to opinion modeling is also called Eulerian [47, 48] or statistical [40].
Macroscopic models describe how the distribution of
opinions (e.g. the vote preferences on some election
or referendum) evolves over time. The statistical approach is typically used in “sociodynamics” [28] and
evolutionary game theory [9, 49] (where the “opinions” of players stand for their strategies); some of
macroscopic models date back to 1930-40s [50, 51].
Microscopic, or agent-based, models of opinion formation describes how opinions of individual social
actors, henceforth called agents, evolve. There is
an analogy between the microscopic approach, also
called aggregative [52], and the Lagrangian formalism
in mechanics [47]. Unlike statistical models, adequate
for very large groups (mathematically, the number of
agents goes to infinity), agent-based models can describe both small-size and large-scale communities.
With the aim to provide a basic introduction to
social dynamics modeling and analysis, this tutorial
is confined to agent-based models with real-valued
scalar and vector opinions, whereas other models are
either skipped or mentioned briefly. All the models,
considered in this paper, deal with an idealistic closed
community, which is neither left by the agents nor can
acquire new members. Hence the size of the group,
denoted by n ≥ 2, remains unchanged.

Definition 1. (Graph) A graph is a pair G = (V, E),
where V = {v1 , . . . , vn } and E ⊆ V ×V are finite sets.
The elements vi 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 = (aij ). In
graph theory, the arc (i, j) usually corresponds to the
positive entry aij > 0. In multi-agent control [56, 57]
and opinion formation modeling it is however convenient1 to identify the arc (i, j) with the entry aji > 0.
Definition 2. (Adjacency matrix) Given a graph
G = (V, E), a nonnegative matrix A = (aij )i,j∈V is
adapted to G or is a weighted adjacency matrix for G
if (i, j) ∈ E when aji > 0 and (i, j) 6∈ 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 assigning to it a binary adjacency matrix
(
1, (j, i) ∈ E
A = (aij )i,j∈V , aij =
0, otherwise.
On the other hand, any nonnegative matrix A =
(aij )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 0 = (V 0 , E 0 ), or G 0 is a subgraph
of G, if ∅ =
6 V 0 ⊆ V and E 0 ⊆ (V 0 × V 0 ) ∩ 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 i0 is a sequence of nodes i0 , . . . , ik ∈ V ,
where i0 = i, ik = i0 and adjacent nodes are connected by arcs: (is−1 , is ) ∈ E for any s = 1, . . . , k. A

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 exposition and examples
of specific graphs can be found in textbooks on graph
theory, networks or SNA, e.g. [4, 9, 10, 53–55]. The

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.

3

3

1

4

2

(a)

(b)
(a)

Figure 1: Examples of graphs: (a) a directed tree with root 4;
(b) a cyclic graph of period 4

(a)

(b)

Figure 3: Strong components of a rooted graph (a) and a graph
without roots (b)

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. 3a has the single root node 4, constituting its own strong component, all other strong
components are not closed. The graph in Fig. 3b has
two closed strong components {4} and {5, 6, . . . , 10}.

(b)

Figure 2: A quasi-strongly connected graph (a) and one of its
directed spanning trees (b)

walk from a node to itself is a cycle. A trivial cycle
of length 1 is called a self-loop (v, v) ∈ E. A walk
without self-intersections (ip 6= iq for p 6= 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.
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.

2.3. Nonnegative matrices and their graphs
In this subsection we discuss some results from matrix theory, regarding nonnegative matrices [59–62].
Definition 8. (Irreducibility) A nonnegative matrix
A is irreducible if G[A] is strongly connected.

The “minimal” quasi-strongly connected graph is a
directed tree (Fig. 1a), that is, a graph with only one
root node, from where any other node is reachable via
only one walk. A directed spanning tree in a graph G
is a directed tree, contained by the graph G and including all of its nodes (Fig. 2b). It can be shown [56]
that a graph has at least one directed spanning tree
if and only if it is quasi-strongly connected. Nodes of
a graph without directed spanning tree are covered
by several directed trees, or spanning forest [58].

Theorem 1. (Perron-Frobenius) The spectral radius
ρ(A) ≥ 0 of a nonnegative matrix A is an eigenvalue
of A, for which a real nonnegative eigenvector exists
Av = ρ(A)v for some v = (v1 , . . . , vn )> 6= 0, vi ≥ 0.
If A is irreducible, then ρ(A) is a simple eigenvalue
and v is strictly positive vi > 0 ∀i.
Obviously, Theorem 1 is also applicable to the transposed matrix A> , and thus A also has a left nonnegative eigenvector w> , such that w> A = ρ(A)w> .
Besides ρ(A), a nonnegative matrix can have other
eigenvalues λ of maximal modulus |λ| = ρ(A). These
eigenvalues have the following property [62, Ch.XIII].

Definition 7. (Components) A strong subgraph G 0
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.
4

Lemma 2. If A is a nonnegative matrix and λ ∈ C
is its eigenvalue with |λ| = ρ(A), then the algebraic
and geometric multiplicities of λ coincide (that is, all
Jordan blocks corresponding to λ are trivial).

Definition 11. (Stochasticity and substochasticity)
A nonnegative matrix A (not necessarily square)
is
P
called stochastic if all its rows sum to 1 (i.e. j aij =
1 ∀i) and substochastic
P if the sum of each row is no
greater than 1 (i.e. j aij ≤ 1 ∀i).

For an irreducible matrix, the eigenvalues of maximal modulus are always simple and have the form
ρ(A)e2πmi/h , where h ≥ 1 is some integer and m =
0, 1, . . . , h − 1. This fundamental property is proved
e.g. in [60, Sections 8.4 and 8.5] and [61, Section 8.3].

The Gershgorin Disc Theorem [60, Ch. 6] implies
that ρ(A) ≤ 1 for any square substochastic matrix
A. If A is stochastic then ρ(A) = 1 since A has an
eigenvector of ones 1 = (1, . . . , 1)> : A1 = 1. A substochastic matrix A, as shown in [63], either is Schur
stable or has a stochastic submatrix A0 = (aij )i,j∈V 0 ,
where V 0 ⊆ {1, . . . , n}; an irreducible substochastic
matrix is either stochastic or Schur stable [61, 63].
∆

Theorem 3. Let an irreducible matrix A have h ≥ 1
different eigenvalues λ1 , . . . , λh on the circle {λ ∈ C :
|λ| = ρ(A)}. Then, the following statements hold:
1. each λi has the algebraic multiplicity 1;
2. {λ1 , . . . , λh } are roots of the equation λh = rh ;
3. if h = 1 then all entries of the matrix Ak are
strictly positive when k is sufficiently large;
4. if h > 1, the matrix Ak may have positive diagonal entries only when k is a multiple of h.

2.4. M-matrices and Laplacians of weighted graphs
In this subsection we introduce the class of Mmatrices 2 [59, 61] that are closely related to nonnegative matrices and have some important properties.
Definition 12. (M-matrix) A square matrix Z is an
M-matrix if it admits a decomposition Z = sI − A,
where s ≥ ρ(A) and the matrix A is nonnegative.

Definition 9. (Primitivity) An irreducible nonnegative matrix A is primitive if h = 1, i.e. λ = ρ(A) is
the only eigenvalue of maximal modulus; otherwise,
A is called imprimitive or cyclic.

For instance, if A is a substochastic matrix then
Z = I − A is an M-matrix. Another important class
of M-matrices is given by the following lemma.

It can be shown via induction on k = 1, 2, . . . that
if A is a nonnegative matrix and B = (bij ) = Ak ,
then bij > 0 if and only if in G[A] there exists a walk
of length k from j to i. In particular, the diagonal
entry (Ak )ii is positive if and only if a cycle of length
k from node i to itself exists. Hence, cyclic irreducible
matrices correspond to periodic strong graphs.

Lemma 5. Let Z = (zij ) satisfies the following
two
P
conditions: 1) zij ≤ 0 when i 6= j; 2) zii ≥ j6=i |zij |.
Then, Z is an M-matrix; precisely, A = sI − Z is
nonnegative and ρ(A) ≤ s whenever s ≥ maxi zii .
Indeed, if s ≥ maxi zii then A
P= sI −Z is nonnegative
and ρ(A) ≤ maxi (s − zii + j6=i |zij |) ≤ s thanks to
the Gershgorin Disc Theorem [60].
Noticing that the eigenvalues of Z and A are in oneto-one correspondence λ 7→ s−λ and using Theorem 1
and Lemma 2, one arrives at the following result.

Definition 10. (Periodicity) A graph is periodic if
it has at least one cycle and the length of any cycle is
divided by some integer h > 1. The maximal h with
such a property is said to be the period of the graph.
Otherwise, a graph is called aperiodic.

Corollary 6. Any M-matrix Z = sI − A has a real
eigenvalue λ0 = s − ρ(A) ≥ 0, whose algebraic and
geometric multiplicities coincide. For this eigenvalue
there exist nonnegative right and left eigenvectors v
and p: Zv = λ0 v, p> Z = λ0 p> . These vectors are
positive if the graph G[−Z] is strongly connected. For
any other eigenvalue λ one has Re λ > λ0 , and hence
Z is non-singular (det Z 6= 0) if and only if s > ρ(A).

The simplest example of a periodic graph is a cyclic
graph (Fig. 1b). Any graph with self-loops is aperiodic. Theorem 3 implies the following corollary.
Corollary 4. An irreducible matrix A is primitive
if and only if G[A] is aperiodic. Otherwise, G[A] is
periodic with period h, where h > 1 is the number of
eigenvalues of the maximal modulus ρ(A).
Many models of opinion dynamics employ stochastic and substochastic nonnegative matrices.

2

The term “M-matrix” was suggested by A. Ostrowski in
honor of Minkowski, who studied such matrices in early 1900s.

5

Non-singular M -matrices are featured by the following important property [59, 61].

goal of French, however, was not to study consensus
and learning mechanisms but rather to find a mathematical model for social power [68, 74, 75]. An individual’s social power in the group is his/her ability to
control the group’s behavior, indicating thus the centrality of the individual’s node in the social network.
French’s work has thus revealed a profound relation
between opinion formation and centrality measures.

Lemma 7. Let Z = sI − A be a non-singular M matrix, i.e. s > ρ(A). Then Z −1 is nonnegative.
An example of a singular M-matrix is the Laplacian
(or Kirchhoff ) matrix of a weighted graph [54, 64, 65].
Definition 13. (Laplacian) Given a weighted graph
G = (V, E, A), its Laplacian matrix is defined by

−aij ,
i 6= j
L[A] = (lij )i,j∈V , where lij = P a , i = j. (1)
ij


3.1. The French-DeGroot model of opinion formation
The French-DeGroot model describes a discretetime process of opinion formation in a group of n
agents, whose opinions henceforth are denoted by
x1 , . . . , xn . First we consider the case of scalar opinions xi ∈ R. The key parameter of the model
is a stochastic n × n matrix of influence weights
W = (wij ). The influence weights wij ≥ 0, where
j = 1, . . . , n may be considered as some finite resource, distributed by agent i to self and the other
agents. Given a positive influence weight wij > 0,
agent j is able to influence the opinion of agent i at
each step of the opinion iteration; the greater weight
is assigned to agent j, the stronger is its influence
on agent i. Mathematically, the vector of opinions
x(k) = (x1 (k), . . . , xn (k))> obeys the equation

j6=i

The Laplacian is an M-matrix due to Lemma 5.
Obviously, L[A] has the eigenvalue λ0 = 0 since
L[A]1n = 0, where n is the dimension of A. The zero
eigenvalue is simple if and only if the graph G[A] has
a directed spanning tree (quasi-strongly connected).
Lemma 8. For an arbitrary nonnegative square matrix A the following conditions are equivalent
1. 0 is an algebraically simple eigenvalue of L[A];
2. if L[A]v = 0, v ∈ Rn then v = c1n for some c ∈
R (e.g. 0 is a geometrically simple eigenvalue);
3. the graph G[A] is quasi-strongly connected.

x(k + 1) = W x(k),

k = 0, 1, . . . .

which is equivalent to the system of equations
n
X
xi (k + 1) =
wij xj (k), ∀i k = 0, 1, . . . .

The equivalence of statements 1 and 2 follows from
Corollary 6. The equivalence of statements 2 and 3
was in fact proved in [34] and rediscovered in recent
papers [66, 67]. A more general relation between the
kernel’s dimension dim ker L[A] = n − rank L[A] and
the graph’s structure has been established3 in [58, 65].

(2)

(3)

j=1

Hence wij is the contribution of agent j’s opinion at
each step of the opinion iteration to the opinion of
agent i at its next step. The self-influence weight
wii ≥ 0 indicates the agent’s openness to the assimilation of the others’ opinions: the agent with
wii = 0 is open-minded and completely relies on the
others’ opinions, whereas the agent with wii = 1 (and
wij = 0 ∀j 6= i) is a stubborn or zealot agent, “anchored” to its initial opinion xi (k) ≡ xi (0).
More generally, agent’s opinions may be vectors
of dimension m, conveniently represented by rows
xi = (xi1 , . . . , xim ). Stacking these rows on top of one
another, one obtains an opinion matrix X = (xil ) ∈
Rn×m . The equation (2) should be replaced by

3. The French-DeGroot Opinion Pooling
One of the first agent-based models4 of opinion
formation was proposed by the social psychologist
French in his influential paper [68], binding together
SNA and systems theory. Along with its generalization, suggested by DeGroot [38] and called “iterative
opinion pooling”, this model describes a simple procedure, enabling several rational agents to reach consensus [69–71]; it may also be considered as an algorithm of non-Bayesian learning [72, 73]. The original

X(k + 1) = W X(k),
3

k = 0, 1, . . . .

(4)

Every column xi (k) = (x1i (k), . . . , xni (k))> ∈ Rn
of X(k), obviously, evolves in accordance with (2).
Henceforth the model (4) with a general stochastic
matrix W is referred to as the French-DeGroot model.

As discussed in [55, Section 6.6], the first studies on the
Laplacian’s rank date back to 1970s and were motivated by the
dynamics of compartmental systems in mathematical biology.
4
As was mentioned in Section 2, a few statistical models of
social systems had appeared earlier, see in particular [50, 51].

6

program [79]. To obtain a simpler algorithm of reaching consensus, a heuristical algorithm was suggested
in [80], replacing the convex optimization by a very
simple procedure of weighted averaging, or opinion
pooling [81]. Developing this approach, the procedure of iterative opinion pooling (4) was suggested
in [38]. Unlike [77, 80], the DeGroot procedure was a
decentralized algorithm: each agent modifies its opinion independently based on the opinions of several
“trusted” individuals, and there may be no agent
aware of the opinions of the whole group. Unlike the
French model [68], the matrix W can be an arbitrary
stochastic matrix and the opinions are vector-valued.

3.2. History of the French-DeGroot model
A special case of the model (2) has been introduced
by French in his seminal paper [68]. This paper first
introduces a graph G, whose nodes correspond to the
agents; it is assumed that each node has a self-loop.
An arc (j, i) exists if agent j’s opinion is displayed to
agent i, or j “has power over” i. At each stage of the
opinion iteration, an agent updates its opinion to the
mean value of the opinions, displayed to it, e.g. the
weighted graph in Fig. 4 corresponds to the dynamics

 


x1 (k + 1)
1/2 1/2 0
x1 (k)
x2 (k + 1) = 1/3 1/3 1/3 x2 (k) . (5)
x3 (k + 1)
0 1/2 1/2
x3 (k)

3.3. Algebraic convergence criteria
In this subsection, we discuss convergence properties of the French-DeGroot model (2); the properties
for the multidimensional model (4) are the same.
A straightforward computation shows that the dynamics (2) is “non-expansive” in the sense that

Obviously, the French’s model is a special case of
equation (2), where the matrix W is adapted to the
graph G and has positive diagonal entries; furthermore, in each row of W all non-zero entries are equal.
Hence each agent uniformly distributes influence between itself and the other nodes connected to it.

min xi (0) ≤ · · · ≤ min xi (k) ≤ min xi (k + 1),
i

i

i

max xi (0) ≥ · · · ≥ max xi (k) ≥ max xi (k + 1)
i

i

i

for any k = 0, 1, . . .. In particular, the system (2)
is always Lyapunov stable 5 , but this stability is not
asymptotic since W always has eigenvalue at 1.
The first question, regarding the model (4), is
whether the opinions converge or oscillate. A more
specific problem is convergence to a consensus [38].

Figure 4: An example of the French model with n = 3 agents

French formulated without proofs several conditions for reaching a consensus, i.e. the convergence
xi (k) −−−→ x∗ of all opinions to a common “unanik→∞

mous opinion” [68] that were later corrected and rigorously proved by Harary [53, 76]. His primary interest was, however, to find a quantitative characteristics of the agent’s social power, that is, its ability to
influence the group’s collective opinion x∗ (the formal
definition will be given in Subsect. 3.5).
A general model (4), proposed by DeGroot [38],
takes its origin in applied statistics and has been suggested as a heuristic procedure to find “consensus of
subjective probabilities” [77]. Each of n agents (“experts”) has a vector opinion, standing for an individual (“subjective”) probability distribution of m outcomes in some random experiment; the experts’ goal
is to “form a distribution which represents, in some
sense, a consensus of individual distributions” [77].
This distribution was defined in [77] as the unique
Nash equilibrium [78] in a special non-cooperative
“Pari-Mutuel” game (betting on horse races), which
can be found by solving a special optimization problem, referred now to as the Eisenberg-Gale convex

Definition 14. (Convergence) The model (2) is convergent if for any initial condition x(0) the limit exists
x(∞) = lim x(k) = lim W k x(0).
k→∞

k→∞

(6)

A convergent model reaches a consensus if x1 (∞) =
. . . = xn (∞) for any initial opinion vector x(0).
The convergence and consensus in the model (2)
are equivalent, respectively, to regularity and full regularity 6 of the stochastic matrix W .
Definition 15. (Regularity) We call the matrix W
regular if the limit W ∞ = lim W k exists and fully
k→∞

regular if, additionally, the rows of W ∞ are identical
n
(that is, W ∞ = 1n p>
∞ for some p∞ ∈ R ).
5

This also follows from Lemma 2 since ρ(W ) = 1.
Our terminology follows [62]. The term “regular matrix”
sometimes denotes a fully regular matrix [82] or a primitive
matrix [83]. Fully regular matrices are also referred to as SIA
(stochastic indecomposable aperiodic) matrices [56, 57, 84, 85].
6

7

Lemma 2 entails the following convergence criterion.

As shown in the next subsection, Theorem 12 can
be derived from the standard results on the Markov
chains convergence [82], using the duality between
Markov chains and the French-DeGroot opinion dynamics. Theorem 12 has an important corollary, used
in the literature on multi-agent consensus.

Lemma 9. [62, Ch.XIII] The model (2) is convergent (i.e. W is regular) if and only if λ = 1 is the only
eigenvalue of W on the unit circle {λ ∈ C : |λ| = 1}.
The model (2) reaches consensus (i.e. W is fully regular) if and only if this eigenvalue is simple, i.e. the
corresponding eigenspace is spanned by the vector 1.

Corollary 13. Let the agents’ self-weights be positive wii > 0 ∀i. Then, the model (2) is convergent.
It reaches a consensus if and only if G[W ] is quasistrongly connected (i.e. has a directed spanning tree).

Using Theorem 3, Lemma 9 implies the equivalence
of convergence and consensus when W is irreducible.
Lemma 10. For an irreducible stochastic matrix W
the model (2) is convergent if and only if W is primitive, i.e. W k is a positive matrix for large k. In this
case consensus is also reached.

It should be noted that the existence of a directed
spanning tree is in general not sufficient for consensus
in the case where W has zero diagonal entries. The
second part of Corollary 13 was proved8 in [76] and
included, without proof, in [53, Chapter 4]. Numerous extensions of this result to time-varying matrices
W (k) [56, 86–89] and more general nonlinear consensus algorithms [90, 91] have recently been obtained.
Some time-varying extensions of the French-DeGroot
model, namely, bounded confidence opinion dynamics [92] and dynamics of reflected appraisal [93] will
be discussed in Part II of this tutorial.

Since an imprimitive irreducible matrix W has
7
eigenvalues {e2πki/h }h−1
k=0 , where h > 1, for almost all
initial conditions the solution of (2) oscillates.
3.4. Graph-theoretic conditions for convergence
For large-scale social networks, the criterion from
Lemma 9 cannot be easily tested. In fact, convergence of the French-DeGroot model (2) does not depend on the weights wij , but only on the graph G[W ].
In this subsection, we discuss graph-theoretic conditions for convergence and consensus. Using Corollary 4, Lemma 10 may be reformulated as follows.

3.5. The dual Markov chain and social power
Notice that the matrix W may be considered as
a matrix of transition probabilities of some Markov
chain with n states. Denoting by pi (t) the probability
of being at state i at time t, the row vector p> (t) =
(p1 (t), . . . , pn (t)) obeys the equation

Lemma 11. If the graph G = G[W ] is strong, then
the model (2) reaches a consensus if and only if G
is aperiodic. Otherwise, the model is not convergent
and opinions oscillate for almost all x(0).

p(k + 1)> = p(k)> W,

Considering the general situation, where G[W ] has
more than one strong component, one may easily notice that the evolution of the opinions in any closed
strong component is independent from the remaining
network. Two different closed components obviously
cannot reach consensus for a general initial condition.
This implies that for convergence of the opinions
it is necessary that all closed strong components are
aperiodic. For reaching a consensus the graph G[W ]
should have the only closed strong component (i.e. be
quasi-strongly connected), which is aperiodic. Both
conditions, in fact, appear to be sufficient.

(7)

The convergence of (2), that is, regularity of W implies that the probability distribution converges to
the limit p(∞)> = limk→∞ p(k)> = p(0)> W ∞ . Consensus in (2) implies that p(∞) = p∞ , where p∞ is
the vector from Definition 15, i.e. the Markov chain
“forgets” its history and convergence to the unique
stationary distribution. Such a chain is called regular or ergodic [62, 94]. The closed strong components in G[W ] correspond to essential classes of
states, whereas the remaining nodes correspond to
inessential (or non-recurrent) states [94]. The standard ergodicity condition is that the essential class is
unique and aperiodic, which is in fact equivalent to
the second part of Theorem 12. The first part of Theorem 12 states another known fact [94]: the Markov

Theorem 12. [10, 86] The model (2) is convergent
if and only if all closed strong components in G[W ]
are aperiodic. The model (2) reaches a consensus if
and only if G[W ] is quasi-strongly connected and the
only closed strong component is aperiodic.

8

7

t = 0, 1, . . .

Formally, [53, 76] address only the French model, however,
the proof uses only the diagonal entries’ positivity wii > 0 ∀i.

“Almost all” means “all except for a set of zero measure”.

8

chain always converges to a stationary distribution if
and only if all essential classes are aperiodic.
Assuming that W is fully regular, one notices that
x(k + 1) = W k x(0) −−−→ (p>
∞ x(0))1n .
k→∞

(8)

Figure 5: The graph of the French-DeGroot model with two
stubborn agents (source nodes) 1 and 3.

The element p∞i can thus be treated as a measure
of social power of agent i, i.e. the weight of its initial
opinion xi (0) in the final opinion of the group. The
greater this weight is, the more influential is the ith
individual’s opinion. A more detailed discussion of
social power and social influence mechanism is provided in [68, 75]. The social power may be considered
as a centrality measure, allowing to identify the most
“important” (influential) nodes of a social network.
This centrality measure is similar to the eigenvector
centrality [95], which is defined as the left eigenvector of the conventional binary adjacency matrix of
a graph instead of the “normalized” stochastic adjacency matrix. Usually centrality measures are introduced as functions of the graph topology [96] while
their relations to dynamical processes over graphs are
not well studied. French’s model of social power introduces a dynamic mechanism of centrality measure
and a decentralized algorithm (7) to compute it.

then the opinions reach a consensus (the source node
is the only closed strong component of the graph).
If more than one stubborn agent exist (i.e. G[W ]
has several sources), then consensus among them is,
obviously, impossible. Theorem 12 implies, however,
that typically the opinions in such a group converge.
Corollary 14. Let the group have s ≥ 1 stubborn
agents, influencing all other individuals (i.e. the set
of source nodes is connected by walks to all other
nodes of G[W ]). Then the model (2) is convergent.
Indeed, source nodes are the only closed strong components of G[W ], which are obviously aperiodic.
In Section 6 it will be shown that under the assumptions of Corollary 14 the final opinion x(∞) is
fully determined by the stubborn agents’ opinions9 .
Example 2. Consider the French-DeGroot model,
corresponding to the weighted graph in Fig. 5
 



1 0 0
x1 (k + 1)
x1 (k)
x2 (k + 1) =  1 1 1  x2 (k) .
3
3
3
x3 (k + 1)
x3 (k)
0 0 1

Example 1. Consider the French model with n =
3 agents (5), corresponding to the graph in Fig. 4.
One can expect that the “central” node 2 corresponds
to the most influential agent in the group. This is
confirmed by a straightforward computation: solving
>
>
the system of equations p>
∞ = p∞ W and p∞ 1 = 1,
2 3 2
one obtains the vector of social powers p>
∞ = ( 7 , 7 , 7 ).

It can be shown that the steady opinion vector of this
model is x(∞) = (x1 (0), x1 (0)/2 + x3 (0)/2, x3 (0))> .

3.6. Stubborn agents in the French-DeGroot model
Although consensus is a typical behavior of the
model (2), there are situations when the opinions do
not reach consensus but split into several clusters.
One of the reasons for that is the presence of stubborn agents (called also radicals [97] or zealots [98]).

4. Abelson’s Models and Diversity Puzzle
In his influential work [34] Abelson proposed a
continuous-time counterpart of the French-DeGroot
model (2). Besides this model and its nonlinear extensions, he formulated a key problem in opinion formation modeling, referred to as the community cleavage problem [19] or Abelson’s diversity puzzle [99].

Definition 16. (Stubbornness) An agent is said to
be stubborn if its opinion remains unchanged independent of the others’ opinions.
If the opinions obey the model (2) then agent i is
stubborn xi (k) ≡ xi (0) if and only if wii = 1. Such
an agent corresponds to a source node in a graph
G[W ], i.e. a node having no incoming arcs but for
the self-loop (Fig. 5). Theorem 12 implies that if
G[W ] has the only source, being also a root (Fig. 3a),

9

This fact can also be derived from the Markov chain theory.
In the dual Markov chain (7), stubborn agents correspond to
absorbing states. The condition from Corollary 14 implies that
all other states of the chain are non-recurrent, i.e. the Markov
chain is absorbing [83] and thus arrives with probability 1 at
one of the absorbing states. Thus the columns of the limit
matrix W ∞ , corresponding to non-stubborn agents, are zero.

9

4.1. Abelson’s models of opinion dynamics
To introduce Abelson’s model, we first consider
an alternative interpretation of thePFrench-DeGroot
model (2). Recalling that 1−wii = j6=i wij , one has
X
xi (k + 1) − xi (k) =
wij [xj (k) − xi (k)] ∀i. (9)
|
{z
}
{z
}
|
∆xi (k)

j6=i

4.2. Convergence and consensus conditions
Note that Corollary 6, applied to the M-matrix
L[A] and λ0 = 0, implies that all Jordan blocks, corresponding to the eigenvalue λ0 = 0, are trivial and
for any other eigenvalue λ of the Laplacian L[A] one
has Re λ > 0. Thus, the model (12) is Lyapunov
stable (yet not asymptotically stable) and, unlike the
French-DeGroot model, is always convergent.

∆(j) xi (k)

The experiments with dyadic interactions (n = 2)
show that “the attitude positions of two discussants
... move toward each other” [52]. The equation (9)
stipulates that this argument holds for simultaneous
interactions of multiple agents: adjusting its opinion
xi (k) by ∆(j) xi (k), agent i shifts it towards xj (k) as

Corollary 15. For any nonnegative matrix A the
limit P ∞ = lim e−L[A]t exists, and thus the vector of
t→∞

opinions in (12) converges x(t) −−−→ x∞ = P ∞ x(0).
t→∞

The matrix P ∞ is a projection operator onto the
Laplacian’s null space ker L[A] = {v : L[A]v = 0} and
is closely related to the graph’s structure [58, 102].
Similar to the discrete-time model (2), the system (12) reaches a consensus if the final opinions co∞
incide x∞
1 = . . . = xn for any initial condition x(0).
Obviously, consensus means that ker L[A] is spanned
n
by the vector 1n , i.e. P ∞ = 1n p>
∞ , where p ∈ R is
some vector. By noticing that x = 1n is an equilibrium point, one has P 1n = 1n and thus p>
∞ 1n = 1.
Since P commutes with L[A], it can be easily shown
that p>
∞ L[A] = 0. Recalling that L[A] has a nonnegative left eigenvector p such that p> L[A] = 0 due to
Corollary 6 and dim ker L[A] = 1, one has p∞ = cp,
where c > 0. Combining this with Lemma 8, one
obtains the following consensus criterion.

x0i = xi + ∆(j) xi =⇒ |xj − x0i | = (1 − wij )|xj − xi |.
The increment in the ith agent’s opinion ∆xi (k) is
the “resultant” of these simultaneous adjustments.
Supposing that the time elapsed between two steps
of the opinion iteration is very small, the model (9)
can be replaced by the continuous-time dynamics
X
ẋi (t) =
aij (xj (t) − xi (t)), i = 1, . . . , n.
(10)
j6=i

Here A = (aij ) is a non-negative (but not necessarily
stochastic) matrix of infinitesimal influence weights
(or “contact rates” [34, 52]). The infinitesimal shift
of the ith opinion dxi (t) = ẋi (t)dt is the superposition
of the infinitesimal’s shifts aij (xj (t)−xi (t))dt of agent
i’s towards the influencers. A more general nonlinear
mechanism of opinion evolution [34, 35, 52] is
X
ẋi (t) =
aij g(xi , xj )(xj (t) − xi (t)) ∀i.
(11)

Theorem 16. The linear Abelson model (12)
reaches consensus if and only if G[A] is quasistrongly connected (i.e. has a directed spanning tree).
In this case, the opinions converge to the limit

j6=i

lim x1 (t) = . . . = lim xn (t) = p>
∞ x(0),

t→∞

Here g : R×R → (0; 1] is a coupling function, describing the complex mechanism of opinion assimilation10 .
In this section, we mainly deal with the linear Abelson model (10), whose equivalent matrix form is
ẋ(t) = −L[A]x(t),

t→∞

where p∞ ∈ Rn is the nonnegative vector, uniquely
>
defined by the equations p>
∞ L[A] = 0 and p∞ 1n = 1.
Similar to the French-DeGroot model, the vector p∞
may be treated as a vector of the agents’ social powers, or a centrality measure on the nodes of G[A].
It is remarkable that a crucial part of Theorem 16
was proved by Abelson [34], who called quasi-strongly
connected graphs “compact”. Abelson proved that
the null space ker L[A] consists of the vectors c1n if
and only if the graph is “compact”, i.e. statements 2
and 3 in Lemma 8 are equivalent. He concluded that
“compactness” is necessary and sufficient for consensus; the proof, however, was given only for diagonalizable Laplacian matrices. In general, the sufficiency

(12)

where L[A] is the Laplacian matrix (1). Recently the
dynamics (12) has been rediscovered in multi-agent
control theory [56, 100, 101] as a continuous-time consensus algorithm. We discuss the convergence properties of this model in the next subsection.
10

The reasons to consider nonlinear couplings between the
individuals opinions (attitudes) and possible types of such couplings are discussed in [35]. Many dynamic models, introduced
in [35], are still waiting for a rigorous mathematical analysis.

10

clustering [114]) are to be identified. This requires to
find mathematical models of opinion formation that
are able to capture the complex behavior of real social
groups, yet simple enough to be rigorously examined.
As discussed in Subsect. 3.6, one of the reasons for
opinion clustering is the presence of stubborn agents,
whose opinions are invariant. In the models (10) and
(11), agent i is stubborn if and only if aij = 0 ∀j, corresponding thus to a source node of the graph G[A].
In the next sections we consider more general models
with “partially” stubborn, or prejudiced, agents.

part requires to prove that the zero eigenvalue of L[A]
is algebraically simple (statement 1 in Lemma 8). The
full proof of Theorem 16 was given only in [66]; the
case of strong graph was earlier considered in [100].
As already discussed, the model (12) arises as a
“limit” of the French-DeGroot model as the time between consecutive opinion updates becomes negligibly small. The inverse operation of discretization
transforms (12) into the French-DeGroot model.
Lemma 17. [56, 66] For any nonnegative matrix A
and τ > 0 the matrix Wτ = e−τ L[A] is stochastic, and
thus P ∞ = lim Wτ from Corollary 15 is stochastic.
τ →∞
The matrices Wτ have positive diagonal entries.

5. Cleavage and Prejudices: Taylor’s model
In this section, we consider an extension of the linear Abelson model (10), proposed in [115]. Whereas
the French-DeGroot and Abelson models have triggered extensive studies on multi-agent consensus,
Taylor’s model in fact has anticipated the recent studies on containment control algorithms [57, 116–118].
The model from [115], as usual, involves n agents
with opinions x1 , . . . , xn ∈ R and m ≥ 1 communication sources (such as e.g. mass media), providing
static opinions s1 , . . . , sm ∈ R. The agents’ opinions
are influenced by these sources, obeying the model

Lemma 17 implies that the vectors x̃(k) = x(τ k)
satisfy a special French-DeGroot model with W =
Wτ and allows to derive Theorem 16 from Corollary 13; this lemma can also be used for analysis of
time-varying extensions of Abelson’s model [56].
Many results, regarding consensus algorithms over
time-varying graphs, have been obtained in [56,
100, 101, 103–108] and extended to general dynamic
agents [56, 57, 109–111]. More advanced results on
nonlinear consensus algorithms [105, 112, 113] allow
to examine the nonlinear Abelson model (11) under
different assumptions on the coupling function g(·).
The statement of Abelson [34, 52] that the model (11)
reaches consensus for any function g(a, b) ∈ (0; 1]
when G[A] is “compact” (quasi-strongly connected)
is, obviously, incorrect unless additional assumptions
are adopted11 ; however, it holds for continuous function g(a, b), as implied by the results of [112, 113].

ẋi (t) =

n
X
j=1

aij (xj (t)−xi (t))+

m
X

bik (sk −xi (t)). (13)

k=1

Besides the nonnegative matrix of influence weights
A = (aij ), the Taylor model (13) involves the nonsquare n × m nonnegative matrix B = (bik ) of “persuasibility constants” [115], which describe the influence of the communication sources on the agents.
Some agents can be free of the external influence
bP
i1 = . . . = bim = 0, whereas the agents with
m
k=1 bik > 0 are influenced by one or several sources.
Taylor has shown that the presence of external influence typically causes the cleavage of opinions; moreover, unlike the Abelson model, the system (13) is
usually asymptotically stable and converges to the
unique equilibrium, determined by s1 , . . . , sk .
Besides the linear model (13), Taylor [115] considered nonlinear opinion dynamics, which extend (11)
and some other models from [34] and are still waiting for a rigorous mathematical examination. These
systems are however beyond the scope of this tutorial.

4.3. The community cleavage problem
Admitting that in general the outcome of consensus is “too strong to be realistic” [52], Abelson formulated a fundamental problem, called the community cleavage problem [19] or Abelson’s diversity puzzle [99]. The informal formulation, stated in [34],
was: “Since universal ultimate agreement is an ubiquitous outcome of a very broad class of mathematical
models, we are naturally led to inquire what on earth
one must assume in order to generate the bimodal
outcome of community cleavage studies.” In other
words, the reasons for social cleavage, that is, persistent disagreement among the agents’ opinions (e.g.

5.1. Equivalent representations of the Taylor model
Note that formally the model (13) may be considered as the Abelson model with n + k agents, where

11

Moreover, if the mapping g(·) is discontinuous, the system (11) may have no solution in the classical sense.

11

To examine the stability properties of (15), we split
the agents into two classes. Agent i is said to be
P-dependent (prejudice-dependent) if is either prejudiced or influenced by some prejudiced agent j (that
is, a walk from j to i exists in the graph G[A]). Otherwise, we call the agent P-independent. Renumbering
the agents, we assume that agents 1, . . . , r ≥ 1 are Pdependent and agents r + 1, . . . , n are P-independent
(possibly, r = n). Denote the corresponding parts of
the opinion vector by, respectively, x1 (t) and x2 (t).
Since P-dependent agents are not connected to Pindependent ones, Eq. (15) is decomposed as follows

the “virtual” agents n + 1, . . . , n + k are stubborn:
xn+i = si for i = 1, . . . , k. Corollary 15 implies
that the model (13) is convergent: for any x(0) and
s1 , . . . , sk there exist the limit x(∞) = lim x(t). The
t→∞

converse is also true: for the Abelson model with
k ≥ 1 stubborn agents, their static opinions may be
considered as “communication sources” for the others. However, some properties of the system (e.g. stability) are easier to formulate for Taylor’s system (13)
than for the augmented Abelson’s model.
Another transformation allows to reduce (13) to a
formally less general model, where each agent may
have its own “communication source” or prejudice
ẋi (t) =

n
X

ẋ1 (t) = −(L11 + Γ11 )x1 (t) − L12 x2 (t) + Γ11 u1 (16)
ẋ2 (t) = −L22 x2 (t).

aij (xj (t) − xi (t)) + γi (ui − xi (t)) (14)

j=1

The matrix L22 is Laplacian of size (n − r) × (n − r),
i.e. (17) is the Abelson model. The matrix L11 is, in
general, not Laplacian; one has L11 1r ≥ 0.

where γi ≥ 0. Obviously, (13) reduces to (14), choosP
∆ P
∆
ing γi = km=1 bim ≥ 0 and ui = γi−1 km=1 bim sm (if
γi = 0, we set ui = 0 without loss of generality).

Theorem 18. Let the community have r ≥ 1 Pdependent agents and n − r ≥ 0 P-independent ones.
Then the dynamics of P-dependent agents (16) is
asymptotically stable, i.e. the matrix −(L11 + Γ11 )
is Hurwitz. The vector of their opinions converges to
 1 


u
∆
1
, M = (L11 +Γ11 )−1 Γ11 L12 .
x (∞) = M 2
x (∞)
(18)
The matrix M is stochastic, and thus the final opinion
of any agent is a convex combination of the prejudices
and the final opinions of P-independent agents13 .

Definition 17. (Prejudiced agents) Given a group of
n agents, governed by the model (14), we call agent i
prejudiced if γi > 0; the external inputs ui are referred
to as the prejudices of corresponding agents12 .
The prejudice may be considered as some “internal” agent’s opinion, formed by some external factors (as in the Taylor model (13)) or the individual’s
personal experience. An agent that is not prejudiced
obeys the usual Abelson mechanism (10). A prejudiced agent may be totally closed to the interpersonal influence aij = 0 ∀j; in this case its opinion
converges to its prejudice xi (t) −−−→ ui and γi regu-

Theorem 18 easily follows from the properties of Mmatrices. Using Lemma 5, L11 + Γ11 is proved to be
M-matrix. It suffices to show that the corresponding
eigenvalue λ0 from Corollary 6 is positive. Suppose
on the contrary that λ0 = 0 and let p stand for the
nonnegative left eigenvector p> (L11 + Γ11 ) = 0. Multiplying by 1r and noticing that L11 1r ≥ 0, one has
p> Γ11 1r = 0, that is, p> Γ11 = 0 and pi = 0 whenever γi > 0, i.e. pi = 0 for all prejudiced agents i.
Since p> L11 = 0,Pfor any j such that pj = 0 one has
P
i6=j pi aij = pj
j6=i aji = 0, i.e. pi = 0 whenever
aij > 0. In other words, if node j is connected to node
i and pj = 0 then also pi = 0. This implies that p = 0
which contradicts to the choice of p. This contradiction shows that λ0 > 0 and hence the system (16) is

t→∞

lates the convergence rate. In the special case where
ui = xi (0) such an agent is stubborn since xi (t) ≡ ui .
The concept of a prejudiced agent is however much
more general and allows the agent to be influenced
by both its prejudice and the others’ opinions.
5.2. Stability of the Taylor model
In this subsection, we examine asymptotic stability of the Taylor model. Obviously, it suffices to
examine only the system (14), to which the original model (13) reduces. Introducing the matrix
Γ = diag(γ1 , . . . , γn ), the model (14) is rewritten as
ẋ(t) = −(L[A] + Γ)x(t) + Γu.

(17)

(15)

12

Note that the model (14) has been studied in [114] as a
protocol for multi-agent clustering; prejudiced agents in [114]
are called informed, whereas other agents are said to be naive.

13

Recall that computation of x2 (∞) reduces to the analysis
of the Abelson model (17), discussed in Section 4.

12

stable, entailing (18). Since (−L12 ) is nonnegative,
Lemma 7 implies that the matrix M is also nonnegative. Choosing u = 1n , it is obvious that (14) has an
equilibrium x = 1n , which implies that M 1n = 1r ,
i.e. M is stochastic, which ends the proof.

The equivalence 1 ⇐⇒ 2 is established by Theorem 18. Obviously, 3 =⇒ 1: choosing s1 = . . . =
sk = 0, one has S = {0} and (19) is the asymptotic
stability condition. It remains to prove the implication 1 =⇒ 3. In the scalar case d = 1 it is immediate from Theorem 18. In general, let v ∈ Rd and
x̃i (t) = v > xi (t), s̃m = v > sm . Then, obviously x̃i , s̃m
obey the scalar model (13) and thus v > xi (∞) =
x̃i (∞) ≥ minm s̃m = minm v > sm = mins∈S v > s.
Since v is arbitrary, one has xi (∞) ∈ S for any i.
In the recent literature on containment control [57,
116, 117, 119, 120] Theorem 20 has been extended
in various directions: the leaders may be dynamic
(and thus their convex hull is time-varying S = S(t)),
the interaction graph may also be time-varying and
the agents may have non-trivial dynamics. Furthermore, the polyhedron S can be replaced by an arbitrary closed convex set; the relevant problem is sometimes referred to as the target aggregation [121] and
is closely related to distributed optimization [122].

Corollary 19. The system (14) is asymptotically
stable, i.e. the matrix −(L[A] + Γ) is Hurwitz if and
only if all agents are P-dependent.
In terms of the original model (13), Corollary 19
can be reformulated as follows: the system (13) is
asymptotically stable if and only if any agent is in14
fluenced by at least one “communication
Pk source” .
This influence can be direct (if γi = m=1 bim > 0)
or indirect (through a chain of the other agents).
5.3. The Taylor model and containment control
A multidimensional extension of the Taylor
model (13) arises in the containment control problems [57, 116–118]. The agents stand for mobile
robots or vehicles, and the “opinion” xi ∈ Rd is the
position of agent i. The “communication sources”
s1 , . . . , sk ∈ Rd are the positions of k static leaders.
The mobile agents’ goal is to reach the convex hull
(
∆

S=

k
X

αm sm : αm ≥ 0,

m=1

k
X

6. Friedkin-Johnsen Model
It is a remarkable fact that no discrete-time counterpart of the Taylor model had been suggested till
1990s, when Friedkin and Johnsen [123–125] introduced a discrete-time modification of the dynamics (14). Unlike many models of opinion formation,
proposed in the literature, this model has been experimentally validated for small and medium-size groups,
as reported in [19, 93, 125–127].
Similar to DeGroot’s dynamics (2), the FriedkinJohnsen model employs a stochastic matrix of social influences W , corresponding to the influence
graph G[W ]. Besides this matrix, a diagonal matrix
Λ = diag(λ1 , . . . , λn ) is introduced, where λi ∈ [0, 1]
stands for the susceptibility of agent i to the process
of social influence. The vector of the agents’ opinions
evolves in accordance with

)
αm = 1

⊂ Rd

m=1

spanned by the leaders s1 , . . . , sk . Agent i is directly
influenced by the leader m (i.e. bim > 0) if it can measure its position (in general, none of the agents can
observe the whole set S). Similar to the scalar case,
such agents can be called “prejudiced”. The other
agents can be either “P-dependent” (indirectly influenced by one or several leaders) or “P-independent”.
Theorem 20. The three conditions are equivalent
1. the system (13) is Hurwitz stable;
2. any agent is influenced directly or indirectly by
one of the leaders (P-dependent);
3. the mobile agents reach the target convex hull
xi (∞) ∈ S

∀i = 1, . . . , n

x(k + 1) = ΛW x(k) + (I − Λ)u.

Here u is a constant vector of the agents’ prejudices.
The susceptibilities’ complements 1−λi play the same
role as the coefficients γi in (14); in the case Λ = 0 the
model (20) turns into the French-DeGroot model (2).
If 1 − λi = 0 then agent i is independent of the prejudice vector u and applies the usual French-DeGroot
“opinion pooling” rule. When λi < 1, agent i is “anchored” to its prejudice ui and factors its into any

(19)

for any positions of the leaders s1 , . . . , sk ∈ Rd
and the initial conditions x1 (0), . . . , xn (0) ∈ Rd .
14

(20)

This statement was formulated in [115] (Theorem 1).

13

system (20) is decomposed as follows

opinion iteration. If λi = 0 then the ith agent’s opinion stabilizes at the first step xi (k) ≡ ui ∀k ≥ 1; such
an agent is stubborn xi (k) ≡ xi (0) when ui = xi (0).
In the Friedkin-Johnsen theory [19, 125, 127] it is
supposed traditionally that u = x(0), i.e. the prejudices of the agents are their initial opinions. This is
explained by the assumption [125] that the individuals prejudices have been formed by some exogenous
conditions, which influenced the group in the past;
in this sense the vectors of prejudices u and initial
opinions x(0) store the information about the group’s
history. The assumption u = x(0) in turn motivates
to adopt the “coupling condition” 1 − λi = wii , stating that the levels of agents’ “anchorage” to the initial opinions are determined by their self-confidence
weights. At the same time, similar to Taylor’s model,
the prejudice may be independent of the initial opinion x(0) and caused by media or some other “communication sources”. For this reason, we do not adopt
these coupling conditions in this tutorial, allowing the
prejudices and initial opinions to be independent; the
same holds for the matrices Λ and W .

x1 (k + 1) = Λ11 [W 11 x1 (k) + W 12 x2 (k)] + (I − Λ11 )u1
(21)
x2 (k + 1) = W 22 x2 (k).

(22)

Notice that W 22 is a stochastic matrix, i.e. the Pindependent agents obey the French-DeGroot model.
Theorem 21. Let the community have r ≥ 1 Pdependent agents and n − r ≥ 0 P-independent ones.
Then, the subsystem (21) is asymptotically stable,
i.e. Λ11 W 11 is Schur stable ρ(Λ11 W 11 ) < 1. The
model (20) is convergent if and only if r = n or (22)
is convergent, i.e. W 22 is regular. In this case
 1 
u
1
x (∞) = V 2
,
x (∞)
(23)


∆
11
11 −1
11
11
12
Ir − Λ
Λ W
V = (Ir − Λ W )
.
The matrix V is stochastic15 , i.e. the final opinion of
any agent is a convex combination of the prejudices
and final opinions of P-independent agents16 .
Below we give the sketch of the proof of Theorem 21, retracing the proof of Theorem 18. An equivalent proof in [63] relies on some properties on substochastic matrices17 . Suppose on the contrary that
ρ(Λ11 W 11 ) = 1 and let p ∈ Rr stand for the nonnegative left eigenvector, corresponding to this eigenvalue p> Λ11 W 11 = p> and such that p> 1r = 1.
Since W 11 is substochastic, one has p> Λ11 1r ≥ 1
and thus pi = 0 when λi < 1 (i.e. agent i is prejudiced). Recalling
that p is a left eigenvector, one
Pr
has pj λj =
i=1 pi λi wij for any j = 1, . . . , r and
thus if pj = 0 and wij > 0 (i.e. j is connected to i)
then pi λi = 0, which implies that pi = 0 (as we have
already shown, λi = 0 entails that pi = 0). Thus
p = 0, which is a contradiction and thus Λ11 W 11 is
Schur stable. The second statement and the validity
of (23) if (22) converges are now obvious. To prove
that V is stochastic, note first that V 1n = 1r . Indeed, (Ir − Λ11 )1r + Λ11 W 12 1n−r = (Ir − Λ11 )1r +

6.1. Convergence and stability conditions
Similar to the Taylor model, a generic FriedkinJohnsen model is asymptotically stable, i.e. the substochastic matrix ΛW is Schur stable ρ(ΛW ) < 1.
This holds e.g. when Λ < I or Λ 6= I and ΛW
is irreducible (since an irreducible substochastic matrix is either stochastic or Schur stable [61]). In this
subsection, we give a necessary and sufficient stability condition, similar to Theorem 18 and established
in [63]. Henceforth we assume that Λ 6= In since otherwise (20) reduces to the French-DeGroot model (2).
Following Section 5, we call agent i prejudiced if
λi < 1, i.e. the prejudice ui influences its opinion at
each step k. Agent i is P-dependent if it is prejudiced
or influenced by some prejudiced agent j, that is, a
walk from j to i in the graph G[W ] exists. Otherwise, the agent is P-independent. Renumbering the
agents, one may assume that agents 1, . . . , r are Pdependent (where r ≥ 1), whereas agents r + 1, . . . , n
are P-independent (it is possible that r = n, i.e.
all agents are P-dependent). We denote the corresponding parts of the opinion vector by, respectively,
x1 (t) ∈ Rr and x2 (t) ∈ Rn−r . Since P-independent
agents are, by definition, not prejudiced (λi = 1), the

15

Sometimes V is referred to as the control matrix [19].
Recall that computation of x2 (∞) reduces to the analysis
of the French-DeGroot model (22), discussed in Section 3.
17
Note that [63] uses a different terminology: prejudiced
agents are called “stubborn”, stubborn agents in our sense
are called “totally stubborn”, P-independent agents are called
“oblivious”, for P-dependent agents no special term is used.
16

14

Λ11 (1r − W 11 1r ) = (Ir − Λ11 W 11 )1r . On the other
hand, (Ir − Λ11 W 11 ) is an M-matrix, and thus V is
nonnegative thanks to Lemma 7.

1
0.8
0.6
0.4
0.2

Corollary 22. The Friedkin-Johnsen model (20) is
asymptotically stable if and only if all agents are Pdependent. Then, V = (I − ΛW )−1 (I − Λ). This
holds, in particular, if Λ < In or Λ 6= In and G[W ] is
strongly connected (W is irreducible).

0
-0.2
-0.4
agent
agent
agent
agent

-0.6
-0.8

1
2
3
4

-1
0

2

4

6

8

10

(a) Λ = I

Corollary 22 may be transformed into a criterion
of Schur stability for substochastic matrices since the
matrix A is substochastic if and only if A = ΛW with
diagonal Λ (where 0 ≤ Λ ≤ I) and stochastic W . The
sufficiency part in Corollary 22 was proved in [128].

1
0.8
0.6
0.4
0.2
0
-0.2

Corollary 23. The model (20) converges if and only
if A = ΛW is regular, i.e. the limit lim Ak exists.

-0.4
agent
agent
agent
agent

-0.6
-0.8

k→∞

1
2
3
4

-1
0

To prove Corollary 23 it remains to notice that A is
regular if and only if its submatrix W 22 from (22) is
regular. This result is formulated in [19, 125] without
rigorous proof. The property from Corollary 23 is
non-trivial since in general the system

2

4

6

8

10

(b) Λ = I − diag(W )
1
0.8
0.6
0.4
0.2

x(k + 1) = Ax(k) + Bu

0
-0.2

with a regular matrix A and some matrix B is not
convergent and may have unbounded solutions, as
demonstrated by the counterexample A = B = I.

-0.4
agent
agent
agent
agent

-0.6
-0.8

1
2
3
4

-1
0

2

4

6

8

10

(c) Λ = diag(1, 0, 0, 1)

Example 3. This example illustrates the behavior
of opinions in the Friedkin-Johnsen model (20) with
n = 4 agents and the matrix of influence weights [125]


0.220 0.120 0.360 0.300
0.147 0.215 0.344 0.294
.
W =
(24)
 0
0
1
0 
0.090 0.178 0.446 0.286

Figure 6: Opinion dynamics for W from (24) and different Λ.

6.2. Friedkin’s influence centrality and PageRank
A natural question arises whether the concept of social power, introduced for the French-DeGroot model,
can be extended to the model (20). In this subsection,
we discuss such an extension, introduced by Friedkin [19, 129] and based on the equality (23). We
confine ourselves to the case of asymptotically stable
model (20) with the prejudice vector u = x(0), hence
x(∞) = V x(0), where V = (I − ΛW )−1 (I − Λ).
Recall that the definition of French’s social power
assumed that the agents converge to the same consensus opinion x1 (∞) = . . . = xn (∞); the social
power of agent i is defined as the weight of its initial opinion xi (0) in this final opinion of the group.
The Friedkin-Johnsen model provides a generalization of social power of agent i as the mean weight
of its initial opinion in determining group members’

We put u = x(0) = [−1, −0.2, 0.6, 1]> and consider
the evolution of opinions for three different matrices Λ (Fig. 6): Λ = I, Λ = I − diag(W ) and
Λ = diag(1, 0, 0, 1). In all cases agent 3 is stubborn.
In the first case the model (20) reduces to the FrenchDeGroot model, and the opinions reach consensus
(Fig. 6a). In the second case (Fig. 6b) agents 1, 2, 4
move their opinions towards the stubborn agent 3’s
opinion, however, the visible cleavage of their opinions is observed. In the third case (Fig. 6c) agents 2
and 3 are stubborn, and the remaining agents 1 and
4 converge to different yet very close opinions, lying
between the opinions of the stubborn agents.
15

final opinions [19]. Mathematically, these mean influence weights are elements of the non-negative vector
∆
c = n−1 V > 1n , which satisfies the following equality

the probability to open webpage i on step k by pi (k),
the row vector p(k)> = (p1 (k), . . . , pn (k)) obeys the
“dual” French-DeGroot model (7). As discussed in
Section 6, if the French social power vector p∞ is
well-defined, then the probability distribution p(k)
>
converges to p∞ . Since p>
∞ = p W , the vector p∞
satisfies the natural principle of webpage ranking: a
webpage referred by highly ranked webpages should
also get a high rank. However, the web graphs are often disconnected, so W may be not fully regular, i.e.
the French’s social power may not exist. To avoid
this problem, the Markov process of random surfing
is modified, allowing the teleportation [131] from each
node to a randomly chosen webpage. With probability m ∈ (0, 1), at each step the surfer “gets tired” and
opens a random webpage, sampled from the uniform
distribution20 . The Markov chain (7) is replaced by

n

x̄ =

1X
1
xi (∞) = 1>
V x(0) = c> x(0).
n
n n

(25)

i=1

Following [19, 129], we call ci the influence centrality
of agent i. Since V is stochastic, c> 1n = 1. Similar
to French’s social power, the influence centrality is
generated by an opinion formation mechanism18 .
Choosing a stochastic matrix W , adapted to a
given graph G with n nodes, and some diagonal matrix Λ, Friedkin’s construction gives a very insightful
and broad class of centrality measures. For a fixed
W , let Λ = αIn with α ∈ (0, 1) and consider the
corresponding matrix Vα and vector cα . Obviously,
c0 = n−1 1n , i.e. the social power is uniformly distributed between all agents. As α → 1, the vector cα
converges to French’s social power (when it exists).

p(k + 1)> = (1 − m)p(k)> W +

α→1−0

Indeed, as follows from [63, Eq. (12)] Vα = (1 −
α)(I − αW )−1 −−−−→ W ∞ , where W ∞ = lim W k =
α→1−

(26)

which is dual to the Friedkin-Johnsen model (20)
with Λ = (1 − m)In . It can be easily shown that
m >
−1
p(k)> → c>
1−m = n 1n (1−(1−m)W ) . Being a special case of Friedkin’s influence centrality, this limit
probability is referred to as PageRank [131, 133] (the
Google algorithm [130] used the value m = 0.15). Another extension of the PageRank centrality, based on
the general model (20), has been proposed in [138].

Lemma 24. Let W be a fully regular matrix and p∞
stand for the vector of French’s social power, corresponding to the model (2). Then, p∞ = lim cα .

1n p> . Thus cα = n−1 Vα> 1n −−−−→ p∞ .

m >
1 ,
n n

k→∞

α→1−

6.3. Alternative interpretations and extensions
Obviously, the French-DeGroot model (2) can be
considered as a degenerate case of (20) with Λ = In .
The French-DeGroot model with stubborn agents,
examined in Subsect. 3.6, may be transformed to
the more insightful model (20), where λi = 0 and
ui = xi (0) when agent i is stubborn (wii = 1) and
λi = 1, ui = 0 otherwise. Under the assumption of
Corollary 14, the system (20) is asymptotically stable21 and the final opinion vector x(∞) = V u is determined by the stubborn agents’ opinions. On the other
hand, (20) may be considered as an “augmented”
French-DeGroot model with “virtual” n stubborn
agents, anchored at xn+i ≡ ui (here i = 1, . . . , n).

The class of Friedkin’s centrality measures fα contains the well-known PageRank [130–136], proposed
originally for ranking webpages in Web search engines and used in scientometrics for journal ranking [133]. The relation between the influence centrality and PageRank, revealed in [137], follows from the
construction of PageRank via “random surfing” [131].
Consider a segment of World Wide Web (WWW)
with n webpages and a stochastic n × n hyperlink
matrix W = (wij ), where wij > 0 if and only if
a hyperlink leads from the ith webpage to the jth
one19 . Reaching webpage i, the surfer randomly follows one of the hyperlinks on it; the probability to
choose the hyperlink leading to webpage j is wij (the
webpage may refer to itself wii > 0). Such a process of random surfing is a Markov process; denoting

20
Note however that the procedure of journal ranking, which
is beyond this tutorial, uses a non-uniform distribution [133].
21
It may seem paradoxical that the equivalent transformation
of the neutrally stable French-DeGroot model into (20) yields
in an asymptotically stable system. The explanation is that
changing the initial condition x(0) in (20), the prejudice vector
u remains constant. In the original system (2) the prejudice is
a part of the state vector, destroying the asymptotic stability.

18
Notice that analogous influence centrality can be introduced for Taylor’s model (14) with the prejudice u = x(0).
19
Usually, W is obtained from the adjacency matrix of some
known web graph via normalization and removing the “dangling” nodes without outgoing hyperlinks [131, 133].

16

Concluding Remarks and Acknowledgements

The model (20) has an elegant game-theoretic interpretation [139, 140]. Suppose that each
P agent is associated to a cost function Ji (x) = λi nj=1 wij (xj −
xi )2 + (1 − λi )(xi − ui )2 : the first term penalizes the
disagreement from the others’ opinions, whereas the
other term “anchors” the agent to its prejudice. The
update rule (20) implies that each agent i updates its
opinion in a way to minimize Ji (x), assuming that
xj (k), j 6= k, are constant. If the system is convergent, the vector x(∞) stands for the Nash equilibrium [139] in the game, which however P
does not
optimize the overall cost functional J(x) = i Ji (x).
J(x(∞))
Some estimates for the ratio min
(considered as
x J(x)
the “price of anarchy”) are given in [139]. In some
special cases the model (20) can also be interpreted
in terms of electric circuits [134, 140].
The model (20) with scalar opinions can be extended to d-dimensional opinions; similarly to the DeGroot model (4), these opinions can be wrapped into
a n × d matrix X(k), whose ith row xi (k) represents
the opinion of agent i; the multidimensional prejudices are represented by the matrix U . The process
of opinion formation is thus governed by the model
X(k + 1) = ΛW X(k) + (I − Λ)U.

In the first part of the tutorial, we have discussed
several dynamic models, in continuous and discretetime, for opinion formation and evolution. A rigorous analysis of the convergence and stability properties of these models is provided, the relations with
recent results on multi-agent systems are discussed.
Due to the page limit, we do not discuss some important “scalability” issues, regarding the applicability of the models to large-scale social networks.
Among such issues are the algorithmic analysis of
convergence conditions [144], the models’ convergence
rates [140, 145–148] and experimental validation on
big data [149]. An important open problem is to find
the relation between the behavior of opinions in the
models from Sections 3-6 and the structure of communities or modules in the network’s graph [150].
In the second part of the tutorial, we are going
to discuss advanced more advanced models of opinion formation, based on the ideas of bounded confidence [92, 151, 152], antagonistic interactions [153–
155] and asynchronous gossip-based interactions [134,
156]. Future perspectives of systems and control in
social and behavioral sciences will also be discussed.
The authors are indebted to Prof. Noah Friedkin,
Prof. Francesco Bullo, Dr. Paolo Frasca and the
anonymous reviewers for their invaluable comments.

(27)

Similar to the multidimensional Taylor model in Subsect. 5.3, the model (27) may be considered as a
discrete-time containment control algorithm [141].
An important extension of the model (27), proposed
in [63, 142] considers the case where an individual vector-valued opinion represents his/her positions
on several interdependent topics (such opinions can
stand e.g. for belief systems, obeying some logical
constraints [142, 143]). The mutual dependencies between the topics can be described by introducing additional “internal” couplings, described by a stochastic d × d matrix C. The model (27) is replaced by
X(k + 1) = ΛW X(k)C > + (I − Λ)U.

References
[1] K. Lewin, Frontiers in group dynamics: Concept, method
and reality in social science; social equilibria and social
change, Human Relations 1 (5) (1947) 5–41.
[2] J. Moreno, Who Shall Survive? A New Approach to the
Problem of Human Interrelations, Nervous and Mental
Disease Publishing Co., Washington, D.C., 1934.
[3] J. Moreno, Sociometry, Experimental Method, and the
Science of Society, Beacon House, Ambler, PA, 1951.
[4] S. Wasserman, K. Faust, Social Network Analysis: Methods and Applications, Cambridge Univ. Press, Cambridge, 1994.
[5] J. Scott, Social Network Analysis, SAGE Publications,
2000.
[6] L. Freeman, The Development of Social Network Analysis. A Study in the Sociology of Science, Empirical Press,
Vancouver, BC Canada, 2004.
[7] J. Scott, P. Carrington (Eds.), The SAGE Handbook on
Social Network Analysis, SAGE Publications, 2011.
[8] M. Diani, D. McAdam (Eds.), Social Movements and
Networks, Oxford Univ. Press, Oxford, 2003.
[9] D. Easley, J. Kleinberg, Networks, Crowds and Markets.
Reasoning about a Highly Connected World, Cambridge
Univ. Press, Cambridge, 2010.

(28)

As shown in [63], the stability conditions for (28) remain the same as for the original model (20). In [142]
(see also Supplement to this paper) an extension
of (28) has been also examined, where agents’ have
heterogeneous sets of logical constraints, corresponding to n different coupling matrices C1 , . . . , Cn .
Finally, gossip-based versions of the models (20)
and (28) with asynchronous communication have
been proposed in [63, 128, 134, 135]; these models
will be considered in Part II of this tutorial.
17

11 (2007) 279–300.
[32] D. Acemoglu, M. Dahleh, I. Lobel, A. Ozdaglar, Bayesian
learning in social networks, Rev. Econom. Studies 78 (4)
(2011) 1201–1236.
[33] H. Xia, H. Wang, Z. Xuan, Opinion dynamics: A multidisciplinary review and perspective on future research,
Int. J. Knowledge Systems Sci. 2 (4) (2011) 72–91.
[34] R. Abelson, Mathematical models of the distribution of
attitudes under controversy, in: N. Frederiksen, H. Gulliksen (Eds.), Contributions to Mathematical Psychology, Holt, Rinehart & Winston, Inc, New York, 1964,
pp. 142–160.
[35] J. Hunter, J. Danes, S. Cohen, Mathematical Models of
Attitude Change, vol.1, Acad. Press, Inc., 1984.
[36] S. Kaplowitz, E. Fink, Dynamics of attitude change, in:
R. Levine, H. Fitzgerald (Eds.), Analysis of Dynamic
Psychological Systems. Vol. 2: Methods and Applications, Plenum Press, New York and London, 1992.
[37] J. Y. Halpern, The relationship between knowledge, belief, and certainty, Annals of Mathematics and Artificial
Intelligence 4 (3) (1991) 301–322.
[38] M. DeGroot, Reaching a consensus, Journal of the American Statistical Association 69 (1974) 118–121.
[39] L. Li, A. Scaglione, A. Swami, Q. Zhao, Consensus, polarization and clustering of opinions in social networks,
IEEE J. on Selected Areas in Communications 31 (6)
(2013) 1072–1083.
[40] W. Weidlich, The statistical description of polarization
phenomena in society, Br. J. Math. Stat. Psychol. 24
(1971) 251–266.
[41] P. Clifford, A. Sudbury, A model for spatial conflict,
Biometrika 60 (3) (1973) 581–588.
[42] M. Granovetter, Threshold models of collective behavior,
Amer. J. Sociology 83 (6) (1978) 1420–1443.
[43] R. Holley, T. Liggett, Ergodic theorems for weakly interacting infinite systems and the voter model, The Annals
of Probability 3 (4) (1975) 643–663.
[44] K. Sznajd-Weron, J. Sznajd, Opinion evolution in closed
community, Int. J. Mod. Phys. C 11 (06) (2000) 1157–
1165.
[45] E. Yildiz, A. Ozdaglar, D. Acemoglu, A. Saberi,
A. Scaglione, Binary opinion dynamics with stubborn
agents, ACM Transactions on Economics and Computation 1 (4) (2013) article No. 19.
[46] R. Axelrod, The dissemination of culture: A model with
local convergence and global polarization, J. Conflict
Resolut. 41 (1997) 203–226.
[47] C. Canuto, F. Fagnani, P. Tilli, An Eulerian approach
to the analysis of Krause’s consensus models, SIAM J.
Control Optim. 50 (2012) 243–265.
[48] A. Mirtabatabaei, P. Jia, F. Bullo, Eulerian opinion dynamics with bounded confidence and exogenous inputs,
SIAM J. Appl. Dynam. Syst. 13 (1) (2014) 425–446.
[49] J. Maynard Smith, Evolution and the Theory of Games,
Cambridge Univ. Press, 1982.
[50] N. Rashevsky, Studies in mathematical theory of human
relations, Psychometrika 4 (3) (1939) 221–239.
[51] N. Rashevsky, Mathematical Theory of Human Relations, Principia Press, Bloomington, 1947.
[52] R. Abelson, Mathematical models in social psychology,
in: L. Berkowitz (Ed.), Advances in Experimental Social
Psychology, v. 3, Acad. Press, New York, 1967, pp. 1–49.

[10] M. Jackson (Ed.), Social and Economic Networks,
Princeton Univ. Press, Princeton and Oxford, 2008.
[11] D. Knoke, Political Networks. The Structural Perspective, Cambridge Univ. Press, 1993.
[12] A. O’Malley, P. Marsden, The analysis of social networks,
Health Serv. Outcomes Res. Method. 8 (4) (2008) 222–
269.
[13] S. Strogatz, Exploring complex networks, Nature 410
(2001) 268–276.
[14] M. Newman, The structure and function of complex networks, SIAM Rev. 45 (2) (2003) 167–256.
[15] M. Newman, A. Barabasi, D. Watts, The Structure and
Dynamics of Networks, Princeton Univ. Press, 2006.
[16] N. Wiener, Cybernetics, or Control and Communications
in the Animal and the Machine, Wiley & Sons, New York,
1948.
[17] N. Wiener, The Human Use of Human Beings: Cybernetics and Society, Houghton Mifflin, New Haven, 1954.
[18] F. Geyer, The challenge of sociocybernetics, Kybernetes
24 (4) (1995) 6–32.
[19] N. Friedkin, The problem of social control and coordination of complex systems in sociology: A look at the
community cleavage problem, IEEE Control Syst. Mag.
35 (3) (2015) 40–51.
[20] R. Murray (Ed.), Control in an Information Rich World:
Report of the Panel on Future Directions in Control, Dynamics and Systems, SIAM, Philadelphia, PA, 2003.
[21] T. Samad, A. Annaswamy (Eds.), The Impact of Control Technology. Overview, Success Stories, and Research
Challenges, IEEE Control Systems Society, 2011.
[22] A. Annaswamy, T. Chai, S. Engell, S. Hara, A. Isaksson, P. Khargonekar, F. Lamnabhi-Lagarrigue, R. Murray, H. Nijmeijer, T. Samad, D. Tilbury, P. V. den Hof,
Systems & control for the future of humanity. Research
agenda: current and future roles, impact and grand challenges, to be published in Annual Reviews in Control.
[23] S. Strogatz, Sync: The Emerging Science of Spontaneous
Order, Hyperion Press, New York, 2003.
[24] P. Sorokin, Society, Culture, and Personality: Their
Structure and Dynamics, a System of General Sociology,
Harper & Brothers Publ., New York & London, 1947.
[25] R. Breiger, K. Carley, P. Pattison (Eds.), Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, National Acad. Press, Washington,
DC, 2003.
[26] P. Holme, J. Saramäki (Eds.), Temporal Networks,
Springer-Verlag, Berlin Heidelberg, 2013.
[27] C. Aggarwal, K. Subbian, Evolutionary network analysis:
A survey, ACM Comput. Surveys 47 (1) (2014) 1–36.
[28] W. Weidlich, Thirty years of sociodynamics. An integrated strategy of modelling in the social sciences: applications to migration and urban evolution, Chaos, Solitons and Fractals 24 (2005) 45–56.
[29] C. Castellano, S. Fortunato, V. Loreto, Statistical physics
of social dynamics, Rev. Mod. Phys. 81 (2009) 591–646.
[30] V. Arnaboldi, A. Passarella, M. Conti, R. Dunbar, Online Social Networks. Human Cognitive Constraints in
Facebook and Twitter Personal Graphs, Elsevier, New
York, NY, 2015.
[31] W. Mason, F. Conrey, E. Smith, Situating social influence processes: Dynamic, multidirectional flows of influence within social networks, Personal. Soc. Psychol. Rev.

18

pp. 168–182.
[77] E. Eisenberg, D. Gale, Consensus of subjective probabilities: the Pari-Mutuel method, The Annals of Math.
Stat. 30 (1959) 165–168.
[78] J. Nash, Non-cooperative games, The Annals of Mathematics 54 (2) (1951) 286–295.
[79] K. Jain, V. Vazirani, Eisenberg–Gale markets: Algorithms and game-theoretic properties, Games and Economic Behavior 70 (1) (2010) 84–106.
[80] R. Winkler, The consensus of subjective probability distributions, Management Science 15 (2) (1968) B61–B75.
[81] M. Stone, The opinion pool, The Annals of Math. Stat.
32 (1961) 1339–1342.
[82] E. Seneta, Non-Negative Matrices and Markov Chains,
2nd ed., Springer-Verlag, New York, 1981.
[83] F. Kemeny, J. Snell, Finite Markov Chains, Springer Verlag, New York, Berlin, Heidelberg, Tokyo, 1976.
[84] J. Wolfowitz, Products of indecomposable, aperiodic,
stochastic matrices, Proceedings of Amer. Math. Soc. 15
(1963) 733–737.
[85] A. Jadbabaie, J. Lin, A. Morse, Coordination of groups of
mobile autonomous agents using nearest neighbor rules,
IEEE Trans. Autom. Control 48 (6) (2003) 988–1001.
[86] P. DeMarzo, D. Vayanos, J. Zwiebel, Persuasion bias,
social influence, and unidimensional opinions, Quaterly
J. Econom. 118 (3) (2003) 909–968.
[87] J. Tsitsiklis, D. Bertsekas, M. Athans, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Autom. Control 31 (9)
(1986) 803–812.
[88] V. Blondel, J. Hendrickx, A. Olshevsky, J. Tsitsiklis,
Convergence in multiagent coordination, consensus, and
flocking, in: Proc. IEEE Conf. Decision and Control,
2005, pp. 2996 – 3000.
[89] M. Cao, A. Morse, B. Anderson, Reaching a consensus
in a dynamically changing environment: a graphical approach, SIAM J. Control Optim. 47 (2) (2008) 575–600.
[90] L. Moreau, Stability of multiagent systems with timedependent communication links, IEEE Trans. Autom.
Control 50 (2) (2005) 169–182.
[91] D. Angeli, P. Bliman, Stability of leaderless discrete-time
multi-agent systems, Math. Control, Signals, Syst. 18 (4)
(2006) 293–322.
[92] R. Hegselmann, U. Krause, Opinion dynamics and
bounded confidence models, analysis, and simulation, J.
Artifical Societies Social Simul. (JASSS) 5 (3) (2002) 2.
[93] N. Friedkin, P. Jia, F. Bullo, A theory of the evolution of
social power: natural trajectories of interpersonal influence systems along issue sequences, Soc. Science 3 (2016)
444–472.
[94] J. Seneta, Markov chains, Cambridge Univ. Press, 1998.
[95] P. Bonacich, P. Lloyd, Eigenvector-like measures of centrality for asymmetric relations, Social Networks 23
(2001) 191–201.
[96] M. Newman, The structure and function of complex networks, SIAM Rev. 45 (2) (2003) 167–256.
[97] R. Hegselmann, U. Krause, Opinion dynamics under the
influence of radical groups, charismatic leaders and other
constant signals: a simple unifying model, Networks and
Heterogeneous Media 10 (3) (2015) 477–509.
[98] N. Masuda, Opinion control in complex networks, New
J. Phys. 17 (3) (2015) 033031.

[53] F. Harary, R. Norman, D. Cartwright, Structural Models.
An Introduction to the Theory of Directed Graphs, Wiley
& Sons, 1965.
[54] W. T. Tutte, Graph Theory, Addison-Wesley, 1984.
[55] F. Bullo, Lectures on Network Systems, published online at http://motion.me.ucsb.edu/book-lns, 2016, with
contributions by J. Cortes, F. Dorfler, and S. Martinez.
[56] W. Ren, R. Beard, Distributed Consensus in MultiVehicle Cooperative Control: Theory and Applications,
Springer-Verlag, London, 2008.
[57] W. Ren, Y. Cao, Distributed Coordination of Multiagent Networks, Springer, 2011.
[58] P. Chebotarev, R. Agaev, Forest matrices around the
Laplacian matrix, Linear Algebra Appl. 356 (2002) 253–
274.
[59] A. Berman, R. Plemmons, Nonnegative matrices in the
mathematical sciences, Acad. Press, New York, 1979.
[60] R. Horn, C. Johnson, Matrix Analysis, Cambridge Univ.
Press, 1985.
[61] C. Meyer, Matrix Analysis and Applied Linear Algebra,
SIAM, 2000.
[62] F. Gantmacher, The Theory of Matrices, Vol. 2, AMS
Chelsea Publishing, 2000.
[63] S. Parsegov, A. Proskurnikov, R. Tempo, N. Friedkin,
Novel multidimensional models of opinion dynamics in
social networks, IEEE Trans. Autom. Control 62 (5)
(2017) (published online).
[64] C. Godsil, G. Royle, Algebraic Graph Theory, SpringerVerlag New York, Inc., 2001.
[65] R. Agaev, P. Chebotarev, On the spectra of nonsymmetric Laplacian matrices, Linear Algebra Appl. 399 (2005)
157–168.
[66] W. Ren, R. Beard, Consensus seeking in multiagent systems under dynamically changing interaction topologies,
IEEE Trans. Autom. Control 50 (5) (2005) 655–661.
[67] Z. Lin, B. Francis, M. Maggiore, Necessary and sufficient
graphical conditions for formation control of unicycles,
IEEE Trans. Autom. Control 50 (1) (2005) 121–127.
[68] J. French Jr., A formal theory of social power, Physchol.
Rev. 63 (1956) 181–194.
[69] K. Lehrer, When rational disagreement is impossible,
Noûs 10 (3) (1976) 327–332.
[70] C. Wagner, Consensus through respect: A model of rational group decision-making, Philosophical Studies: An
International Journal for Philosophy in the Analytic Tradition 34 (4) (1978) 335–349.
[71] K. Lehrer, C. Wagner, Rational Consensus in Science and
Society, D. Reidel Publ., 1981.
[72] B. Golub, M. O. Jackson, Naive learning in social networks and the wisdom of crowds, American Economic
Journal: Microeconomics 2 (1) (2010) 112–149.
[73] A. Jadbabaie, P. Molavi, A. Sandroni, A. Tahbaz-Salehi,
Non-Bayesian social learning, Games and Economic Behavior 76 (2012) 210–225.
[74] J. French, B. Raven, The bases of social power, in:
D. Cartwright (Ed.), Studies in Social Power, Univ. of
Michigan Press, Ann Arbor, MI, 1959, pp. 251–260.
[75] N. Friedkin, A formal theory of social power, J. of Math.
Sociology 12 (2) (1986) 103–126.
[76] F. Harary, A criterion for unanimity in French’s theory
of social power, in: D. Cartwright (Ed.), Studies in Social
Power, Univ. of Michigan Press, Ann Arbor, MI, 1959,

19

[99] T. Kurahashi-Nakamura, M. Mäs, J. Lorenz, Robust
clustering in generalized bounded confidence models, J.
Artificial Societies and Social Simulation 19 (4) (2016) 7.
[100] R. Olfati-Saber, R. Murray, Consensus problems in networks of agents with switching topology and time-delays,
IEEE Trans. Autom. Control 49 (9) (2004) 1520–1533.
[101] M. Mesbahi, M. Egerstedt, Graph Theoretic Methods
in Multiagent Networks, Princeton University Press,
Princeton and Oxford, 2010.
[102] P. Chebotarev, R. Agaev, The forest consensus theorem,
IEEE Trans. Autom. Control 59 (9) (2014) 2475–2479.
[103] L. Moreau, Stability of continuous-time distributed consensus algorithms, in: Proc. IEEE Conf. Decision and
Control (CDC 2004), 2004, pp. 3998 – 4003.
[104] J. Hendrickx, J. Tsitsiklis, Convergence of typesymmetric and cut-balanced consensus seeking systems,
IEEE Trans. Autom. Control 58 (1) (2013) 214–218.
[105] A. Matveev, I. Novinitsyn, A. Proskurnikov, Stability of
continuous-time consensus algorithms for switching networks with bidirectional interaction, in: Proc. Europ.
Control Conference (ECC), 2013, pp. 1872–1877.
[106] S. Martin, A. Girard, Continuous-time consensus under
persisten connectivity and slow divergence of reciprocal interaction weights, SIAM J. Control. Optim. 51 (3)
(2013) 2568–2584.
[107] S. Martin, J. Hendrickx, Continuous-time consensus under non-instantaneous reciprocity, IEEE Trans. Autom.
Control 61 (9) (2016) 2484–2495.
[108] A. Proskurnikov, A. Matveev, M. Cao, Opinion dynamics in social networks with hostile camps: Consensus vs.
polarization, IEEE Trans. Autom. Control 61 (6) (2016)
1524–1536.
[109] F. Lewis, H. Zhang, K. Hengster-Movris, A. Das, Cooperative Control of Multi-Agent Systems. Optimal and
Adaptive Design Approaches, Springer-Verlag, London,
2014.
[110] A. Proskurnikov, M. Cao, Consensus in multi-agent systems, in: J. Webster (Ed.), Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley & Sons, 2016.
[111] Z. Li, Z. Duan, G. Chen, L. Huang, Consensus of multiagent systems and synchronization of complex networks:
A unified viewpoint, IEEE Trans. on Circuits and Systems - I 57 (1) (2010) 213–224.
[112] Z. Lin, B. Francis, M. Maggiore, State agreement for
continuous-time coupled nonlinear systems, SIAM J.
Control Optim. 46 (1) (2007) 288–307.
[113] U. Münz, A. Papachristodoulou, F. Allgöwer, Consensus
in multi-agent systems with coupling delays and switching topology, IEEE Trans. Autom. Control 56 (12) (2011)
2976–2982.
[114] W. Xia, M. Cao, Clustering in diffusively coupled networks, Automatica 47 (11) (2011) 2395–2405.
[115] M. Taylor, Towards a mathematical theory of influence
and attitude change, Human Relations 21 (2) (1968) 121–
139.
[116] M. Ji, G. Ferrari-Trecate, M. Egerstedt, A. Buffa, Containment control in mobile networks, IEEE Trans. Autom. Control 53 (8) (2008) 1972–1975.
[117] H. Liu, G. Xie, L. Wang, Necessary and sufficient conditions for containment control of networked multi-agent
systems, Automatica 48 (7) (2012) 1415–1422.
[118] Y. Cao, Consensus of multi-agent systems with state con-

[119]

[120]

[121]

[122]

[123]
[124]
[125]

[126]
[127]
[128]

[129]
[130]

[131]

[132]

[133]

[134]

[135]

[136]

[137]
[138]

20

straints: A unified view of opinion dynamics and containment control, in: Proc. of Amer. Control Conf. (ACC),
2015, pp. 1439–1444.
Y. Cao, W. Ren, M. Egerstedt, Distributed containment
control with multiple stationary or dynamic leaders in
fixed and switching directed networks, Automatica 48 (8)
(2012) 1586–1597.
G. Shi, Y. Hong, K. Johansson, Connectivity and set
tracking of multi-agent systems guided by multiple moving leaders, IEEE Trans. Autom. Control 57 (2012) 663–
676.
G. Shi, Y. Hong, Global target aggregation and state
agreement of nonlinear multi-agent systems with switching topologies, Automatica 45 (5) (2009) 1165–1175.
G. Shi, K. Johansson, Y. Hong, Reaching an optimal consensus: Dynamical systems that compute intersections
of convex sets, IEEE Trans. on Autom. Control 58 (3)
(2013) 610–622.
N. Friedkin, E. Johnsen, Social influence and opinions, J.
Math. Sociol. 15 (3-4) (1990) 193–205.
N. Friedkin, A Structural Theory of Social Influence,
Cambridge Univ. Press, New York, 1998.
N. Friedkin, E. Johnsen, Social influence networks and
opinion change, in: S. Thye, E. Lawler, M. Macy,
H. Walker (Eds.), Advances in Group Processes, Vol. 16,
1999, pp. 1–29.
C. Childress, N. Friedkin, Cultural reception and production, Amer. Soc. Rev. 77 (2012) 45–68.
N. Friedkin, E. Johnsen, Social Influence Network Theory, Cambridge Univ. Press, New York, 2011.
P. Frasca, C. Ravazzi, R. Tempo, H. Ishii, Gossips
and prejudices: Ergodic randomized dynamics in social
networks, in: Proc. of IFAC NecSys 2013 Workshop,
Koblenz, Germany, 2013, pp. 212–219.
N. Friedkin, Theoretical foundations for centrality measures, Amer. J. Sociology 96 (6) (1991) 1478–1504.
S. Brin, L. Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN
Systems archive 30 (1998) 107–117.
P. Boldi, M. Santini, S. Vigna, PageRank: Functional
dependencies, ACM Trans. Inform. Syst. 27 (4) (2009)
1–23.
H. Ishii, R. Tempo, Distributed randomized algorithms
for the PageRank computation, IEEE Trans. Autom.
Control 55 (9) (2010) 1987–2002.
H. Ishii, R. Tempo, The PageRank problem, multi-agent
consensus and Web aggregation: A systems and control
viewpoint, IEEE Control Syst. Mag. 34 (3) (2014) 34–53.
P. Frasca, H. Ishii, C. Ravazzi, R. Tempo, Distributed
randomized algorithms for opinion formation, centrality
computation and power systems estimation: A tutorial
overview, Europ. J. Control 24 (7) (2015) 2–13.
C. Ravazzi, P. Frasca, R. Tempo, H. Ishii, Ergodic randomized algorithms and dynamics over networks, IEEE
Trans. Control of Network Syst. 2 (1) (2015) 78–87.
K. You, R. Tempo, L. Qiu, Distributed algorithms for
computation of centrality measures in complex networks,
IEEE Trans. Autom. Control (published online).
N. Friedkin, E. Johnsen, Two steps to obfuscation, Social
Networks 39 (2014) 12–13.
A. Proskurnikov, R. Tempo, M. Cao, PageRank and
opinion dynamics: Missing links and extensions, in:

[139]

[140]

[141]

[142]

[143]

[144]

[145]

[146]

[147]

[148]

[149]

[150]
[151]

[152]

[153]
[154]

[155]

[156]

Proc. of IEEE Conf. Norbert Wiener in the 21st Century, Melbourne, 2016, pp. 12–17.
D. Bindel, J. Kleinberg, S. Oren, How bad is forming your
own opinion?, in: Proc. of IEEE Symp. on Foundations
of Computer Science, 2011, pp. 57–66.
J. Ghaderi, R. Srikant, Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate, Automatica 50 (12) (2014) 3209–3215.
X. Mu, Z. Yang, Containment control of discrete-time
general linear multi-agent systems under dynamic digraph based on trajectory analysis, Neurocomputing 171
(2016) 1655–1660.
N. Friedkin, A. Proskurnikov, R. Tempo, S. Parsegov,
Network science on belief system dynamics under logic
constraints, Science 354 (6310) (2016) 321–326.
P. Converse, The nature of belief systems in mass publics,
in: D. Apter (Ed.), Ideology and Discontent, Free Press,
New York, 1964, pp. 206–261.
J. Jarvis, D. Shier, Graph-theoretic analysis of finite
Markov chains, in: D. Shier, K. Wallenius (Eds.), Applied Mathematical Modeling: A Multidisciplinary Approach, Chapman & Hall/CRC, 2000.
M. Cao, A. Morse, B. Anderson, Reaching a consensus in
a dynamically changing environment: convergence rates,
measurement delays, and asynchronous events, SIAM J.
Control Optim. 47 (2) (2008) 601–623.
A. Olshevsky, J. Tsitsiklis, Convergence speed in distributed consensus and averaging, SIAM Rev. 53 (4)
(2011) 747–772.
M. Pirani, S. Sundaram, On the smallest eigenvalue of
grounded Laplacian matrices, IEEE Trans. Autom. Control 61 (2) (2016) 509–514.
A. Proskurnikov, R. Tempo, M. Cao, N. Friedkin, Opinion evolution under time-varying social influence with individual prejudices: from consensus to disagreement, in:
Proc. of IFAC World Congress, Toulouse, France, 2017.
C. Vande Kerckhove, S. Martin, P. Gend, P. Rentfrow,
J. Hendrickx, V. Blondel, Modelling influence and opinion evolution in online collective behaviour, PLoS One
11 (6) (2016) e0157685.
S. Fortunato, Community detection in graphs, Physics
Reports 486 (3–5) (2010) 75–174.
V. Blondel, J. Hendrickx, J. Tsitsiklis, Continuoustime average-preserving opinion dynamics with opiniondependent communications, SIAM J. Control Optim. 48
(2010) 5214–5240.
I. C. Morarescu, A. Girard, Opinion dynamics with decaying confidence: Application to community detection
in graphs, IEEE Transactions on Automatic Control
56 (8) (2011) 1862–1873.
C. Altafini, Dynamics of opinion forming in structurally
balanced social networks, PLoS ONE 7 (6) (2012) e38135.
C. Altafini, Consensus problems on networks with antagonistic interactions, IEEE Trans. Autom. Control 58 (4)
(2013) 935–946.
G. Shi, A. Proutiere, M. Johansson, J. Baras, K. Johansson, The evolution of beliefs over signed social networks,
Oper. Res. 64 (3) (2016) 585–604.
G. Deffuant, D. Neau, F. Amblard, G. Weisbuch, Mixing
beliefs among interacting agents, Advances in Complex
Systems 3 (2000) 87–98.

21

