# Post-hoc Evaluation of Nodes Influence in Information Cascades: The Case of
Coordinated Accounts

Niccolò Di Marco<EMAIL_ADDRESS>0000-0003-4335-7328 Sapienza
University of RomeViale Regina Elena 295RomaItaly ,  Sara Brunetti
<EMAIL_ADDRESS>0000-0001-8607-6900 University of SienaSienaItaly ,
Matteo Cinelli<EMAIL_ADDRESS>0000-0003-3899-4592 Sapienza
University of RomeViale Regina Elena 295RomaItaly and  Walter Quattrociocchi
<EMAIL_ADDRESS>0000-0002-4374-9324 Sapienza University of
RomeViale Regina Elena 295RomaItaly

###### Abstract.

In the last years, social media has gained an unprecedented amount of
attention, playing a pivotal role in shaping the contemporary landscape of
communication and connection. However, Coordinated Inhautentic Behaviour
(CIB), defined as orchestrated efforts by entities to deceive or mislead users
about their identity and intentions, has emerged as a tactic to exploit the
online discourse. In this study, we quantify the efficacy of CIB tactics by
defining a general framework for evaluating the influence of a subset of nodes
in a directed tree. We design two algorithms that provide optimal and greedy
post-hoc placement strategies that lead to maximising the configuration
influence. We then consider cascades from information spreading on Twitter to
compare the observed behaviour with our algorithms. The results show that,
according to our model, coordinated accounts are quite inefficient in terms of
their network influence, thus suggesting that they may play a less pivotal
role than expected. Moreover, the causes of these poor results may be found in
two separate aspects: a bad placement strategy and a scarcity of resources.

Trees, Influence, Coordinated Inhautentic Behaviour

††copyright: acmlicensed††ccs: Networks Network algorithms††ccs: Applied
computing††ccs: Mathematics of computing Trees††ccs: Mathematics of computing
Graph algorithms

##  1\. Introduction

Social media has transformed how we connect and share information, thus
reshaping some of the mechanisms that we use for engaging with the world.
Platforms that have been initially designed for entertainment, are
increasingly becoming the principal environment in which opinions and views
take form, determining a new tendency in information consumption
(bakshy2012role, ; flaxman2016filter, ; schmidt2017anatomy, ).

However, this radical change came at the cost of a number of downsides such as
online harassment, toxicity and hateful speech (ZINOVYEVA2020113362, ;
trujillo2022make, ), polarisation (garrett2009echo, ; bail2018exposure, ;
tucker2018social, ; cinelli2021echo, ; falkenberg2022growing, ) and the
spreading of misleading information (bakshy2012role, ; del2016spreading, ;
lazer2018science, ; bovet2019influence, ; santos2021link, ;
hristakieva2022spread, ; juul2021comparing, ; pierri2023propaganda, ). In this
landscape, special attention has been posed to investigate the phenomenon of
Coordinated Inauthentic Behaviour (CIB) which, according to Meta’s definition,
is ”the use of multiple Facebook or Instagram assets, working in concert to
engage in inauthentic behaviour, where the use of fake accounts is central to
the operation”. More in detail, according to the platform’s Community
Standards (https://transparency.fb.com/en-gb/policies/community-
standards/inauthentic-behavior/), the concept of inauthentic behaviour refers
to people who ”misrepresent themselves on Facebook, use fake accounts,
artificially boost the popularity of content or engage in behaviours designed
to enable other violations”. Related to CIB researchers investigated the
phenomenon of Coordinated Behavior (CB), which can be defined as an
unexpected, suspicious, or exceptional similarity among users of a group
(nizzoli2021coordinated, ).

Recent studies highlight that accounts displaying CIB, CB and social bots
(i.e. software agents that communicate autonomously on social media and other
platforms, having different uses and purposes (Lebeuf2019, ; Seering2018, ;
Zheng2019, ; Klopfenstein2017, )) may have played a role in relevant events
(ruths2019misinformation, ) such as political elections (grinberg2019fake, ;
cinelli2022coordinated, ; keller2020political, ), and in disseminating false
information (shao2018spread, ; mendoza2020bots, ; cresci2020decade, ;
sharma2021identifying, ; Pacheco2020, ). It follows that, beyond detection
challenges (nizzoli2021coordinated, ; pacheco2021uncovering, ;
luceri2023unmasking, ; nwala2023language, ), one key reason to study such
accounts relies on their potential to manipulate public opinion by swaying the
narrative and influence the perceptions and views of a large audience
(schoch2022coordination, ).

In this work, we measure the influence of such potentially malicious accounts
as the numerosity of the audience they interact with. In particular, we
introduce a general framework that allow us to compare their influence with
two different theoretical (post-hoc) models for coordinated accounts placement
in information cascades:

  1. (1)

first we consider an optimal model, in which we identify the number and
disposition of coordinated accounts to ensure the maximal influence over the
tree, without imposing any constraints on the number of coordinated accounts
to be used;

  2. (2)

second, we focus on a greedy strategy in which we have a fixed number of
coordinated accounts to place to maximise the influence (i.e. limited
capabilities case).

Notably, the algorithms provided can be extended to any other influence
problem modelled using binary labels on trees.

Using simulations on synthetic data, we show that, on average, it is possible
to exert maximum influence using a limited number of coordinated accounts
whose value highly depends on the height of the considered tree. Furthermore,
the labelling that corresponds to the optimal placement results to be rare
compared to the whole set of possible arrangements of node labels. As a case
study, we compare the influence obtained by our models in a large dataset made
of $\sim 50K$ Twitter cascades, built starting from $~{}1.4M$ of tweets about
the 2019 UK political elections (cinelli2022coordinated, ).

Our results show that, according to our modelling, coordinated accounts exert
a much lower influence than the one obtained using both the unconstrained
algorithm and the greedy strategy. The reasons for this behaviour have to be
searched in two distinct factors: a limited number of available resources
(i.e. coordinated accounts) and a bad placement strategy. We conclude by
noticing that, in general, the observed placement closely resembles a random
placement rather than a specific strategy.

