# Countering Misinformation on Social Networks Using Graph Alterations

Yigit Ege Bayiz, Ufuk Topcu Y. E. Bayiz, and U. Topcu are with Univeristy of
Texas at Austin, TX 78712 USA. E-mails: {egebayiz<EMAIL_ADDRESS>
###### Abstract

We restrict the propagation of misinformation in a social-media-like
environment while preserving the spread of correct information. We model the
environment as a random network of users in which each news item propagates in
the network in consecutive cascades. Existing studies suggest that the cascade
behaviors of misinformation and correct information are affected differently
by user polarization and reflexivity. We show that this difference can be used
to alter network dynamics in a way that selectively hinders the spread of
misinformation content. To implement these alterations, we introduce an
optimization-based probabilistic dropout method that randomly removes
connections between users to achieve minimal propagation of misinformation. We
use disciplined convex programming to optimize these removal probabilities
over a reduced space of possible network alterations. We test the algorithm’s
effectiveness using simulated social networks. In our tests, we use both
synthetic network structures based on stochastic block models, and natural
network structures that are generated using random sampling of a dataset
collected from Twitter. The results show that on average the algorithm
decreases the cascade size of misinformation content by up to $70\%$ in
synthetic network tests and up to $45\%$ in natural network tests while
maintaining a branching ratio of at least $1.5$ for correct information.

###### Index Terms:

social networks, misinformation, optimization, network design

##  I Introduction

Be it a deliberate spread of controversy caused by a disinformation campaign,
or benign misinformation content that cascades through the internet, the
propagation of false news is a major issue in social media networks. The
increasing public consumption of social media over the last decade has caused
more and more people to rely on social media as a source of news[10, 18]. And
the attempts to counter misinformation using manual content classification and
human moderators have failed to scale up the sheer amount of content [6] that
propagates through modern social networks. Therefore over the last decade,
automated means of countering false news have drawn great interest.

Existing automated counters to false news mainly focus on the detection of
misinformation content. The exact form of these detection algorithms depends
on the type of content and the underlying social media network. In general,
most misinformation detection methods rely on content classification using
some black-box machine learning algorithm that is trained on a dataset labeled
by humans. These content classification methods can yield high accuracy.
However, these content classifiers still suffer from large biases caused by
the biases in the training datasets [8]. And their use in social media
platforms can lead to ethnic, religious or political discrimination within the
platform.

In this work, we deviate from the existing literature that mainly focuses on
misinformation detection, and instead, we approach the problem of countering
misinformation as an optimal control problem on a network. In this approach,
we study the problem of altering the social network dynamics in a way that
restricts misinformation spread while keeping the propagation of true content
above some acceptable level. As such, we represent the problem of countering
misinformation as an optimization problem on a social network model and then
solve this optimization problem to find real-world changes to the social
network that reduce the misinformation spread over the network.

In our social network model, we represent the propagation of news on a social
media platform using a percolation process model. In this model, each news
item propagates in a small-world network of users in consecutive cascades. In
each cascade, the users in the network that believe a news content is correct
re-share the news content probabilistically. Then, each user that receives the
shared news content, either believes in it or discards it based on a
probability distribution determined by the polarization of the sharing and
receiving users and the reflexivity of the receiving user.

The evidence suggests that there are subtle yet detectable differences in the
cascade behaviors of misinformation and true content. User polarization and
reflexivity are thought to be the main drivers of this difference [4, 19].
Thus, the above model can capture different propagation patterns of
misinformation and true content. Our approach to countering misinformation
relies on this difference in propagation patterns to discriminate between
different content types. We exploit this propagation difference to design
alterations on the network of users that selectively hinders the spread of
misinformation containing news while maintaining acceptable propagation of
true content.

The specific methods that can be used to control the content flow over the
network vary significantly depending on the capabilities and the structure of
the underlying online platform. We assume a social media environment that can
acquire usage data from the users and can estimate the polarization of the
user as well as the probability to reshare a particular news content. Under
this assumption, we propose a method called the Dropout Method. This method
relies on selectively limiting the content flow over the network by the random
omission of news items in a user’s news feed with a predetermined dropout
probability. These probabilities must be set up to reduce misinformation
spread while minimally affecting the spread of correct content. To achieve
this discrimination between misinformation and true content, we let the
dropout probabilities depend on the polarization of both the sharing and
receiving users. As mentioned before, these quantities are known to affect
misinformation and true content flow differently, thus they can be used to
identify news shares that are likely to contain misinformation.

###  I-A Main Contributions

We have two main contributions:

  1. 1.

In section 3, we develop an optimization-based approach to model the problem
of countering misinformation through alterations in the social network
structure.

  2. 2.

In section 4, we seek approximate solitouns to the problem we develop in
section 3, and ultimately develop an algorithm that can counter misinformation
through alterations in the social network structure.

###  I-B Related Work

####  I-B1 Misinformation Propagation

The existing works on misinformation propagation can be separated into two
different categories. the first of these categories focuses on finding
mathematical models that describe the propagation of misinformation content.
Most of these models describe the propagation of misinformation using
established epidemiological models. The epidemiological models that have been
most widely used in modeling viral content are, susceptible-infected-
susceptible (SIS) [12, 9], susceptible-infected-removed (SIR) [26, 23], and
susceptible-exposed-infected-removed (SEIR) [25, 16]. All of these models
describe misinformation propagation over a social network by classification
the users on the social network to different groups and modeling how these
groups evolve over time. In their work Raponi et. al. provides a comprehensive
analysis of these epidemiological models and their use in modeling
misinformation spread [21]. In our work we use an SIR-based model for content
propagation as it is a widely accepted model for modelling fake news and it is
simple to analyze.

The second category of works on misinformation propagation focuses on
discriminating misinformation spread from the spread of other content. In
their work Zhao et. al. statistically show that the propagation patterns of
fake news differ predictably form other content [27]. Wu et. al. uses support
vector machine classifiers to detect identify misinformation campaigns based
on propagation patterns [24]. There are also mixed approaches to
misinformation detection that uses both automated content classifiers and
propagation patterns to detect misinformation. Varol et. al. uses a supervised
learning approach based on k-nearest neighbors classifiers that uses sentiment
values and propagation patterns to identify promoted campaigns on social media
[22]. Our approach is similar to these works in the sense that we seek
discrimination between misinformation and other content. However, our method
does not attempt to explicitly identify misinformation.

####  I-B2 Countering Misinformation

There are some existing works that attempt to limit the propagation of
misinformation. In their work Fan et. al. proposes two models for multiple
competing diffusion processes on network and investigates the problem of
containing rumor spread on a competitive diffusion model [5]. Similarly Litou
et. al. model the competition between misinformation and credible information
on a network using a novel dynamic linear threshold model and investigate the
problem of finding optimal set of users on a network to initiate the
propagation of credible content [14, 15]. More recently there has been work on
refining this approach by considering location [28] or community [17]
structures of the underlying social network. Unlike these works we do not
focus on minimizing the influence of misinformation by maximizing the
influence of a competing diffusion model. Instead we focus on altering the
social media dynamics in a way that passively reduces misinformation spread
without requiring any competing credible content.

##  II Preliminaries

###  II-A Random Graphs

A _random directed graph_ [3] is a tuple $\mathcal{G}=(V,[p_{ij}])$ composed
of a set $V$ of vertices, a set $E\subseteq V\times V$ of edges, and a matrix
of edge probabilities $p_{ij}$ that assigns probability to each edge. An
instance of a random directed graph $\mathcal{G}$ is a directed graph
$G=(V,E^{\prime})$, where $E^{\prime}\subseteq E$ and $\mathbb{P}((i,j)\in
E^{\prime})=p_{ij}$.

###  II-B Discrete-Time SIR Model on Graphs

A discrete-time _susceptible-infected-removed_ (SIR) model [7] is a contagion
propagation model that is often used to model propagation of epidemics. In
this model, the contagion spreads in a network over consecutive iterations.
Given a random directed graph $\mathcal{G}=(V,[p_{ij}])$, at each time $t$,
The SIR model first splits the vertex set $V$ into three time-dependent
partitions composed of a susceptible set $S_{t}$, an infected set $I_{t}$, and
a removed set $R_{t}$. At each time step, each infected node $i\in I_{t}$
spreads its infection to all susceptible nodes $j\in S_{t}$, with probability
$p_{ij}$. That is,

$\mathbb{P}(j\in I_{t+1}|j\in S_{t})=1-{\sum_{\begin{subarray}{c}i\in I_{t}\\\
i\neq j\end{subarray}}{(1-p_{ij})}}.$ (1)

Each node that gets infected remains infected for exactly $m$ turns where $m$
is a known integer constant. After that, they get removed. That is, for all
$i\in I_{t}$,

$i\in\begin{cases}R_{t+1},\quad i\in I_{\tau},\;\forall\tau\in\\{t-m\dots
t\\}\\\ I_{t+1},\quad\textrm{otherwise}\end{cases}$ (2)

In our analysis and for the remainder of this work we take $m=1$. This
restricted form of SIR model is equivalent to another commonly used content
propagation model called the _independent cascade process_ [11].

In addition to being used extensively in epidemics research, SIR models also
see significant use in modelling viral content spread over social networks.

###  II-C Stochastic Block Models

A stochastic block model (SBM) is a random graph model with inbuilt
communities. We use the notation
$\mathcal{G}_{SBM}(\mathcal{C},[b_{uv}]_{uv})$ to refer to an SBM model
generated by a finite partition $\mathcal{C}=\\{C_{1},C_{2},\dots C_{k}\\}$ of
the set of nodes $V$ and a $k\times k$ SBM matrix $[b_{uv}]_{uv}$. We define
this SBM as the random graph $\mathcal{G}=(V,E,[p_{ij}]_{ij})$, where
$V=\bigcup_{u=1}^{k}{C_{u}}$ and the edge probabilities $p_{ij}$ are given as

$p_{ij}=b_{uv}\quad\textrm{for all}\quad i\in C_{u},\,j\in C_{v}.$ (3)

##  III Models and Problem Setup

###  III-A The Social Media Setup

Consider a Twitter-like social media environment that has $N$ users. We call
any user posts or news articles that occur in this social media as _content_.
We use the term _true content_ to describe a content that contains correct or
scientific information, and we use the term _false content_ to describe any
content which contains misinformation, disinformation or conspiracy.

Contents are spread over the social media environment through _shares_ between
users. Once a user receives a content, they can freely choose whether to _re-
share_ it again. A content always originates from a subset of users, which we
call _seeds_ , and notate as $I_{0}$. In practice the number $|I_{0}|$ of
seeds is almost always small compared to the total number $N$ of users.

Following the Twitter model, we assume that the information spreads over the
network in _multicast_ fashion. That is, whenever a user shares a content, the
content is transmitted to all _receivers_ simultaneously. We also assume that
each user can share or re-share a particular content only once.

In practice, user shares can occur at any time $t\in[0,\infty)$. However,
modelling and analysis in this continuous time domain is difficult. Thus, in
our network model we use the discretized time
$t\in\mathbb{N}=\\{0,1,2,3,...\\}$. The propagation of content in the network
can be summarized as the following iterative process.

  1. 1.

Set $t=0$.

  2. 2.

Content originates form seeds $I_{0}$. The seeds share the content.

  3. 3.

Set $t\leftarrow t+1$.

  4. 4.

Some of the users that receive the content decide to re-share it again.

  5. 5.

If there are new re-shares, return to step $3$.

###  III-B Modelling Content Propagation

Given a social network with $N$ users, let
$\mathcal{C}=\\{C_{1},C_{2},\dots,C_{k}\\}$ denote the partition on the set of
users that is induced by user polarization. These partitions can be generated
by the political or moral opinions of the users, as well as the echo chambers
that exist over the network. We model each user’s probability of re-sharing
received content using two quantities:

  * •

$r_{i}^{+}$: The probability that the user $i$ re-shares a received true
content.

  * •

$r_{i}^{-}$: The probability that the user $i$ re-shares a received false
content.

These quantities reflect both _reflexivity_ , which is the ability to
discriminate true and false content, and the probability of each user re-
sharing the content they believe to be true.

We model the probability of a content shared by user $i\in C_{u}$ to be
received by user $j\in C_{v}$ as a constant probability $c^{-}_{uv}$ and
$c^{+}_{uv}$ for false and true content respectively. In practice, for social
media networks, we have $c_{uu}^{-}\geq c_{uv}^{-}$ and $c_{uu}^{+}\geq
c_{uv}^{+}$ for all $u\neq v$ since the echo chambers that result from the
user polarizations encourage content sharing between agents within the same
polarization class and discourage content propagation across different
polarization classes. We can write the total probability of content being
transferred from user $i\in C_{u}$ to $j\in C_{v}$ as

$\displaystyle p^{-}_{ij}$ $\displaystyle=r^{-}_{i}c^{-}_{uv}\quad\textrm{for
false content},$ (4a) $\displaystyle p^{+}_{ij}$
$\displaystyle=r^{+}_{i}c^{+}_{uv}\quad\textrm{for true content}.$ (4b)

Following the social media setup in section 3.1, we model the content
propagation using an SIR model with an infectious period of $1$. Here the
partition $S_{t}$ represents the users that have not yet received a piece of
content at time $t$, $I_{t}$ represents the users that have received the
content in the current time step $t$, and
$R_{t}=\bigcup_{\tau=1}^{t-1}I_{\tau}$ is the set of nodes that have
previously received the content.

We can approximate these content propagation dynamics as an SIR model with
infectious period of $1$ on one of two stochastic block models:

$\displaystyle\mathcal{G}^{-}$
$\displaystyle:=\mathcal{G}_{SBM}(\mathcal{C},[b^{-}_{uv}]_{uv})\quad\textrm{for
false content},$ (5a) $\displaystyle\mathcal{G}^{+}$
$\displaystyle:=\mathcal{G}_{SBM}(\mathcal{C},[b^{+}_{uv}]_{uv})\quad\textrm{for
true content},$ (5b)

where for all $u,v\in\\{1,2,\dots,k\\}$ we have

$\displaystyle b^{-}_{uv}=\frac{1}{|C_{u}|}\sum_{i\in
C_{u}}r^{-}_{i}c^{-}_{uv},$ (6a) $\displaystyle
b^{+}_{uv}=\frac{1}{|C_{u}|}\sum_{i\in C_{u}}r^{+}_{i}c^{+}_{uv}.$ (6b)

The difference between the stochastic block models $\mathcal{G}^{+}$ and
$\mathcal{G}^{-}$ results in different content propagation characteristics to
be predicted by the SIR model. This reflects the difference in content
propagation patterns that can be seen between real-world true and false
content. When correctly fitted to the actual social media network, these
simplified content propagation models are often capable of sufficiently
capturing the difference in propagation patterns between true and false
content.

We assume throughout this work that we know $b^{-}_{uv}$ and $b^{+}_{uv}$.
This is a reasonable assumption since we can fit these SBMs to the real data
collected from social media by directly estimating $b^{-}_{uv}$ and
$b^{+}_{uv}$. A simple method of doing this is by first observing the
propagation patterns of sample contents which are known to be either true or
false, and then using a frequentist estimation of $b^{-}_{uv}$ and
$b^{+}_{uv}$ from the observed propagation patterns. As more propagation data
on true/false contents become available, this estimation can be repeated
periodically to refine the estimates for $b^{-}_{uv}$ and $b^{+}_{uv}$ over
time.

This estimation process requires reliable knowledge of whether the observed
sample contents are true or false. Therefore we require reliable content
classification to fit the SBMs $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ to the
actual social media. To minimize the bias and fairness issues associated with
automated content classification systems, we suggest doing the content
classification either using user responses to the content (likes, comments,
etc.) or manually by expert human moderators. This is possible, since there is
no strict requirement to classify content during its propagation period, and
the classification can easily be done afterward without any constraint on
time. As we elaborate in the following sections, the fact that automated
content classification is superfluous for estimating content propagation
models is one of the major advantages of our approach.

###  III-C Graph Alterations and Dropouts

To counter the spread of false content over the social media network we need
to determine how we can control the content propagation over the network. The
classical way of achieving this is first determining if a piece of content is
true or false using automated algorithms, and then restricting, or banning the
content which is determined to be false. This is an effective means of
stopping the propagation of content that is classified as false. However, as
mentioned previously, this approach suffers from its explicit reliance on
automated content classification methods, and the issues this reliance brings.

To resolve this reliance on automated agents, we introduce a network-design-
based approach to counter false content called _graph alterations_. Let
$f:V\times V\times[0,1]\rightarrow[0,1]$ be a function that given a node pair
$i,j$ and content transfer probability $p_{ij}$, generates an altered content
transfer probability of $f(i,j,p_{ij})$. We define a graph alteration
$\mathfrak{A}_{f}:\mathcal{G}\mapsto\tilde{\mathcal{G}}$ as the mapping
induced by $f$ between two random graphs. That is for any random graph
$\mathcal{G}:=(V,[p_{ij}]_{ij})$ we have

$\mathfrak{A}_{f}(\mathcal{G}):=\tilde{\mathcal{G}}:=(V,[f(i,j,p_{ij})]_{ij}).$
(7)

In other words, given a random graph $\mathcal{G}$, with transfer
probabilities $[p_{ij}]_{ij}$ $\mathfrak{A}_{f}(\mathcal{G})$ is a new random
graph with altered transfer probabilities $[f(i,j,p_{ij})]_{ij}$.

Suppose that we have two random graphs $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$
describing the propagation of true and false content respectively on a social
network. For any fixed $f$, applying the same graph alteration
$\mathfrak{A}_{f}$ to $\mathcal{G}^{-}$ and $\mathcal{G}^{+}$ provides a
method to alter the structure of both of these graphs simultaneously in a way
that does not explicitly depend on the content type. Each graph alteration
$\mathfrak{A}_{f}$ corresponds to a change in the social network structure
that results in the true and false contents to propagate according to random
graphs $\mathfrak{A}_{f}(\mathcal{G}^{+})$ and
$\mathfrak{A}_{f}(\mathcal{G}^{-})$ respectively.

The set of graph alterations that are feasible to implement on a social media
network depend heavily on the design and capabilities of the social media
platform. In this work, we focus on the graph alterations corresponding to
randomized content dropouts. We define a dropout as the artificial prevention
of a content transfer between two agents. For example, in a Twitter-like
social media platform, we can implement such randomized content dropouts by
artificially excluding a content from the receiver’s feed. In the SBM model
described in Section 3.4, we model a random dropout between two users $i\in
C_{u}$ and $j\in C_{v}$ using an altered content transfer probability
function.

$f_{d}(i,j,p_{ij}):=d_{uv}p_{ij},$ (8)

where $d_{uv}$ are the dropout probabilities. Then under graph alteration
$\mathfrak{A}_{f_{d}}$, the altered SBMs corresponding to true and false
content propagation graphs are

$\displaystyle\tilde{\mathcal{G}}^{-}:=\mathfrak{A}_{f_{d}}(\mathcal{G}^{-})$
$\displaystyle:=\mathcal{G}_{SBM}(\mathcal{C},[\tilde{b}^{-}_{uv}]_{uv})\quad\textrm{for
false content},$ (9a)
$\displaystyle\tilde{\mathcal{G}}^{+}:=\mathfrak{A}_{f_{d}}(\mathcal{G}^{+})$
$\displaystyle:=\mathcal{G}_{SBM}(\mathcal{C},[\tilde{b}^{+}_{uv}]_{uv})\quad\textrm{for
true content},$ (9b)

where

$\displaystyle\tilde{b}^{-}_{uv}$ $\displaystyle:=d_{uv}b^{-}_{uv},$ (10a)
$\displaystyle\tilde{b}^{+}_{uv}$ $\displaystyle:=d_{uv}b^{+}_{uv}.$ (10b)

Assuming that the original SBMs $\mathcal{G}^{-}$ and $\mathcal{G}^{+}$ are
accurate models of content propagation over the network, we can use these
altered SBMs to predict the effect of graph alterations on the real-world
social network.

###  III-D Problem Statement

In the most general case, the problem of countering misinformation is finding
a graph alteration $\mathfrak{A}_{f}$ that minimizes the predicted propagation
of false content, whilst keeping the predicted propagation of true content
above some acceptable level. That is for a given safety parameter $\alpha$, at
every time $t$ we wish to solve the following optimization problem.

$\displaystyle\min_{\mathfrak{A}_{f}}$
$\displaystyle\quad\mathbf{E}_{\tilde{\mathcal{G}}^{-}}[|I_{t+1}||S_{t},I_{t},R_{t}],$
(11a) s.t.
$\displaystyle\quad\mathbf{E}_{\tilde{\mathcal{G}}^{+}}[|I_{t+1}||S_{t},I_{t},R_{t}]\geq\alpha|I_{t}|.$
(11b)

The general case given in (11) is a non-convex optimization problem over all
possible graph alterations $\mathfrak{A}_{f}$. This is intractable for large
networks. However, we can reduce it into a simpler problem by restricting and
parametrizing the graph alterations $\mathfrak{A}_{f}$. Throughout the rest of
this work, we restrict our analysis to graph alterations
$\mathfrak{A}_{f_{d}}$ that are generated by randomized dropouts
$[d_{uv}]_{uv}$ where $d_{uv}$ is the dropout probability of a content
transfer from a user in polarization class $C_{u}$ to a user in polarization
class $C_{v}$. This yields the following optimization problem.

$\displaystyle\min_{d\in[0,1]^{k\times k}}$
$\displaystyle\quad\mathbf{E}_{\mathfrak{A}_{f_{d}}(\mathcal{G}^{-})}[|I_{t+1}||S_{t},I_{t},R_{t}],$
(12a) s.t.
$\displaystyle\quad\mathbf{E}_{\mathfrak{A}_{f_{d}}(\mathcal{G}^{+})}[|I_{t+1}||S_{t},I_{t},R_{t}]\geq\alpha|I_{t}|,$
(12b)

where $f_{d}$ is the altered transfer probability function defined in eq. (8),
and $\mathfrak{A}_{f_{d}}$ is the graph alteration induced by $f_{d}$.

After solving these optimization problems with model social networks
$\mathcal{G}^{-}$ and $\mathcal{G}^{+}$, we use the optimal graph alterations
found by these problems to alter the content transfer probabilities of the
real-world social network. Since the optimal solutions of problems (12) and
(11) are time-dependent, we need to update the graph alteration at each time
$t$ by re-evaluating the optimal solution to the optimization problem at hand
based on the observed $S_{t},I_{t},R_{t}$.

##  IV Theory and Algorithms

As a general solution template, we consider the dynamic false content
minimization loop given in Algorithm 1. We run Algorithm 1 independently for
each content that propagates over the network. In Algorithm 1
$\textrm{OPT}(\textrm{problem \eqref{eqn::dropout_problem}})$ refers to the
optimal solution of problem (12), and
Observe$(S_{t+1},I_{t+1},R_{t+1}|S_{t},I_{t},R_{t},\tilde{\mathcal{G}})$
returns the observed $S_{t+1},I_{t+1},R_{t+1}$ sets generated by an SIR model
on altered social network $\tilde{\mathcal{G}}$ with known current state
$S_{t},I_{t},R_{t}$. That is, the $S_{t+1},I_{t+1},R_{t+1}$ denotes the next
set of susceptible, infected, removed users given that the real social network
is altered using a dropouts $d^{*}$. This dropout is the optimal dropout based
on our model networks $\mathcal{G}^{+},\mathcal{G}^{-}$, which are stochastic
block models as described in the previous section. Intuitively, given a piece
of content that propagates as an SIR model on a real-world network
$\mathcal{G}$ with unknown transfer probabilities, Algorithm 1 attempts to
minimize the spread of the content if it propagates like a false content, and
preserves the spread of the content if it propagates like a true content.

Algorithm 1 False Content Minimization

0: Model Networks $\mathcal{G}^{-},\mathcal{G}^{+}$, Real-World Network
$\mathcal{G}$, Set of seed users $I_{0}$, Safety parameter $\alpha$.

1: $t\leftarrow 0$

2: $S_{0}\leftarrow V\setminus I_{0}$

3: $R_{0}\leftarrow\emptyset$

4: while $|I_{t}|>0$ do

5: $d^{*}=\textrm{OPT}(\textrm{problem \eqref{eqn::dropout_problem}})$

6: $\tilde{\mathcal{G}}\leftarrow\mathfrak{A}_{f_{d^{*}}}(\mathcal{G})$ {Alter
the real-world social network.}

7: $S_{t+1},I_{t+1},R_{t+1}\leftarrow$
Observe$(S_{t+1},I_{t+1},R_{t+1}|S_{t},I_{t},R_{t},\tilde{\mathcal{G}})$

8: $t\leftarrow t+1$

9: end while

The problem given in eq. (12) is a non-convex problem. To solve it, we
formulate an asymptotic approximation of it by considering the behavior of
$\tilde{\mathcal{G}}^{+}=\mathbf{E}_{\mathfrak{A}_{f_{d}}(\mathcal{G}^{+})}[|I_{t+1}||S_{t},I_{t},R_{t}]$
as the number $N$ of users diverges towards infinity. This is a reasonable
approximation since the number $N$ of users in real social networks is often
large enough that the inaccuracies caused by the asymptotic approximation is
negligible compared to other sources of model inaccuracy.

We define $I^{u}_{t}=I_{t}\cap C_{u}$ as the set of infected users in
polarization class $C_{u}$ at iteration $t$. Similarly, we also let
$R^{u}_{t}=R_{t}\cap C_{u}$, and $S^{u}_{t}=S_{t}\cap C_{u}$. Then, for any
$j\in C_{v}$ we have

$\mathbb{P}_{\tilde{\mathcal{G}}^{+}}[j\in
I_{t+1}|S_{t},I_{t},R_{t}]=\begin{cases}1-\prod_{u=1}^{k}(1-d_{uv}b^{+}_{uv})^{|I^{u}_{t}|},&\;j\in
S_{t},\\\ 0,&\;j\not\in S_{t}.\end{cases}$ (13)

This probability immediately follows from the transition probabilities of the
altered SBM $\tilde{\mathcal{G}}^{+}=\mathfrak{A}_{f_{d}}(\mathcal{G}^{+})$
corresponding to the false content.

The social networks that we are interested in often have a large number of
users. Thus, we are interested in the asymptotic behavior of eq. (13) for
large $N$. For such large networks we can approximate (13) as

$\mathbb{P}_{\tilde{\mathcal{G}}^{+}}[j\in
I_{t+1}|S_{t},I_{t},R_{t}]=\begin{cases}1-\prod_{u=1}^{k}\exp(-|I^{u}_{t}|d_{uv}b^{+}_{uv}),&\,j\in
S_{t},\\\ 0,&\,j\not\in S_{t}.\end{cases}$ (14)

Under this approximation, for true content we have

$\mathbf{E}_{\tilde{\mathcal{G}}^{+}}[|I_{t+1}|\,|S_{t},I_{t}]=\sum_{v=1}^{k}|S^{v}_{t}|\Big{(}1-\exp\Big{(}-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{+}_{uv}\Big{)}\Big{)},$
(15)

and similarly, for false content, we write

$\mathbf{E}_{\tilde{\mathcal{G}}^{-}}[|I_{t+1}|\,|S_{t},I_{t}]=\sum_{v=1}^{k}|S^{v}_{t}|\Big{(}1-\exp\Big{(}-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{-}_{uv}\Big{)}\Big{)}.$
(16)

Using equations (15) and (16), we can rewrite the optimization problem given
in (12) as

$\displaystyle\min_{d\in[0,1]^{k\times k}}$
$\displaystyle\quad\sum_{v=1}^{k}|S^{v}_{t}|\Big{(}1-\exp\Big{(}-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{-}_{uv}\Big{)}\Big{)},$
(17a) s.t.
$\displaystyle\quad\sum_{v=1}^{k}|S^{v}_{t}|\Big{(}1-\exp\Big{(}-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{+}_{uv}\Big{)}\Big{)}\geq\alpha|I_{t}|.$
(17b)

There is no guarantee that the optimization problem in eq. (17) is feasible.
In fact, since the left hand side of the constraint (17) is monotonically
increasing with $d_{uv}$ for all $u,v\in\\{1,\dots,k\\}$ the problem (17) is
feasible if and only if we have

$\sum_{v=1}^{k}|S^{v}_{t}|\Big{(}1-\exp\Big{(}-\sum_{u=1}^{k}|I^{u}_{t}|b^{+}_{uv}\Big{)}\Big{)}\geq\alpha|I_{t}|.$
(18)

That is, the problem (17) is feasible exactly when $(I_{t})_{t}$ has branching
ratio greater than or equal to $\alpha$ in the SIR model defined on the non-
altered true content graph $\mathcal{G}^{+}$. Therefore choosing $\alpha$ too
large can lead to infeasibility.

Another issue to note is that due to the dynamics of the SIR model given in
equations (1) and (2), whenever we have $|I_{\tau}|=0$ for some $\tau$, we
guarantee $|I_{t}|=0$ for all $t>\tau$. This means that even though (17) might
be feasible, the propagation of true content can halt if a random event leads
to $|I_{\tau}|=0$ at some $\tau$. Clearly, the probability of this event
$|I_{\tau}|=0$ decreases with larger safety parameter $\alpha$. But as stated
previously, too large of a choice for the parameter $\alpha$ leads to
infeasibility in the problem (17). Therefore, when choosing a safety parameter
$\alpha$ one needs to consider a trade-off between feasibility, and robustness
to probabilistic effects. In Lemma 1 we investigate this trade-off further and
characterize the relation between $\alpha$ and the probability that the
$|I_{\tau}|=0$ given that the problem given in (17) is feasible.

######  Lemma 1.

Suppose that there exists some $T\in\mathbb{N}$ such that the optimization
problem (12) is feasible for all $t\in[0,T]$, and let
$(S_{t},I_{t},R_{t})_{t}$ be the stochastic SIR process generated as in
Algorithm 1. Then if $\mathcal{G}=\mathcal{G}^{+}$, then for any non-negative
$\lambda$ we have,

$\mathbb{P}[\inf_{0\leq t\leq
T}{|I_{t}|}=0]\leq\mathbf{E}\Big{[}e^{-\lambda\frac{|I_{T}|}{\alpha^{T}}}\Big{]}=\mathbf{M}_{|I_{T}|}\Big{(}-\frac{\lambda}{\alpha^{T}}\Big{)},$
(19)

where $\mathbf{M}_{|I_{T}|}$ denotes the moment generating function of
$|I_{T}|$.

###### Proof.

Let $(\mathcal{F}_{t})_{0\leq t\leq T}$ be the natural filtration generated by
the stochastic process $(|I_{t}|)_{0\leq t\leq T}$. Let
$Y_{t}=\frac{|I_{t}|}{\alpha^{t}}$. Then by the constraint of problem (12) for
all $t\in(0,T]$ we have $\mathbf{E}[Y_{t+1}|\mathcal{F}_{t}]=Y_{t}$. That is,
$(Y_{t})_{t}$ is Martingale. Then by Jensen’s inequality, for all non-negative
$\lambda$ and $t\in(0,T]$, we have $\mathbf{E}[e^{-\lambda
Y_{t+1}}|\mathcal{F}_{t}]\geq e^{-\lambda Y_{t}}$. Notice that
$(\mathcal{F}_{t})_{t}$ is also a natural filtration for the stochastic
process $(e^{-\lambda Y_{t}})_{t}$ since $e^{-\lambda Y_{t}}$ relates
bijectively to $|I_{t}|$. Therefore $(e^{-\lambda Y_{t}})_{t}$ is a sub-
Martingale sequence. Then,

$\displaystyle\mathbb{P}[\inf_{0\leq t\leq T}{|I_{t}|}=0]$
$\displaystyle=\mathbb{P}[\inf_{0\leq t\leq T}{|I_{t}|}\leq 0]$ (20a)
$\displaystyle=\mathbb{P}[\inf_{0\leq t\leq T}{Y_{t}}\leq 0]$ (20b)
$\displaystyle=\mathbb{P}[\sup_{0\leq t\leq T}{e^{-\lambda Y_{t}}}\geq 1]$
(20c)
$\displaystyle\leq\mathbf{E}\Big{[}e^{-\lambda\frac{|I_{T}|}{\alpha^{T}}}\Big{]},$
(20d)

where the last line follows from Doob’s Martingale inequality. ∎

The optimization problem (17) can be solved using gradient-based methods.
However, it is also possible to simplify it further. We are mainly interested
in the initial period of the viral spread of the content. That is, we want to
counter false content before it spreads to a significant fraction of users.
Similarly for true content, if we can ensure that the spread of true content
is not restricted in the first couple of iterations, it is likely that a
significant fraction of users will eventually receive the true content. Thus
in practical applications, $N$ is usually much larger than $I_{t}$. Under this
assumption, the inequalities

$\displaystyle\exp\Big{(}\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{-}_{uv}\Big{)}$
$\displaystyle\geq 1-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{-}_{uv},$ (21a)
$\displaystyle\exp\Big{(}\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{+}_{uv}\Big{)}$
$\displaystyle\geq 1-\sum_{u=1}^{k}|I^{u}_{t}|d_{uv}b^{+}_{uv},$ (21b)

becomes tight. Therefore in the regime $N\>>I_{t}$ we can approximate the
solution the optimization problem (17) using the following optimization
problem,

$\displaystyle\min_{d\in[0,1]^{k\times k}}$
$\displaystyle\quad\sum_{v=1}^{k}\sum_{u=1}^{k}|S^{v}_{t}||I^{u}_{t}|d_{uv}b^{-}_{uv},$
(22a) s.t.
$\displaystyle\quad\sum_{v=1}^{k}\sum_{u=1}^{k}|S^{v}_{t}||I^{u}_{t}|d_{uv}b^{+}_{uv}\geq\alpha|I_{t}|.$
(22b)

The above form is simply a linear program and it can be solved very
efficiently using existing linear program solvers. As before, the optimization
problem (22) is feasible if and only if we have

$\sum_{v=1}^{k}\sum_{u=1}^{k}|S^{v}_{t}||I^{u}_{t}|b^{+}_{uv}\geq\alpha|I_{t}|.$
(23)

(a) False Content, Balanced, 2 partitions, Control

(b) False Content, Balanced, 2 partitions, $\alpha=1.5,\lambda=1$

(c) False Content, Unbalanced, 3 partitions, $\alpha=1.5,\lambda=1$

(d) True Content, Balanced, 2 partitions, Control

(e) True Content, Balanced, 2 partitions $\alpha=1.5,\lambda=1$

(f) True Content, Unbalanced, 3 partitions $\alpha=1.5,\lambda=1$

Figure 1: Cascade size of false and true content across two different SBM
configurations.

In application, viral true content almost always satisfies this feasibility
condition for some $\alpha\geq 1$ in the initial propagation period. However,
less viral content may violate the feasibility condition. In this case, our
original optimization goals cannot be reached. To counter this issue, for
content that violates the feasibility criterion (23) infeasible we can soften
the linear program (22). That is,

$\min_{d\in[0,1]^{k\times
k}}\quad\sum_{v=1}^{k}\sum_{u=1}^{k}|S^{v}_{t}||I^{u}_{t}|d_{uv}b^{-}_{uv}+\lambda|S^{v}_{t}||I^{u}_{t}|d_{uv}b^{+}_{uv},$
(24)

where $\lambda$ is a weight parameter that signifies the importance of
preserving true content relative to the importance of suppressing false
content.

We can use the linear programs (22) and (24) in conjunction to provide a
general approximate solution the our main problem (12) given in section 3.4.
The Algorithm 2 provides a method to achieve which this conjunction. Here
$\textrm{OPT}(*)$ refers to the optimal solution on the optimization problem
$*$, which in the case of Algorithm 2 can be found efficiently using existing
linear program solution methods.

Algorithm 2 False Content Minimization Using Dropouts

0: Networks $\mathcal{G}^{-},\mathcal{G}^{+}$, Real-World Network
$\mathcal{G}$, Set of seed users $I_{0}$, Safety parameter $\alpha$, Weight
$\lambda$.

1: $t\leftarrow 0$

2: $S_{0}\leftarrow V\setminus I_{0}$

3: $R_{0}\leftarrow\emptyset$

4: while $|I_{t}|>0$ do

5: if
$\sum_{v=1}^{k}\sum_{u=1}^{k}|S^{v}_{t}||I^{u}_{t}|b^{+}_{uv}\geq\alpha|I_{t}|.$
then

6: $d^{*}=\textrm{OPT}(\textrm{linear program
\eqref{eqn::dropout_problem_asymptotic_linear}})$

7: else

8: $d^{*}=\textrm{OPT}(\textrm{linear program
\eqref{eqn::dropout_problem_asymptotic_linear_soft}})$

9: end if

10: $\tilde{\mathcal{G}}\leftarrow\mathfrak{A}_{f_{d^{*}}}(\mathcal{G})$
{Alter the real-world social network.}

11: $S_{t+1},I_{t+1},R_{t+1}\leftarrow$ Observe
$(S_{t+1},I_{t+1},R_{t+1}|S_{t},I_{t},R_{t},\tilde{\mathcal{G}})$

12: $t\leftarrow t+1$

13: end while

##  V Experimental Results

We test Algorithm 2 both on synthetic stochastic block model networks and on a
real misinformation dataset collected over Twitter. The dataset we used is
called WICO [20] which contains over $3500$ separate tweets and status updates
collected between January 2020 and July 2020. In these tests, we use the total
cascade size $R_{\infty}$, which is the total size of the set of users that
have received a piece of content after the SIR propagation terminates, as the
performance metric. For the case of true content, we want $R_{\infty}$ to be
high, and for the case of false content, we want $R_{\infty}$ to be low.

###  V-A Experiments Using Synthetic Model

In this section, we test the performance of Algorithm 2 using synthetic social
networks that are modeled as SBMs. We test the effectiveness of Algorithm 2
over four different test configurations. We name these configurations as
follows: Balanced with $2$ partitions, unbalanced with $2$ partitions,
balanced with $3$ partitions, and unbalanced with $3$ partitions. All of these
configurations have $1000$ users. The balanced configurations have partition
sizes of $[500,500]$ for $2$ partition case and $[334,333,333]$ for $3$
partition case. The unbalanced configurations have partition sizes of
$[800,200]$ for $2$ partition case and $[500,300,200]$ for $3$ partition case.

We associate a base matrix $\mathbf{b}_{\textrm{base}}$ with each of these
test configurations. For configurations with $2$ partitions this base matrix
is defined as,

$\mathbf{b}_{\textrm{base}}:=\begin{bmatrix}0.01&0.002\\\
0.002&0.01\end{bmatrix}.$ (25)

Similarly, for configurations with $3$ partitions, we define this base matrix
as,

$\mathbf{b}_{\textrm{base}}:=\begin{bmatrix}0.01&0.002&0.002\\\
0.002&0.01&0.002\\\ 0.002&0.002&0.01\\\ \end{bmatrix}.$ (26)

We use these base matrices to generate SBMs that simulate true and false
content propagation. To test the effect of different content propagation
dynamics on the performance of algorithm 2, we select two parameters
$x\in[0,0.01]$ and $y\in[0,0.001]$. For each configuration, we sweep across
the range of possible $x$ and $y$ combinations with $50$ subdivisions in each
dimension. For each $x$ and $y$ choice, we generate the SBMs $\mathcal{G}^{+}$
and $\mathcal{G}^{-}$ that describe the content transfer probabilities for
true and false content respectively. We define the SBM matrices for
$\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ as follows: For true content we define

$[b^{+}_{uv}]_{uv}=\mathbf{b}_{\textrm{base}}+x\mathbb{I}-y(\mathbb{J}-\mathbb{I}),$
(27)

and for false content we define

$[b^{-}_{uv}]_{uv}=\mathbf{b}_{\textrm{base}}-x\mathbb{I}+y(\mathbb{J}-\mathbb{I}),$
(28)

where $\mathbb{I}$ is the identity matrix and $\mathbb{J}$ is the all-ones
matrix. Then we simulate content propagation over these networks and determine
the cascade sizes $R_{\infty}$ that result from different choices for $\alpha$
and $\lambda$.

Table I, summarizes the normalized mean cascade size
$\mathbf{E}[R_{\infty}]/N$ and ratio of tests that have cascade size less than
$N/10$ to all tests. These statistics are collated over the complete range of
all $x$ and $y$ combinations. For all configurations, we test two different
parameter assignments for $\alpha$ and $\lambda$. The rows indicated as
$(\alpha,\lambda)=(-,-)$ are control groups with no network alterations. This
table shows that regardless of the choice of parameters $\alpha$ and
$\lambda$, on average Algorithm 2 manages to reduce false content more than it
reduces true content. Moreover, $\mathbb{P}[R_{\infty}<{N/10}]$ are much
higher on false content compared to true content. The fact that
$\mathbb{P}[R_{\infty}<{N/10}]$ are high on false content indicates that the
cascade size $R_{\infty}$ has high variance. That is, the performance of
Algorithm 2 varies greatly depending on the dynamics of the social network
structure.

TABLE I: Summmary of Results for Synthetic Tests SBM Type | Partitions | $\alpha$ | $\lambda$ | Mean Cascade Size ($\mathbf{E}[R_{\infty}]/N$) | Low Cascades ($\mathbb{P}[R_{\infty}<{N/10}]$)
---|---|---|---|---|---
|  |  |  | True Content | False Content | True Content | False Content
Balanced | 2 | - | - | 0.89 | 0.98 | 0.08 | 0.09
Balanced | 2 | 1.5 | 1 | 0.51 | 0.32 | 0.28 | 0.43
Balanced | 2 | 2 | 1.5 | 0.72 | 0.41 | 0.18 | 0.30
Unbalanced | 2 | - | - | 0.92 | 0.96 | 0.08 | 0.08
Unbalanced | 2 | 1.5 | 1 | 0.46 | 0.14 | 0.22 | 0.82
Unbalanced | 2 | 2 | 1.5 | 0.68 | 0.38 | 0.27 | 0.57
Balanced | 3 | - | - | 0.86 | 0.95 | 0.12 | 0.09
Balanced | 3 | 1.5 | 1 | 0.52 | 0.36 | 0.33 | 0.48
Balanced | 3 | 2 | 1.5 | 0.73 | 0.48 | 0.18 | 0.37
Unbalanced | 3 | - | - | 0.88 | 0.97 | 0.11 | 0.13
Unbalanced | 3 | 1.5 | 1 | 0.51 | 0.23 | 0.29 | 0.70
Unbalanced | 3 | 2 | 1.5 | 0.66 | 0.37 | 0.22 | 0.64

Figure 1 shows the average cascade size three configurations over the full
span of $x,y$ combinations, where the average is computed over $50$ separate
trials. This figure shows that the Algorithm 2 affects the true content in a
similar way across all $x,y$ values. This is of course expected since the
constraint in the linear program (22) in Algorithm 2 fixes the expected
propagation rate of true content. On the contrary, the effect of Algorithm 2
on the false content depends heavily on both the value of $x$ and $y$ and the
overall structure of the social media network. In general, there is a sharp
boundary transition in the cascade size of the false content and the Algorithm
2 tends to either reduce the cascade size of false content to near $0$, or
have very little impact to the propagation of the false content. This explains
the high $\mathbb{P}[R_{\infty}<{N/10}]$ values seen in Table I. The sharp
transition in cascade size seen in Figures 1(b) and 1(c) is caused by the same
mechanism that causes the state-transition-like behavior that is present in
most complex real networks, where a giant connected component can appear
suddenly as we increase the overall expected degree of nodes in a large graph
[3].

###  V-B Experiments Using Real World Data

We use a pre-existing dataset named WICO [20] for these tests. This dataset
contains share times and propagation networks for separate pieces of content.
These content are labeled as follows:

  1. 1.

5G-Corona Conspiracy: Conspiracy content that claims there is a causation
between the Covid-19 pandemic and 5G,

  2. 2.

Other Conspiracy,

  3. 3.

Non-Conspiracy.

In this dataset, we re-label content that is labeled as “5G-Corona Conspiracy”
or “Other Conspiracy” as false content, and we re-label Non-Conspiracy content
as true content.

We then assign polarizations to each user by running modularity based
clustering [2] with resolution [13] set to $2$ on the union of all graphs in
the WICO dataset. The resulting network has $153779$ nodes and $216848$ edges.
The modularity class assignment has $63914$ partitions. We restrict the number
of partitions by merging all partitions with a number of users less than $1\%$
of the total number of users in the merged graph. The resulting partitioning
of the graph has $13$ partitions. These partitions correspond to different
echo chambers in the network, therefore they are a close approximation for the
polarization classes of the users in the social network.

After determining polarization classes, we fit the model networks
$\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ to the dataset by frequentist
estimation of SBM matrices $[b^{+}_{uv}]_{uv}$ and $[b^{-}_{uv}]_{uv}$ by
counting the number of content transfers between different polarization
groups. We then use Algorithm 2 to generate dropout-based alterations on the
actual social media network. We simulate the content propagation under these
dropout-based alterations by sampling a random content from the dataset and
then following its propagation while randomly dropping content transfers based
on dropout probabilities $d^{*}$ given by Algorithm 2.

We test the three different parameter settings for Algorithm 2. These settings
are $(\alpha,\lambda)=(1.5,1)$, $(\alpha,\lambda)=(2,1.5)$,
$(\alpha,\lambda)=(3,2)$. Table II shows the resulting cascade size
statistics, averaged over $500$ samples, for these each of these settings as
well as a control group which is denoted as $(\alpha,\lambda)=(-,-)$. Contrary
to the previous synthetic tests, we do not normalize the expected cascade size
value in Table II, since the cascade sizes of these networks are very small
compared to the total number of users in the network. The fact that the
cascade sizes are small is not surprising, since often in the real world
social media network only a small fraction of users tend to participate in re-
sharing a piece of content they receive due to the vastness of the number of
available content and the variability of interests of users. The average
performance of Algorithm 2 decreases in these real-world datasets compared to
synthetic model test due to the inaccuracies in the SBM models
$\mathcal{G}^{+}$ and $\mathcal{G}^{-}$. However, for all choices of
$(\alpha,\lambda)$ Algorithm 2 achieves discrimination between true and false
content.

TABLE II: Summmary of Results for WICO Dataset Tests $\alpha$ | $\lambda$ | $\mathbf{E}[R_{\infty}]$ |  $\mathbb{P}[R_{\infty}<5$]
---|---|---|---
|  | True C. | False C. | True C. | False C.
- | - | 50.1 | 48.7 | 0.01 | 0.00
1.5 | 1 | 32.8 | 26.1 | 0.05 | 0.13
2 | 1.5 | 39.4 | 28.2 | 0.04 | 0.09
3 | 2 | 41.1 | 36.0 | 0.00 | 0.02

##  VI Conclusion and Future Work

We demonstrated that it is possible to counter misinformation without explicit
identification of misinformation content by altering the content propagation
dynamics on social network. A major advantage of our approach is that it does
not require the system to be able to identify if a particular news item
contains misinformation content or not. Furthermore, our approach can be used
in conjunction with these detection algorithms to improve the effectiveness of
misinformation control while maintaining some of the advantages offered by the
network-design-based approach. In our future studies, we will investigate this
possibility further.

Throughout this work we have assumed that content is either true and false. In
reality this clear of a separation between true and false content types is
rarely possible. It is possible to extend our methods and algorithms to admit
more content types, which can increase the performance of Algorithm 1 since
more content types can achieve a more nuanced description of real
misinformation dynamics. However, this extension requires modifications on the
problem statement and the formulation of the problem.

## Acknowledgements

This work was supported in part by ONR N00014-21-1-2502 and NSF 1652113.

## References

  * [1]
  * Blondel et al. [2008] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ (2008), P10008.
  * Bollobás [2001] Béla Bollobás. 2001\.  _Random Graphs_ (2 ed.).  Cambridge University Press.  https://doi.org/10.1017/CBO9780511814068
  * Del Vicario et al. [2016] Michela Del Vicario, Alessandro Bessi, Fabiana Zollo, Fabio Petroni, Antonio Scala, Guido Caldarelli, H. Eugene Stanley, and Walter Quattrociocchi. 2016\.  The spreading of misinformation online.  _Proceedings of the National Academy of Sciences_ 113, 3 (2016), 554–559.  https://doi.org/10.1073/pnas.1517441113
  * Fan et al. [2014] Lidan Fan, Weili Wu, Xuming Zhai, Kai Xing, Wonjun Lee, and Ding-Zhu Du. 2014\.  Maximizing rumor containment in social networks with constrained time.  _Social Network Analysis and Mining_ 4, 1 (2014), 1–10.
  * Gilbert [2013] Eric Gilbert. 2013\.  Widespread Underprovision on Reddit. In _ACM Conference on Computer Supported Cooperative Work_.  https://doi.org/10.1145/2441776.2441866
  * Hill et al. [2010] Alison L Hill, David G Rand, Martin A Nowak, and Nicholas A Christakis. 2010.  Infectious disease modeling of social contagion in networks.  _PLOS computational biology_ 6, 11 (2010).
  * Hirlekar and Kumar [2020] Vaishali Vaibhav Hirlekar and Arun Kumar. 2020.  Natural Language Processing based Online Fake News Detection Challenges – A Detailed Review. In _International Conference on Communication and Electronics Systems_.  https://doi.org/10.1109/ICCES48766.2020.9137915
  * Jin et al. [2013] Fang Jin, Edward Dougherty, Parang Saraf, Yang Cao, and Naren Ramakrishnan. 2013.  Epidemiological modeling of news and rumors on twitter. In _Proceedings of Workshop on Social Network Mining and Analysis_.
  * Jr [2019] Edson C. Tandoc Jr. 2019\.  Tell Me Who Your Sources Are.  _Journalism Practice_ 13, 2 (2019), 178–190.  https://doi.org/10.1080/17512786.2017.1423237
  * Kempe et al. [2003] David Kempe, Jon Kleinberg, and Éva Tardos. 2003\.  Maximizing the Spread of Influence through a Social Network. In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD)_.  https://doi.org/10.1145/956750.956769
  * Kimura et al. [2009] Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2009\.  Efficient estimation of influence functions for SIS model on social networks. In _International Joint Conference on Artificial Intelligence_.
  * Lambiotte et al. [2008] Renaud Lambiotte, Jean-Charles Delvenne, and Mauricio Barahona. 2008.  Laplacian Dynamics and Multiscale Modular Structure in Networks.  _arXiv_ (2008).
  * Litou et al. [2016] Iouliana Litou, Vana Kalogeraki, Ioannis Katakis, and Dimitrios Gunopulos. 2016.  Real-Time and Cost-Effective Limitation of Misinformation Propagation. In _IEEE International Conference on Mobile Data Management_.  https://doi.org/10.1109/MDM.2016.33
  * Litou et al. [2017] Iouliana Litou, Vana Kalogeraki, Ioannis Katakis, and Dimitrios Gunopulos. 2017.  Efficient and timely misinformation blocking under varying cost constraints.  _Online Social Networks and Media_ 2 (2017), 19–31.
  * Liu et al. [2017] Qiming Liu, Tao Li, and Meici Sun. 2017.  The analysis of an SEIR rumor propagation model on heterogeneous network.  _Physica A: Statistical Mechanics and its Applications_ 469 (2017), 372–380.
  * Lv et al. [2019] Jiaguo Lv, Bin Yang, Zhen Yang, and Wei Zhang. 2019\.  A community-based algorithm for influence blocking maximization in social networks.  _Cluster Computing_ 22, 3 (2019), 5587–5602.
  * Marchi [2012] Regina Marchi. 2012\.  With Facebook, Blogs, and Fake News, Teens Reject Journalistic “Objectivity”.  _Journal of Communication Inquiry_ 36, 3 (2012), 246–262.  https://doi.org/10.1177/0196859912458700
  * Pennycook and Rand [2021] Gordon Pennycook and David G. Rand. 2021.  The Psychology of Fake News.  _Trends in Cognitive Sciences_ 25, 5 (2021), 388–402.  https://doi.org/10.1016/j.tics.2021.02.007
  * Pogorelov et al. [2021] Konstantin Pogorelov, Daniel Thilo Schroeder, Petra Filkuková, Stefan Brenner, and Johannes Langguth. 2021.  WICO Text: A Labeled Dataset of Conspiracy Theory and 5G-Corona Misinformation Tweets. In _ACM Workshop on Open Challenges in Online Social Networks_.  https://doi.org/10.1145/3472720.3483617
  * Raponi et al. [2022] Simone Raponi, Zeinab Khalifa, Gabriele Oligeri, and Roberto Di Pietro. 2022.  Fake news propagation: a review of epidemic models, datasets, and insights.  _ACM Transactions on the Web_ 16, 3 (2022), 1–34.
  * Varol et al. [2017] Onur Varol, Emilio Ferrara, Filippo Menczer, and Alessandro Flammini. 2017.  Early detection of promoted campaigns on social media.  _EPJ Data Science_ , 1–19.
  * Wang and Wang [2017] Ya-Qi Wang and Jing Wang. 2017.  SIR rumor spreading model considering the effect of difference in nodes’ identification capabilities.  _International Journal of Modern Physics_ 28, 05 (2017).
  * Wu et al. [2015] Ke Wu, Song Yang, and Kenny Q. Zhu. 2015.  False rumors detection on Sina Weibo by propagation structures. In _IEEE International Conference on Data Engineering_.  https://doi.org/10.1109/ICDE.2015.7113322
  * Xia et al. [2015] Ling-Ling Xia, Guo-Ping Jiang, Bo Song, and Yu-Rong Song. 2015\.  Rumor spreading model considering hesitating mechanism in complex social networks.  _Physica A: Statistical Mechanics and its Applications_ 437 (2015), 295–303.
  * Zhao et al. [2013] Laijun Zhao, Hongxin Cui, Xiaoyan Qiu, Xiaoli Wang, and Jiajia Wang. 2013.  SIR rumor spreading model in the new media age.  _Physica A: Statistical Mechanics and its Applications_ 392, 4 (2013), 995–1003.
  * Zhao et al. [2020] Zilong Zhao, Jichang Zhao, Yukie Sano, Orr Levy, Hideki Takayasu, Misako Takayasu, Daqing Li, Junjie Wu, and Shlomo Havlin. 2020.  Fake news propagates differently from real news even at early stages of spreading.  _EPJ Data Science_ 9, 1 (2020), 7.  https://doi.org/10.1140/epjds/s13688-020-00224-z
  * Zhu et al. [2019] Wenlong Zhu, Wu Yang, Shichang Xuan, Dapeng Man, Wei Wang, Xiaojiang Du, and Mohsen Guizani. 2019.  Location-based seeds selection for influence blocking maximization in social networks.  _IEEE Access_ (2019), 27272–27287.


