ZoĆ© Christoff edited section_Convergence_When_do_the__.tex  about 8 years ago

Commit id: 97b684f8a257763a3cb53cfc1d89a69f9f58ac08

deletions | additions      

       

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  \section{Convergence}  When do the opinions of a group of individuals influencing each other stabilize? Conditions have been given, in the literature, for the general paradigms whichour  BDPs are limit cases of. In this section, we give a characterization of convergence for BDPs. \subsection{Graph-theoretic preliminaries}  We start with some preliminary graph-theoretic remarks.  

\end{fact}  \begin{proof}  Assume that $C$ does not contain any cycle. Since $\N$ is finite path do not repeat any node, any path in $C$ is finite. Let $i$ be the last element of one of  the longuest path paths  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 node 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.  Assume that $C$ contains more than one cycle. Since each cycle forms a closed set, there is no path connecting any node inside the cycle to any node outside the cycle, which contradicts connectedness. So $C$ contains a unique cycle, which forms a closed set.   \end{proof}  This means that influence graphs of BDPs will  look like confluent chains aiming together towards cyclical tails.

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   (\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 are opinion profiles exists a distribution of opinions  which do not converge. 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$.   \begin{lemma}\label{lemma:influence}