Despite the limitations of our post-hoc models, our results suggest that CB
may exert a limited influence, contrary to what is expected.

##  2\. Definitions

We consider a directed tree $T=(V,E)$ such that $|V|=n$. In particular, each
node represents a user, while a directed edge indicates the direction of the
flow of information among them. To distinguish between coordinated and non-
coordinated users, we assign a binary label $\mathscr{l}_{v}$ to each node,
such that $v$ belongs to the coordinated users if and only if
$\mathscr{l}_{v}=1$. To keep us general, we say that $v$ is a $1-$node if
$\mathscr{l}_{v}=1$ and a $0-$node otherwise. We collect the labels in the
vector $\mathscr{l}$.

We denote with $N(v)$ the out-neighbourhood of a node $v$ (without $v$ itself)
and as $d(v)$ its out-degree. Moreover, we define
$d_{0}^{\mathscr{l}}(v)=\\{w\in N(v)\;|\;\mathscr{l}_{w}=0\\}$, i.e. the
number of $0-$nodes in the out-neighbourhood of $v$. A similar definition
holds for $d_{1}^{\mathscr{l}}(v)$.

Given a labelling $\mathscr{l}$, we denote the subset of $1-$nodes in $V$ by
$V_{1}^{\mathscr{l}}=\\{v\in V\;|\;\mathscr{l}_{v}=1\\}$, and its cardinality
by $k_{\mathscr{l}}=\lvert V_{1}^{\mathscr{l}}\rvert$, i.e. the number of
$1-$nodes in $V$.

Finally, $p_{\mathscr{l}}(w)$ is the binary variable indicating if the parent
of $w$ is a $1-$node (i.e. it has a direct interaction with a coordinated
account).

We define the influence of a configuration $(T,\mathscr{l})$ as

(1) $I_{\mathscr{l}}(T)=\sum_{v\in
V_{1}^{\mathscr{l}}}d_{0}^{\mathscr{l}}(v).$

Equation (1) counts the number of non-coordinated users that are connected
(i.e. share content) of a coordinated one. Therefore, it provides a measure of
the impact that coordinates users exert on non-coordinated ones.

We are interested in defining an algorithm that searches the labelling (i.e.
the disposition of coordinated accounts) that maximises (1). We denote the
optimum influence among all the labelings by $I_{\mathscr{l}}^{*}(T)$ and its
labeling using the minimum number of coordinated accounts by
$\mathscr{l}^{*}(T)$. Accordingly, we denote as $V_{1}^{*}$ and
$k^{*}(T)=\lvert V_{1}^{*}\rvert$ the set of optimal $1-$nodes and its
cardinality. We highlight that, when the context is clear, we will omit
$\mathscr{l}$ and $T$ from all the previous notations.

For example, consider the tree depicted in Figure 1. Among all the possible
labels, the optimal one has $I^{*}=6$ and $k^{*}=2$. Indeed, even for any
labelling of size $k=3$, the influence reaches at most $6$.

Figure 1. Example of an optimal configuration. The coordinated accounts are
highlighted in red.

Interestingly, it is possible to give some constraints over the possible
values of $I^{*}$ and $k^{*}$. In more detail, let $T_{n}$ be the set of all
directed trees with $n$ vertices. Then, $\max\\{I^{*}(T):\;T\in T_{n}\\}=n-1$
and it is obtained for the configuration depicted in Figure 2 $(a)$. Note that
it corresponds also to the lower bound for $k^{*}$. On the other hand,
$\min\\{I^{*}(T):\;T\in T_{n}\\}=\lfloor\frac{n}{2}\rfloor$ and it is obtained
for the configuration depicted in Figure 2 $(b)$ which also provides the upper
bound for $k^{*}$.

Therefore, for a general directed tree $T$ on $n\geq 2$ vertices, the
following inequalities hold:

(2) $\lfloor\frac{n}{2}\rfloor\leq I^{*}(T)\leq n-1,$

(3) $1\leq k^{*}(T)\leq\lfloor\frac{n}{2}\rfloor.$

Figure 2. $(a)$ The configuration that maximizes $I^{*}(n)$ and minimizes
$k^{*}(n)$. $(b)$ The configuration that minimizes $I^{*}(n)$ and maximizes
$k^{*}(n)$.

##  3\. Data and methods

###  3.1. Data

Our dataset for this study is based on a collection of tweets related to the
online debate about the 2019 United Kingdom general elections presented in
(nizzoli2021coordinated, ). In brief, data were collected using official
Twitter API and performing both hashtag search (#GeneralElection19,
#VoteLabour, #VoteConservative etc.) and timeline download of the involved
political parties and their leaders. The time window for the download lasted
for one month, from 12 November to 12 December 2019, and the volume of
downloaded data is 11,264,820 tweets published by 1,179,659 distinct users.
The dataset is available at https://doi.org/10.5281/zenodo.4647893. The set of
coordinated accounts is also the same provided in (nizzoli2021coordinated, )
in which a method for coordinated account detection is presented. The method
is made up of the following steps: 1) Selection of influential users or super-
spreaders; 2) Selection of users similarity measure (e.g. cosine similarity);
3) Creation of a users similarity network using pairwise comparison; 4)
Filtering of users similarity network; 5) Clustering of the similarity
network. This method provides clusters of users provided with a continuous
coordination score. The distinction between coordinated and non-coordinated
accounts and the reconstruction of information cascades was performed in a
later work (cinelli2022coordinated, ) that we describe in the following lines.
Coordinated accounts were selected by retaining only the nodes at the
endpoints of the 1% of the links having the highest similarity scores. The
number of tweets is 49,331, and for each of them an information cascade based
on retweets was reconstructed using a method proposed in (de2015towards, ).
The motivation for using a specific method for cascade reconstruction is due
to the fact that Twitter API didn’t (and do not) provide the full structure of
the retweet trees so that if a user $j$ retweets $t$ by user $i$ and user $k$
retweets the same tweet $t$ from the retweet of user $j$ the edge list
provided by the Twitter API will be ($i\rightarrow j$; $i\rightarrow k$), thus
a star. However, this star is not a proper representation of the actual
information flow, being it ($i\rightarrow j$; $j\rightarrow k$). For this
reason, the method proposed in (de2015towards, ) provides a deterministic way
for reconstructing retweet-based information cascades that relies on the
knowledge of friendship networks (i.e. following relationships) and on the
assumption that a user will be retweeting a tweet from the latest retweeters
of $t$ contained in her/his list of friends. Therefore, assuming the same
situation as before, but knowing that user $k$ follows user $j$, the
reconstructed cascade will be ($i\rightarrow j$; $j\rightarrow k$). Using this
procedure on the selected 49,331 tweets and their retweets the same number of
information cascades was reconstructed. Details about the structure of such
cascades are provided in Table 1.