# Supplementary Information: Experimental nonequilibrium memory erasure beyond
Landauer’s bound

Mario A. Ciampini  Vienna Center for Quantum Science and Technology (VCQ),
Faculty of Physics, University of Vienna, A-1090 Vienna, Austria  Tobias Wenzl
Vienna Center for Quantum Science and Technology (VCQ), Faculty of Physics,
University of Vienna, A-1090 Vienna, Austria  Michael Konopik  Institute for
Theoretical Physics I, University of Stuttgart, D-70550 Stuttgart, Germany
Gregor Thalhammer  Division for Biomedical Physics, Medical University of
Innsbruck, 6020 Innsbruck, Austria  Markus Aspelmeyer  Vienna Center for
Quantum Science and Technology (VCQ), Faculty of Physics, University of
Vienna, A-1090 Vienna, Austria  Institute for Quantum Optics and Quantum
Information (IQOQI), Austrian Academy of Sciences, 1090 Vienna, Austria  Eric
Lutz  Institute for Theoretical Physics I, University of Stuttgart, D-70550
Stuttgart, Germany  Nikolai Kiesel  Vienna Center for Quantum Science and
Technology (VCQ), Faculty of Physics, University of Vienna, A-1090 Vienna,
Austria

##  I Generalised Landauer’s Bound

