Consensus 13/06/2020

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\).

network

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.

network-adj

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.

It appears you don't have a PDF plugin for this browser. No biggie... you can click here to download the PDF file.