Number of cascades | 49331
---|---
Minimum number of nodes | 1
Maximum number of nodes | 9066
Minimum number of coordinated accounts | 0
Maximum number of coordinated accounts | 236
Table 1. Data breakdown of the cascades collected from Twitter.

###  3.2. Optimal placement of coordinated accounts without constraints on
their number

In this section we design an algorithm that, starting from a directed tree $T$
rooted at node $r$, provides $I^{*}(T)$ and $V_{1}^{*}(T)$. We highlight that,
in this section, we are not imposing an upper bound to the number of
$1-$nodes, resembling a case of unlimited resource capability.

For a node $v$, let $\mathrm{MI}(v)$ denote the value of the maximum influence
in the subtree of $T$ rooted at $v$, and $V_{1}$ denote the set of the
coordinated accounts of $T$. Moreover, let $\mathrm{MIyes}(v)$ and
$\mathrm{MIno}(v)$ be the values of the maximum influence of the subtree
rooted in $v$ that includes $v$ in $V_{1}$, and that excludes $v$ from
$V_{1}$, respectively. Our aim is to compute
$\mathrm{MI}(r)=\max\\{\mathrm{MIyes}(r),\;\mathrm{MIno}(r)\\}$.

We give a recursive definition of $\mathrm{MIyes}(r)$ and $\mathrm{MIno}(r)$.
The base cases are obtained when the height of the tree is zero or one. If the
height is zero, it means that $V=\\{r\\}$ and $E=\emptyset$. In this case,
$\mathrm{MIyes}(r)=\mathrm{MIno}(r)=0$, and
$\mathrm{MI}(r)=\mathrm{MIno}(r)=0$ since the maximum influence is 0.

If the height is one and $V=\\{r=v_{1},v_{2},\ldots v_{n}\\}$ then, without
loss of generality, let $E=\\{(v_{1},v_{2}),\ldots(v_{1},v_{n})\\}$ (i.e. $T$
is the tree depicted in Figure 2a). Then, $\mathrm{MIyes}(r)=\sum_{w\in
N(r)}(\mathrm{MIno}(w)+1)$, since if $r\in V_{1}$ the maximum influence is
equal to the sum of the children nodes not belonging to $V_{1}$. In this case
$\mathrm{MIno}(w)=0$ for all $w\in N(r)$ being leaves, and so we get

$\mathrm{MI}(r)=\mathrm{MIyes}(r)=\sum_{w\in N(r)}1=d(r).$

Suppose $T$ has height more than one. The maximum influence is computed by
considering the maximum influence of the subtrees rooted at the children of
$r$. Let’s denote the children of $r$ by $w_{1},\ldots,w_{d(r)}$, and
$T_{1}\ldots T_{d(r)}$ the subtrees rooted at each child of $r$. Then, the
following recurrence relation describes how to obtain $\mathrm{MI}(r)$:

(4) $\mathrm{MI}(r)=\max\begin{cases}\mathrm{MIno}(r)=\sum_{w\in
N(r)}\max(\mathrm{MIyes}(w),\;\mathrm{MIno}(w))\\\
\mathrm{MIyes}(r)=\sum_{w\in
N(r)}\max(\mathrm{MIyes}(w),\mathrm{MIno}(w)+1)\end{cases}$

Indeed, if the maximum influence is obtained by $r\notin V_{1}$, then it is
the sum of the values of the maximum influences for the subtrees rooted at its
children. Otherwise, if it is obtained for $r\in V_{1}$, it is the sum of the
values of the maximum influences for the subtrees rooted at its children and
adding one for every child that is not a coordinated node.

We memoize the functions $\mathrm{MIyes}$ and $\mathrm{MIno}$ into the tree
itself by defining two fields for each node $v$, that is $v.\mathrm{MIyes}$
and $v.\mathrm{MIno}$. The algorithm computes the label of each node
$v.\mathscr{l}$ by comparing $v.\mathrm{MIyes}$ and $v.\mathrm{MIno}$. Node
$v$ is included in $V_{1}$ if and only if $v.MIyes>v.MIno$ (i.e. if
$d_{0}(v)>0$).

The implementation uses a post-order tree traversal realised by one recursive
call. We denote the label obtained by the algorithm as $\bar{\mathscr{l}}$.

Algorithm 1 $\mathrm{TreeMaxInfluence}$

$v$

$I^{*}(T_{v}),V_{1}^{\bar{\mathscr{l}}}$

$v.\mathrm{MIno}\leftarrow 0$

$v.\mathrm{MIyes}\leftarrow 0$

if $v$ is a leaf then

$v.\mathscr{l}\leftarrow 0$ $\triangleright$ $v\notin V_{1}$

return $v.\mathrm{MIno}$ $\triangleright$ the Max Influence value is zero

else$\triangleright$ It has at least one child

for each child $w$ of $v$ do

$\mathrm{treeMax}\leftarrow\mathrm{TreeMaxInfluence}(w)$