We reformulate Landauer’s principle in terms of relative entropies between
distributions, to take into account the non-equilibrium characteristic of the
initial state. Starting from the First and Second law of thermodynamics, we
can rewrite work as:

$\langle W\rangle\geq\Delta U-T\Delta S\equiv W_{L}.$ (1)

Where $\Delta U$ is the change in internal energy and $\Delta S$ is the change
in entropy. The time-dependent equilibrium Hamiltonian can be rewritten using
the equilibrium distribution $H_{eq}=-kT\ln Z_{eq}-kT\ln\rho_{eq}.$ Therefore:

$\displaystyle W_{L}$ $\displaystyle=$ $\displaystyle\langle
H_{eq}\rangle_{i}-\langle H_{eq}\rangle_{f}+T(S_{f}-S_{i})$ $\displaystyle=$
$\displaystyle
kT(\langle\ln\rho_{eq}\rangle_{i}-\langle\ln\rho_{eq}\rangle_{f}+\langle\ln\rho_{f}\rangle_{f}-\langle\ln\rho_{i}\rangle_{i})$
$\displaystyle=$ $\displaystyle
T(I(\rho_{f},\rho_{eq})-I(\rho_{i},\rho_{eq}))=T\Delta I,$

with the relative entropy being defined as
$I(\rho_{f/i},\rho_{\text{eq}})=k\langle\ln\left[\rho_{f/i}/\rho_{eq}\right]\rangle=k\int\rho_{f/i}\ln\left[\rho_{f/i}/\rho_{\text{eq}}\right]dxdv$.
Heat is then given by

