When do the opinions of a group of individuals influencing each other stabilize? Conditions have been given, in the literature, for the general paradigms of which BDPs are limit cases. This section introduces the necessary graph-theoretic notions and briefly recalls those results before giving a characterization of convergence for BDPs.
We start with some preliminary graph-theoretic remarks. Let us first recall some vocabulary. Let \(G=\left\langle N,R\right\rangle\) be a graph and \(R^{*}\) be the transitive and symmetric closure of \(R\). A path is a sequence of nodes \(\left\langle i_{1},\dots,i_{k}\right\rangle\), such that, for all \(l\in\{1,\dots,k\}\), \(i_{l}Ri_{l+1}\). The distance between two nodes \(i,j\) is the length of the shortest path \(\left\langle i,\dots,j\right\rangle\) between them. The diameter of a graph is the maximal distance between any two nodes related by a path. A cycle is a path of length \(k\) such that \(i_{1}=i_{k}\). A set of nodes \(S\subseteq N\) is said to be:
a cycle in \(G\) if all elements in \(S\) are in one cycle of length \(|S|\),
connected if for any \(i,j\in S\): \(iR^{*}j\),
strongly connected if for any \(i,j\in S\): there is a path \(\left\langle i,\dots,j\right\rangle\),
closed if for any \(i\in S\), \(j\notin S\), it is not the case that \(iRj\),
a connected component if for any \(i,j\in N\): \(iR^{*}j\) if and only if \(i,j\in S\),
aperiodic if the greatest common divisor of the lengths of its cycles is \(1\).
Note that the class of graphs BDPs rely on (finite, serial and functional) present a special shape:
Let \(G\) be an influence graph and \(C\) be a connected component of \(G\). Then \(C\) contains exactly one cycle, and the set of nodes in the cycle is closed.
Assume that \(C\) does not contain any cycle. Since \(N\) is finite and since no path can repeat any node, any path in \(C\) is finite too. Let \(i\) be the last element of (one of) the longest path(s) in \(C\). Then \(i\) does not have any successor, which contradicts seriality. So \(C\) contains at least one cycle. Let \(S\) be the set of nodes of a cycle in \(C\). Assume that \(S\) is not closed: for some \(i\in S\) and \(j\notin S\), \(iRj\). Since \(S\) is a cycle, there is also some \(k\in S\), such that \(iRk\), which contradicts functionality. Therefore, the nodes of any cycle in \(C\) forms a closed set. Now assume that \(C\) contains more than one cycle. Since the nodes of each cycle forms a closed set, there is no path connecting any node inside a cycle to any node in any other cycle, which contradicts connectedness. So \(C\) contains a unique cycle, whose nodes form a closed set. ∎
Intuitively, influence graphs of BDPs then look like sets of confluent chains aiming together towards common cycles.
For the general case of DeGroot processes, an influence structure guarantees that any distribution of opinions will converge if and only if “every set of nodes that is strongly connected and closed is aperiodic” \cite[p.233]{jackson08social}. In the propositional opinion diffusion setting, sufficient conditions for stabilization have been given by \cite[Th. 2]{Grandi:2015:POD:2772879.2773278}: on influence structures containing cycles of size at most one (i.e, only self-loops), for agents using an aggregation function satisfying (ballot-)monotonicity and unanimity11Notice that the rule underpinning BDP, that is the ‘guru-copying’ rule on serial and functional graphs, trivially satisfies those constraints., opinions will always converge in at most at most \(k+1\) steps, where \(k\) is the diameter of the graph.22A second sufficient condition for convergence is given by —\cite{Grandi:2015:POD:2772879.2773278}—: when agents use the unanimity aggregation rule, on irreflexive graphs with only vertex-disjoint cycles, such that for each cycle there exists an agent who has at least two influencers, opinions converge after at most \(N\) steps. Note that no BDP satisfies this second condition.
Our results will show how BDPs are an interesting limit case of both DeGroot and propositional opinion diffusion processes.
Let us now turn to convergence for the limit case of BDPs. We start with some terminology. We say that the stream of opinion profiles \({\bf O}^{0},{\bf O}^{1},\ldots,{\bf O}^{n},\ldots\) converges if there exists \(n\in\mathbb{N}\) such that for all \(m\in\mathbb{N}\), if \(m\geq n\), then \({\bf O}^{m}={\bf O}^{n}\).
We will also say that a stream of opinion profiles converges for issue \(p\) if there exists \(n\in\mathbb{N}\) such that, for all \(m\in\mathbb{N}\), if \(m\geq n\), then \({\bf O}^{m}(p)={\bf O}^{n}(p)\). Given a stream of opinion profiles starting at \({\bf O}\) we say that agent \(i\in N\) stabilizes in that stream for issue \(p\) if there exists \(n\in\mathbb{N}\) such that \(O^{n}_{i}(p)=O^{m}_{i}(p)\) for any \(m>n\). So a BDP on influence graph \({\bf G}\) starting with the opinion profile \({\bf O}\) is said to converge if the stream \({\bf O}^{0},{\bf O}^{1},\ldots,{\bf O}^{n},\ldots\) generated according to Definition \ref{def:BDP} where \({\bf O}={\bf O}^{0}\) converges. Similarly, A BDP is said to converge for issue \(p\) if its stream converges for \(p\), and an agent \(i\) in the BDP is said to stabilize for \(p\) if it stabilizes for \(p\) in the stream generated by the BDP.
It must be intuitively clear that non-convergence in a BDP is linked to the existence of cycles in the influence graphs. However, from the above observation (Fact \ref{fact:uniquecycle}), we know that nodes in a cycle cannot have any influencers outside this cycle, and hence that cycles (including self-loops) can only occur at the “tail” of the influence graph. Hence, if the opinions in the (unique) cycle do not converge, which can only happen in a cycle of length \(\geq 2\), the opinions of the whole population in the same connected component will not converge. The above implies that for any influence graphs with a cycle of length \(\geq 2\), there exists a distribution of opinions which loops. This brings us back to convergence result for general (not necessarily Boolean) DeGroot processes. Indeed, for functional and serial influence graphs, a closed connected component is aperiodic if and only if its cycle is of length \(1\).
Let \({\bf G}\) be an influence profile. Then the following are equivalent:
The BDP converges for any opinion profile \({\bf O}\) on \({\bf G}\).
For all \(p\in{\bf P}\), \(G_{p}\) contains no cycle of length \(\geq 2\).
For all \(p\in{\bf P}\), all closed connected components of \(G_{p}\) are aperiodic.
\(2)\Rightarrow 1)\) Let \(p\in{\bf P}\) and assume that \(G_{p}\) contains no cycle of length \(\geq 2\) and has diameter \(k\). Let \(C_{p}\) be a connected component of \(G_{p}\). By Fact \ref{fact:uniquecycle}, \(C_{p}\) contains a unique cycle, which, by assumption, is of length \(1\). Hence, \(C_{p}\) is aperiodic. Let \(i\) be the node in the cycle. The opinion of \(i\) will spread to all nodes in \(C_{p}\) after at most \(k\) steps. Therefore, all BDPs on \(G\) will converge after at most \(l\) steps, where \(l\) is the maximum within the set of diameters of \(G_{p}\) for all \(p\in{\bf P}\). \(1)\Rightarrow 3)\) We proceed by contraposition. Assume that for some \(p\in{\bf P}\), a connected component \(C_{p}\) of \(G_{p}\) contains a cycle of length \(k\geq 2\). By \ref{fact:uniquecycle}, this cycle is unique, and therefore the greatest common divisor of the cycles lengths of \(C_{p}\) is \(k\), so \(C_{p}\) is not aperiodic. Let \(S\) be the set of nodes in the cycle. Let \({\bf O}\) be such that for some \(i,j\in S\) with distance \(d\) from \(i\) to \(j\), \(O_{i}(p)\neq O_{j}(p)\). Then \({\bf O}_{i}(p)\) will not converge, but enter a loop of size \(k\): for all \(x\in\mathbb{N}\), \(O^{x\times k}_{i}(p)\neq O^{(x\times k)+d}_{i}(p)\). Hence, \({\bf O}\) does not converge. \(3)\Rightarrow 2)\) Trivial. ∎
It is worth noticing that one direction (namely from \(3\) to \(1\)) of the above result is actually a corollary of both the convergence result for DeGroot processes stated at the beginning of this section (cf. \cite{jackson08social}), and of a known convergence result for propositional opinion diffusion \cite[Th. 2]{Grandi:2015:POD:2772879.2773278}, also stated earlier.
The above gives a characterization of the class of influence profiles on which all opinion streams converge. But we can aim at a more general result, characterizing the class of pairs of opinion and influence profiles which lead to convergence:
Let \({\bf G}\) be an influence profile and \({\bf O}\) be an opinion profile. Then the following statements are equivalent:
The BDP converges for \({\bf O}\) on \({\bf G}\).
For all \(p\in{\bf P}\), there is no set of agents \(S\subseteq N\) such that: \(S\) is a cycle in \(G_{p}\) and there are two agents \(i,j\in S\) such that \(O_{i}(p)\neq O_{j}(p)\).
\(1)\Rightarrow 2)\) We proceed by contraposition. Let \(p\in{\bf P}\), \(S\subseteq N\) be a cycle in \(G_{p}\), \(i,j\in S\), and \(O_{i}(p)\neq O_{j}(p)\). Let \(k\) be the length of the cycle and \(d\) be the distance from \(i\) to \(j\). Then \(O_{i}(p)\) will enter a loop of size \(k\): for all \(x\in\mathbb{N}\), \(O^{x\times k}_{i}(p)\neq O^{(x\times k)+d}_{i}(p)\). \(2)\Rightarrow 1)\) Assume \(S\subseteq N\) be such that \(S\) is a cycle in \(G_{p}\), and for all \(i,j\in S\), \(O_{i}(p)=O_{j}(p)\). Then, for all \(j\in S\), and all \(x\in\mathbb{N}\), \(O^{x}_{j}(p)=O_{i}(p)\) and for all \(f\in N\notin S\) with distance \(d\) from \(f\) to \(i\), for all \(x\in\mathbb{N}\), such that \(x\geq d\), \(O^{x}_{f}(p)=O_{i}(p)\). ∎
This trivially implies that the class of opinion profiles which guarantees convergence for any influence profile, is the one where everybody agrees on everything already. Note that the only stable distributions of opinions are the ones where, in each connected component in \(G\), all members have the same opinion, i.e, on BDPs, converging and reaching a consensus (within each connected component) are equivalent, unlike in the stochastic case. Moreover, for an influence profile where influence graphs have at most diameter \(d\) and the smallest cycle in components with diameter \(d\) is of length \(c\), it is easy to see that if a consensus is reached, it will be reached in at most \(d-c\) steps, which is at most \(n-1\).
Finally observe that Theorem \ref{theorem:opinion} subsumes Fact \ref{fact:influence}. If \(G_{p}\) contains only cycles of length \(1\) (second statement in Fact \ref{fact:influence}) then, trivially, no two agents in a cycle can disagree (second statement in Theorem \ref{theorem:opinion}).