$v.\mathrm{MIno}\leftarrow v.\mathrm{MIno}+\mathrm{treeMax}$ $\triangleright$
Compute the field $\mathrm{MIno}$ of $v$

if $\mathrm{treeMax}=w.\mathrm{MIno}$ then

Increment $\mathrm{count}$ $\triangleright$ Count the children $w\notin V_{1}$

end if

end for

$v.\mathrm{MIyes}\leftarrow v.\mathrm{MIno}+\mathrm{count}$ $\triangleright$
Compute the field $\mathrm{MIyes}$ of $v$

if $v.\mathrm{MIyes}>v.\mathrm{MIno}$ then

$v.\mathscr{l}\leftarrow 1$ $\triangleright$ $v\in V_{1}$

return $v.\mathrm{MIyes}$ $\triangleright$ Return the Max Influence value

else

$v.\mathscr{l}\leftarrow 0$ $\triangleright$ $v\notin V_{1}$

return $v.\mathrm{MIno}$ $\triangleright$ Return the Max Influence value

end if

end if

###### Theorem 1.

$TreeMaxInfluence(r)$ computes the optimal value of the influence of $T$ in
$O(|V|)$ time.

###### Proof.

Suppose to start with an optimal labelling of each of the subtrees rooted at
the children $w_{i}$ of $r$, i.e. $T_{i}$, with $i=1,\ldots d(r)$. If
$r.\mathrm{MIyes}\leq r.\mathrm{MIno}$ then $r$ is not inserted in $V_{1}$ and
the configuration is optimal.

Otherwise, if $r.\mathrm{MIyes}>r.\mathrm{MIno}$, $r$ is included into
$V_{1}$. If all the $r$-children are $0$-nodes, $r.\mathrm{MIyes}$ is the
optimum. Suppose that $\mathrm{MI}(r)>r.\mathrm{MIyes}$, that is, it is not
optimal and let $\mathscr{l}$ be the computed labelling. Notice that since
$r.\mathrm{MIyes}>r.\mathrm{MIno}$ and
$r.\mathrm{MIyes}=r.\mathrm{MIno}+d_{0}(r)$, then $d_{0}(r)>0$. Since
$r.MIyes$ is not optimal, there are at least two nodes $w_{i},w_{j}$ such that
$\mathscr{l}(w_{i})=0$, and $\mathscr{l}(w_{j})=1$. We have that
$w_{j}.\mathrm{MIyes}>w_{j}.\mathrm{MIno}$, where
$w_{j}.\mathrm{MIyes}=w_{j}.\mathrm{MIno}+d_{0}(w_{j})$. Thus,
$d_{0}(w_{j})>0$ which implies $w_{j}.\mathrm{MIyes}-1\geq
w_{j}.\mathrm{MIno}$. To increase the influence in the tree rooted at $r$ with
$r\in V_{1}$, one more child should be added to the $0$-nodes. Therefore let
$\bar{\mathscr{l}}$ be the new labelling that differ only for
$\bar{\mathscr{l}}(w_{j})=0$. This leads to a change of

(5)
$\Delta(I)=1-w_{j}.\mathrm{MIno}-w_{j}.\mathrm{MIyes}=d_{0}(r)+1-d_{0}(r)+w_{j}.\mathrm{MIno}-w_{j}.\mathrm{MIyes}$

since all the other terms cancel each others (they are unchanged in the two
labellings). Moreover, by $w_{j}.\mathrm{MIyes}-1\geq w_{j}.\mathrm{MIno}$
follows that $\Delta(I)\leq 1+w_{j}.\mathrm{MIyes}-1-w_{j}.\mathrm{MIyes}\leq
0$. This means that the influence cannot be increased, and hence it was
maximal.

To conclude, since each node is visited once and some constant-time operations
are applied in each case, the algorithm runs in $O(|V|)$ time. ∎

Although Algorithm 1 returns the optimal value of the influence, it is
possible that $\lvert V_{1}^{\bar{\mathscr{l}}}\rvert\geq k^{*}$. To solve
this problem and obtain $\mathscr{l}^{*}$, we use Algorithm 2.

Algorithm 2 $clear1nodes$

$T=(V,E)$, $V_{1}^{\bar{\mathscr{l}}}$

A minimum 1-labelling $\mathscr{l}^{*}$

if $d_{0}^{\mathscr{l}}(r)=0$ and $d_{0}^{\mathscr{l}}(w_{i})=1$ for each
$w_{i}\in N(r)$ then

$r.\mathscr{l}=1$

$w_{i}.\mathscr{l}=0$ for $w_{i}\in N(r)$

end if

for each $v\in V_{1}^{\bar{\mathscr{l}}}$ do

if $d_{0}^{\mathscr{l}}(v)=p_{\mathscr{l}}(v)$ then

$v.\mathscr{l}\leftarrow 0$ $\triangleright$ $v\notin V_{1}$

end if

end for

The correctness of the algorithm easily follows: if all the children of $r$
are $1-$nodes and their out-degree is $1$, we can simply put $r$ in the
$1$-nodes and remove all its children. This procedure reduces the number of
used coordinated accounts without changing the influence. Moreover, since each
node $v\in T$ has exactly one father (except for the root), the only case in
which $v$ does not contribute to the influence is when $d_{0}(v)=1$ and its
father is a $1-$node. The algorithm runs in $O(k^{*})$.

A visual example of the running of Algorithm 2 is depicted in Figure 3.

Figure 3. $(a)$ a directed tree and the label obtained trough Algorithm 1. The
$1-$nodes highlighted by the blue arrows can be removed. $(b)$ After a run of
Algorithm 2 the nodes are deleted and $V_{1}^{*}$ is returned.

###  3.3. A greedy placement with constraints on the number of coordinated
accounts

In this section we propose a greedy strategy to face the case in which we want
to maximize $I$ with a fixed number $k$ of coordinated accounts.

