Dynamic Epistemic Logics
of Diffusion and Prediction
in Social Networks

Baltag A., Christoff Z., Rendsvig R., Smets S.

Studia Logica (2019) 107: 489–531

Summary by Vitor Machado

Condensed Abstract

• Threshold models:
• used to study the diffusion of opinions, new technologies, infections, or behaviors in social networks;
• consist of a network graph of agents connected by a social relationship and a threshold value which regulates the diffusion process;
• agents adopt a new behavior/product/opinion when the proportion of their neighbors who have already adopted it meets the threshold;
• develop dynamically towards a guaranteed fixed point.
• Epistemic dimension:
• investigate how information about more distant neighbors' behavior allows agents to anticipate changes in behavior of their closer neighbors.

Goals

This paper has two goals:

• First goal: propose logics for reasoning about threshold models and their dynamics;
• Second goal: investigate how the agents' knowledge affects such dynamics.

Threshold-Limited Influence

Threshold-limited influence relies on an imitation or conformity pressure effect: agents adopt a behavior/product/opinion/fashion whenever a critical fraction of their neighbors in the network have adopted it already.

So-called threshold models, having gained early, wide-spread attention, are used precisely to represent the dynamics of diffusion under threshold-limited influence

Logic Overview

The logical setting introduced is "minimal": propositional logic is used to specify both the network structure and the agents behavior, and a single dynamic modality is used to represent the threshold-limited influence.

Moreover, while others focus on the limit thresholds of 100% (all neighbors) and non-0% (at least one neighbor), here they allow for any (uniform) adoption threshold, as is standard within the literature on threshold models.

The paper also shows how the logic captures the relationship between clusters and diffusion of a behavior to the whole network.

Network

Definition: a network is a pair $(\mathcal{A}, N)$ where $\mathcal{A}$ is a non-empty finite set of agents, and the function $N : \mathcal{A} \rightarrow \mathcal{P}(\mathcal{A})$ assigns a set $N(a)$ to each $a \in \mathcal{A}$.

It is irreflexive (an agent is not a friend of itself), symmetric (friends are friends of each other) and serial (no agent in the network has no friends).

Threshold Model

Definition: a threshold model is a tuple $\mathcal{M} = (\mathcal{A}, N, B, \theta)$ where $(\mathcal{A}, N)$ is a network, $B \in \mathcal{A}$ is a behavior and $\theta \in [0, 1]$ is a uniform adoption threshold.

It is assumed throughout the paper that both the network structure and the adoption threshold stay constant under updates. Therefore, the spread of the behavior (i.e., the extension of B) at ensuing time steps may be calculated using the fixed threshold and network structure.

Threshold Model Update

An updated threshold model $\mathcal{M}' = (\mathcal{A}, N, B', \theta)$, where $B'$ is given by: \[ B' = B \cup \left\{ a \in \mathcal{A} : \frac{\lvert N(a) \cap B \rvert}{\lvert N(a) \rvert} \geq \theta \right\} \]