$\langle Q\rangle\geq W_{L}-\Delta U\equiv Q_{L},$ (3)

using the sign convention $\Delta U=W-Q$.

###  I.1 Asymmetry corrections

Here we derive Landauer’s bound by taking into account asymmetry in the
potential and imperfect erasure. We approximate the double-well potential with
high-barrier by fitting both wells with harmonic oscillator potentials, for
the theoretical bound we also ignore any potential momentum distribution
differences, i.e. we assume that the momentum distribution stays approximately
thermal. There are three relevant distributions, the equilibrium distribution
$\rho_{\text{eq}}$ which is used to determine the equilibrium potential, the
initial distribution $\rho_{\text{i}}$ and the final one $\rho_{\text{f}}$.

The position distribution for the equilibrium distribution is given by:

$\rho_{eq}=\begin{cases}p^{0}_{eq}e^{-\beta\sigma^{0}_{eq}(x-x_{0})^{2}}/Z^{0}_{eq}&\text{for
}x>0\\\ p^{1}_{eq}e^{-\beta\sigma^{1}_{eq}(x+x_{1})^{2}}/Z^{1}_{eq}&\text{for
}x<0.\end{cases}$ (4)

The distribution parameters $p^{0/1}_{eq},\sigma^{0/1}_{eq}$ are replaced by
$p^{0/1}_{i},\sigma^{0/1}_{i}$ when describing the initial out-of-equilibrium
distribution, and by $p^{0/1}_{f},\sigma^{0/1}_{f}$ for the final one. Here,
we assume for simplicity that the position of the minimum does not change
before/after reset. $p^{0/1}$ represents the probability of the particle being
on either side of the wells, thus $p^{0}=1-p^{1}$ holds. In order to recover
the well-known Landauer’s bound of $kT\ln 2$, $p^{0}_{eq}=p^{0}_{i}=1/2$ and
$p^{0}_{f}=1$. This treatment allows to recover bounds accounting for
asymmetry in the potential and a non-perfect reset. We do assume, however,
that $p^{0/1}_{eq}=p^{0/1}_{i}$: we improve the reset by solely altering the
entropy within the wells.

