this is for holding javascript data
ZoƩ Christoff edited untitled.tex
about 8 years ago
Commit id: 620ddf029a30ee7465fca39bf416e1c39936cd92
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index 5dbea91..75bfef9 100644
--- a/untitled.tex
+++ b/untitled.tex
...
Let us first recall some vocabulary.
Let $G = \tuple{\N, R}$ be a graph and $R^*$ be the transitive and symmetric closure of $R$.
A \emph{path} is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$, $i_lRi_{l+1}$.
The \emph{distance} between two nodes $i,j$ is the length of the shortest path $$ between them.
The \emph{diameter} of a graph is the maximal distance between any two of its nodes.
A \emph{cycle} is a path of length $k$ such that $i_1=i_k$.
A set of nodes $S\subseteq \N$ is said to be:
\begin{itemize}
...
\item[]\emph{aperiodic} if the greatest common divisor of the lengths of its cycles is $1$.
\end{itemize}
Note that the class of graphs
our BDPs
come with rely on (finite, serial and functional)
come with present a special shape:
\begin{fact} \label{fact:uniquecycle}
Let $G$ be an influence graph and $C$ be a connected component of $G$.
Then $C$ contains exactly one cycle, and this cycle forms a closed set.
...
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 will look like confluent chains aiming together towards cyclical tails.
\subsection{Convergence of BDPs}
...
\begin{lemma}\label{lemma:influence}
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$. $\G$
%\item[] The BDP converges for any opinion profile $\O$ on $\G$ in at most $k$ steps, where $k$ is the maximum in the set of diameters of $G_{p_j} for all $j\in \{1,\ldots,m\}$.
\item[] For all $j\in \{1,\ldots,m\}$, $G_{p_j}$ contains no cycle of length $\geq 2$.
\item[] For all $j\in \{1,\ldots,m\}$, all closed connected components of $G_{p_j}$ are aperiodic.
\end{itemize}
\end{lemma}
\begin{proof}
Let
$j\in\{1,\dots,m}$ and assume that $G_{p_j}$
contain contains no cycle of length $\geq
2$. 2$ and has diameter $k$. Let $C_{p_j}$ be a connected component of $G_{p_j}$. By
Fact \ref{fact:uniquecycle},
we know $C_{p_j}$ contains a unique cycle, which, by assumption, is of length $1$. Hence, $C_{p_j}$ is aperiodic. Let $i$ be the node in the cycle. The opinion of $i$ will spread to all nodes in $C_{p_j}$ 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_j} for all $j\in \{1,\ldots,m\}$.
Assume that
each for some $j\in\{1,\dots,m}$, a connected component
$C_{p_j}$ of $G_{p_j}$ contains a
unique cycle, which has to be cycle of length
$1$. $k\geq 2$. By \ref{fact:uniquecycle}, this cycle is unique, and therefore the greatest common divisor of the cycles lengths of $C_{p_j}$ is $k$, so $C_{p_j}$ is not aperiodic.
Let $S$ be the set of nodes in the cycle.
Let $\O$ be such that for some $i,j\in\S$ with distance $d$, $O_i{p_j}\neq O_j{p_j}$. Then $O_i{p_j}$ will not converge, but enter a loop of size $k$: for all $x\in\mathbb{N}$, $O^{x\times k}_i{p_j}=\neq O^{(x\times k)+d}_i{p_j}$.
\end{proof}
The above gives a characterization of the class of influence profiles on which \emph{all} opinion streams converge.