Part of this post (the application to flocking) is implemented on my Github
Consensus is "a generally accepted opinion or decision among a group of people" (Cambridge Dictionary). More
interestingly the state of consensus around a particular issue can evolve over time, through discussion and debate
of ideas.
To think about this mathematically we will first take a leap into graph theory. A group of people can be described as a network, where each person is
connected to some (or maybe all) of the others. The most obvious example of this is the social network
we construct between friends and family, here "connectedness" just means person \(A\) is friends with
person \(B\).
In the visual representation the people (nodes) are circles and the friendship status (connectivity) between people are represented by lines
drawn between them.
Moving back to consensus we can use the network by saying that each person has a current
decision \(x_{i}(t)\), where \(i\) is an integer representing the individual and \(t\) is time. Here we've
implied that a persons "decision" is represented as some number, that can also vary as time progresses. The way
in which this number varies for each person (the different \(i\)'s) will be linked to the edges in the network.
If we imagine that \(x_{2}(0)\) is a representation of person \(2\)'s opinion about a topic at time \(0\), it would
make sense if the people person \(2\) is friends with, \(3\) and \(5\) from the network, could change person \(2\)'s opinon i.e
change \(x_{2}(0)\). As a first go we might say that a person's opinion changes proportionaly to the
difference between their opinion, and the average of the friend's opinions. We can even rigPPht
this down for person \(2\)
$$ x_{2}(1) = \frac{x_{3}(0)-x_{2}(0) + x_{5}(0) - x_{2}(0)}{2} = \frac{x_{5}(0)+x_{3}(0)}{2}-x_{2}(0) $$
Intuitively this means if person \(2\)'s opinion is higher (remember "opinions" are numbers here) than
\(3\) and \(5\)'s then \(2\)'s opinion will decrease towards \(3\) and \(5\)'s based upon how different their
views are (on average).
Borrowing some more graph theory we can summarise "who knows who" by a \(N\cdot N\) grid of numbers, if there are \(N\) people, called an "Adjacency Matrix". Think of this as a table with a row and a column for each person,
as we read one row \(2\) across the columns, when there is a \(1\) this tells us person \(2\) is friends with the
person represented by this column, when there is a \(0\) person \(2\) is not friends with them.
The image above show a visual representation of this adjacency matrix, here a black square means "not friends" and
a yello one means "friends", or as numbers \(0\) and \(1\). Mathematically we can write this down as
$$ \boldsymbol{A} =
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}$$
Where notice that unhelpfully the mathematics convention has it flipped with
repspect to the image! Either way we can now say \(\boldsymbol{A}_{32}=1\), or in plain language the value at
the \(3\)rd row and \(2\)nd column is \(1\).
So how does this relate to our consensus problem? Well we cna begin to genralise how we write
down how each person influences the others, e.g for the example from before we can now write
$$ x_{2}(1) = \frac{A_{23}}{2}(x_{3}(0)-x_{2}(0)) + \frac{A_{25}}{2}(x_{5}(0)-x_{2}(0)) $$
This hasn't changed much yet, but it means we can write the general equation for any \(i\)!
$$ x_{i}(t) = \frac{\sum_{j\neq i}\boldsymbol{A}_{ij}(x_{j}(t-1)-x_{i}(t-1))}{\sum_{j\neq i}\boldsymbol{A}_{ij}} $$
Where the mathematical notation \(\sum_{i}\) means a summation over the index \(i\), so \(\sum_{i=1}^{5}i = 1 + 2 + 3 + 4 + 5\), and
\(\neq\) means not equal to, therefore \(\sum_{j\neq 2}\boldsymbol{A}_{2j}\) means summing over the columns of the grid of numbers
ignoring where the column is equal to the row \(2\), i.e the number of friends person \(2\)! Which is \(2\)
To wrap up, we have a general equation for how each person influences the others opinions in their friendship
group, but what is consensus? Looking back at our original definition consensus would mean
that everyone shares the same opinion, i.e
$$ x_{1}(t) = x_{2}(t) = x_{3}(t) = x_{4}(t) = x_{5}(t) = x_{6}(t) $$
And it turns out that we can prove how long it will take before this consensus condition is met, that is
when a graph is fully connected, in our example person \(1\) is on their own and so won't
change their opinion ever under this model!
As a final note, the maths here does not just describe social networks and opinions, we can
apply the same reasoning to any process by which multiple "agents" choose a desision and
influence the decisions of others, some examples are politics (voter models), collective motion
(e.g bird flocks), distributed computation, and swarm robotics.
The pdf below contains the full detail of mathematics, and some applications.