We define the switch(v,w) operator that, starting from a labelling
$\mathscr{l}$, provides a new labelling $\bar{\mathscr{l}}$ that increase the
obtained influence:

###### Definition 1.

Let $\mathscr{l}$ be a labelling of nodes of a given directed tree $T$.
Suppose $v\in V_{1}^{l}$ and $w\in V\setminus V_{1}^{\mathscr{l}}$; the
switching operator $switch(v,w)$ exchanges the labels between $v$ and $w$,
i.e. it sets $\mathscr{l}_{v}=0$ and $\mathscr{l}_{w}=1$.

Thus, the operator provides a new labelling $\bar{\mathscr{l}}$, where
$V_{1}^{\bar{\mathscr{l}}}=\left(V_{1}^{\mathscr{l}}\setminus\\{v\\}\right)\cup\\{w\\}$.

Based on this idea, we apply the following strategy: we start by including
sequentially that of the $k$ nodes which contribute the most to the influence.
Then, we try to increment the influence by applying trySwitch. When it is no
longer possible to increase $I$ using a call of switch, the algorithm stops.

Figure 4. An example of how switch is applied.

To formally define the concept of increment, consider a node $v\in
V_{1}^{\mathscr{l}}$ and $w\in V\setminus V_{1}^{\mathscr{l}}$. Switching
$l(v$) with $l(w)$ leads to an increment if

(6)
$d^{\mathscr{l}}_{0}(v)<\Delta(v,w):=d^{\bar{\mathscr{l}}}_{0}(w)-p_{\bar{\mathscr{l}}}(w)+p_{\bar{\mathscr{l}}}(v),$

where $\bar{\mathscr{l}}$ is the label resulting from $switch(v,w)$.

The motivation is easily obtained: $d^{\bar{\mathscr{l}}}_{0}(w)$ counts the
number of $0-$nodes in the out-neighbour of $w$. Moreover, when changing $v$
with $w$ it is possible to add $1$ to the influence if the parent of $v$ is a
$1-$node, i.e. $p_{\bar{\mathscr{l}}}(v)=1$. Similarly, we subtract $1$ from
the influence if the parent of $w$ is a $1-$node i.e.
$p_{\bar{\mathscr{l}}}(w)=1$.

Summarizing, if $\eqref{eq:increment}$ is satisfied, $switch(v,w)$ assures
that $I_{\mathscr{l}}>I_{\mathscr{l}}$.

Algorithm 4 implements the pseudo-code of the greedy strategy.

Algorithm 3 trySwitch

$T=(V,E),\mathscr{l}$

$\bar{\mathscr{l}}$

$check=TRUE$

while $check$ do$\triangleright$ Try to apply switch

$check=FALSE$

for $v\in V_{1}^{\mathscr{l}}$ do

if $d_{0}(v)<\max_{u\in V\setminus V_{1}^{\mathscr{l}}}\Delta(v,u)$ then
$\triangleright$ It is possible to increase the influence

$check=TRUE$

$S=\\{w\in V\setminus V_{1}^{\mathscr{l}}\;|\;\Delta(v,w)=\max_{u\in
V\setminus V_{1}^{\mathscr{l}}}\Delta(v,u)\\}$

choose randomly $u\in S$

$\mathscr{l}=switch(v,u)$

end if

end for

end while

$\bar{\mathscr{l}}=\mathscr{l}$

Algorithm 4 An heuristic for the optimal bot placement

$T=(V,E)$, $\mathscr{l}$,$k$

an approximation $\tilde{\mathscr{l}}$ of the optimal solution

for $i=1:k$ do$\triangleright$ Place the first $k$ nodes

$W=\\{w\in V\setminus
V_{1}^{\mathscr{l}}\;|\;d_{0}(w)-p_{\mathscr{l}}(w)=max_{u\in
V}\left(d_{0}(u)-p_{\mathscr{l}}(u)\right)$}

Select randomly a node $v\in W$

$\mathscr{l}(v)=1$

end for

$\tilde{\mathscr{l}}=trySwitch(T,\mathscr{l})$

##  4\. Results

###  4.1. Growth rate of $I^{*}$ and $k^{*}$

In this section we are interested in determining the growth rate of $I^{*}$
and $k^{*}$ depending on the number of nodes (i.e. users) and on height of the
tree. Although those values are bounded, as shown in (2)-(3), finding an
explicit expression for them it’s beyond the scope of this work.

To obtain an approximation we consider $N=100$ random trees made up of $5\leq
n\leq 100$ nodes. We apply to each of them Algorithm 1 and Algorithm 2 to
obtain $I^{*}$ and $k^{*}$. Then, we average the results over the $N$ graph
realisations for each of the $n$ values We plot the results in Figure 5$(a)$
and $(b)$.

Figure 5. Upper row: relation between the number of nodes of a tree and $(a)$
mean optimal influence $(b)$ mean optimal number of bots. Bottom row:
comparison between the height of the tree and $(c)$ mean optimal influence and
$(d)$ mean optimal number of nodes. The two horizontal red lines show the
maximum and minimum values of the measure, while the ribbon around the curves
represents a standard deviation from the mean.

Interestingly, we observe in both cases a linear relation ($p<0.001$,
$R^{2}=0.99$) in which the slope is much lower than $1$ ($\approx 0.28)$ in
the case of $k^{*}$ while closer to the unity $(\approx 0.6)$ in the case of
$I^{*}$. This suggests that it is possible to reach the point of maximum
influence using approximately $0.3\cdot n$ coordinated accounts. Moreover,
they are sufficient to exert a great influence on the tree (approximately
$0.6\cdot n$).

