# Opinion formation by belief propagation: A heuristic to identify low-
credible sources of information

Enrico Maria Fenoaltea1111Corresponding author. Email:
<EMAIL_ADDRESS>and Alejandro Lage-Castellanos2

###### Abstract

With social media, the flow of uncertified information is constantly
increasing, with the risk that more people will trust low-credible information
sources. To design effective strategies against this phenomenon, it is of
paramount importance to understand how people end up believing one source
rather than another. To this end, we propose a realistic and cognitively
affordable heuristic mechanism for opinion formation inspired by the well-
known belief propagation algorithm. In our model, an individual observing a
network of information sources must infer which of them are reliable and which
are not. We study how the individual’s ability to identify credible sources,
and hence to form correct opinions, is affected by the noise in the system,
intended as the amount of disorder in the relationships between the
information sources in the network. We find numerically and analytically that
there is a critical noise level above which it is impossible for the
individual to detect the nature of the sources. Moreover, by comparing our
opinion formation model with existing ones in the literature, we show under
what conditions people’s opinions can be reliable. Overall, our findings imply
that the increasing complexity of the information environment is a catalyst
for misinformation channels.

1Physics Department, University of Fribourg, Chemin du Musée 3, 1700 Fribourg,
Switzerland

2Group of Complex Systems and Statistical Physics, Physics Faculty, Havana
University, La Habana, CP 10400, Cuba

keywords: Belief propagation, Signed network, learning, Heuristic, node
classification, Phase transition

##  1 Introduction

Social media have revolutionized how people communicate and inform themselves,
becoming the primary source of information for most users. However, content in
social media is often published without the intermediation of experts, thus
increasing the risk of spreading unreliable news [1, 2, 3, 4]. With the
advance of the research on how opinions propagate in networks [5, 6], how news
goes viral [7, 8], and how polarization affects public opinion [9, 10, 11],
methods have been proposed to limit the spread of incorrect information and
help users distinguish true news from fake news [12, 13, 14, 15]. Despite
these efforts, misinformation still threatens society. Indeed, it is not
trivial for the general public to distinguish between reliable and unreliable
content. A pertinent example was the recent media circus around the war in
Ukraine: people have faced an overwhelming amount of both reliable news and
news whose only purpose was to make propaganda. This has generated widespread
confusion with dangerous implications for society. Therefore, it is crucial to
understand how people form their opinions and provide them with strategies for
properly getting informed in a world full of often conflicting information
channels.

In addition to studies in psychology [16, 17] and sociology [18, 19], opinion
formation is widely investigated by quantitative methods, such as network
science [20, 21], game theory [22, 23], or statistical physics [24, 25, 26].
In particular, models have been proposed to study opinion contagion in social
networks [27, 28], and how such contagion leads to the emergence of cohesion
[29, 30] or fragmentation [31, 32] in society. Recently, a model has been
proposed in [33] that differs from the models mentioned above by including
potential relationships (both positive and negative) between the subjects on
which an individual, in the absence of social influence, tries to form an
opinion. In fact, such connections are a fundamental component of the world of
social media and information channels [34, 35]. The authors in [33] discuss a
cognitively and computationally simple heuristic rule by which an individual
navigates the network of subjects and gradually forms an opinion about each of
them. Then, based on an a priori hidden truth, the proportion of correct and
incorrect opinions is measured. Other heuristic rules were then investigated
in [36]. Such works do not consider the probabilistic and uncertain nature of
human decisions [37, 38], but assume that an individual’s opinions have a
binary character (e.g., trust or distrust of an information channel). However,
people’s beliefs and opinion systems can be more nuanced.

Within the same framework of these models (which we explain in more detail
below), here we allow for uncertainties in the opinion formation process by
studying a new heuristic rule whose mechanism is based on the well-known
belief propagation algorithm [39]. In particular, we consider an individual
who wants to learn something about a topic (e.g., the motivations for the
Ukrainian war) and observes a network of information sources- some reliable,
others unreliable- discussing that topic. While it is immediate to understand
that two sources promote conflicting content, it is more difficult for the
layman to choose which one to trust. These sources of information can be
websites, Youtube channels, or newspapers whose interconnections represent
their mutual relationship of trust or distrust. For example, two Youtube
channels with the same view on a subject will tend to collaborate; conversely,
if they have an opposite opinion, they will diss each other. In the
literature, such a relationship system is formalized as a signed network with
positive and negative links [40]. Moreover, the relationships between sources
of information should follow the logic of Heilder’s balance rule [41]: if two
sources have a link of the same sign with a third source, they are connected
to each other by a positive link; conversely, if they have links of the
opposite sign with a third source, they are connected by a negative link (this
is a formalization of the proverb “my enemy’s friend is my friend”). While
this is certainly an oversimplification of the more complex existing spectrum
of relationships between different sources of information, this structure has
been observed in data sets of various political and social systems [42, 43,
44]. Nevertheless, there may be several deviations: for example, for some
reason, two sources of information that generally agree may disagree on a
minor issue, and the individual is misled because he/she observes a negative
connection between them; or the topic addressed is so complex that it is
difficult to determine which is the true relationship between the sources,
increasing the risk that the individual will observe incorrect link signs. To
account for this, we assume that the link signs in the network of information
sources are at odds with the balance rule with some small probability that we
refer to as noise.

Assuming that, initially, the individual has information about the reliability
of only one source of information in the network, his/her goal is to identify
which of the sources are reliable by observing the (noisy) relationships
between them. This task can be cognitively very expensive, so humans must rely
on simple heuristics when dealing with complex issues [45, 46]. Hence, we
study a probabilistic and local heuristic rule (i.e., where only local
knowledge of the source network is required) inspired by the belief
propagation algorithm. This algorithm is useful to efficiently solve inference
problems by passing local messages [47]. It has important applications in
statistical physics [48, 49], error-correcting coding theory [50], computer
vision [51], and artificial intelligence [52, 39]. In this paper, we recast
the belief propagation algorithm in the framework of opinion formation.

Specifically, we investigate how the noise affects the performance- in terms
of the number of information sources correctly labeled as reliable or
unreliable- of our belief propagation rule and show that, in addition to
realistically describing how humans reason, it outperforms existing heuristics
in the literature. However, we find analytically that there is a critical
noise level beyond which, even with our belief propagation approach, one
cannot extract information from the source network. Then we show numerically
that, independently of the noise, the performance of any local rules
inevitably decreases as the size of the sources network increases. This
adverse outcome can be limited if the individual forms his/her opinions by
aggregating information from multiple sources. We also extend our model and
the models in [33, 36] to study the effect of repeated opinion updating,
showing that it is beneficial only for local heuristic rules involving the
above-mentioned multiple sources aggregation.

Our findings suggest that, because we have limited information capabilities,
our opinions can be highly sensitive to the complexity of the information
environment, thus calling for a policy to provide less cluttered communication
to the general public. Moreover, by giving insights into what conditions
increase the risk of people relying on low-credible sources, our work can help
design new tools or improve existing ones to prevent the proliferation of
false beliefs.

##  2 Opinion formation processes

###  2.1 The basic framework

Consider a system composed of $N$ interconnected sources of information. For
simplicity, we assume that each source can be of two types, reliable or
unreliable, with equal probability. We represent these two types with positive
and negative signs, respectively. If two information sources of the same sign
are connected, they have a positive relationship (mutual trust); if they are
of the opposite sign, they have a negative relationship (mutual distrust). In
this way, the information sources define an undirected signed network with $N$
nodes $V=\\{i,i\in[1,N]\\}$. Each node $i$ can be positive or negative, i.e.,
$s_{i}\in\\{-1,1\\}$, and the relationships between nodes are defined by a
weighted graph where, whenever there is an edge between two nodes $i$ and $j$,
this edge has an associate weight $J_{ij}=s_{i}s_{j}$. This can be
equivalently encoded into a weighted matrix $J$, whose elements $J_{ij}$ are
zero if the sources are non-interacting, while +1 if they are of the same type
and -1 if they are of a different type. In the following, we consider only the
random network topology with average degree $k\in\mathbf{N}$, which means that
two nodes have a link with probability $p=k/(N-1)$. Therefore, the average
number of links $E$ is given by $E=pN(N-1)$. We will refer to this network as
the ground truth network $G(V,E,J)$.

Now, consider an external observer who, having only partial knowledge of the
nodes in $G$, tries to figure out which sources of information are reliable
and which are not, i.e., forms opinions about them. Formally, The opinion
$o_{i}$ on a node $i$ is a two-dimensional vector such that:

$o_{i}:=\left[\begin{array}[]{c}P(s_{i}=+1)\\\ P(s_{i}=-1)\end{array}\right]$
(1)

where the first element represents the degree of confidence (or the
probability), according to the external observer, that the information source
$i$ is reliable, while the second element is its complement, i.e.
$P(s_{i}=-1)=1-P(s_{i}=+1)$. We assume that the observer initially knows only
one node $i^{*}$, such that $o_{i^{*}}=(1,0)$ if $s_{i^{*}}=+1$ and
$o_{i^{*}}=(0,1)$ if $s_{i^{*}}=-1$. We refer to this node as seed node.

Then, we introduce a parameter $r\in[0,1/2]$ that represents the noise on the
relation matrix $J$. Specifically, the observer is not able to ”see” the real
$J$ but observes a relation matrix $J^{o}$ such that

$\forall_{(i,j)}\quad J^{o}_{ij}=\left\\{\begin{array}[]{cc}J_{ij}&\mbox{ with
prob }1-r\\\ -J_{ij}&\mbox{ with prob }r\end{array}\right.$ (2)

In this way, $r$ serves to include the structural noise present in any real
system in which it is not straightforward to determine the type of
relationship between two sources. When $r=0$, the matrix $J$ and the observed
matrix $J^{o}$ coincide, so the observer knows with certainty which are the
true relationships between the information sources. When $r=1/2$, however,
$J^{o}$ is not informative about the links’ signs in $G$, as $J$ and $J^{o}$
are not correlated.

Given a ground truth network $G(V,E,J)$, a seed node $i^{*}$, and a noise
level $r$ generating $J^{o}$, the observer’s goal is exploiting the
information from $i^{*}$ and $J^{o}$ to form opinions that reflect as
accurately as possible the true types of the nodes in $G$ (see Fig.1a). At the
two extremes, the formation of an accurate opinion is either impossible
($J^{o}$ uninformative with $r=1/2$) or trivial ($J^{o}=J$ with $r=0$).
Indeed, starting from the seed node, the observer can assign each node the
type according to $\Pi_{i}J_{\pi_{i-1}\pi_{i}}$, where $\pi$ is any path
connecting the seed node to the target node, and $\pi_{i}$ is the $i$-th node
of the path $\pi$.

In the following, we introduce different opinion formation processes and study
their performance as $r$ varies. As a measure of process performance, we use
the resulting average overlap $q$ between the expected value (from the
observer’s point of view) of the sign of node $i$ and its true value $s_{i}$:

$q:=\frac{1}{N}\sum_{i=1}^{N}\langle o_{i}\rangle s_{i},$ (3)

where $\langle o_{i}\rangle:=P(s_{i}=+1)-P(s_{i}=-1)$. The overlap is one when
the observer infers with certainty the correct sign of each node of $G$ and is
zero in the extreme case where the observer fails to extract any information
about $G$.

###  2.2 The optimal Bayesian

Before introducing the opinion formation processes of an external observer
able to handle only local information, we briefly describe the Bayesian
approach, already examined in [36]. This will be useful as a conceptual
introduction to the belief propagation algorithm.

Let us denote by $\\{\textbf{s}\\}$ the set of all possible configurations of
node signs in $G$, and by s a specific configuration. The conditional
probability $P(J^{o}|\textbf{s})$ that, given a configuration s, a specific
$J^{o}$ is observed, is

$P(J^{o}|\textbf{s})=\prod_{(i,j)\in E}\Psi(J^{o}_{ij}|J_{ij}),$ (4)

where the product is over all the connected nodes in $G$ and $\Psi$ is the
probability of observing $J^{o}_{ij}$ given $J_{ij}$. From Eq. 2,
$\Psi(J^{o}_{ij}|J_{ij})=1-r$ if $J^{o}_{ij}=J_{ij}$, and
$\Psi(J^{o}_{ij}|J_{ij})=r$ otherwise. The Bayes rule gives the conditional
probability $P(\textbf{s}|J^{o})$ that, given observations $J^{o}$, the true
configuration of the nodes’ signs in $G$ is s:

$P(\textbf{s}|J^{o})=\frac{P(J^{o}|\textbf{s})P(\textbf{s})}{\sum_{\textbf{s}\in\\{\textbf{s}\\}}P(J^{o}|\textbf{s})P(\textbf{s})},$
(5)

where $P(\textbf{s})$ is the a priori distribution of the nodes’ signs in $G$,
and the normalization is given by the sum over all possible configurations.

From Eq. 1, the opinion $o_{i}$ about node $i$ is obtained from the
probability $P(s_{i}=+1)$ that node $i$ is positive. Denoting by
$\\{\textbf{s}^{i}\\}$ the set of all configurations in which $s_{i}=+1$, we
can write:

$P(s_{i}=+1)=\sum_{\textbf{s}\in\\{\textbf{s}^{i}\\}}P(\textbf{s}|J^{o}).$ (6)

With this probability, we can also compute the average overlap as in Eq. 3.

The Bayesian approach described in this section is the optimal way to process
available information [36]. Nevertheless, its computation is hard and its
application is unfeasible from a cognitive point of view. Indeed, it requires
the knowledge of all the configurations in $\\{\textbf{s}\\}$: since each node
can be in two states (positive or negative), the number of configurations is
$2^{N}$. When $N$ is large enough, this is a computationally prohibitive
number even for computers.

In the following, we propose a heuristic opinion formation process where,
contrary to the Bayesian approach, the amount of information to be processed
is local and reasonable for a human observer.

###  2.3 Belief Propagation and opinion formation

We now introduce an opinion formation process, based on the well-known belief
propagation (BP) algorithm [47], where the observer walks through the network
starting from $i^{*}$ and gradually forms an opinion on each of the remaining
nodes $i\neq i^{*}$. The BP algorithm is based on the so-called message
passing. We first introduce the message $m_{i\to j}$ from node $i$ to node $j$
as a two-component vector

$m_{i\to j}=\left(\begin{array}[]{c}m_{i\to j}^{+}\\\ m_{i\to
j}^{-}\end{array}\right),$

where the first element can intuitively be understood as the observer’s
confidence stemming from the information about node $i$ that node $j$ is
positive; similarly, the second element indicates the observer’s confidence
that node $j$ is negative. The message from node $i$ to node $j$ is defined
recursively as the aggregation of all messages toward $i$ without the one
coming from $j$ (see Fig.1b):

$m_{i\to j}=\phi_{J_{ij}}(i,j)\prod_{z\in\partial i\setminus j}m_{z\to i}.$
(7)

Here, $\partial i\setminus j$ is the set of nodes, excluding $j$, connected to
$i$ in $G$. Notice that the product of the messages is a Hadamard product
[53], i.e., a component-wise product. $\phi_{J_{ij}}(i,j)$ is called the
compatibility matrix between node $i$ and node $j$ and is defined as

$\phi_{J_{ij}}(i,j)=\begin{pmatrix}1-r&r\\\ r&1-r\end{pmatrix}\quad\text{if
$J^{o}_{ij}=+1$}$ $\phi_{J_{ij}}(i,j)=\begin{pmatrix}r&1-r\\\
1-r&r\end{pmatrix}\quad\text{if $J^{o}_{ij}=-1$}$ (8)

and the product between this matrix and the vectors in Eq.7 is the standard
matrix product.

The compatibility matrix must be interpreted as the Bayesian information about
the sign of the link between node $i$ and node $j$ and is the local analogue
of Eq.5. Specifically, the terms in the diagonal of $\phi(i,j)$ represent the
probability that nodes $i$ and $j$ have the same sign given the observed value
of $J^{o}_{ij}$; Similarly, the terms in the anti-diagonal represent the
conditional probability that $i$ and $j$ have opposite signs.

Finally, the observer forms its opinion $o_{i}$ on node $i$ by multiplying all
its incoming messages:

$o_{i}=\frac{\prod_{z\in\partial i}m_{z\to i}}{Z},$ (9)

where $\partial i$ is the complete set of nodes connected to $i$ in $G$, and
$Z$ is the normalization given by

$Z:=\left(\prod_{z\in\partial i}m_{z\to
i}^{+}\right)+\left(\prod_{z\in\partial i}m_{z\to i}^{-}\right).$ (10)

Now, in the line of thought of [33], we can define our BP process of opinion
formation. Since at the beginning of the process the observer knows no nodes
except the seed node $i^{*}$, at time $t=0$ we set $m_{i\to j}=(1/2,1/2)$ for
any $i,j\neq i^{*}$, and $m_{i\to i^{*}}=o_{i^{*}}$ for any $i$. The process
continues as follows:

  1. 1.

at each time step $t$, choose a random node $i$ with $o_{i}=(1/2,1/2)$ that
has at least one neighbor on which the observer has an opinion different than
$(1/2,1/2)$;

  2. 2.

compute the messages toward $i$, i.e. $m_{j\to i}$ for any $j\in\partial i$,
as in Eq. 7;

  3. 3.

the observer’s opinion $o_{i}$ on $i$ is computed as in Eq. 9;

  4. 4.

return to step 1.

This process is repeated until $t=N-1$, when the observer has an opinion on
each node. In reality, however, people occasionally re-evaluate their beliefs.
We can include this re-evaluation in the model by running the opinion
formation process even for $t\geq N$ so that the observer evaluates more times
the same node. For $t\geq N$, the first step of the process is modified as
follows:

  1. 1.

at each time step $t\geq N$, choose a random node $i\neq i^{*}$.

This process is repeated until a desired time $t$ is reached.

In this way, opinion formation undergoes two different phases: when $t<N$, the
observer covers the entire information source network by exploring only the
unknown nodes; when $t\geq N$, the observer can jump randomly on any nodes, as
all nodes have already been explored in the past. When the observer passes
over the node $i$ several times, it means that he/she is updating his/her
opinion about $i$. Such an updated opinion is based on more information than
the opinion formed for the first time, as in the former case the messages
coming from all $i$’s neighbors have already been computed in previous steps.
The value $\tau=t/(N-1)$ thus represents the average number of times an
opinion is updated, and we shall refer to it as the observer’s thinking time.
We want to study the average overlap $q$ as a function of noise $r$, network
size $N$, and thinking time $\tau$. A related model, involving the
classification of nodes in a network into distinct groups based on network
topology observation, is known in the literature as the stochastic block
model. Its equilibrium state, corresponding to the infinite time case, has
been extensively studied using the cavity method from statistical mechanics
[54, 55]. It is worth mentioning that, for finite-size networks, the cavity
method is equivalent to belief propagation. Nevertheless, although our
approach bears similarities to the stochastic block model, it incorporates the
relationship between groups through the sign of the links, whereas the
stochastic block model considers the different probability of link presence
between elements of different groups: For an individual observer browsing a
network of information sources, they are a very different problem.

Figure 1: (a) An instance of the information source network: the black node
represents the seed node $i^{*}$ on which the observer has the opinion
$o_{i^{*}}=(1,0)$ (in the figure, we assume that $s_{i^{*}}=+1$); the gray
nodes are the sources on which the observer will have to form an opinion; the
solid lines represent the positive links between sources while the dashed
lines represent the negative links between sources. Note that the figure
depicts the relationships observed by the individual (not those in the ground
truth network). Indeed, there are some triangles that violate Heilder’s
balance rule. (b) A graphical representation of the message passing rule in
the belief propagation algorithm: the message from node $a$ to node $x$ is
given by the product of the messages toward $a$, excluding the one from $x$,
multiplied by the compatibility matrix in Eq.8. Finally, the opinion on $x$,
$o_{x}$, is given by the product of all messages toward $x$.

It is now worth dwelling on the interpretation of our BP opinion formation
mechanism. In fact, at first glance, one might think that the computations
described in this section are too intricate to be performed in our everyday
reasoning. Here are some remarks to explain the connection between the belief
propagation algorithm and human reasoning. First, let us elucidate the role of
the compatibility matrix in Eq.8. When we observe the current relationship
between two sources of information, we are aware, based on our experience,
that it gives insights into the true relationship between the two parties but,
at the same time, also that such insights can be misleading. For example,
consider the case of anti-vax people: how likely is it that two individuals,
both anti-vax (thus with $J^{o}_{ij}=+1$), also have the same general
worldview (i.e., $J_{ij}=+1$)? The compatibility matrix answers this question
by incorporating the observer’s awareness of the reliability of the observed
relations. In this case, it is well known that supporting conspiracy theories
about vaccines is strongly correlated with supporting populist political
beliefs and distrusting of elites and experts [56, 57, 58]. Naturally, this is
not always the case: assuming that the noise is $r=0.1$, this is true $90\%$
of the time. In Bayesian reasoning, this data represents the likelyhood of
$J_{ij}=+1$ or $J_{ij}=-1$ given a fixed $J^{o}_{ij}$. In turn, this is used
by the observer to infer the posterior probability that $J_{ij}=+1$ or
$J_{ij}=-1$ given the observed $J^{o}_{ij}$, corresponding to the elements of
$\phi_{J_{ij}}(i,j)$.

Once the posterior distribution of the link’s sign connecting a node $i$ to a
node $j$ is known, Eq.7 corresponds to aggregating all the information on node
$i$ from its neighbors. Thus, by combining the information on $i$ with the
probabilities in $\phi_{J_{ij}}(i,j)$, the observer can extract information
about $j$, with the support of the balance rule postulate (i.e., two nodes
have a positive relationship if they have the same sign and a negative
relationship otherwise). The final opinion on a node is then the aggregation
of all messages directed to that node.

Unlike in the optimal Bayesian approach, in the BP approach, the observer
needs only local information. Indeed, to form an opinion on a node, the
observer must only know its neighbors. Hence, our BP heuristic is a feasible
strategy for a human observer with limited computation capabilities. Moreover,
there is strong behavioral and physiological evidence that the brain
represents probability distributions and performs local Bayesian inference
[59, 59, 60, 61]. Therefore, it is a plausible hypothesis that our BP
mechanism may occur even spontaneously during individuals’ opinion formation
process.

###  2.4 Other heuristic processes

As a benchmark, we also study and extend other processes proposed in the
literature. In particular, we focus on the so-called majority rule (MR) and
random neighbor (RN) processes [33, 36].

#### Majority rule process

With the basic framework described above, the MR process is defined as follows
[36]. At time $t=0$, the opinion on the seed node is $o_{i^{*}}$; while for
each $i\neq i^{*}$, the initial opinion is $o_{i}=(0,0)$. The following steps
are iterated:

  1. 1.

at each time step $t$, choose a random node $i$ with $o_{i}=(0,0)$ that has at
least one neighbor on which the observer has an opinion different than
$(0,0)$;

  2. 2.

for any $j\in\partial i$ such that $o_{j}\neq(0,0)$, compute its vote $v_{j}$:

$v_{j}=\begin{cases}+J_{ij}^{o}&\mbox{if }o_{j}=(1,0)\\\ -J_{ij}^{o}&\mbox{if
}o_{j}=(0,1)\end{cases}$

  3. 3.

if $\sum_{j}v_{j}>0$, then $o_{i}=(1,0)$. If $\sum_{j}v_{j}<0$, then
$o_{i}=(0,1)$. If $\sum_{j}v_{j}=0$, then $o_{i}=(1,0)$ or $o_{i}=(0,1)$ with
equal probability;

  4. 4.

return to step 1.

These steps are repeated until all opinions are different from $(0,0)$, that
is, until $t=N-1$.

#### Random Neighbor process

At time $t=0$, the RN process has the same initial settings as the MR process.
Then, it proceeds as follows [33]:

  1. 1.

at each time step $t$, choose a random node $i$ with $o_{i}=(0,0)$ that has at
least one neighbor on which the observer has an opinion different than
$(0,0)$;

  2. 2.

chose a random node $j\in\partial i$ such that $o_{j}\neq(0,0)$.

  3. 3.

if $J^{o}_{ij}=+1$, then set $o_{i}=o_{j}$. If $J^{o}_{ij}=-1$, then set
$o_{i}=(1,1)-o_{j}$;

  4. 4.

return to step 1.

Again, these steps are repeated until $t=N-1$.

We introduce the thinking time $\tau$ also for MR and RN processes. When
$\tau>1$, the first step is modified for both as follows:

  1. 1.

at each time step $\tau\geq 1$, choose a random node $i\neq i^{*}$.

The next steps, instead, are the same as before and processes continue until a
desired $\tau$.

###  2.5 Interpretations and differences between the proposed opinion
formation processes

To elucidate the structural differences between the three heuristics presented
in this paper, some remarks are in order. First, in the RN process, the
observer forms his/her opinions on a node $i$ by using the information from
only one of its neighbors, whereas in both the MR and BP process the observer
aggregates the information from all $i$’s neighbors. Hence, for the RN
process, we expect a lower overlap $q$ (given the same amount of noise). On
the other hand, the observer with an RN strategy demands the least cognitive
and computational effort, while the cost of the BP and MR strategies grows
with the network’s average degree $\langle k\rangle$. Then, the difference
between the aggregate information of the MR and that of the BP processes lies
in the weight assigned to the information from each $i$’s neighbor.
Specifically, in the MR process, the observer gives the same weighs to all
$i$’s neighbors’ votes; in our BP process, instead, a message from a $i$’s
neighbor with $|\langle o\rangle|$ close to one (i.e., with small
uncertainty), is more informative and thus has a larger weight than a message
from a $i$’s neighbor with $|\langle o\rangle|$ close to zero (i.e., with
higher uncertainty). Therefore, the BP process should outperform the MR
process.

Second, in the MR and RN process, the opinion on a node can only be in two
states: either $(1,0)$ or $(0,1)$. So, in this case, the overlap in Eq.3 is
simply the difference between the average number of nodes where the observer’s
opinion matches the ground truth and that where it is opposite. Instead, in
the BP process, the opinion is probabilistic (see Eq. 1) and admits a wider
spectrum of possibilities. However, the interpretation of the overlap $q$ is
the same as in the case of the MR or RN mechanism provided that, at the end of
each realization of the process, the observer is forced to fix the value of
each node using the marginal values as the decision criteria. In practice, for
any $i$, the observer chooses $o_{i}=(1,0)$ with probability $P(s_{i}=+1)$,
and $o_{i}=(0,1)$ otherwise.

Last but not least, in both the MR and RN cases, opinion formation occurs with
the observer unaware of the noise in the system. As we discussed in section
2.3, instead, the observer in the BP process exploits the knowledge of the
noise to compute the posterior distributions in the compatibility matrix
$\phi_{J_{ij}}(i,j)$. To obtain this knowledge, the observer has to undertake
more extensive searches, and it is reasonable to assume that this involves
more cognitive effort.

In summary, all three processes proposed in this paper require having only
local information while exploring the network of information sources. However,
the RN process is the least expensive but also the least accurate of the
three; in contrast, the BP process requires the most effort but we expect it
to pay off with the best performance; the MR process lies in between.

##  3 Results and discussion

To perform our analysis, it is necessary to consider the a priori distribution
$P(\textbf{s})$ of the nodes’ signs in $G$. Since in each realization of the
source network, $s_{i}$ is +1 or -1 with equal probability, we have
$P(\textbf{s})=1/2^{N}$. This induces the wrong idea that we are facing a
highly complex model (NP-complete optimization problem, or spin glass like
[62, 63, 64]). However, in our analytical calculations, we use the fact that
it is computationally and statistically equivalent to a simpler model that,
using the physics terminology, belongs to the category of ferromagnetic models
[65]222The relationship between the noise $r$ and the temperature $T=1/\beta$
is given by $r(\beta)=\frac{e^{-\beta}}{2cosh(\beta)}$. It is a particularity
of the current model that the parameter $r$ defines both the disorder of the
system (through Eq.2) and its temperature. Disordered models can be hard to
treat, especially if the disorder is high and the temperature is low. However,
in our case, $r=0$ produces a $T=1/\beta=0$ temperature but in a fully
ferromagnetic model, which is easy because it has no disorder. In the other
extreme, $r=0.5$ produces a fully disordered model but at $T=\infty$, which is
again trivial. Furthermore, the relationship between disorder and temperature
in this model puts it on top of the so-called Nishimori line [66], for any
$r$. This means that the model passes from an uninformative phase (with $q\sim
0$) to a ferromagnetic phase (with $q>0$) without crossing any spin-glass
phase.. In particular, with the following transformation

$\forall_{(i,j):s_{i}=-1}[(s_{i}=1)\text{ and }\forall_{j\in\partial
i}(J_{ij}=-J_{ij})]$

we redefine all nodes to be of type +1 while changing the $J_{ij}$ to have the
same statistic as in Eq.2. Hence, the transformed ground truth network $G$ has
$s_{i}=1$ for any $i$, and the fraction of misleading links observed by the
individual is $r$. In this way, the average overlap in Eq.3 is the sum of the
opinion’s expected values divided by $N$. In the physics literature, this is
often called a gauge transformation [66].

In the following sections, we start by studying the equilibrium solution
(i.e., for $\tau\to\infty$) of the three heuristic rules (in the RN case, we
obtain an analytical solution even for a finite thinking time). Finally, with
numerical simulations, we compare their performances for any $\tau$.

###  3.1 Equilibrium belief propagation process

We first study analytically the properties of the BP process at the
equilibrium, i.e., when $\tau\to\infty$.

Let us rewrite the message updating equation (7) in the following normalized
form:

$m_{i\to j}^{+}=\frac{1}{Z^{*}}\sum_{s=1,2}\phi^{+}(s)\prod_{z\in\partial
i\setminus j}m_{z\to i}(s),$ (11)

where $\phi^{+}(s)$ is the $s$-th element of the first row of matrix
$\phi_{J_{ij}}(i,j)$ in Eq.8 (we denote the second row as $\phi^{-}$),
$m_{z\to i}(s)$ is the $s$-th element of the $m_{z\to i}$ vector, and $Z^{*}$
is the normalization constant given by

$Z^{*}:=\sum_{(a=\pm)}\sum_{s=1,2}\phi^{a}(s)\prod_{z\in\partial i\setminus
j}m_{z\to i}(s).$ (12)

In this way, we have $m^{-}_{i\to j}=1-m^{+}_{i\to j}$. Now, let us denote the
message in Eq.11 as a function of $\phi^{+}$ and all messages $m_{z\to i}$ for
$z\in\partial i\setminus j$, i.e. $m^{+}_{i\to j}\equiv f(\phi^{+},m_{z\to
i},z\in\partial i\setminus j)$. The distribution of $m_{i\to j}^{+}$ can be
written recursively as

$P(m_{i\to j}^{+})=\mathbf{E}_{J^{o}}\Bigg{[}\int\prod_{z\in\partial
i\setminus j}dm^{+}_{z\to i}P(m_{z\to j}^{+})\delta(m_{i\to
j}^{+}-f)\Bigg{]},$ (13)

where the expected value is over the observed relation matrix $J^{o}$. At the
equilibrium, for $N$ sufficiently large, messages for every neighbour of node
$i$ are equal, i.e. $m^{+}_{z\to i}=m^{+}_{z^{\prime}\to i}\equiv m^{+}$ for
$z,z^{\prime}\in\partial i$. Assuming that the number of neighbors of $i$ is
exactly $k$, the expected value of $m^{+}_{i\to j}$ can be written as

$\int
dm^{+}P(m^{+})m^{+}=\mathbf{E}_{J^{o}}\Bigg{[}\int\prod^{k-1}dm^{+}f(m^{+},\phi^{+})P(m^{+})\Bigg{]}.$
(14)

This equation is obtained by multiplying Eq.13 by $m^{+}$, integrating over
all its possible values, and then applying the Dirac delta on the right-hand
side. Since, for $t\to\infty$, the overlap is $q=2m^{+}-1$, Eq.14 can be
solved numerically to obtain the equilibrium overlap $q$ as a function of
noise $r$. A trivial solution is when no information on nodes’ signs can be
retrieved from the messages interactions, i.e., when all messages are $1/2$.
By performing a stability analysis of this trivial solution, we find that
there exists a phase transition at a critical noise value $r_{c}$ below which
the infinite-time overlap is non-zero. To show this, let us expand Eq.14
around $m^{+}=1/2$. In particular, for some small $\epsilon$, we set
$m^{+}=1/2+\epsilon$ and $m^{-}=1/2-\epsilon$. In this way, using $\int
dm^{+}P(m^{+})=1$ and writing explicitly the function $f$, Eq.14 becomes

$\frac{1}{2}+\epsilon=\frac{1}{Z^{*}}\mathbf{E}_{J^{o}}\Bigg{[}\frac{1}{2^{k-1}}+(k-1)[\phi^{+}(1)-\phi^{+}(2)]\epsilon\Bigg{]}.$
(15)

Noting that the partition function is $Z^{*}=\frac{1}{2^{k-2}}$ (as
$\phi^{+}(1)+\phi^{+}(2)=1$) and
$\mathbf{E}_{J^{o}}[\phi^{+}(1)-\phi^{+}(2)]=(1-2r)^{2}$, the condition for
which Eq.14 has exactly one fixed point is

$(1-2r)^{2}<\frac{1}{k-1}\implies r_{c}=\frac{1}{2}-\frac{1}{2\sqrt{k-1}}.$
(16)

This stability analysis is equivalent to the replica symmetric computation of
the transition temperatures in disorder systems [67]. When $r>r_{c}$, there is
only one solution to Eq.14 corresponding to the one with non-informative
messages and hence with $q=0$. On the other hand, when $r<r_{c}$, the overlap
is different from zero and, since we consider a positive seed node, we have
$q>0$. Fig.2a shows the phase diagram of the equilibrium overlap in the BP
process in the $[k,r]$ parameter space. It shows that numerical simulations
are consistent with Eq.16.

Figure 2: (a) Phase diagram of the equilibrium BP process in the $[r,k]$ space
(where $r$ is the noise and $k$ the average degree. Colors represent the
values of the average overlap $\langle q\rangle$. Each pixel in the phase
diagram is the average of 500 simulations of the BP process in a source
network with $N=1000$ nodes. The solid line corresponds to Eq.16. (b) Average
overlap $\langle q\rangle$ against noise $r$ in the equilibrium MR process for
different average degree $k$. Each point is the average of 1000 simulations
with $N=1000$ nodes. Vertical lines shows the theoretical values of the noise
tipping point predicted by Eq.17 for the corresponding $k$.

This result implies that, when $N$ is sufficiently large, there exists a noise
threshold above which an observer that lingers on the network for an infinite
time is unable to extract any information about the sources’ reliability.
However, when $r<r_{c}$, the overlap limit is non-zero and the observer’s
opinions are not random. Note that, with the standard assumption that the BP
algorithm determines the correct marginals probabilities [54], the above
result is true for any algorithm: when the noise is larger than $r_{c}$, no
heuristic rules or algorithms can detect the real nature of the information
sources.

###  3.2 MR and RN processes

As with the BP process, because of the strong non-linearity of the MR process,
we treat analytically only its equilibrium state. With a stability analysis
analogous to that performed for the BP heuristic, we again find that, for $N$
large enough, there is a noise threshold above which the individual’s opinions
for $\tau\to\infty$ are random (not correlated with the ground truth). This
critical noise is given by (detailed calculations are shown in Appendix A):

$r_{c}=\frac{1}{2}-\frac{2^{k-2}}{\sum_{i=\left\lfloor{k/2}\right\rfloor+1}^{k}\binom{k}{i}(2i-k)}.$
(17)

However, this result is valid only in the large $k$ limit. Whether there is a
real phase transition for small average degrees is an open question.
Nevertheless, even for small $k$, Eq.17 gives us a tipping point beyond which
the majority rule is no longer efficient in extracting information from the
source network, as shown in Fig.2b.

Given the simplicity of the opinion formation rule of the RN process, we can
solve it analytically even for finite $\tau$ and $N$. Let us first show the
results for $\tau=1$, i.e., $t=N-1$, already known in the literature. Through
a master equation approach, it is possible to show that, given a network size
$N$ and a noise $r$, the expected value of $q$ is given by [33, 36]

$\langle
q(N,r)\rangle^{RN}_{\tau=1}=\frac{\Gamma(N+1-2r)}{N\Gamma(N)\Gamma(2-2r)},$
(18)

which, as expected, simplifies to $1$ for $r=0$, and to 0 for $r=1/2$.
Moreover, it decreases rapidly with $r$, as widely discussed in [33]. By
expanding Eq.18 for large $N$, we have

$\langle q(N,r)\rangle^{RN}_{\tau=1}\sim N^{-2r},$ (19)

showing that, for $r>0$ and $\tau=1$, the overlap goes to 0 in the
$N\to\infty$ limit. Hence, an observer who navigates the source network for a
short time ($\tau=1$) using the RN rule does not get an encouraging result:
his/her opinions would tend to be totally random for large network sizes,
regardless of how small is the noise (excluding the $r=0$ case).

With a similar approach, we can also study the case $\tau>1$, showing that the
observer’s performance does not improve. In particular, we can write the
expected value of $q$ for $\tau>1$ as (the detailed calculations are in
appendix B):

$\langle
q(N,r)\rangle^{RN}_{\tau>1}=q_{1}\left(1-\frac{2r}{N}\right)^{(\tau-1)(N-1)},$
(20)

where $q_{1}:=\langle q(N,r)\rangle^{RN}_{\tau=1}$. Fig.3 shows that Eq.20 is
consistent with numerical simulations. As for the $\tau=1$ case, the overlap
for $\tau>1$ decreases rapidly with noise. Moreover, it is straightforward to
show that, when fixing $\tau$ and $r$, the behavior of Eq.20 with $N$ is the
same as that of Eq.19. At the same time, when $N$ and $r$ are fixed, Eq.20
decreases exponentially with the thinking time, asymptotically reaching 0 for
$\tau\to\infty$. Notice also that all the above results on the RN process do
not depend on the average degree $k$ (provided we neglect any finite-size
effect). This was expected since, with the RN heuristic, the observer uses
information from only one neighbor of the target node, regardless of its
degree.

These findings show that the performance of the RN process not only decreases
with the number of information sources but, unlike the BP and MR heuristics,
also decreases with the time it spends for the observer to form opinions,
regardless of how small the noise is. In short, the RN process, although it
requires the least cognitive effort, is not a good strategy for forming
opinions about a world of interconnected sources of information. Moreover, if
the observer spends more time trying to infer the correct opinions with the RN
rule, the performance is even worse.

Figure 3: (a) Expected value of the overlap $\langle q(N,r)\rangle^{RN}_{c>1}$
vs thinking time $\tau=t/(N-1)$ for the RN process with different level of
noise $r$. (b) Expected value of the overlap $\langle
q(N,r)\rangle^{RN}_{c>1}$ vs noise $r$ for different values of the thinking
time $\tau$. In both panels: each point is the average of 1000 simulations
with $N=1000$ nodes and average degree $k=200$; solid lines correspond to
Eq.20

###  3.3 Performance comparison

From the findings above, it is evident that, at the equilibrium, the RN
process is the least efficient. Indeed, for $t\to\infty$, the overlap is 1/2
regardless of the noise level and the source network size. In the equilibrium
BP and MR processes, however, $q$ can be larger than 1/2. In particular, in
the large $N$ limit, there is a critical noise value below which $q>1/2$.
Comparing the critical noise of the BP and the MR process, Eqs.16 and 17, we
observe that the former is always larger than the latter. It implies that when
opinion formation with the MR strategy ceases to be informative, the BP
strategy can still extract knowledge about the ground truth network. Said
otherwise: the BP process is more tolerant to noise than the MR process.

Then, from numerical simulations, we find that the equilibrium overlap of the
BP process is larger than that of the MP process even when $r<r_{c}$, for any
$k$ and $N$ (see Fig.4). These results are the consequence that in the BP
heuristic the observer weighs the information from the neighbors of each node
and harnesses the noise awareness to its advantage, as already mentioned. From
these considerations, it is natural that the performance of the BP process at
equilibrium is better than that of the MR process.

Furthermore, while it is obvious that both processes at equilibrium improve
their performance as $k$ increases (as they can collect more information from
the surroundings of each node), interestingly, the overlap for $t\to\infty$ of
both processes (with $k$ fixed) decreases with $N$, until their convergence
values. When the number of information sources is larger, the evaluation
errors have more space to propagate and amplify the difference between the
observer’s opinions and the ground truth. This effect is most pronounced
around the critical noise, where correlations between opinions in finite
systems are most relevant. In light of these findings, we conjecture that, in
random sources networks, any local heuristic rule makes individuals’ opinions
fragile to the number of information sources they must deal with. However,
when opinions are the result of the aggregation of information from multiple
sources, the decrease in performance slows down for larger $N$ until it stops
when the phase transition in $r_{c}$ can actually be observed. In fact, note
that for finite $N$ the equilibrium overlap $q$ for both the BP and MR cases
is a continuous and derivable function and that the calculations to obtain
$r_{c}$ were performed in the so-called thermodynamic limit where the finite
size effects can be neglected. The point about phase transitions being a
property of infinite systems is a general clue from statistical physics [68,
69].

Figure 4: (a) Equilibrium average overlap $\langle q\rangle$ against noise $r$
for both the MR and the BP process with different network sizes $N$ and with
average degree $k=5$. (b) Same as panel (a) with average degree $k=30$. In
both panels: each point is the average over 1000 realizations.

Let us now study the more realistic case where the observer spends a limited
time navigating the network of information sources. As shown in section 3.2,
the RN overlap is strongly sensitive to noise and decreases exponentially with
$N$ up to the limiting value of 1/2 for $N\to\infty$. Fig.5a compares the
results for different $\tau$ in the BP and MR cases, showing that their
overlaps decrease less dramatically with noise. Note that, for small $\tau$,
the BP and MR processes have similar performances; instead, with large $\tau$,
The BP strategy is significantly better than the MR one. This means that the
benefit of spending time trying to form the correct opinions is larger in the
case of the BP process. This is even more evident in Fig.5b which shows the
overlap as a function of $\tau$ for the BP and MR processes.

Figure 5: (a) Equilibrium average overlap $\langle q\rangle$ against noise $r$
for both the MR and the BP process with different thinking times $\tau$. (b)
Equilibrium average overlap $\langle q\rangle$ against thinking time $\tau$
for both the MR and the BP process with different noise $r$. In both panels:
each point is the average over 1000 realizations with network size $N=1000$
and average degree $k=10$.

Remember that, for the RN process, the performance decreases exponentially
with time up to the limit value of 1/2 in its steady state, regardless of $r$.
The reason for this decrease stems from the opinion formation rule that relies
on a randomly chosen neighbor of the target node. Indeed, the noise in the
sources network accumulates with the opinion updating, amplifying the
difference between the observer’s opinions and the ground truth. Notably, this
phenomenon is reversed for the BP and MR processes: as the thinking time
increases, the overlap in both processes increases to its equilibrium value.
This happens since both strategies aggregate information from all neighbors of
a target node, with the effect of correcting errors instead of accumulating
them. Again, from Fig.5, we see that the BP performance improvement with the
thinking time is much faster than that of the MR process. Indeed, in the BP
process, the observer’s opinions are probabilistic and allow uncertainties. As
already mentioned, this results in a more careful aggregation of information
which, as the thinking time increases, implies a higher capacity to identify
reliable sources of information. In general, the more the opinion formation
strategy is cognitively involved, the more it pays to think long and hard;
conversely, lazier heuristic rules require more instinctive decisions.
Finally, for the same reasons discussed in the previous section, the
performance of both processes increases with $k$ and decreases with $N$,
independently of $\tau$. Since we do not have an analytic solution away from
the equilibrium, whether the BP and MR overlaps converge to a finite value
when the network size becomes infinite remains an open question.

##  4 Conclusion

To summarize, we have reformulated the mechanism of the well-known belief
propagation algorithm in the context of opinion formation. We proposed a
probabilistic and local heuristic rule by which an individual extracts
information from a system of interconnected sources to identify which among
them are credible and which are not. Based on recent empirical evidence on the
functioning of human reasoning, we claim that our model can realistically
describe one of the mechanisms underlying the individuals’ spontaneous opinion
formation process. Thus, the next step would be to gauge it with real data and
experiments. In addition, we have shown that our approach performs better than
existing local heuristic rules in the literature: It is less sensitive to both
structural noise and the size of the network of information sources; it also
benefits more from the thinking time that individuals spend forming their
opinions. However, we have shown that the efficiency of any local heuristic
decreases as the number of information sources increases and that a phase
transition is observed at equilibrium: even with our belief propagation
approach, above a critical level of noise the individual’s opinions are
random.

These findings, although less pessimistic than the conclusions in [33], still
hint that the reliability of the opinions of individuals with limited
computation capabilities can be easily compromised, paving the way for the
spread of misinformation. However, we provide a realistic framework that shows
what are the conditions under which this is most likely. For this reason, we
believe that our model is a useful tool for studying strategies to help people
become properly informed. At the same time, our work is strongly related and
contributes to the literature on human learning with bounded rationality (see,
for example, [70, 71]).

Our model can be extended in many directions. First, note that we only
addressed the case of a random source network. On the one hand, this has many
advantages since, in random networks, it can be proven that the equilibrium
belief propagation algorithm is a good approximation of the optimal Bayesian
computation [47]. However, in the real world we observe different types of
networks, and therefore, in future research, it may be insightful to study how
the performance of our belief propagation process varies in more complex
network topologies.

Second, for the sake of simplicity, we assumed that the noise, and thus the
compatibility matrices, are the same for every link in the network. However,
in the real world, different sources have different relationships, and thus
the structural noise is also not the same. Hence, future models could
investigate how different noise distributions among links in the source
network affect the outcomes of opinion formation heuristic rules. Moreover, a
limitation of our model over existing ones is that we must rely on the somehow
strong assumption that the observer knows the true magnitude of the noise.
However, Bayesian estimates of the human brain are imperfect, and this could
be encoded in our model by defining another noise that affects the observer’s
estimate of the original noise. In this way, the compatibility matrices would
be stochastic quantities. Another possibility to relax the assumption of
perfect noise knowledge would be to design models by which the observer can
“learn” and infer the noise in the network before the opinion formation
process begins.

Finally, note that this paper investigates only one aspect of opinion
formation, i.e., solitary opinion formation without social interaction. In
contrast, previous literature has mostly focused on the social aspect of
opinion propagation. Thus, the natural next step is to combine our heuristic
rule with social influence.

#### Acknowledgements

We thank M. Medo and Y.C. Zhang who helped to improve this paper by their
comments.

#### Author contributions

E.M.F. and A.L.C. contributed equally to this work.

#### Competing Interests statement

The authors declare no competing interests.

##  Appendix A Derivation of the MR tipping noise

Here, we derive Eq.17. Let us denote by $P_{i}(t)$ the probability that, with
the MR heuristic, the observer has the correct opinion on node $i$ at time
$t$, i.e., $o_{i}(t)=(1,0)$ (under the gauge transformation). When the source
network size $N$, the average degree $k$, and time $t$ are large enough, we
can neglect correlations and assume $P_{i}(t)=P_{j}(t)\equiv P(t)$ for each
$i$ and $j$. In this way, we can write

$P(t+1)=P(t)\frac{N-1}{N}+\frac{1}{N}\sum_{i=\left\lfloor{k/2}\right\rfloor+1}^{k}\binom{k}{i}W_{t}^{i}(1-W_{t})^{k-i}.$
(A.1)

The first term on the right-hand side is the probability that the observer, at
time $t$, has the correct opinion on the target node and that the latter is
not chosen by the observer at time $t+1$ (recall that, for $t>N-1$, the
observer chooses, at each time step, a random node). The second term is the
probability that the target node is chosen at time $t+1$ and that the observer
forms the correct opinion. Here, $W_{t}$ is the probability that the vote $v$
of a node toward the considered node is positive (at time $t$), i.e.,
$W_{t}\equiv(1-2r)P(t)+r$. Note that in Eq.A.1 we have implicitly made two
further approximations: first, we have again assumed that the number of
neighbors of each node exactly matches the average degree $k$; second, we have
neglected the probability that $v=0$ (possible only when $k$ is even), i.e.,
we did not include in the sum the term
$\frac{1}{2}\binom{k}{k/2}[W(1-W)]^{k/2}$ (however, in the critical noise
calculation shown below, this term would not affect the result).

Now, at equilibrium we have $P(t+1)=P(t)\equiv P$ and $W_{t}\equiv W$. Thus,
Eq.A.1 becomes

$P=\sum_{i=\left\lfloor{k/2}\right\rfloor+1}^{k}\binom{k}{i}W^{i}(1-W)^{k-i}.$
(A.2)

We observe that when $r=1/2$ the only possible solution to this equation is
$P=1/2$; on the other hand, when $r=0$, there are three possible solutions,
i.e., $P=\pm 1$ and $P=1/2$. Therefore, we expect that there exists a critical
noise $r=r_{c}$ such that, for $r<r_{c}$ and a positive seed node, $P>1/2$ and
thus $q>0$ for $\tau\to\infty$. Indeed, expanding to first order Eq.A.2 around
$P=1/2$, and solving the equation for $r$, we retreive Eq.17.

##  Appendix B Derivation of the RN overlap

Here, we derive Eq.20. Let us define the probability $P(x,t)$ that, at time
$t$, the number of correct opinions with the RN heuristic (and thus
corresponding to $(1,0)$ due to the gauge transformation) is $x$. At each time
step, $x$ can increase or decrease by one, or remain the same. Thus, the
master equation of the RN process has the form

$P(x,t+1)=P(x-1,t)W(x-1\to x)+P(x+1,t)W(x+1\to x)+P(x,t)W(x\to x),$ (B.1)

where $W(x\to y)$ is the transition probability that the number of correct
opinions becomes $y$ from $x$. To increase $x$ by one, the observer must pass
over a node with an incorrect opinion and reevaluate it correctly. The
probability that this occurs corresponds to $W(x-1\to x)$, which, for a given
$r$, is given by

$W(x-1\to
x)=\frac{N-x+1}{N}\left[\frac{x-1}{N-1}(1-r)+\frac{N-x}{N-1}r\right].$ (B.2)

Here, the first factor is the probability of choosing a node with an incorrect
opinion. The second factor is the probability that the opinion on that node is
reevaluated correctly. Similarly, we can write

$W(x+1\to x)=\frac{x+1}{N}\left[\frac{x}{N-1}r+\frac{N-1-x}{N-1}(1-r)\right].$
(B.3)

The transition probability $W(x\to x)$, instead, is given by the probability
that the observer does not change his/her past opinion on a node. This is

$W(x\to x)=\frac{x}{N}\left[\frac{x-1}{N-1}(1-r)+\frac{N-x}{N-1}r\right]\\\
+\frac{N-x}{N}\left[\frac{x}{N-1}r+\frac{N-1-x}{N-1}(1-r)\right].$ (B.4)

Now, by multiplying both sides of Eq.B.1 by $x$, summing over all possible
$x$, and considering sufficiently large $N$, we can rearrange Eq.B.1 to obtain

$\langle x(t+1)\rangle=\langle x(t)\rangle\left(1-\frac{2r}{N}\right)+r.$
(B.5)

Since the relation between $x$ and $q$ is $Nq=2x-1$, Eq.B.5 is a recursive
equation that must be solved with the initial condition

$\langle x(N-1)\rangle=\frac{Nq_{1}-1}{2},$

where $q_{1}:=\langle q(N,r)\rangle^{RN}_{\tau=1}$. Finally, from the solution
of Eq.B.5, we can write the expected value of $q$ for $\tau>1$ as in Eq.20.
Notice that this result better reproduces the numerical simulations when the
information source network is not sparse (i.e. when $k$ is sufficiently large)
so that the proportion of correct opinions in the transition probabilities of
Eq.B.2, B.3, and B.4 is better approximated.

## References

  * [1] David MJ Lazer, Matthew A Baum, Yochai Benkler, Adam J Berinsky, Kelly M Greenhill, Filippo Menczer, Miriam J Metzger, Brendan Nyhan, Gordon Pennycook, David Rothschild, et al.  The science of fake news.  Science, 359(6380):1094–1096, 2018.
  * [2] Chengcheng Shao, Giovanni Luca Ciampaglia, Onur Varol, Kai-Cheng Yang, Alessandro Flammini, and Filippo Menczer.  The spread of low-credibility content by social bots.  Nature communications, 9(1):1–9, 2018.
  * [3] Andrew M Guess, Brendan Nyhan, and Jason Reifler.  Exposure to untrustworthy websites in the 2016 us election.  Nature human behaviour, 4(5):472–480, 2020.
  * [4] Riccardo Gallotti, Francesco Valle, Nicola Castaldo, Pierluigi Sacco, and Manlio De Domenico.  Assessing the risks of ‘infodemics’ in response to covid-19 epidemics.  Nature human behaviour, 4(12):1285–1293, 2020.
  * [5] Michela Del Vicario, Alessandro Bessi, Fabiana Zollo, Fabio Petroni, Antonio Scala, Guido Caldarelli, H Eugene Stanley, and Walter Quattrociocchi.  The spreading of misinformation online.  Proceedings of the national academy of Sciences, 113(3):554–559, 2016.
  * [6] Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, H Eugene Stanley, and Shlomo Havlin.  Local structure can identify and quantify influential global spreaders in large scale social networks.  Proceedings of the National Academy of Sciences, 115(29):7468–7472, 2018.
  * [7] Alessandro Bessi, Mauro Coletto, George Alexandru Davidescu, Antonio Scala, Guido Caldarelli, and Walter Quattrociocchi.  Science vs conspiracy: Collective narratives in the age of misinformation.  PloS one, 10(2):e0118093, 2015.
  * [8] Jonas L Juul and Johan Ugander.  Comparing information diffusion mechanisms by matching on cascade size.  Proceedings of the National Academy of Sciences, 118(46):e2100786118, 2021.
  * [9] Ana Lucía Schmidt, Fabiana Zollo, Michela Del Vicario, Alessandro Bessi, Antonio Scala, Guido Caldarelli, H Eugene Stanley, and Walter Quattrociocchi.  Anatomy of news consumption on facebook.  Proceedings of the National Academy of Sciences, 114(12):3035–3039, 2017.
  * [10] Neil F Johnson, Nicolas Velásquez, Nicholas Johnson Restrepo, Rhys Leahy, Nicholas Gabriel, Sara El Oud, Minzhang Zheng, Pedro Manrique, Stefan Wuchty, and Yonatan Lupu.  The online competition between pro-and anti-vaccination views.  Nature, 582(7811):230–233, 2020.
  * [11] Michela Del Vicario, Walter Quattrociocchi, Antonio Scala, and Fabiana Zollo.  Polarization and fake news: Early warning of potential misinformation targets.  ACM Transactions on the Web (TWEB), 13(2):1–22, 2019.
  * [12] Jamal Abdul Nasir, Osama Subhani Khan, and Iraklis Varlamis.  Fake news detection: A hybrid cnn-rnn based deep learning approach.  International Journal of Information Management Data Insights, 1(1):100007, 2021.
  * [13] Fabiana Zollo, Alessandro Bessi, Michela Del Vicario, Antonio Scala, Guido Caldarelli, Louis Shekhtman, Shlomo Havlin, and Walter Quattrociocchi.  Debunking in a world of tribes.  PloS one, 12(7):e0181821, 2017.
  * [14] Aditi Gupta, Ponnurangam Kumaraguru, Carlos Castillo, and Patrick Meier.  Tweetcred: Real-time credibility assessment of content on twitter.  In Social Informatics: 6th International Conference, SocInfo 2014, Barcelona, Spain, November 11-13, 2014. Proceedings 6, pages 228–243. Springer, 2014.
  * [15] Jacob Ratkiewicz, Michael Conover, Mark Meiss, Bruno Gonçalves, Alessandro Flammini, and Filippo Menczer.  Detecting and tracking political abuse in social media.  In Proceedings of the International AAAI Conference on Web and social media, volume 5, pages 297–304, 2011.
  * [16] Thomas J Leeper and Rune Slothuus.  Political parties, motivated reasoning, and public opinion formation.  Political Psychology, 35:129–156, 2014.
  * [17] Harold B Gerard and Ruben Orive.  The dynamics of opinion formation.  In Advances in experimental social psychology, volume 20, pages 171–202. Elsevier, 1987.
  * [18] Noah E Friedkin and Francesco Bullo.  How truth wins in opinion dynamics along issue sequences.  Proceedings of the National Academy of Sciences, 114(43):11380–11385, 2017.
  * [19] Noah E Friedkin and Eugene C Johnsen.  Social influence and opinions.  Journal of Mathematical Sociology, 15(3-4):193–206, 1990.
  * [20] X Flora Meng, Robert A Van Gorder, and Mason A Porter.  Opinion formation and distribution in a bounded-confidence model on various networks.  Physical Review E, 97(2):022312, 2018.
  * [21] Mahdi Jalili.  Social power and opinion formation in complex networks.  Physica A: Statistical mechanics and its applications, 392(4):959–966, 2013.
  * [22] Daron Acemoglu and Asuman Ozdaglar.  Opinion dynamics and learning in social networks.  Dynamic Games and Applications, 1:3–49, 2011.
  * [23] Alessandro Di Mare and Vito Latora.  Opinion formation models based on game theory.  International Journal of Modern Physics C, 18(09):1377–1395, 2007\.
  * [24] Fabian Baumann, Philipp Lorenz-Spreen, Igor M Sokolov, and Michele Starnini.  Modeling echo chambers and polarization dynamics in social networks.  Physical Review Letters, 124(4):048301, 2020.
  * [25] Tuan M Pham, Andrew C Alexander, Jan Korbel, Rudolf Hanel, and Stefan Thurner.  Balance and fragmentation in societies with homophily and social balance.  Scientific Reports, 11(1):17188, 2021.
  * [26] Frank Schweitzer.  Sociophysics.  Phys. Today, 71(2):40, 2018.
  * [27] Javier Alvarez-Galvez.  Network models of minority opinion spreading: Using agent-based modeling to study possible scenarios of social contagion.  Social Science Computer Review, 34(5):567–581, 2016.
  * [28] Jonas S Juul and Mason A Porter.  Hipsters on networks: How a minority group of individuals can lead to an antiestablishment majority.  Physical Review E, 99(2):022313, 2019.
  * [29] Sidney Redner.  Reality-inspired voter models: A mini-review.  Comptes Rendus Physique, 20(4):275–292, 2019.
  * [30] Enrico Maria Fenoaltea, Fanyuan Meng, Run-Ran Liu, and Matúš Medo.  Phase transitions in growing groups: How cohesion can persist.  Physical Review Research, 5(1):013023, 2023.
  * [31] Tuan Minh Pham, Jan Korbel, Rudolf Hanel, and Stefan Thurner.  Empirical social triad statistics can be explained with dyadic homophylic interactions.  Proceedings of the National Academy of Sciences, 119(6):e2121103119, 2022.
  * [32] Fanyuan Meng, Jiadong Zhu, Yuheng Yao, Enrico Maria Fenoaltea, Yubo Xie, Pingle Yang, Run-Ran Liu, and Jianlin Zhang.  Disagreement and fragmentation in growing groups.  Chaos, Solitons & Fractals, 167:113075, 2023.
  * [33] Matúš Medo, Manuel S Mariani, and Linyuan Lü.  The fragility of opinion formation in a complex world.  Communications Physics, 4(1):1–10, 2021.
  * [34] David Easley, Jon Kleinberg, et al.  Networks, crowds, and markets.  Cambridge Books, 2012.
  * [35] Derek Hansen, Ben Shneiderman, and Marc A Smith.  Analyzing social media networks with NodeXL: Insights from a connected world.  Morgan Kaufmann, 2010.
  * [36] Fanyuan Meng, Matúš Medo, and Berno Buechel.  Whom to trust in a signed network? optimal solution and two heuristic rules.  Information Sciences, 2021.
  * [37] Ward Edwards.  Dynamic decision theory and probabilistic information processings.  Human factors, 4(2):59–74, 1962.
  * [38] Alexandre Pouget, Jan Drugowitsch, and Adam Kepecs.  Confidence and certainty: distinct probabilistic quantities for different goals.  Nature neuroscience, 19(3):366–374, 2016.
  * [39] Judea Pearl.  Probabilistic reasoning in intelligent systems: networks of plausible inference.  Morgan kaufmann, 1988.
  * [40] Nicholas M Harrigan, Giuseppe Joe Labianca, and Filip Agneessens.  Negative ties and signed graphs research: Stimulating research on dissociative forces in social networks.  Social Networks, 2020.
  * [41] Fritz Heider.  Attitudes and cognitive organization.  The Journal of psychology, 21(1):107–112, 1946.
  * [42] Michael Moore.  Structural balance and international relations.  European Journal of Social Psychology, 1979.
  * [43] Angela Fontan and Claudio Altafini.  A signed network perspective on the government formation process in parliamentary democracies.  Scientific reports, 11(1):5134, 2021.
  * [44] Giuseppe Facchetti, Giovanni Iacono, and Claudio Altafini.  Computing global structural balance in large-scale signed social networks.  Proceedings of the National Academy of Sciences, 108(52):20953–20958, 2011.
  * [45] Kahneman Daniel.  Thinking, fast and slow.  Farrar, Straus and Giroux, 2013.
  * [46] Gerd Gigerenzer and Wolfgang Gaissmaier.  Heuristic decision making.  Annual review of psychology, 62:451–482, 2011.
  * [47] Jonathan S Yedidia, William T Freeman, Yair Weiss, et al.  Understanding belief propagation and its generalizations.  Exploring artificial intelligence in the new millennium, 8(236-239):0018–9448, 2003.
  * [48] Jonathan S Yedidia, William Freeman, and Yair Weiss.  Generalized belief propagation.  Advances in neural information processing systems, 13, 2000.
  * [49] Fabrizio Altarelli, Alfredo Braunstein, Luca Dall’Asta, Alejandro Lage-Castellanos, and Riccardo Zecchina.  Bayesian inference of epidemics on networks via belief propagation.  Physical review letters, 112(11):118701, 2014.
  * [50] Frank R Kschischang, Brendan J Frey, and H-A Loeliger.  Factor graphs and the sum-product algorithm.  IEEE Transactions on information theory, 47(2):498–519, 2001.
  * [51] Brendan J Frey and Brendan J Frey.  Graphical models for machine learning and digital communication.  MIT press, 1998.
  * [52] Robert J. McEliece, David J. C. MacKay, and Jung-Fu Cheng.  Turbo decoding as an instance of pearl’s” belief propagation” algorithm.  IEEE Journal on selected areas in communications, 16(2):140–152, 1998.
  * [53] George PH Styan.  Hadamard products and multivariate statistical analysis.  Linear algebra and its applications, 6:217–240, 1973.
  * [54] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Inference and phase transitions in the detection of modules in sparse networks.  Physical Review Letters, 107(6):065701, 2011.
  * [55] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  Physical Review E, 84(6):066106, 2011.
  * [56] Matthew J Hornsey, Emily A Harris, and Kelly S Fielding.  The psychological roots of anti-vaccination attitudes: A 24-nation investigation.  Health psychology, 37(4):307, 2018.
  * [57] Matthew Motta, Timothy Callaghan, and Steven Sylvester.  Knowing less but presuming more: Dunning-kruger effects and the endorsement of anti-vaccine policy attitudes.  Social Science & Medicine, 211:274–281, 2018.
  * [58] Jonathan Kennedy.  Populist politics and vaccine hesitancy in western europe: an analysis of national-level data.  European journal of public health, 29(3):512–516, 2019.
  * [59] Joshua I Sanders, Balázs Hangya, and Adam Kepecs.  Signatures of a statistical computation in the human sense of confidence.  Neuron, 90(3):499–506, 2016.
  * [60] Samuel Gershman and Noah Goodman.  Amortized inference in probabilistic reasoning.  In Proceedings of the annual meeting of the cognitive science society, volume 36, 2014.
  * [61] Alexandre Pouget, Jeffrey M Beck, Wei Ji Ma, and Peter E Latham.  Probabilistic brains: knowns and unknowns.  Nature neuroscience, 16(9):1170–1178, 2013.
  * [62] Marc Mézard and Giorgio Parisi.  The bethe lattice spin glass revisited.  The European Physical Journal B-Condensed Matter and Complex Systems, 20:217–233, 2001.
  * [63] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9.  World Scientific Publishing Company, 1987.
  * [64] Enzo Marinari, Giorgio Parisi, and JJ Ruiz-Lorenzo.  Numerical simulations of spin glass systems.  In Spin Glasses and Random Fields, pages 59–98. World Scientific, 1998.
  * [65] Rudolf Peierls.  On ising’s model of ferromagnetism.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 32, pages 477–481. Cambridge University Press, 1936.
  * [66] Hidetoshi Nishimori.  Statistical physics of spin glasses and information processing: an introduction.  Number 111. Clarendon Press, 2001.
  * [67] Viktor Dotsenko.  Introduction to the replica theory of disordered statistical systems.  Introduction to the Replica Theory of Disordered Statistical Systems, 2005.
  * [68] Leo P Kadanoff.  More is the same; phase transitions and mean field theories.  Journal of Statistical Physics, 137:777–797, 2009.
  * [69] Alexander K Hartmann and Martin Weigt.  Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics.  John Wiley & Sons, 2006.
  * [70] Daniel J Benjamin.  Errors in probabilistic reasoning and judgment biases.  Handbook of Behavioral Economics: Applications and Foundations 1, 2:69–186, 2019.
  * [71] Mirta Galesic, Henrik Olsson, Jonas Dalege, Tamara van der Does, and Daniel L Stein.  Integrating social and cognitive aspects of belief dynamics: Towards a unifying framework.  Journal of the Royal Society Interface, 18(176):20200857, 2021.