In thermal equilibrium, we can reconstruct the potential by using
$V(x)=-\text{kT}\ln(p(x))$. Calculating explicitly the quantities in Eq.I, the
energies are given by

$\langle
H_{eq}\rangle_{i}=\frac{kT}{2}\left(p^{0}_{i}\frac{\sigma^{0}_{eq}}{\sigma^{0}_{i}}+p^{1}_{i}\frac{\sigma^{1}_{eq}}{\sigma^{1}_{i}}\right)-kT(p^{0}_{i}\ln
p^{0}_{eq}+p^{1}_{i}\ln p^{1}_{eq}),$ (5)

for the initial case and replacing $p^{0/1}_{f}$ for $p^{0/1}_{i}$ as well as
$\sigma^{0/1}_{f}$ for $\sigma^{0/1}_{i}$ for the final case. The entropy
difference is given by

$\displaystyle\Delta S$ $\displaystyle=$
$\displaystyle-k\left(\int\rho_{f}\ln\rho_{f}dx-\int\rho_{i}\ln\rho_{i}dx\right)$
$\displaystyle=$ $\displaystyle k(p^{0}_{i}\ln p^{0}_{i}+p^{1}_{i}\ln
p^{1}_{i}-p^{0}_{f}\ln p^{0}_{f}-p^{1}_{f}\ln p^{1}_{f}$
$\displaystyle+p^{0}_{f}\ln Z^{0}_{f}+p^{1}_{f}\ln Z^{1}_{f}-p^{0}_{i}\ln
Z^{0}_{i}-p^{1}_{i}\ln Z^{1}_{i})$ $\displaystyle=$ $\displaystyle
k\ln\frac{{(p^{0}_{i})}^{p^{0}_{i}}{(p^{1}_{i})}^{p^{1}_{i}}}{{(p^{0}_{f})}^{p^{0}_{f}}{(p^{1}_{f})}^{p^{1}_{f}}}+k\ln\frac{{(Z^{0}_{f})}^{p^{0}_{f}}{(Z^{1}_{f})}^{p^{1}_{f}}}{{(Z^{0}_{i})}^{p^{0}_{i}}{(Z^{1}_{i})}^{p^{1}_{i}}}.$