To evaluate the impact of the tree’s height on $I^{*}$ and $k^{*}$, we
consider several random directed trees having a fixed number of nodes
($n=50$), and height spanning between $1$ and $n$. For each $h$, we generate
$N=100$ random trees having height $h$. Similarly to the previous case, we
then average the results obtained by our algorithms, which are shown in Figure
5$(c)$ and $(d)$. As depicted, $I^{*}$ drops dramatically as soon as the
height increases, and starts to decrease more softly when $h\geq 10$. A
symmetrical result holds for $k^{*}$. This suggests an expected result, i.e.
for a fixed number of users in the conversation, information cascades in which
the majority of the retweets are close to the original user (i.e. the
associated tree has a low height) can be covered with fewer coordinated
accounts, obtaining a greater impact.

However, the Figure also suggests that from a certain height threshold
($\approx 20\cdot n$ in our simulation case) $I^{*}$ starts to show greater
stability with respect to the increase in the height of the tree.

Symmetrical results hold for $k^{*}$.

###  4.2. Phase diagram of the relative positions of node labels

In Section 3 we defined an algorithm that finds one of the optimal placements
node labels. Interestingly, the same problem can be translated into finding an
assignment of binary node metadata such that the number of (directed) edges
between $1-$nodes and $0-$nodes is maximised (cinelli2020network, ).

In such a framework, let’s denote with $m_{11}$ ($m_{10}$) the number of
directed edges between $1$ and $1$ ($0$). To better understand how rare the
optimal placement is when compared to the set of all the labellings, we
computed the phase diagram relative to $m_{11}$ and $m_{10}$
(park2007distribution, ).

More in detail, we generate a random directed tree of $n=25$ nodes and compute
its optimal influence, obtaining $I^{*}=14,k^{*}=7$. Then, we generated all
the $\binom{25}{7}$ possible placements, storing for each of them the
corresponding values of $m_{11}$ and $m_{10}$. We show a $2d-$histogram of the
results in Figure 6.

Figure 6. Phase diagram of possible values of $(m_{10},m_{11})$. The
intersection of red (green) lines highlights $(m_{10},m_{11})$ for the optimal
(greedy) placement. The colours that fill the bins use a logarithmic scale.

We observe that both the optimal and greedy placements are located in low-
frequency areas at the boundary of the diagrams, obtaining high values of
$m_{10}$. This provides results related to the statistical significance of the
obtained labellings and suggests that they are somewhat rare with respect to
the whole sets of labels. In general, a placement without a specific strategy
is less likely to obtain good results.

###  4.3. Results of the algorithm on real cascades

In this section we consider a dataset of Twitter’s cascades (modelled as
directed trees) in which nodes are labelled as either coordinated or non-
coordinated as explained in section 3.1. In each cascade, we aim to detect the
influence exerted compared to the optimum placement provided by Algorithm 1.
In particular, the size of a cascade is the number of its nodes (i.e. users).

For a given cascade $c$, we denote as $I(c)$ the influence obtained by them
and as $k(c)$ the number of coordinated accounts acting in $c$. The optimal
influence and number of coordinated accounts are denoted accordingly as
$I^{*}(c)$ and $k^{*}(c)$.

For our analysis, we only consider cascades having at least $15$ nodes and at
least $1$ coordinated account. Such a restriction allows us to consider more
complex properties and structures at the cost of losing some of the data.
After this procedure, we obtain 4119 trees to which we apply Algorithm 1 and
Algorithm 2 to compute $I^{*}(c)$ and $k^{*}(c)$.

In each cascade we measure how close $I(c)$ is to $I^{*}(c)$ using

(7) $\rho(c)=\frac{I(c)}{I^{*}(c)}.$

Note that $0\leq\rho(c)\leq 1$, where a value close to one indicates that the
influence obtained by the detected coordinated accounts is close to the
optimal value.

Figure 7. Results of the algorithm on real cascades. $(a)$ and $(b)$ show the
$2$-dimensional density of the number of nodes and $(a)$ $I(c)$ or $(b)$
$k(c)$. In $(a)$ we add 1 to the influence of each tree for graphical reason.
$(c)$ $2-$dimensional density of the number of nodes and $\rho(c)$. $(d)$
$2-$dimensional density of $k(c)$ and $k^{*}(c)$. The colours that fill the
bins use a logarithmic scale.

As reported in Figure 7, the majority of the cascades have a limited size and,
in general, the influence obtained from the coordinated accounts is low, as
depicted in $(a)$. In fact, in the biggest trees, $I(c)$ is approximately
$10\%$ of the number of nodes, much lower than the expected $60\%$ suggested
by Figure 5$(a)$. A somewhat similar result is observed in $(b)$, which
indicates the majority of the cascades contain a very low number of
coordinated accounts. Also in this case, approximately $1\%$ of the nodes is
coordinated in the biggest cascades, while Figure 5$(b)$ suggests that $30\%$
of the number of nodes is needed to obtain the optimal results. Accordingly,
Figure 7$(c)$ shows that only small cascades succeed in obtaining influence
values close to the optimal one. For larger cascades, we observe a dramatic
collapse in $\rho(c)$, probably due also to the much more complex structures
arising with a higher number of nodes. Finally, $(d)$ shows that, apart from
the smallest trees in which the two measures are approximately similar, $k(c)$
largely differ from $k^{*}(c)$, yielding a possible explanation of the low
values of $\rho(c)$.

Summarising, we conclude that coordinated accounts exert an influence much
lower than the upper bound provided by our algorithm. Moreover, there is
evidence that this may be due to a limited number of coordinated accounts
placed in each cascade.

###  4.4. Comparison with optimum using a fixed number of coordinated accounts

In the previous section we compared the behaviour of coordinated accounts with
an optimal strategy that considers having, at prior, an undefined number of
coordinated accounts to place. As highlighted before, the scarce results
obtained by them could be due to a limited number of resources employed to
influence other nodes.

Therefore, here we are interested in unveiling if the observed non-optimal
behaviour changes if we compare it to the greedy strategy proposed in
Algorithm 4, using exactly $k(c)$ coordinated accounts. Observing poor results
in this case could suggest that they are due also to a bad placement strategy
of coordinated accounts.

