deletions | additions
diff --git a/untitled.tex b/untitled.tex
index 228ee92..85f895b 100644
--- a/untitled.tex
+++ b/untitled.tex
...
Convergence results have been given both for DeGroot processes \cite{Golub_2010} and for propositional opinion diffusion for specific aggregation procedures \cite{Grandi:2015:POD:2772879.2773278}. Let us briefly recall those results.
In the case of DeGroot processes, a graph guarantees that any distribution of opinion will converge if and only if ''every set of nodes that is strongly connected and closed is aperiodic" (Jackson, p.233).\footnote{A set of nodes is said to be ``strongly connected" if there is a directed path from any node to any other node in the set, ``closed" if there is no link from nodes in the set to nodes outside the set, and aperiodic if the greatest common divisor of all directed cycles is
$1$.} $1$}
%This result applies of course to our limit cases, the BDGs.
In the multi-agent perspective of ``propositional opinion diffusion", two main results give sufficient conditions for stabilization.
First, on graphs containing cycles of size at most one (i.e, only self-loops), for agents using any aggregation function satisfying ballot-monotonicity, opinions will always converge in at most at most $k+1$ steps, where $k$ is the diameter of the graph.
(THIS IS THM 2 IN THE PAPER. NOTE THAT THE PROPERTY OF ALLOWING ONLY CYCLES OF LENGTH 1 GUARANTEES THAT THE GRAPH IS APERIODIC, ALREADY MEETING DEGROOT'S CONDITION FOR STABILIZATION.)
...
What do these results correspond to when applied to our ``follow your guru" policy, that is, when imposing functionality and seriality on graphs and focusing solely on the unanimity rule? They imply the following: if, for all $i\in\{1,\ldots,m\}$, the influence graph $\G_i$ contains only cycles of length $1$, then all opinions profiles on $\G$ converge. Note that this follows directly both from the deGroot convergence result stated earlier (since graphs with only cycles of length one are trivially aperiodic) and from the propositional opinion diffusion theorem above (since the unanimity rule is trivially monotonic). This illustrates how the BDPs are limit cases both of the opinion diffusion and of the DeGroot stochastic opinion diffusion.
Can we go beyond the above and give a characterization of the class of
influence graphs guaranteeing convergence of BDPs?
Let us first remark that for functional graphs, no node in a cycle can have any successor outside of the cycle. Therefore, all cycles have to be vertex-disjoint:
...
Let $G_{p_j}$ be an influence graph, such that it contains two cycles which are not vertex disjoint. Then there is a vertex $i$ contained in both cycles, such that $i$ has a different successor in each cycle. But since $G_{p_j}$ is functional, $i$ has at most one successor. Contradiction.
\end{proof}
We can also note that
cycles in our influence graphs
cannot contain two cycles in the same connected component. Cycles are not only vertex-disjoint, they
cannot belong to
different the same connected
components component\footnote{A connected component $C$ of a graph $G = \tuple{\N, R}$ is a set of
nodes $\C\subseteq\N$ such that: for any $i,j\in\C$, $iR^+j$, where $R^+$ is the
graph: symmetric closure of $R$.}.:
\begin{lemma}
Let $G_{p_j}$ be an influence
graph. A graph and $C_{p_j}$ be a finite connected component of
$G_{p_j}$ $G_{p_j}$. Then $C_{p_j}$ contains
at most exactly one cycle.
\end{lemma}
\begin{proof}
Let $G_{p_j}$ be an influence graph, such that one connected component of $G_{p_j}$ contains two cycles of length $\leq k$. By the previous lemma, we know that the two cycles are vertex-disjoint. For any node $i$ in the component, by connectivity, there exists a path to a node in one of the cycles. If $i$ is contained in one of the cycles, by functionality there is no path from $i$ leading to any node outside the cycle. If $i$ is not contained in any of the cycles, then by connectedness it must have a path leading to one of the cycles. But then the same reasoning apply: there is no path from any node inside a cycle to any node outside this cycle.
\end{proof}
Since nodes in a cycle cannot have any influencers outside this cycle, cycles (including self-loops) can only be at the
``tail"(s) ``tail"(s)/root of the graph (i.e this is what Umberto calls "a source", since he draws the influence arrows in the opposite direction).
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 loop. The above implies that for any influence graphs with a cycle of length $\geq 2$, there can be a distribution of opinions which loops.
Note that this brings us back to the general result on DeGroot processes. For our influence graphs, a closed component is aperiodic if and only if its unique cycle is of length $1$.
Hence, if the opinions in the (unique) cycle of length $\geq$ loop, the opinions of the whole population (in the same connected component) will loop. The above implies that for any influence graphs with cycles of length , there can be a distribution of opinions which loops.
\begin{proposition}
Let $\G=(G_{p_1},\dots,G_{p_m})$ be an influence profile. Then the following are equivalent:
\begin{itemize}
\item[] The BDP converges for any opinion profile $\O$ on $\G$.
\item [] For all $j\in \{1,\ldots,m\}$, $G_{p_j}$ contains no cycle of length $\geq 2$.
\item [] All closed connected components $j\in \{1,\ldots,m\}$, $G_{p_j}$ are aperiodic.
\end{itemize}
\end{proposition}
\begin{proof}
=>:
Let $\G=(G_{p_1},\dots,G_{p_m})$ be an influence profile and $G_{p_j}$ be the influence graph for issue $p_j$ for an arbitrary $j\in \{1,\ldots,m\}$. Assume that $G_{p_j}$ contains a cycle of length $k \geq 1$, such that $i,j\in\N$ are two of the nodes of the cycle. TO BE CONTINUED...
\end{proof}