A diffusion sequence $\mathcal{S}_\mathcal{M}$ is the sequence of threshold models $\mathcal{M}_0, \mathcal{M}_1, \mathcal{M}_2, \dots$ such that, for any $n \in \mathbb{N}$, $\mathcal{M}_n = (\mathcal{A}, N, B_n, \theta)$ where $B_n$ is given by: \[ B_0 = B \ \text{and} \ B_{n+1} = B_n' \] The paper shows that any such diffusion process reaches a fixed point.

Unadoption

An alternate diffusion model is given, which also allows Unadoption by capturing a conservative tie-breaking rule:

\[ B' = \left\{ a : \frac{\lvert N(a) \cap B \rvert}{\lvert N(a) \rvert} > \theta \right\} \cup \left\{ a : \frac{\lvert N(a) \cap B \rvert}{\lvert N(a) \rvert} = \theta \ \text{and} \ a \in B \right\} \]

Since this does not cause $B$ to inflate, this alternative rule allows the possibility of loops in behavior, i.e. where $B = B'' \neq B'$. Notice that a diffusion sequence with this model does not necessarily reach a fixed point.

Logic

The language $\mathcal{L}_{[]}$ is an extension of propositional logic, given by: \[ \varphi := N_{ab} \mid \beta_a \mid \neg \varphi \mid \varphi \land \varphi \mid [adopt]\varphi \] where atoms are given by $\Phi = \{ N_{ab} : a, b \in \mathcal{A} \} \cup \{ \mathcal{B}_a : a \in \mathcal{A} \}$.

The formulas of $\mathcal{L}$ are those of $\mathcal{L}_{[]}$ that do not involve the $[adopt]$-modality.

Truth Clauses

Conventional formulas are evaluated in the standard way. Others, as follows:

• $\mathcal{M} \models \beta_a \leftrightarrow a \in B$;
• $\mathcal{M} \models N_{ab} \leftrightarrow b \in N(a)$;
• $\mathcal{M} \models [adopt] \varphi \leftrightarrow \mathcal{M}' \models \varphi$, where $\mathcal{M}'$ is the updated threshold model.

Abbreviations

Consider the recursive abbreviation $[adopt]^n \varphi$: \[ [adopt]^0 \varphi := \varphi\\ [adopt]^{n+1} \varphi := [adopt][adopt]^n \varphi \]

And also the abbreviation $\beta_N(a) \geq \theta$, expressing that the proportion of agent $a$'s neighbours who adopted the behavior is equal to or above the threshold $\theta$: \[ \beta_N(a) \geq \theta := \bigvee_{\mathcal{G} \subseteq \mathcal{N} \subseteq \mathcal{A} : \frac{\lvert \mathcal{G} \rvert}{\lvert \mathcal{N} \rvert} \geq \theta} \left(\bigwedge_{b \in \mathcal{N}}N_{ab} \land \bigwedge_{b \not\in \mathcal{N}}\neg N_{ab} \land \bigwedge_{b \in \mathcal{G}} \beta_b \right) \]

Cascades

An agent adopting a new behavior may influence some of her neighbors to adopt it at the next moment, which in turn may cause further agents to adopt it, and so on. Such a chain reaction is termed a cascade in the literature, and a cascade is said to be complete when it results into a state where all agents have adopted the new behavior.

The sentence abbreviated by $cascade$ expresses that all agents will have adopted a behavior eventually: \[ cascade := [adopt]^{\lvert \mathcal{A} \rvert - 1} \bigwedge_{a \in \mathcal{A}} \beta_a \]

Clusters

Strongly connected groups of agents are more resilient to external influence. Briefly put, dense components of a network may prevent complete cascades and the denser a group, the better it resists change induced from the outside

A cluster of density $d$ is any group $C \subseteq \mathcal{A}$ such that for all $a \in C$, $ \frac{\lvert N(a) \cap C \rvert}{\lvert N(a) \rvert} \geq d$.

Clusters (example)

A social network with a cluster of density $\frac{2}{3}$

Notice that any network will contain at least one cluster of density $1$, namely the group $\mathcal{A}$, and that each singleton $\{a\} \subseteq \mathcal{A}$ is a cluster of density $0$ (by irreflexivity).

The Cluster Theorem

Given a threshold model $\mathcal{M}$ with threshold $\theta \neq 0$ and a set $B \subseteq \mathcal{A}$ of agents who have adopted, all agents will eventually adopt if and only if there does not exist a cluster of density greater than $1 - \theta$ in $\mathcal{A} \setminus B$.

The theorem can be encoded in $\mathcal{L}_{[]}$ in the following way: \[ \mathcal{M} \models cascade \leftrightarrow \neg \exists C_{\geq 1 - \theta} \neg \beta \] where $\exists C_{\geq 1 - \theta} \neg \beta$ is an abbreviation, which characterizes the existence of a cluster of density $d$ among agents who have not adopted: \[ \bigvee_{C \subseteq \mathcal{A}} \bigwedge_{a \in C} \bigvee_{\mathcal{G} \subseteq \mathcal{N} \subseteq \mathcal{A} : \frac{\lvert \mathcal{G} \cap C\rvert}{\lvert \mathcal{N} \rvert} \geq d} \left(\bigwedge_{b \in \mathcal{N}}N_{ab} \land \bigwedge_{b \not\in \mathcal{N}}\neg N_{ab} \land \bigwedge_{b \in \mathcal{G}} \neg \beta_b \right) \]

Generalizations

It's possible to define the threshold $\theta$ not as a constant but as a function assigning a particular threshold to each agent, i.e., set $\theta : \mathcal{A} \rightarrow [0,1]$, and replace $\theta$ by $\theta(a)$ in the definition of the update.

It's also possible to generalize the logic to capture several behaviors. Let $\mathcal{B}$ be a finite set of behaviors $\mathcal{B} = \{B_1, B_2, \dots, B_n\}$ and define $\theta : \mathcal{A} \times \mathcal{B} \rightarrow [0,1]$.

Epistemic Threshold Models

A situation of uncertainty. Agent $a$ cannot tell whether world $w$ or world $v$ is the actual one.

The paper extends the standard threshold models with an epistemic dimension and define a refined adoption policy where agents' behavior change depends on their knowledge of others' behavior.

Sight

We will say that an agent has sight $n$ when it can "see" at least $n$ agents away, i.e., when the agent knows at least both the network structure and the behavior of all agents within distance $n$.

Let be given an ETM $\mathcal{M} = (\mathcal{W}, \mathcal{A}, N, B, \theta, \{\sim_a\}_{a \in \mathcal{A}})$ and let $n \in \mathbb{N}$. Define $N^n : \mathcal{W} \rightarrow \mathcal{A} \rightarrow \mathcal{P}(\mathcal{A})$ (n-reachable) as follows, for any $w \in \mathcal{W}$ and any $a, b, c \in \mathcal{A}$:

• $N^0(w)(a) = \{a\}$
• $N^{n+1}(w)(a) = N^n(w)(a) \cup \\ \{b \in \mathcal{A} : \exists c \in N^n(w)(a) \ \text{and} \ b \in N(w)(c)\}$

Informed Update

The (n sight) informed adoption update of $\mathcal{M}$ produces results in an ETM $\mathcal{M}^i = (\mathcal{W}, \mathcal{A}, N, B^i, \theta, \{\sim_a^i\}_{a \in \mathcal{A}})$:

• $B^i(w) = B(w) \cup \left\{ a \in \mathcal{A} : \forall v \sim_a w \frac{\lvert N(v)(a) \cap B(v) \rvert}{\lvert N(v)(a) \rvert} \geq \theta \right\}$
• $w \sim_a^i w' \leftrightarrow w \sim_a w' \ \text{and} \\ \forall b \in N^n(w)(a) : b \in B^i(w) \Leftrightarrow b \in B^i(w')$

Distant Knowledge is Redundant

The paper concludes that the standard threshold models make the implicit epistemic assumption that agents know their neighborhood and its behavior.

Another conclusion is that knowledge about more distant agents is redundant as it will not affect behavior.

Distant Knowledge is Redundant (cont.)

Let $\mathcal{M}$ be an ETM and $w \in \mathcal{W}$. Let $\mathcal{M}^i$ be the informed update, and $\mathcal{M}(w)$ the state-generated model of $\mathcal{M}$ (equivalent standard threshold model for the state $w$). Let $\mathcal{M}^i(w)$ be the state-generated model of $\mathcal{M}^i$ and let $\mathcal{M}(w)'$ be the standard threshold update of $\mathcal{M}(w)$. Then:

if $\mathcal{M}$ has sight $n \geq 1$ then $\mathcal{M}^i(w) = \mathcal{M}(w)'$

Sight 0

A diffusion process "slowed down" by the uncertainty of agent $b$, with threshold $\theta = \frac{1}{2}$. Consider the situation in world $w$: agent $a$ has adopted, but agent $b$ does not know it. Therefore, agent $b$ will not adopt immediately.

Cluster Theorem Revisited

The lack of knowledge may for instance block a cascade, despite the absence of a cluster-obstacle. Note that under the non-epistemic threshold update, or if agent $b$ knew that $a$ has adopted, the situation depicted in state $w$ would evolve into a complete cascade.

Chapters 4, 5 and 6 in the future...