We denote as $I_{k}(c)$ the influence computed by Algorithm 4. Similarly as
before, we measure how close $I(c)$ and $I_{k}(c)$ are using

(8) $\rho_{k}(c)=\frac{I(c)}{I_{k}(c)}.$

In Figure 8 we show a $2-$dimensional histogram of $\rho_{k}(c)$ versus the
number of nodes in the cascade.

Figure 8. $2-$dimensional density of the number of nodes and $\rho(c)_{k}(c)$.
The colours used to fill the bins use a logarithmic scale.

Notably, the figure looks very similar to Figure 5(c): only small cascades get
comparable results with the greedy algorithm but, when the size of the cascade
increases, the placement of coordinated accounts in real cascades hardly reach
the influence obtained through the greedy strategy.

Taking into account all the previous results, it seems that, in real cascades,
coordinated accounts may be placed randomly, without a specific rationale. To
validate this observation, for each cascade we generate $N=10$ random
labellings and we compute the mean influence obtained by those random
placements. This results in a new distribution of influence values, denoted as
$q_{random}$. We also denote as $p_{real},q_{greedy}$ the real and greedy
influence distributions.

We then compute Kullback-Leibler divergence (kld, ) to compare $p_{real}$ with
the other two distributions, adding a small correction of $10^{-4}$ to handle
the cases in which $q_{greedy}$ and $q_{random}$ distributions have $0$
probability. The results are shown in Table 2.

$D_{KL}(p_{real}||q_{greedy})$ | $4.278$
---|---
$D_{KL}(p_{real}||q_{random})$ | $0.097$
Table 2. Kullback-Leibler divergence values.

The values suggest that, as expected, $p_{real}$ is much more similar to
$q_{random}$ than $q_{greedy}$, thus confirming that, according to our model,
coordinated nodes are placed quite randomly.

Joining these results with the previous ones, we can conclude the results
observed in real cascades are scarce for two reasons: a scarcity of resources
and also a bad placement strategy.

##  5\. Conclusion

In this work we have proposed a general framework that allows to evaluate the
influence of coordinated accounts in real cascades, providing an upper bound
to its value.

First, we show (using synthetic data) that it is possible to exert the maximum
influence with a low number of coordinated accounts. Moreover, the majority of
node labelling gives far-from-optimum results, confirming that random
placement is not likely to obtain good results.

As a case of study, we consider $\approx 4K$ information cascades on Twitter
about $2019$ UK political elections. We show that observed coordinated
accounts exert a very low influence on the tree, compared to both greedy and
optimal strategies. Our results suggest that this is due to a double reason: a
scarcity of resources (i.e. used coordinated accounts) and an absence of a
strategy in how coordinated accounts act.

Despite the possible limitations of our model and the limitations of the
detection procedure and the reconstruction of Twitter cascades, our results
overall suggest that CIB may play a less pivotal role than expected in
information diffusion. Nonetheless, as often reported in social media studies
(ruths2019misinformation, ), different methodological settings and case
studies may lead to different results thus future work may employ the proposed
framework to consider the impact of CIB and other similar actors in a wider
range of scenarios.

## Acknowledgement

The work is supported by IRIS Infodemic Coalition (UK government, grant no.
SCH-00001-3391), SERICS (PE00000014) under the NRRP MUR program funded by the
European Union - NextGenerationEU, project CRESP from the Italian Ministry of
Health under the program CCM 2022, PON project “Ricerca e Innovazione”
2014-2020 and project SEED n. SP122184858BEDB3.

We would like to thank Maurizio Tesconi for providing the dataset employed for
the case study.

