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). Moreinterestingly the state of consensus around a particular issue can evolve over time, through discussion and debateof 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 isconnected to some (or maybe all) of the others. The most obvious example of this is the social networkwe construct between friends and family, here "connectedness" just means person \(A\) is friends withperson \(B\).



In the visual representation the people (nodes) are circles and the friendship status (connectivity) between people are represented by linesdrawn between them.

Moving back to consensus we can use the network by saying that each person has a currentdecision \(x_{i}(t)\), where \(i\) is an integer representing the individual and \(t\) is time. Here we'veimplied that a persons "decision" is represented as some number, that can also vary as time progresses. The wayin 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 wouldmake sense if the people person \(2\) is friends with, \(3\) and \(5\) from the network, could change person \(2\)'s opinon i.echange \(x_{2}(0)\). As a first go we might say that a person's opinion changes proportionaly to thedifference between their opinion, and the average of the friend's opinions. We can even rigPPhtthis 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 theirviews 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 theperson 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" anda 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 withrepspect to the image! Either way we can now say \(\boldsymbol{A}_{32}=1\), or in plain language the value atthe \(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 writedown 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 numbersignoring 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 friendshipgroup, but what is consensus? Looking back at our original definition consensus would meanthat 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 iswhen a graph is fully connected, in our example person \(1\) is on their own and so won'tchange their opinion ever under this model!

As a final note, the maths here does not just describe social networks and opinions, we canapply the same reasoning to any process by which multiple "agents" choose a desision andinfluence 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.