Using Eq. I, the expression for the generalized Landauer’s bound for our
potential is:

$\displaystyle\frac{W_{L}}{kT}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\frac{\sigma^{0}_{eq}(p^{0}_{i}\sigma^{0}_{i}-p^{0}_{i}\sigma^{0}_{f})}{\sigma^{0}_{i}\sigma^{0}_{f}}+\frac{\sigma^{1}_{eq}(p^{1}_{i}\sigma^{1}_{i}-p^{1}_{i}\sigma^{1}_{f})}{\sigma^{1}_{i}\sigma^{1}_{f}}\right)$
$\displaystyle+\ln\frac{(p^{0}_{eq})^{p^{0}_{i}}(p^{1}_{eq})^{p^{1}_{i}}}{(p^{0}_{eq})^{p^{0}_{f}}(p^{1}_{eq})^{p^{1}_{f}}}-\ln\frac{(p^{0}_{i})^{p^{0}_{i}}(p^{1}_{i})^{p^{1}_{i}}}{(p^{0}_{f})^{p^{0}_{f}}(p^{1}_{f})^{p^{1}_{f}}}-\ln\frac{(Z^{0}_{f})^{p^{0}_{f}}(Z^{1}_{f})^{p^{1}_{f}}}{(Z^{0}_{i})^{p^{0}_{i}}(Z^{1}_{i})^{p^{1}_{i}}}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(\frac{\sigma^{0}_{eq}(p^{0}_{f}\sigma^{0}_{i}-p^{0}_{i}\sigma^{0}_{f})}{\sigma^{0}_{i}\sigma^{0}_{f}}+\frac{\sigma^{1}_{eq}(p^{1}_{f}\sigma^{1}_{i}-p^{1}_{i}\sigma^{1}_{f})}{\sigma^{1}_{i}\sigma^{1}_{f}}\right)$
$\displaystyle+\ln\frac{(p^{0}_{f})^{p^{0}_{f}}(p^{1}_{f})^{p^{1}_{f}}}{(p^{0}_{eq})^{p^{0}_{i}}(p^{1}_{eq})^{p^{1}_{i}}}+\frac{1}{2}\ln\frac{(\sigma^{1}_{f})^{p^{1}_{f}}(\sigma^{1}_{f})^{p^{1}_{f}}}{(\sigma^{0}_{i})^{p^{0}_{i}}(\sigma^{1}_{i})^{p^{1}_{i}}},$

where in the last line we assumed $p^{0}_{eq}=p^{0}_{i}$. There are three
contributions to the work cost. The latter two are comprised of the logical
component given by the probabilities and the internal potential width
components. The first term is the energy difference between the initial
locally squeezed distribution and the equilibrium one. The thermal energy
$kT/2$ of the thermal distribution is reduced by the initial distribution in
the equilibrium potential. The first fast step thus is accompanied with an
energetic cost to work that makes the work larger than heat in the Landauer’s
bound (up to $kT/2$). If we ignore the fast step, then this term would vanish
and work/heat would be equal in the symmetric case and only differ because of
the potential offsets. As the first step is faster than the movement of the
particle, this work offset is just added numerically when retrieving the
bound.

We further explicitly distinguish the contribution to the generalised
Landauer’s bound coming from the non-equilibrium character of the initial
state ($\Delta W_{neq}$) from the one coming from the asymmetry of the
potential ($\Delta W_{asymm}$). To this end, we rewrite Eq. I.1 using
$p^{1}=1-p^{0}$, $\sigma^{0}=\sigma^{1}$, $\sigma_{i}=\epsilon\sigma_{eq}$. We
obtain:

$W_{L}/k_{B}T=\frac{1}{2}\left(2\log\left((1-p^{0}_{f})^{1-p^{0}_{f}}(p^{0}_{f})^{p^{0}_{f}}(1-p^{0}_{eq})^{p^{0}_{f}-1}(p^{0}_{eq})^{p^{0}_{f}}\right)-\frac{1}{\epsilon}+\log\left(\frac{1}{\epsilon}\right)+1\right)=\ln
2-(\Delta W_{asymm}+\Delta W_{neq})/k_{B}T.$ (7)

In Table 1 we report the experimental probabilities, as well as the asymmetry
correction to the bound given in Eq. 7. The probability $p^{0}$ ($p^{1}$) is
calculated as the frequency of the particle being in well ”0” (”1”) over the
total number of repetitions. Errors on these parameters are evaluated by
dividing the whole number of protocol repetition in M statistically
independent subsets from which the standard deviation is calculated and
propagated.

##  II Trapping scheme

We create the trap with a CFI TU Plan Fluor EPI 50x, NA=0.8, WD=1mm (Nikon
Corp.) objective in the vacuum chamber is mounted. Between the objective and
the collimation lens, two razor blades, spaced by $\approx 100\mu m$, are
mounted to create the necessary linear unbalancing force. The electrode holder
is a 3D-printed custom designed element, made of Accura Xtreme White (Proto
Labs GmbH). The spacing is small enough that the electrodes are fixed in their
position. The holder is screwed onto a MX25 translation stage that is
controlled by a CU30 controller (Mechonics AG.). This allows for a three-
dimensional movement of the electrodes with 2 mm total travel distance in each
direction (see Fig. S1). Particles are trapped with the standard method using
an ultrasonic nebulizer. We perform the experiment at a pressure in the vacuum
chamber of $(30.0\pm 0.3)$ mbar. The $\text{TEM}_{10}$mode is created by means
of a 512x512 spatial light modulator (SLM) (Meadowlark, Inc.), which has been
previously calibrated to account for non-linear response of the pixels and
non-flatness of the active surface. A simple splitting of the SLM active area
to create a $\pi$ phase shift at the center of the beam (see Fig. S2) creates
the wanted potential.

Figure S1: Schematic representation of the vacuum chamber Figure S2:
Experimental setup: Two independent, orthogonal polarised laser beams (H:
Mephisto (Coherent) + Keopsys Fiber Amplifier, V: Opus (Laser Quantum)) are
modulated in intensity using independently controlled AOM’s working in first-
order diffraction and frequency shifted by 80MHz. Light is coupled into SMF
and compensated in polarisation, then expanded to a beam diameter of approx
7mm and recombined into a PBS. An SLM is programmed to create a
$\text{TEM}_{10}$mode for the vertically polarised light. In the vacuum
chamber a microscope objective (NA=0.8) creates the optical trap. Electrodes
are placed around the focal point and can be positioned through a translation
stage. The light from the trap is then collected and filtered in polarisation.
Vertically polarised light is used to monitor the $\text{TEM}_{10}$power,
horizontally polarised light is split: 1% of the light is used to measure the
particle position using a split-mirror detection scheme, the remaining 99% of
the light is reflected into the vacuum chamber to create the standing wave.
List of acronyms: PBS - polarizing beam splitter, AOM - acusto-optical
modulator, SLM - spatial light modulator, SMF - single mode fiber, CCD -
charged-coupled device fast camera, BS - beam splitter, HWP - half-wave plate,
QWP - quarter-wave plate.

##  III Calibration

###  III.1 Position Detection and Detector Calibration

Figure S3: Power dependence of detector sensitivity. $\sigma_{\phi_{det}}$ as
a function of the power in the detector show a linear response. The optical
power is attenuated right in front of the detector, for a fixed trap frequency
of $\omega_{0}$

The particle position is measured using a standard split-mirror detection
scheme: The forward propagating $\text{TEM}_{00}$light mode is separated from
the $\text{TEM}_{10}$mode, attenuated and split along the vertical axis by
means of a sharp-edged D-shaped mirror. Light is attenuated and sent to a pair
of balanced InGaAs detectors (PDB425C, Thorlabs Inc.) where the difference
signal $\phi_{det}$ is measured. The displacement of the particle is
proportional to that signal when the particle is in trapped close to the
center of the potential ($\Delta x=c_{center}\phi_{det}$). In this condition,
the calibration factor $c_{center}$ can be calculated for each trapped
particle using an independent measurement, where the power of the
$\text{TEM}_{10}$mode is set to zero. By assuming harmonic motion in the
$\text{TEM}_{00}$, we use the equipartition theorem:
$m\omega_{0}^{2}c_{center}\sigma_{\phi_{det}}(\omega_{0})^{2}=kT$. Here
$m=(2.831\pm 0.001)\cdot 10^{-18}\text{kg}$ is the mass of the silica
nanosphere as provided by the manufacturer specifications, $k$ is the
Boltzmann constant, $T=300$K is the room temperature and
$\omega_{0}=2\pi(210.1\pm 0.8)\text{kHz}$ is the particle frequency, for a
power in the optical trap of $P_{0}=(100\pm 1)\text{mW}$, where
$\sigma_{\phi_{det}}(\omega_{0})=(0.042\pm 0.001)\text{V}$ is the standard
deviation of the detector signal. In Fig. S3 we show a typical dependence of
$\sigma_{\phi_{det}}(\omega_{0})$ on the power at the detector, where the
particle trapped at a pressure 0.1 mbar and only in the $\text{TEM}_{00}$mode
at a constant power, ($\alpha=1,\beta=0,F=0$). For this configuration, we
obtain:

$c_{center}=\sqrt{\frac{kT}{m}}\frac{1}{\sigma_{\phi_{det}}\omega_{0}}=(6.95\pm
0.06)\cdot 10^{-7}m/V.$

However, when the particle is significantly off-center (for example when the
particle is in either of the two wells of the $\text{TEM}_{10}$mode) the
sensitivity (i.e. the calibration factor) of the detection scheme is reduced,
because less light from the $\text{TEM}_{00}$mode is scattered by the
particle. In fact, if we repeat the above calibration for when the particle is
on the left and right well, we get:

$\begin{array}[]{cc}c_{left}&=(2.95\pm 0.04)\cdot 10^{-6}m/V.\\\
c_{right}&=(2.62\pm 0.03)\cdot 10^{-6}m/V.\end{array}$

Thus, we investigate the dependence of the calibration factor on the particle
position $c(x)$ for the relevant spatial interval. This is possible by an
analysis of the particle dynamics in an equilibrium scenario, as will be
discussed in the following. The data used to calibrate the effect stems from
the re-initialisation part of the protocols, i.e. is taken independently of
the erasure protocol and with precisely the same experimental configuration
and particle. During the re-initialisation phase we obtain trajectories with
the particle equilibrated in each of both wells, respectively. We obtain this
data for two different powers, with the potential set to ”high” and ”low”. We
label $s(t)$ the uncalibrated particle trajectory registered by the detector.
The goal is to reconstruct calibrated particle trajectory in real space
$x(t)$. We define $\eta(s)=dx/ds$ as the differential calibration factor,
which we expect to correspond to the calibration factor $c_{i}$ as discussed
above (i= left, right, center). Accordingly, $\partial V/\partial s=\partial
V/\partial x\cdot\partial x/\partial s=F(x)\eta(s)$. Let us first consider an
isolated particle (no friction, no force noise) moving in a potential
landscape and detected in a scheme with a position dependent calibration
factor:

$\displaystyle F(x)$ $\displaystyle=$
$\displaystyle\frac{1}{\eta(s)}\cdot\frac{\partial V}{\partial s}$ (8)
$\displaystyle F(s(x))/m$ $\displaystyle=$
$\displaystyle\frac{\partial}{\partial t}(\dot{x})=\frac{\partial}{\partial
t}(\eta(s)\dot{s})=\frac{\partial\eta}{\partial s}\dot{s}^{2}+\eta(s)\ddot{s}$
(9) $\displaystyle=$
$\displaystyle\frac{1}{\eta(s)}\left(\frac{\partial\eta^{2}}{\partial
s}\cdot\frac{\dot{s}^{2}}{2}+\eta^{2}\ddot{s}\right)$ (10)

From this we can deduce how Newtons laws are transformed for the uncalibrated
trajectories in dependence of the differential calibration factor.

$\frac{\partial V}{\partial s}=\frac{\partial\eta(s)^{2}}{\partial
s}\cdot\frac{\dot{s}^{2}}{2}+m\eta^{2}(s)\ddot{s}$ (11)

Clearly, the detected uncalibrated trajectory allows to determine the
calibration factor using the kinetic quantities in this equation. Consider a
particle that is weakly coupled to and in equilibrium with an environment. For
a sufficiently large ensemble of data where a particle crosses a specific
position, the above equations hold on average, as random force noise as well
as friction cancel on average. Accordingly:

$\langle\frac{\partial V}{\partial
s}\rangle=\frac{\partial\eta(s)^{2}}{\partial
s}\cdot\langle\frac{\dot{s}^{2}}{2}\rangle+m\eta^{2}(s)\langle\ddot{s}\rangle$
(12)

The calibration factor is now expressed in terms of a first order differential
equation with uncalibrated quantities, which are known: the reconstructed
potential derivative, the average kinetic energy and the average acceleration
when the particle is in the $\text{TEM}_{00}$mode and in the wells of the
$\text{TEM}_{10}$high and low power mode. We numerically solve the
differential equation to reconstruct $\sqrt{\eta^{2}(s)}$.

In Fig. S4a we show the differential calibration factor as a function of the
voltage response of the detector. The data is obtained by stitching the
numerical results for the ”high” and ”low” as well as the
$\text{TEM}_{00}$potential. While this allows to cover the full relevant range
of data, it results in two apparent discontinuities and corresponding large
error bars due to numerical mismatch in the different reconstructions. In fact
for each component we manually adjust the position offset $\langle
V(s+\epsilon=\epsilon_{0})\rangle$ to minimize discontinuities. We evaluate
error bars on the points by performing a Montecarlo simulation where we
randomly generate $\epsilon$ in an around of $\epsilon_{0}$. In order to
compare this dynamics-based full-range calibration method with the standard
measurement for harmonic potentials described before, Fig.S4 also features the
values $c_{left}$ and $c_{right}$ and $c_{center}$ as blue dots showing a good
agreement between the two calibration methods.

We interpolate the data points with the function
$\alpha_{4}(s-s_{0})^{4}+\alpha_{0}$, which preserves the expected flatness of
the calibration function around zero. In Fig. S4b we show the integrated
calibration factor
$\eta_{0}(x)=\int_{s_{min}}^{x}\eta(s^{\prime})ds^{\prime}$, which allows us
to determine the real space trajectory for any of our measurements in post
processing.

