<figure><img src="image_1.png" /></figure>

HAL
open science

# Active links density in the Voter Model with zealots

Antoine Vendeville, Benjamin Guedj, Shi Zhou

► To cite this version:

Antoine Vendeville, Benjamin Guedj, Shi Zhou. Active links density in the Voter Model with zealots. Conference on Complex Systems 2022, Oct 2022, Palma de Mallorca, Spain. hal-04010520

HAL Id: hal-04010520

https://hal.science/hal-04010520

Submitted on 1 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Active links density in the Voter Model with zealots

Antoine Vendeville¹,², Benjamin Guedj¹,² and Shi Zhou¹

¹University College London, Department of Computer Science,
Centre for Doctoral Training in Cybersecurity and Centre for Artificial Intelligence, London, UK

²Inria, Lille - Nord Europe research centre and Inria London Programme

Echo chambers are a recurring phenomenon in Online Social Networks. In this work we propose to quantify it via the Active Links Density (ALD), that is the proportion of edges that connect nodes with different opinions. We consider a directed, weighted social graph where users hold discrete-valued opinions. We study an unweighted and a weighted version of ALD, in the case where opinions evolve according to the Voter Model with zealots. To this end we develop a novel mean-field approximation for the probability of disagreement of each node pair at equilibrium. We prove that this quantity can be efficiently computed via a power iteration algorithm and demonstrate its accuracy when compared with empirical estimates from numerical simulations. Finally we compare the ALD with various existing metrics for the measurement of echo chambers.

Consider $N$ users interacting on a social network and holding discrete-valued opinions in some set $S = \{1, \dots, S\}$. Relations between them are encapsulated in a directed, weighted user graph so that a positive weight $w_{ij} > 0$ on the edge $j \to i$ indicates that $i$ is a follower of $j$. Each user is endowed with an exponential clock, and when user $i$'s clock rings they adopt the opinion of another they follow, chosen at random with probabilities proportional to the weights $\{w_{ij} : j = 1, \dots, N\}$.

We assume the user graph to be strongly connected and that external control is exerted on the nodes via the presence of zealots, one for each opinion. The s-zealot promotes opinion $s$ and has influence $z_{is}$ over user $i$. Thus $i$ may choose to copy it instead of a neighbour, which happens with probability proportional to $z_{is}$.

The system reaches a state of equilibrium in which all opinions coexist. The central contribution of this work is a mean-field approximation for the equilibrium probability $q_{ij}$ that any two users $i$ and $j$ disagree. Assume that influences are normalised to that $\sum_{j=1}^N w_{ij} + \sum_{s \in S} z_{is} = 1$ is the total amount of influence exerted on $i$. We prove that for all node pairs $\{i, j\}$,

$$2q_{ij} = \sum_{k \neq i, j} (w_{ik}q_{jk} + w_{jk}q_{ik}) + z_i^\top(1 - x_j^*) + z_j^\top(1 - x_i^*).$$

Here $x_{i,s}^*$ is the average proportion of time node $i$ holds opinion $s \in S$ at equilibrium, given by [1]

$$x_{i,s}^* = \sum_{j=1}^{N} w_{ij}x_{j,s}^* + z_{is}.$$

Values of $q$ are solution of a linear system of $N^2$ equations. As matrix inversion is intractable for large systems and we show that it can be solved efficiently via power iteration.

Moreover we observe that as the distance between $i$ and $j$ increases, $q_{ij}$ can be well approximated by $(x_i^*)^\top(1 - x_j^*)$ which can be directly computed from the values $x^*$. This can help further reducing the computations required for finding $q$.

The unweighted and weighted ALD are finally computed via, respectively,

$$\rho = \frac{\sum_{(i,j) \in \mathcal{E}} q_{ij}}{|\mathcal{E}|}, \quad \rho_w = \frac{\sum_{(i,j) \in \mathcal{E}} w_{ij}q_{ij}}{\sum_{(i,j) \in \mathcal{E}} w_{ij}},$$

where $\mathcal{E}$ is the set of edges.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Weighted ALD function of the size $S$ of the opinion set for $N = 100$. **Left:** Erdös-Rényi graph with density 0.05 and random uniform weights. **Middle:** Watts-Strogatz graph with 5 connections per node, rewiring probability 0.1 and random uniform weights. **Right:** Barabasi-Albert graph with 2 connections per arriving node and random exponential weights. Bars delimit 95% confidence intervals.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2: ALD function of the between-group connectivity on an undirected, unweighted graph generated under the Stochastic Block Model. $N = 100$ users, 3 communities each promoting a different opinion, within-group connectivity 0.1. Bars delimit 95% confidence intervals.</figcaption></figure>

<footnote>[1] N. Masuda. Opinion control in complex networks. New J. Phys., 17(3):033031, Mar. 2015.</footnote>