## References

  * [1] Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic.  The role of social networks in information diffusion.  In Proceedings of the 21st international conference on World Wide Web, pages 519–528, 2012.
  * [2] Seth Flaxman, Sharad Goel, and Justin M Rao.  Filter bubbles, echo chambers, and online news consumption.  Public opinion quarterly, 80(S1):298–320, 2016.
  * [3] 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.
  * [4] Elizaveta Zinovyeva, Wolfgang Karl Härdle, and Stefan Lessmann.  Antisocial online behavior detection using deep learning.  Decision Support Systems, 138:113362, 2020.
  * [5] Amaury Trujillo and Stefano Cresci.  Make reddit great again: assessing community effects of moderation interventions on r/the_donald.  Proceedings of the ACM on Human-Computer Interaction, 6(CSCW2):1–28, 2022.
  * [6] R Kelly Garrett.  Echo chambers online?: Politically motivated selective exposure among internet news users.  Journal of computer-mediated communication, 14(2):265–285, 2009.
  * [7] Christopher A Bail, Lisa P Argyle, Taylor W Brown, John P Bumpus, Haohan Chen, MB Fallin Hunzaker, Jaemin Lee, Marcus Mann, Friedolin Merhout, and Alexander Volfovsky.  Exposure to opposing views on social media can increase political polarization.  Proceedings of the National Academy of Sciences, 115(37):9216–9221, 2018.
  * [8] Joshua A Tucker, Andrew Guess, Pablo Barberá, Cristian Vaccari, Alexandra Siegel, Sergey Sanovich, Denis Stukal, and Brendan Nyhan.  Social media, political polarization, and political disinformation: A review of the scientific literature.  Political polarization, and political disinformation: a review of the scientific literature (March 19, 2018), 2018.
  * [9] Matteo Cinelli, Gianmarco De Francisci Morales, Alessandro Galeazzi, Walter Quattrociocchi, and Michele Starnini.  The echo chamber effect on social media.  Proceedings of the National Academy of Sciences, 118(9):e2023301118, 2021.
  * [10] Max Falkenberg, Alessandro Galeazzi, Maddalena Torricelli, Niccolò Di Marco, Francesca Larosa, Madalina Sas, Amin Mekacher, Warren Pearce, Fabiana Zollo, Walter Quattrociocchi, et al.  Growing polarization around climate change on social media.  Nature Climate Change, 12(12):1114–1121, 2022.
  * [11] 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.
  * [12] 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.
  * [13] Alexandre Bovet and Hernán A Makse.  Influence of fake news in twitter during the 2016 us presidential election.  Nature communications, 10(1):7, 2019.
  * [14] Fernando P Santos, Yphtach Lelkes, and Simon A Levin.  Link recommendation algorithms and dynamics of polarization in online social networks.  Proceedings of the National Academy of Sciences, 118(50):e2102141118, 2021.
  * [15] Kristina Hristakieva, Stefano Cresci, Giovanni Da San Martino, Mauro Conti, and Preslav Nakov.  The spread of propaganda by coordinated communities on social media.  In Proceedings of the 14th ACM Web Science Conference 2022, pages 191–201, 2022.
  * [16] 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.
  * [17] Francesco Pierri, Luca Luceri, Nikhil Jindal, and Emilio Ferrara.  Propaganda and misinformation on facebook and twitter during the russian invasion of ukraine.  In Proceedings of the 15th ACM Web Science Conference 2023, pages 65–74, 2023.
  * [18] Leonardo Nizzoli, Serena Tardelli, Marco Avvenuti, Stefano Cresci, and Maurizio Tesconi.  Coordinated behavior on social media in 2019 uk general election.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 443–454, 2021.
  * [19] Carlene Lebeuf, Alexey Zagalsky, Matthieu Foucault, and Margaret-Anne Storey.  Defining and classifying software bots: A faceted taxonomy.  In 2019 IEEE/ACM 1st International Workshop on Bots in Software Engineering (BotSE). IEEE, May 2019.
  * [20] Joseph Seering, Juan Pablo Flores, Saiph Savage, and Jessica Hammer.  The social roles of bots: Evaluating impact of bots on discussions in online communities.  Proceedings of the ACM on Human-Computer Interaction, 2(CSCW):1–29, November 2018.
  * [21] Lei (Nico) Zheng, Christopher M. Albano, Neev M. Vora, Feng Mai, and Jeffrey V. Nickerson.  The roles bots play in wikipedia.  Proceedings of the ACM on Human-Computer Interaction, 3(CSCW):1–20, November 2019.
  * [22] Lorenz Cuno Klopfenstein, Saverio Delpriori, Silvia Malatini, and Alessandro Bogliolo.  The rise of bots: A survey of conversational interfaces, patterns, and paradigms.  In Proceedings of the 2017 Conference on Designing Interactive Systems, DIS ’17. ACM, June 2017.
  * [23] Derek Ruths.  The misinformation machine.  Science, 363(6425):348–348, 2019.
  * [24] Nir Grinberg, Kenneth Joseph, Lisa Friedland, Briony Swire-Thompson, and David Lazer.  Fake news on twitter during the 2016 us presidential election.  Science, 363(6425):374–378, 2019.
  * [25] Matteo Cinelli, Stefano Cresci, Walter Quattrociocchi, Maurizio Tesconi, and Paola Zola.  Coordinated inauthentic behavior and information spreading on twitter.  Decision Support Systems, 160:113819, 2022.
  * [26] Franziska B Keller, David Schoch, Sebastian Stier, and JungHwan Yang.  Political astroturfing on twitter: How to coordinate a disinformation campaign.  Political communication, 37(2):256–280, 2020.
  * [27] 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.
  * [28] Marcelo Mendoza, Maurizio Tesconi, and Stefano Cresci.  Bots in social and interaction networks: detection and impact estimation.  ACM Transactions on Information Systems (TOIS), 39(1):1–32, 2020.
  * [29] Stefano Cresci.  A decade of social bot detection.  Communications of the ACM, 63(10):72–83, 2020.
  * [30] Karishma Sharma, Yizhou Zhang, Emilio Ferrara, and Yan Liu.  Identifying coordinated accounts on social media through hidden influence and group behaviours.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1441–1451, 2021.
  * [31] Diogo Pacheco, Alessandro Flammini, and Filippo Menczer.  Unveiling coordinated groups behind white helmets disinformation.  In Companion Proceedings of the Web Conference 2020, WWW ’20. ACM, April 2020.
  * [32] Diogo Pacheco, Pik-Mai Hui, Christopher Torres-Lugo, Bao Tran Truong, Alessandro Flammini, and Filippo Menczer.  Uncovering coordinated networks on social media: methods and case studies.  In Proceedings of the international AAAI conference on web and social media, volume 15, pages 455–466, 2021.
  * [33] Luca Luceri, Valeria Pantè, Keith Burghardt, and Emilio Ferrara.  Unmasking the web of deceit: Uncovering coordinated activity to expose information operations on twitter.  arXiv preprint arXiv:2310.09884, 2023.
  * [34] Alexander C Nwala, Alessandro Flammini, and Filippo Menczer.  A language framework for modeling social media account behavior.  EPJ Data Science, 12(1):33, 2023.
  * [35] David Schoch, Franziska B Keller, Sebastian Stier, and JungHwan Yang.  Coordination patterns reveal online political astroturfing across the world.  Scientific reports, 12(1):4572, 2022.
  * [36] Tom De Nies, Io Taxidou, Anastasia Dimou, Ruben Verborgh, Peter M Fischer, Erik Mannens, and Rik Van de Walle.  Towards multi-level provenance reconstruction of information diffusion on social media.  In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 1823–1826, 2015.
  * [37] Matteo Cinelli, Leto Peel, Antonio Iovanella, and Jean-Charles Delvenne.  Network constraints on the mixing patterns of binary node metadata.  Physical Review E, 102(6):062310, 2020.
  * [38] Juyong Park and Albert-László Barabási.  Distribution of node characteristics in complex networks.  Proceedings of the National Academy of Sciences, 104(46):17916–17920, 2007.
  * [39] S Kullback and R Leibler.  On information and sufficiencyannals of mathematical statistics, 22, 79–86.  MathSciNet MATH, 3, 1951.