Figure S4: Detector Sensitivity. a) Differential calibration factor as a
function of the detector response. Black points: experimental values. Error
bars are 1-sigma, evaluated with a Montecarlo simulation. Blue points:
calibration factor evaluated using the equipartation theorem in approximately
harmonic traps with error bars are smaller than point size. Red: fit of all
data points with a quartic function. b) Correspondingly calibrated position as
a function of the detector response (uncalibrated position).

Every measured timetrace is rescaled to account for power fluctuations, which
are monitored during the whole measurement, and their linear effect on the
calibration in Fig. S3. Specifically, the data is normalised to a power
$P_{0}$ corresponding to a measured voltage of $\phi_{det_{max}}=(5.51\pm
0.02)V$.

###  III.2 Electrodes Calibration

We calibrate the displacement force $F=c_{f}\phi_{f}$ due to the voltage
$\phi_{f}$ applied to the electrodes by measuring the displacement of the
particle in the $\text{TEM}_{00}$mode as a function of the voltage applied to
the electrodes. The electrodes voltage is increased from $\phi_{f}=-7.5$ V to
$\phi_{f}=7.5$ V in multiple steps using a voltage amplifier. At every step,
we measure the mean position of the particle in the tweezer. A repetition of
at least 10 times decreases the statistical error and compensates for position
drifts. Afterwards, the measurement is fitted with a linear function (see Fig.
S5) from which we extract the parameter $c_{f}$. We get:

$\frac{\langle\phi_{det}\rangle}{\phi_{f}}=\frac{\langle
x\rangle/c_{det}}{F/c_{f}}=\frac{1}{m\omega_{0}^{2}}\cdot\frac{c_{det}}{c_{f}}$

Note: every particle has a different number of charges, and thus needs a
different calibration. All protocols presented here are taken for the same
particle. The force calibration factor determined for this particle is
$c_{f}=(5.1\pm 0.3)10^{-14}N/V$. The maximal tilting force applied in the
protocol is $F_{max}=4.4\cdot 10^{-14}\text{N}$ and corresponds to
$\phi_{f_{max}}=F_{max}/c_{f}=0.86V$ .

Figure S5: Calibration of the electrodes. Top) Potential reconstruction of a
particle in a $\text{TEM}_{00}$mode for various values of the electrodes
voltage. Bottom) Average position of particle as a function of electrodes
voltage.

##  IV Potential Model

The calculation of work applied during a protocol is based on the knowledge of
the optical potential at every time. We model the full time-dependence based
on our time-dependent parameter-settings and the reconstuction of the
potential for relevant, specific parameter settings, corresponding to
snapshots of the protocol. The potential reconstruction for these snapshots is
obtained from a series of independent measurements: we first let the particle
equilibrate to the respective potential landscape. Then we measure the
particle’s position probability distribution $p(x)$ taking a timetrace which
is sufficiently long ($100$ ms) to safely use the ergodic assumption. The
potential is then reconstructed by using: $V(x)=-kT\ln(p(x))$ with Boltzmann
constant $k$, temperature T. We measure the potential for various powers in
$\text{TEM}_{10}$and fixed $\text{TEM}_{00}$power. Measurements are then
sensitivity corrected, calibrated (see III,A), and fitted to find a model for
the potential depending on the power of $\text{TEM}_{00}$and
$\text{TEM}_{10}$(see some examples of measured potentials in Fig. S6). Every
potential is fitted with a function which approximates the optical potential
as a combination of $\text{TEM}_{00}$and $\text{TEM}_{10}$modes:

$f(x)=c-\frac{8\alpha(x-\text{x0})^{2}e^{-\frac{2(x-\text{x0})^{2}}{\sigma^{2}}}}{\pi\sigma^{6}}-\frac{2\beta
e^{-\frac{2(x-\text{x1})^{2}}{\sigma^{2}}}}{\pi\sigma^{4}}$

We first identify parameter $\beta$ by fitting our potential when
$\text{TEM}_{10}$is off (Fig. S6a). We use a “jumping” potential (i.e., when
the particle jumps between the wells, Fig. S6h) to infer $|x_{0}-x_{1}|$,
which identifies the asymmetry in our model, which we assume constant for the
whole experiment. We then fit the remaining potentials to find and interpolate
parameters $\alpha$, $x_{0}$, $\sigma$ and $c$ as a function power in the mode
$\text{TEM}_{10}$. This process gives us the full ability to program $V(x,t)$
for our protocol via the input parameters.

Figure S6: Potential reconstruction. Reconstruction of U(x), fixing the power
of the $\text{TEM}_{00}$after the vacuum chamber to $\alpha_{0}$=50mW, and
varying the power of $\text{TEM}_{10}$from $\beta=120mW$ (h) to $\beta=0mW$
(a).

##  V Protocols and equilibrium phase space

Figure S7: Probability Density of the reinitialisation part of the protocol.
Average position over $\approx 10000$ protocol repetitions. In the first part
the particle is in the ”low” potential, after the reset protocol. At $t=438\mu
s$ the power of $\text{TEM}_{00}$is maximised. After $t=1315\mu s$ the
$\text{TEM}_{10}$power is also maximised. At the end of the reinitialisation,
the particle is reequilibrated to a ”high” power potential.

Every protocol timetrace is measured using a split detection scheme, and
sampled at $6.25MS/s$. A calibrated timetrace $x^{l}(t_{i})$ (i is the i-th
time step, l is the l-th repetition of the protocol). A full protocol consists
of three parts. In the first part we perform a fast ($t_{up}=3\mu s$) increase
in the power of the trap, followed by a slower ($t_{neq}=358\mu s$) decrease
back to the memory potential; In the second part is the equilibrium erasure,
where $\text{TEM}_{10}$is quasi-adiabatically modified to first decrease and
then increase again the potential barrier ($t_{eq}=1358\mu s$). At
$t_{1}=728\mu s$ we introduce a linear increase of the electrostatic force
that reaches its maximum $F_{max}$ at $t_{2}=1258\mu s$, decreasing again
linearly till the end of the protocol. The third part is a reset protocol that
restarts the particle in its original (non-equilibrium) distribution
$\rho_{neq}$. This part is not evaluated for the work and heat consumption.
First the particle is let to equilibrate to the final position, then
$\text{TEM}_{00}$is rapidly increased to its maximum value. Finally,
$\text{TEM}_{10}$is also increased rapidly. This sets the particle to either
of the two wells with a probability that depends on the symmetry of the
potential. Finally, the particle is let to equilibrate to this potential. We
show in Fig. S7 the probability density during the reinitialisation part of
the protocol for the $\epsilon=4$ data-set. Overall, the entire data-set lasts
$t_{tot}=3116\mu s$. The double-well potential is consistently set to the same
power ratio between the two modes ($\text{TEM}_{10}$is 2.7 times the one of
the $\text{TEM}_{00}$measured right after the vacuum chamber). Parameter
$\epsilon$ is set such as the trap power is $(\epsilon+1)$ times stronger than
the power for the equilibrium potential. In Fig. S8 we show the phase-space
distribution of the particle state at the beginning (top) and at the end of
the erasure protocol (bottom).

Figure S8: x-v phase-space of the erasure protocol. Top) Initial state (out of
equilibrium) state, Bottom) Final state after reset. Position and velocity are
normalised to $x_{th}=\sqrt{k_{B}T/(m(2\pi\nu_{0})^{2}}$ and
$v_{th}=\sqrt{k_{B}T/m}$, where $\nu=80kHz$ and $m=2.83fg$.

##  VI Evaluation of Landauer’s bound

Given a protocol timetrace $x^{l}(t_{i})$ and the potential model $V(x,t)$, we
define the average dissipated work as:

$\displaystyle\langle W\rangle_{\epsilon}$
$\displaystyle=\langle\int_{0}^{t_{eq}}\frac{\partial{V(x,t)}}{\partial
t}dt\rangle_{\epsilon}\rightarrow$
$\displaystyle\rightarrow\langle\sum_{i=0}^{t_{fin}}\left[V(x_{i},t_{i+1})-V(x_{i},t_{i})\right]\rangle_{\epsilon}$

The average dissipated heat during the protocol, following the First Law is:

$\displaystyle\langle Q\rangle_{\epsilon}$ $\displaystyle=\langle
W\rangle-\langle\Delta E\rangle$

Here $\langle\rangle$ is the average over $M\approx 10000$ protocols, and
$\epsilon$ is the non-equilibrium parameter. In addition, we define $\Delta
E_{i}=E_{i}(t_{fin})-E_{i}(t_{0})=\frac{1}{2}m((v_{fin}^{i})^{2}-(v_{0}^{i})^{2})+[V(x_{fin}^{i},t_{protocol})-V(x_{init}^{i},t_{protocol})]$
as the total energy variation between the beginning (out-of-equilibrium) and
ending (equilibrium) of the protocol. In Table 1 we report experimental values
for average work, heat, and energy difference as a function of $\epsilon$.
Uncertainty is evaluated through the standard deviation of the resulting
distribution, and propagated for the averaging over all the repetitions of the
protocol.

$\epsilon$ | $p_{0}^{eq}$ | $p_{0}^{f}$ | $\langle W\rangle$ | $\langle\Delta E\rangle$ | $\langle Q\rangle$ | $\Delta W_{asym}$
---|---|---|---|---|---|---
0 | $0.634\pm 0.006$ | $0.040\pm 0.001$ | $0.583\pm 0.045$ | 0 | $0.62\pm 0.064$ | $0.121\pm 0.047$
1 | $0.415\pm 0.006$ | $0.004\pm 0.001$ | $0.487\pm 0.048$ | $0.185\pm 0.031$ | $0.295\pm 0.06$ | $0.060\pm 0.016$
2 | $0.423\pm 0.007$ | $0.0046\pm 0.0014$ | $0.351\pm 0.046$ | $0.283\pm 0.070$ | $0.024\pm 0.086$ | $0.081\pm 0.019$
3 | $0.637\pm 0.021$ | $0.033\pm 0.010$ | $0.196\pm 0.042$ | $0.447\pm 0.042$ | $-0.215\pm 0.06$ | $0.156\pm 0.070$
4 | $0.566\pm 0.015$ | $0.0210\pm 0.0035$ | $0.054\pm 0.023$ | $0.446\pm 0.023$ | $-0.328\pm 0.032$ | $0.222\pm 0.028$
Table 1: Experimental parameters. $\epsilon$ is the non-equilibrium parameter.
$p_{0}^{eq}$ is the probability of the particle starting in well 0.
$p_{0}^{f}$ is the probability of the particle being in well 0 after the
protocol. $\langle W\rangle$ is the average extracted work during all the
repetitions of the protocol. $\langle\Delta E\rangle$ is the average energy
difference between start and end of the protocols. $\langle Q\rangle$ is the
average dissipated heat during the protocols (a negative value indicates
cooling of the environment). $\langle\Delta W_{asym}\rangle$ is the correction
to Landauer’s bound given by the asymmetry of the potential and non-perfect
erasure.