All-path convexity: Combinatorial and complexity aspects

Fábio Protti111Partially supported by CNPq and FAPERJ, Brazilian Research
Agencies

Instituto de Computação - Universidade Federal Fluminense - Brazil

E-mail<EMAIL_ADDRESS>

João V. C. Thompson

Centro Federal de Educação Tecnológica Celso Suckow da Fonseca

CEFET/RJ - Campus Petrópolis - Brazil

E-mail<EMAIL_ADDRESS>
Abstract. Let $\mathscr{P}$ be any collection of paths of a graph $G=(V,E)$.
For $S\subseteq V$, define $I(S)=S\cup\\{v\mid v\ \mbox{lies in a path of}\
\mathscr{P}\ \mbox{with endpoints in}\ S\\}$. Let $\mathcal{C}$ be the
collection of fixed points of the function $I$, that is,
$\mathcal{C}=\\{S\subseteq V\mid I(S)=S\\}$. It is well known that
$(V,\mathcal{C})$ is a finite convexity space, where the members of
$\mathcal{C}$ are precisely the convex sets. If $\mathscr{P}$ is taken as the
collection of all the paths of $G$, then $(V,\mathcal{C})$ is the all-path
convexity with respect to graph $G$. In this work we study how important
parameters and problems in graph convexity are solved for the all-path
convexity.

Keywords: all-path convexity, graph convexity, path convexity

##  1 Introduction

Let $G=(V,E)$ be a simple, finite, nonempty, and connected graph, and let
$\mathcal{C}$ be a collection of subsets of $V$. We say that $(V,\mathcal{C})$
is a (finite) graph convexity space if: (a) $\emptyset\in\mathcal{C}$; (b)
$V\in\mathcal{C}$; (c) $\mathcal{C}$ is closed under intersections. In many
studies, the collection $\mathcal{C}$ is determined as follows. Let
$\mathscr{P}$ be any collection of paths of a graph $G$, and, for $S\subseteq
V$, define

$I(S)=S\cup\\{v\mid v\ \mbox{lies in a path of}\ \mathscr{P}\ \mbox{with
endpoints in}\ S\\}.$

Define $\mathcal{C}\subseteq 2^{V}$ as the collection of fixed points of the
function $I$, that is, $\mathcal{C}=\\{S\subseteq V\mid I(S)=S\\}$. Then
$(V,\mathcal{C})$ is easily seen to be a graph convexity space, generally
called a “path convexity”. In particular, if $\mathscr{P}$ contains precisely
all the shortest paths of $G$ then the corresponding convexity space is the
well-known geodesic convexity with respect to $G$ [18, 19, 22]; if
$\mathscr{P}$ is the collection of induced paths of $G$ then the corresponding
convexity space is the monophonic convexity with respect to $G$ [12, 15]; and
there are in the literature many other examples described below, where in each
case we indicate which collection $\mathscr{P}$ of paths of $G$ is considered:

  * –

$g^{3}$-convexity [23]: shortest paths of length at least three;

  * –

$m^{3}$-convexity [3, 14]: induced paths of length at least three;

  * –

$g_{k}$-convexity [16]: shortest paths of length at most $k$;

  * –

$P_{3}$-convexity [4, 13, 24]: paths of length two;

  * –

$P_{3}^{*}$-convexity [1]: induced paths of length two;

  * –

triangle-path convexity [6, 7]: paths allowing only triangular chords;

  * –

total convexity [11]: paths allowing only non-triangular chords;

  * –

detour convexity [8, 9, 10]: longest paths.

In this work, we study the all-path convexity, which is associated with the
collection $\mathscr{P}$ of all the paths of $G$ [5, 17, 25]. Our study is
concentrated in solving the most important problems in graph convexity for the
specific case of the all-path convexity, including the determination of some
well-known graph convexity parameters, such as the convexity number, the
interval number, and the hull number of $G$. The remainder of this work is
organized as follows. In Section 2 we provide some necessary background. In
Section 3 we present the main results of this work. Finally, Section 4
contains our concluding remarks.

##  2 Preliminaries

In this work, $G=(V,E)$ is always a finite, simple, nonempty, and connected
graph with $n$ vertices and $m$ edges. Let $\mathscr{P}$ be a collection of
paths of $G$, and let $I_{\mathscr{P}}:2^{V}\rightarrow 2^{V}$ be a function
(interval function) associated with $\mathscr{P}$ in the following way:

$I_{\mathscr{P}}(S)=S\cup\\{v\mid v\ \mbox{lies in a path}\ P\in\mathscr{P}\
\mbox{with endpoints in}\ S\\}.$

Define $\mathcal{C}_{\mathscr{P}}$ as the family of subsets of $V$ such that
$S\in\mathcal{C}_{\mathscr{P}}$ if and only if $I_{\mathscr{P}}(S)=S$. Then it
is easy to see that $(V,\mathcal{C}_{\mathscr{P}})$ is a finite convexity
space, whose convex sets are precisely the fixed points of $I_{\mathscr{P}}$.

######  Proposition 1.

[26] $(V,\mathcal{C}_{\mathscr{P}})$ is a finite convexity space.

If $\mathscr{P}$ is the collection of all the paths of $G$, then
$(V,\mathcal{C}_{\mathscr{P}})$ is the all-path convexity with respect to $G$.
In order to ease the notation, we omit the subscript ${\mathscr{P}}$ if it is
clear from the context.

In this work we focus on seven important problems that are usually studied in
the field of convexity in graphs, and solve them for the case of the all-path
convexity. We need some additional definitions. Let $S\subseteq V$. If
$I(S)=V$ then $S$ is an interval set. The convex hull $H(S)$ of $S$ is the
smallest convex set containing $S$. Write $I^{0}(S)=S$ and define
$I^{i+1}(S)=I(I^{i}(S))$ for $i\geq 0$. Note that $I(S)=I^{1}(S)$ and there is
an index $i$ for which $H(S)=I^{i}(S)$. If $H(S)=V$ then $S$ is a hull set.
The convexity number $c(G)$ of $G$ is the size of a maximum convex set $S\neq
V$. The interval number $i(G)$ of $G$ is the size of a smallest interval set
of $G$. The hull number $h(G)$ of $G$ is the size of a smallest hull set of
$G$. Clearly, $h(G)\leq i(G)$. The geodetic iteration number of a graph $G$,
denoted by $gin(G)$, is the smallest $i$ such that $H(S)=I^{i}(S)$ for every
$S\subseteq V(G)$. Equivalently, $gin(G)=\min\\{i\mid I^{i}(S)=I^{i+1}(S)$ for
every $S\subseteq V(G)\\}$. Graphs with geodetic iteration number at most $1$
are called interval monotone graphs

Now we are in position to state the problems dealt with in this work:

  * –

Convex Set
Input: A graph $G$ and a set $S\subseteq V$.
Question: Is $S$ convex?

  * –

Interval Determination
Input: A graph $G$ and a set $S\subseteq V$.
Goal: Determine $I(S)$.

  * –

Convex Hull Determination
Input: A graph $G$.
Goal: Determine $H(S)$.

  * –

Convexity Number
Input: A graph $G$.
Goal: Determine $c(G)$.

  * –

Interval Number
Input: A graph $G$.
Goal: Determine $i(G)$.

  * –

Hull Number
Input: A graph $G$.
Goal: Determine $h(G)$.

  * –

Geodetic Iteration Number
Input: A graph $G$.
Goal: Determine $gin(G)$.

##  3 Main results

In this section we present the solution of the problems stated in the
preceding section for the case of the all-path convexity. For $X,Y\subseteq
V$, denote $N(X,Y)=\\{v\in Y\mid v\ \mbox{is a neighbor of some}\ x\in X\\}$.

######  Theorem 2.

Let $S\subseteq V$. Then $S$ is convex in the all-path convexity if and only
if either $S=V$ or for every connected component $G_{i}$ of $G-S$ it holds
that

$|N(V(G_{i}),S)|=1.$

###### Proof.

Suppose that $S$ is convex and $S\neq V$, and let $G_{i}$ be a connected
component of $G-S$. If $|N(V(G_{i}),S)|\geq 2$ then there are distinct $v,w\in
S$ with neighbors $v^{\prime},w^{\prime}\in V(G_{i})$ (not necessarily
distinct). Let $P^{\prime}=v^{\prime}\ldots w^{\prime}$ be a path from
$v^{\prime}$ to $w^{\prime}$ in $G_{i}$ (such a path exists because $G_{i}$ is
connected). Occasionally, $P^{\prime}$ consists of a single vertex
$v^{\prime}=w^{\prime}$. Now, let $P$ be the path
$vP^{\prime}w=vv^{\prime}\ldots w^{\prime}w$. This means that $v^{\prime}$ (or
$w^{\prime}$) lies in a path with endpoints in $S$, that is, $v^{\prime}\in
I(S)$. Since $v^{\prime}\notin S$, this implies $I(S)\neq S$, a contradiction
to the assumption that $S$ is convex.

Conversely, suppose that $S\neq V$ and $|N(V(G_{i}),S)|=1$ for every connected
component of $G-S$. Assume by contradiction that $S$ is not convex. Then, from
the definition of convex set, there is a path $P=v_{1}v_{2}\ldots v_{k}$ with
(distinct) endpoints in $S$ that contains vertices outside $S$. Let $j$ be the
minimum index for which $v_{j}\in S$ and $v_{j+1}\not\in S$, and assume that
$v_{j+1}\in V(G_{i})$. Since the $G_{i}$’s are mutually isolated (i.e., there
is no edge in $E$ joining a vertex in $G_{i}$ to a vertex in $G_{k}$ for
$i\neq k$), let $l$ be the minimum index for which $l>j$ and $v_{l}\in S$ (in
other words, after visiting $G_{i}$, the path $P$ must return to $S$ before
visiting another component $G_{k}$). Thus $v_{j},v_{l}\in N(V(G_{i}),S)$. But
$j\neq l$, because $P$ is a path. Then $|N(V(G_{i}),S)|\geq 2$, a
contradiction. Therefore, $S$ is convex. ∎

######  Corollary 3.

Convex Set can be solved in $O(n+m)$ time for the all-path convexity.

###### Proof.

If $S\neq V$, computing the connected components of $G-S$ can be easily done
in $O(n+m)$ time. In addition, checking whether $|N(V(G_{i}),S)|=1$ for every
connected component $G_{i}$ of $G-S$ can also be done in $O(n+m)$ time. Thus,
the corollary follows. ∎

Now we deal with the Interval Determination problem. Consider the block
decomposition of $G$ represented by a block-cut tree $T_{G}$, where each
vertex of $T_{G}$ is associated with either a block $B_{j}$ (a cut edge or a
maximal 2-connected subgraph of $G$) or a cut vertex $z_{i}\in V$, and there
is an edge linking a vertex $B_{j}$ and a vertex $z_{i}$ in $T_{G}$ whenever
block $B_{j}$ contains the cut vertex $z_{i}\in V$. This definition implies
that the vertices of $T_{G}$ associated with blocks of $G$ form an independent
set, and the same occurs for the vertices of $T_{G}$ associated with cut
vertices of $G$. In addition, every leaf of $T_{G}$ represent a block of $G$.
An end block of $G$ is a block associated with a leaf of $T_{G}$.

For a set $S\subseteq V$, let $T_{S}$ be the maximal subtree of $T_{G}$ such
that every leaf of $T_{S}$ is associated with a block of $G$ containing a
vertex of $S$ that is not a cut vertex in the subgraph $G_{S}$ induced by
$\cup_{B_{j}\in V(T_{S})}B_{j}$. Figure 1 shows an example.

Figure 1: (a) A graph $G$ and a subset $S=\\{b,j,w\\}$ (represented by the
white vertices), whose blocks are such that $V(B_{1})=\\{a,b\\}$,
$V(B_{2})=\\{b,c,d\\}$, $V(B_{3})=\\{b,e,g,f\\}$, $V(B_{4})=\\{f,l,u,v,w\\}$,
$V(B_{5})=\\{h,i,j,k,l\\}$, $V(B_{6})=\\{w,x\\}$, $V(B_{7})=\\{w,y,z\\}$; (b)
block-cut tree $T_{G}$; (c) subtree $T_{S}$ of $T_{G}$. Block $B_{3}$ is a
leaf of $T_{S}$ because it contains no cut vertex in the graph $G_{S}$ induced
by $V(B_{3})\cup V(B_{4})\cup V(B_{5})$.

######  Lemma 4.

Let $S\subseteq V$, and let $u,w$ be two distinct vertices in $S$, belonging
to blocks $B_{u}$ and $B_{w}$ of $T_{S}$, respectively. Assume that $u$ and
$w$ are not cut vertices in $G_{S}$. Let $B_{j_{1}}z_{1}B_{j_{2}}z_{2}\ldots
z_{k-1}B_{j_{k}}$ be a path in $T_{S}$ between $B_{j_{1}}=B_{u}$ and
$B_{j_{k}}=B_{w}$. Then, for every $v\in\cup_{i=1}^{k}V(B_{j_{i}})$, there is
a path $P$ in $G$ from $u$ to $w$ passing through $v$.

###### Proof.

If $B_{u}=B_{w}$ and there is a vertex $v\in V(B_{u})\setminus\\{u,w\\}$, by
the Fan Lemma (Proposition 9.5 in [2], applied to $2$-connected graphs) there
is a path $P$ from $u$ to $w$ passing through $v$.

If $B_{u}\neq B_{w}$, construct from $B_{j_{1}}z_{1}B_{j_{2}}z_{2}\ldots
z_{k-1}B_{j_{k}}$ a path $P$ in $G$ as follows. Let
$v\in\cup_{i=1}^{k}V(B_{j_{i}})$ and suppose first that $v$ is not a cut
vertex in $G_{S}$. Assume that $B_{v}=B_{j_{s}}$ for some $1<s<k$ (the cases
$s=1$ or $s=k$ are similar).

  * –

Let $P_{1}$ be a path contained in $B_{j_{1}}$ starting at $u$ and ending at
$z_{1}$.

  * –

Let $P_{s}$ be a path contained in $B_{j_{s}}$ starting at $z_{s-1}$, passing
through $v$, and ending at $z_{s}$. Since $v$ is not a cut vertex of $G_{S}$,
the block $B_{j_{s}}$ contains at least three vertices. Thus, the Fan Lemma
guarantees the existence of path $P_{s}$.

  * –

Let $P_{i}$, $2\leq i\leq k-1$, $i\neq s$, be a path contained in $B_{j_{i}}$
starting at $z_{i-1}$ and ending at $z_{i}$.

  * –

Finally, let $P_{k}$ be a path contained in $B_{j_{k}}$ starting at $z_{k-1}$
and ending at $w$.

Now, define $P$ as the concatenation $P_{1}P_{2}\ldots P_{k}$ (remove
replicated vertices that appear consecutively). Then $P$ is a path from $u$ to
$w$ passing through vertex $v$.

The case where $v$ is a cut vertex of $G_{S}$ is dealt with similarly. In this
case, there is no need of applying the Fan Lemma to $B_{j_{s}}$. $P_{s}$ can
be simply taken as a path from $z_{s-1}$ to $z_{s}$, since
$v\in\\{z_{s-1},z_{s}\\}$. ∎

Let $S\subseteq V$ and $v\in V\setminus S$. Say that a vertex $z\neq v$
separates $v$ and $V^{\prime}\subseteq V\setminus\\{v\\}$ if, in graph $G-z$,
the connected component containing $v$ contains no vertex of $V^{\prime}$.

######  Theorem 5.

Let $S\subseteq V$ with $|S|\geq 2$. Then

$I(S)=\bigcup_{B_{j}\in V(T_{S})}B_{j}.$

###### Proof.

Let $v\in\cup_{B_{j}\in V(T_{S})}B_{j}$. If $v\in S$ then $v\in I(S)$. If
$v\not\in S$, consider a block $B_{v}$ containing $v$. Clearly, there is a
maximal path $P_{v}=B_{j_{1}}z_{1}B_{j_{2}}z_{2}\ldots z_{k-1}B_{j_{k}}$ in
$T_{S}$ containing $B_{v}$. Thus, $v\in\cup_{i=1}^{k}V(B_{j_{i}})$. By the
maximality of $P_{v}$, $B_{j_{1}}$ and $B_{j_{k}}$ are leaves in $T_{S}$, and
this implies that $B_{j_{1}}$ contains a vertex $u\in S$ and $B_{j_{k}}$
contains a vertex $w\in S$, $w\neq u$, such that $u$ and $w$ are not cut
vertices in $G_{S}$. Then, by Lemma 4, there is a path $P$ in $G$ from $u$ to
$w$ passing through $v$. Therefore, $v\in I(S)$, i.e., $\cup_{B_{j}\in
V(T_{S})}B_{j}\ \subseteq\ I(S)$.

Now, let $v\in I(S)$. If $v\in S$, then, from the definition of $T_{S}$, it is
clear that $v\in\cup_{B_{j}\in V(T_{S})}B_{j}$. Assume then $v\not\in S$ and
$v\not\in\cup_{B_{j}\in V(T_{S})}B_{j}$. Thus, $v$ is in a block $B_{v}$ of
$T_{G}$ that is not in $T_{S}$, and this implies that there is a cut vertex
$z\in V(B_{v})$, $z\neq v$, that separates $v$ and $\cup_{B_{j}\in
V(T_{S})}B_{j}$. Since $S\subseteq\cup_{B_{j}\in V(T_{S})}B_{j}$, $z$
separates $v$ and $S$, and therefore every path from some $u\in S$ to $v$
passes through $z$, i.e., it is impossible to find a path from a vertex $u\in
S$ to another vertex $w\in S$ passing through $v$. This contradicts the
assumption $v\in I(S)$. Hence, $v\in\cup_{B_{j}\in V(T_{S})}B_{j}$ and
$I(S)\subseteq\cup_{B_{j}\in V(T_{S})}B_{j}$. ∎

######  Corollary 6.

Interval Determination can be solved in $O(n+m)$ time for the all-path
convexity.

###### Proof.

Assume $|S|\geq 2$ (other cases are trivial). The block-cut tree $T_{G}$ of
$G$ can be constructed in $O(n+m)$ time using well-known algorithmic
techniques [20]. The determination of $T_{S}$ can be easily done in $O(n+m)$
time as follows: initialize $T_{S}\leftarrow T_{G}$ and repeat the following
procedure until no longer possible: if $B_{j}$ is a leaf of the tree
containing no vertices of $S$ or containing exactly one vertex of $S$ that is
a cut vertex of $G_{S}$ then remove from the tree the vertex associated with
$B_{j}$ and the cut vertex $z_{i}$ adjacent to $B_{j}$ in the tree. Each
removal takes $O(|V(B_{j})|)$ time, thus the construction of $T_{S}$ from
$T_{G}$ takes $O(n)$ time. Finally, computing $\bigcup_{B_{j}\in
V(T_{S})}B_{j}$ takes $O(n)$ time. Hence, the theorem follows. ∎

In Figure 1, for $S=\\{b,j,w\\}$, we have that $I(S)=V(B_{3})\cup V(B_{4})\cup
V(B_{5})$.

######  Lemma 7.

Let $S\subseteq V$. Then, in the all-path convexity, $I(S)$ is always a convex
set.

###### Proof.

Assume $S\neq V$. By Theorem 5, $I(S)=\cup_{B_{j}\in V(T_{S})}B_{j}$. Let
$X=\cup_{B_{j}\notin V(T_{S})}B_{j}$. In other words, $X$ is formed by all
vertices belonging to blocks of $G$ that are not represented in $T_{S}$. It is
clear that every vertex in $I(S)\cap X$ is a cut vertex of $G$. That is, the
condition

“$|N(V(G_{i}),I(S))|=1$ for every connected component $G_{i}$ of $G-I(S)$”

is valid. Hence, by Theorem 2, $I(S)$ is a convex set. ∎

######  Theorem 8.

In the all-path convexity, $H(S)=I(S)$ for every $S\subseteq V$.

###### Proof.

Follows from Lemma 7. ∎

######  Corollary 9.

In the all-path convexity, every graph $G$ satisfies $gin(G)\leq 1$ (i.e., is
interval monotone).

###### Proof.

Follows from the previous theorem. ∎

######  Corollary 10.

Convex Hull Determination can be solved in $O(n+m)$ time for the all-path
convexity.

###### Proof.

Follows from Corollary 6 and Theorem 8. ∎

######  Corollary 11.

Geodetic Iteration Number can be solved in $O(1)$ time for the all-path
convexity.

###### Proof.

Follows from Corollary 9. ∎

Now we focus on the Convexity Number problem. For an end block $B_{j}$ of $G$,
let $|V(B_{j})|=b_{j}$. Define $b(G)=\min\\{b_{j}\mid B_{j}\ \mbox{is an end
block of}\ G\\}$.

######  Theorem 12.

In the all path convexity, for any graph $G$ it holds that:

$c(G)=\left\\{\begin{array}[]{ll}1,&\mbox{if $|V|=2$ or $G$ is
$2$-connected};\\\ n-b(G)+1,&\mbox{otherwise}.\end{array}\right.$

###### Proof.

If $|V|=2$ then the theorem is trivially true. If $G$ is $2$-connected then,
by the Fan Lemma, for each pair of vertices $u,w\in V,w\neq u$, we have that
every $v\notin\\{u,w\\}$ lies in a path from $u$ to $w$. Hence, for every $S$
with $2\leq|S|\leq n-1$, $S$ is not convex. This implies that $c(G)=1$.

Suppose now that $G$ is not $2$-connected. Note that any $S\subseteq V$
consisting of the union of all vertex sets of all blocks of $G$ but one end
block, say $B_{j}$, is convex, because the only cut vertex $z$ belonging to
$V(B_{j})$ separates all the vertices of $V\setminus V(B_{j})$ from
$V(B_{j})\setminus z$. (Note that $z\in S$.) Thus the maximum convex set in
$G$ is obtained by removing from $G$ all the vertices in an end block $B_{j}$
with minimum size, except the cut vertex $z\in V(B_{j})$. ∎

######  Corollary 13.

Convexity Number can be solved in $O(n+m)$ time for the all-path convexity.

###### Proof.

Follows from Theorem 12 and the fact that the block decomposition of $G$ can
be obtained in $O(n+m)$ time. ∎

Now we finally consider the problems Interval Number and Hull Number. Let
$eb(G)$ be the number of end blocks of $G$.

######  Theorem 14.

In the all path convexity, for any graph $G$ it holds that:

$i(G)=\left\\{\begin{array}[]{ll}1,&\mbox{if $G$ is trivial};\\\ 2,&\mbox{if
$|V|=2$ or $G$ is $2$-connected};\\\
eb(G),&\mbox{otherwise}.\end{array}\right.$

###### Proof.

If $|V|=1$ or $|V|=2$ then the theorem is trivially true. If $G$ is
$2$-connected, by the Fan Lemma any pair $u,w\in V$, $w\neq u$, is an interval
set, and thus $i(G)=2$ in this case.

Finally, if $G$ is not $2$-connected, consider $S\subseteq V$ such that $S\cap
V(B_{j})=\\{v_{j}\\}$ for each end block $B_{j}$ of $G$, where $v_{j}$ is not
a cut vertex of $G$. Note that $|S|=eb(G)$. The definition of $S$ implies that
$T_{S}=T_{G}$, and thus every vertex $v\in V$ is in a block $B_{v}$ of $G$
belonging to a maximal path $B_{j_{1}}z_{1}B_{j_{2}}z_{2}\ldots
z_{k-1}B_{j_{k}}$ in $T_{S}$ such that $B_{j_{1}}$ and $B_{j_{k}}$ are end
blocks of $G_{S}=G$ containing, respectively, vertices $u,w\in S$, $w\neq u$,
that are not cut vertices in $G_{S}=G$. By Lemma 4, there is a path $P$ in $G$
from $u$ to $w$ passing through $v$. In other words, $S$ is an interval set.
To conclude the proof, if a set $S^{\prime}\subseteq V$ is such that
$|S^{\prime}|<eb(G)$ then there is at least one end block $B_{j}$ in $G$ such
that $V(B_{j})\setminus\\{z_{j}\\}$ contains no vertices of $S^{\prime}$,
where $z_{j}$ is the cut vertex of $G$ belonging to $V(B_{j})$. Hence, no
vertex in $V(B_{j})\setminus\\{z_{j}\\}$ can lie in a path starting and ending
at distinct vertices of $S^{\prime}$, i.e., $S^{\prime}$ cannot be an interval
set. Thus $S$ is minimum. ∎

######  Corollary 15.

In the all path convexity, for any graph $G$ it holds that $h(G)=i(G)$.

###### Proof.

Follows from Theorem 8. ∎

######  Corollary 16.

Interval Number and Hull Number can be solved in $O(n+m)$ time for the all-
path convexity.

##  4 Concluding remarks

In this work we showed that the problems Convex Set, Interval Determination,
Convex Hull Determination, Convexity Number, Interval Number, and Hull Number
can all be solved in $O(n+m)$ time for the all-path convexity, whereas
Geodetic Iteration Number can be solved in $O(1)$ time (all graphs are
interval monotone with respect to the all-path convexity). The arguments used
to solve such problems are based on the block decomposition and the block-cut
tree of the graph.

## References

  * [1] R. T. Araujo, R. M. Sampaio, and J. L. Szwarcfiter. The convexity of induced paths of order three. Discrete Mathematics 44 (2013) 109–114.
  * [2] J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008.
  * [3] J. Cáceres, O. R. Oellermann, and M. L. Puertas. Minimal trees and monophonic convexity. Discuss. Math. Graph Theory 32(4) (2012) 685–704.
  * [4] C. C. Centeno, S. Dantas, M. C. Dourado, D. Rautenbach, and J. L. Szwarcfiter. Convex partitions of graphs induced by paths of order three. Discrete Mathematics 12(5) (2010) 175–184.
  * [5] M. Changat, S. Klavzar, and H. M. Mulder. The all-paths transit function of a graph. Czechoslovak Mathematical Journal 51(2) (2001) 439–448.
  * [6] M. Changat and J. Mathew. On triangle path convexity in graphs. Discrete Mathematics 206 (1999) 91–95.
  * [7] M. Changat, P. G. Narasimha-Shenoi, and J. Mathews. Triangle path transit functions, betweenness and pseudo-modular graphs. Discrete Mathematics 309(6) (2009) 1575–1583.
  * [8] M. Changat, P. G. Narasimha-Shenoi, and I. Pelayo. The longest path transit function of a graph and betweenness. Utilitas Mathematica 82 (2010) 111–127.
  * [9] G. Chartrand, H. Escuadro, and P. Zhang. Detour distance in graphs. J. Combin. Math. Combin. Comput. 52 (2005) 75–94.
  * [10] G. Chartrand, L. Garry, and P. Zhang. The detour number of a graph. Utilitas Mathematica 64 (2003) 97–113.
  * [11] V. Chepoi. Peakless functions on graphs. Discrete Applied Mathematics 73(2) (1997) 175–189.
  * [12] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. Complexity results related to monophonic convexity. Discrete Mathematics 158 (2010) 1268–1274.
  * [13] M. C. Dourado, D. Rautenbach, V. F. dos Santos, P. M. Schäfer, J. L. Szwarcfiter, and A. Toman. An upper bound on the $P_{3}$-Radon number. Discrete Math 312(16) (2012) 2433–2437.
  * [14] F. F. Dragan, F. Nicolai, and A. Brandstädt. Convexity and HHD-free graphs. SIAM J. Discrete Math 12 (1999) 119–135.
  * [15] P. Duchet. Convex sets in graphs, II. Minimal path convexity. Journal of Combinatorial Theory, Series B 44 (1988) 307–316.
  * [16] M. Farber and R. E. Jamison. On local convexity in graphs. Discrete Math. 66 (1987) 231–247.
  * [17] G. Gutin and A. Yeo. On the number of connected convex subgraphs of a connected acyclic digraph. Discrete Appl. Math. 157(7) (2009) 1660–1662.
  * [18] F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. Math. Comput. Modelling 17(11) (1993) 89–95.
  * [19] F. Harary and J. Nieminen. Convexity in graphs. Journal of Differential Geometry 16 (1981) 185–190.
  * [20] J. Hopcroft and R. Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM 16:6 (1973) 372–378.
  * [21] R. E. Jamison and R. Nowakowski. A Helly theorem for convexity in graphs. Discrete Mathematics 51:1 (1984) 35–39.
  * [22] L. Nebeský. A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44(1) (1994) 173–178.
  * [23] M. H. Nielsen and O. R. Oellermann. Steiner trees and convex geometries. SIAM J. Discrete Math. 23(2) (2011) 680–693.
  * [24] D. B. Parker, R. F. Westhoff, and M. J. Wolf. Two-path convexity in clone-free regular multipartite tournaments. Australas. J. Combin. 36 (2006) 177–196.
  * [25] E. Sampathkumar. Convex sets in a graph. Indian J. Pure Appl. Math. 15(10) (1984) 1065–1071.
  * [26] M. L. J. van de Vel. Theory of Convex Structures. North Holland, 1993.


# Examining Factors Associated with Twitter Account Suspension Following the
2020 U.S. Presidential Election

Farhan Asif Chowdhury1, Dheeman Saha1, Md Rashidul Hasan1, Koustuv Saha2,
Abdullah Mueen1

###### Abstract

Online social media enables mass-level, transparent, and democratized
discussion on numerous socio-political issues. Due to such openness, these
platforms often endure manipulation and misinformation - leading to negative
impacts. To prevent such harmful activities, platform moderators employ
countermeasures to safeguard against actors violating their rules. However,
the correlation between publicly outlined policies and employed action is less
clear to general people.

In this work, we examine violations and subsequent moderations related to the
2020 U.S. President Election discussion on Twitter. We focus on quantifying
plausible reasons for the suspension, drawing on Twitter’s rules and policies
by identifying suspended users (Case) and comparing their activities and
properties with (yet) non-suspended (Control) users. Using a dataset of 240M
election-related tweets made by 21M unique users, we observe that Suspended
users violate Twitter’s rules at a higher rate (statistically significant)
than Control users across all the considered aspects - hate speech,
offensiveness, spamming, and civic integrity. Moreover, through the lens of
Twitter’s suspension mechanism, we qualitatively examine the targeted topics
for manipulation.

##  1 Introduction

Social media platforms such as Facebook, Twitter, and Reddit have become
vastly popular in public discussion related to societal, economic, and
political issues (Gil de Zúñiga, Jung, and Valenzuela 2012). However, in the
recent past, these platforms were heavily targeted for manipulation and
spreading misinformation relating to numerous civic issues across the world
(Bessi and Ferrara 2016), which is often referred to as “Computational
Propaganda” (Woolley and Howard 2018). In particular, the coordinated
misinformation and influence campaigns of foreign state-sponsored actors
during the 2016 U.S. presidential election were highly scrutinized - which
eventually led to the U.S. Congressional hearings and investigation by the
U.S. Department of Justice (Congress-Hearing 2017; Mueller-Report 2019).

In the aftermath of the 2016 U.S. presidential election, social platforms
announced strict and improved platform moderation policy (Facebook-Update
2017; Twitter-Update 2018). However, these platform’s moderation and
suspension policies have been largely debated and have faced severe criticism
from the political leaders and supporters about bias towards their opposition
(Bias 2016, 2020). Although these platforms publicly outline their moderation
policy, there is no third-party monitoring of their enacted moderation.
Moreover, social platforms like Twitter and Facebook employ extensive
safeguard mechanisms that consider various aspects of user activities
(coordinated activities, impersonation, etc.) to identify malicious behavior
(Twitter-Safety 2021). Therefore, analyzing these suspended users’ tweets and
shared content might shed light on violators’ targeted topics.

In the context of inadequate countermeasures against manipulation during the
2016 U.S. presidential election, the 2020 election was of paramount importance
for platform operators to provide a safe and democratized public discussion
sphere (Twitter-Policy 2021). The impact and importance of these safeguard
measures are not confined to this particular election; instead, they bear
cardinal implications for future online political discussions exceeding all
geopolitical boundaries. Therefore, it is requisite to assess these platforms’
moderation policy — to investigate the correlation between their policies and
actions, examine for potential political biases, and make general people aware
of the targeted malice topics.

In this respect, we focus on analyzing the moderation policy of popular micro-
blogging site Twitter as a case-study by asking the following research
questions:

  * •

RQ1: What factors associate with Twitter account suspension following the 2020
U.S. President Election?

  * •

RQ2: How do political ideologies associate with the suspended accounts?

  * •

RQ3: What was the topic of discussion among suspended users? What type of
content these users shared?

This work. To answer these research questions, we collect a large-scale
dataset of 240M tweets made by 21M unique users over eight weeks centering the
2020 U.S. President Election. Afterward, we identify 355K suspended users who
participated in this election discussion. We draw upon Twitter’s rules and
policies to examine plausible suspension factors. To investigate the user
activity that might lead to suspension, we adopt the “case-control” study
design from epidemiology (Schulz and Grimes 2002). We consider the suspended
users as Case group and sample similar number of non-suspended users as
Control group. We devise several classification techniques to quantify
suspension factors among these two groups. We infer these users’ political
leaning by utilizing the political bias of the news media outlet they share.
By employing a language differentiation technique, we contrast the
conversational topics and shared content among Case and Control groups.
Through the lens of Twitter’s suspension policy, we passively infer the
targeted topics by platform violators and identify the online content
platforms utilized to sway the discussion.

Summary findings. We find that across all suspension factors, the Suspended
users have higher (statistically significant) violation occurrences. Coherent
with prior work, we find that Suspended users are short-lived, have fewer
followers, and show more tweeting activity. We observe a higher presence of
right-leaning users than left-leaning users among Suspended users. We find
that Suspended users use more curse and derogatory words and personally-
attacking and propaganda related hashtags. We also notice that these users
share news content from heavily biased right-leaning news-propaganda sites. We
discuss the implications and limitations of our work in the Conclusion.

##  2 Related Work

There have been several works related to Twitter suspension, most of which
focused primarily on spam-related suspensions (Thomas et al. 2011; Amleshwaram
et al. 2021). More recently, Le et al. studied suspended users in the context
of the 2016 U.S. presidential election (Le et al. 2019), and Chowdhury et al.
examined a large group of suspended users related to a large-scale Twitter
purge in 2018 (Chowdhury et al. 2020). We refer readers to (Le et al. 2019;
Chowdhury et al. 2020) for a more comprehensive understanding of suspension
and moderation on online platforms. However, none of these works quantify
specific factors associated with Twitter suspension. Additionally, political
discussions and related manipulation on online platforms have been thoroughly
studied previously (Ferrara 2017; Im et al. 2020), mostly related to the 2016
U.S.presidential election (Badawy, Ferrara, and Lerman 2018; Zannettou et al.
2019). These works primarily focus on characterizing malicious users and
inferring their motivation and impact. Im et al.; Badawy, Ferrara, and Lerman
provide an extensive overview of this line of work (Im et al. 2020; Badawy,
Ferrara, and Lerman 2018). In contrast, we focus on quantifying suspension
factors and examining malice topics related to the 2020 U.S. presidential
election.

##  3 Data

To collect tweets related to the 2020 U.S. President Election discussion, we
deployed an uninterrupted data collection framework utilizing Twitter’s
streaming API to filter real-time tweets based on given keywords. Similar to
prior work that collected specific theme or event-related tweets (Olteanu et
al. 2014), we initialize the keyword set with manually curated election-
related words and hashtags. To cover the continuously evolving election
discussions and topics, we update the keyword set daily with new trending
hashtags and words from previous days collection, as employed in (Abu-El-Rub
and Mueen 2019; Olteanu et al. 2015). We provide a list of all the keywords in
the supporting website (Website 2021). Our data collection time-period spans
over around ten weeks, centering the election date - from “September 28, 2020”
to “December 04, 2020”. Approximately one month after our data collection
ends, on “January 01, 2021” we start probing Twitter for each of the
participating users from our dataset to identify the suspended users. Twitter
returns the response code $63$ when requested user information for a suspended
user. In this process, we identify 355,573 suspended users from roughly 21M
participating users. We provide a summary descriptive statistics of our
dataset in Table 1 and plot per user tweet count in Figure 1. We discuss the
limitation of our data collection framework in Section 6.

Figure 1: Distribution of # of users by # of tweets.

Statistic | Value
---|---
# Tweets | 240M
# Unique users | 21M
# Retweets | 173M
# Quote tweets | 60M
# $\mu$ tweets per user | 11
# Suspended users | 355K
# Tweets by sus. users | 7.2M

Table 1: Descriptive statistics of Twitter Dataset.

Ethical Concerns. Throughout our data collection, experiment design, and
analysis process, we maintain ethical research standards (Rivers and Lewis
2014). Hence, the accommodating academic institution’s Institutional Review
Board exempted this project after a formal review. Following Twitter’s terms
of services guideline: (1) we use the Twitter API key only for passive data
collection purposes, (2) we do not publish user-specific information, (3) we
do not redistribute the data, and (4) we only share aggregated statistics and
derived information to facilitate future work.

##  4 Methods

### RQ1: Inferring Suspension Factors

Twitter rules and policies. To infer the plausible factors that explain
suspension, we draw upon Twitter’s rules, and policies for free and safe
public discussion (TwitterRules 2021). Twitter outlines three specific
categories — (1) safety, (2) privacy, (3) authenticity, each of which entails
finer sub-categories on specific violating activities. We specifically focus
on five sub-categories that are more likely to be enacted upon on election
discussion: three from safety — (1) hateful conduct, (2) abuse/harassment, (3)
terrorism/violent extremism; two from authenticity — (4) spamming, (5) civic
integrity. The rest are either not largely relevant (i.e., copyright, nudity)
or inferred from our data (i.e., impersonation - as we do not have user and
tweet information for all the tweet, sensitive media content - as we do not
crawl media content).

Hateful Conduct and Offensive Behavior. Several recent works aim to identify
hateful and abusive activities in online platforms, which produced publicly
available datasets and trained models (Founta et al. 2018; Davidson et al.
2017). However, as the distinction between abusive and violent language is
ill-defined, they unified these categories. Similarly, we combine both abusive
and violent tweets into one category - offensive. We utilize an automatic hate
speech and offensive language detection technique to detect hateful and
offensive tweet, known as HateSonar (Davidson et al. 2017). HateSonar is a
logistic regression classifier that uses several text features (i.e., TF-IDF
of word-grams, sentiment, etc.), which has been trained on manually labeled
tweet corpus. We use a pre-trained HateSonar model to classify each tweet into
three categories: (1) hateful, (2) offensive, and (3) normal.

Civic integrity. Twitter has established strict rules to prevent users from
“manipulating or interfering in elections or other civic processes”, including
“posting and sharing misleading content” (Twitter-Integrity 2021). To infer
such violation, we utilize the posted hashtags and shared news website URLs.
We curate a list of hashtags related to misinformation, propaganda, and
conspiracy theories, borrowing from the work by (Ferrara et al. 2020), where
they curated a list of conspiracy related hashtags. Additionally, we compile a
list of biased and propaganda-spreader news websites based on a publicly
available dataset from (FactCheck 2021; Politifact 2021). If a tweet contains
a hashtag or news article from our curated list, we consider it a violation of
civic integrity policy.

Spam. Several previous works have identified spamming on Twitter, most of
which consider both tweet content and user attributes for user-level
classification. Here, we primarily infer spamming violations at tweet-level
based on tweet content, for which we utilize a collection of spam keywords
(Benevenuto et al. 2010). However, to quantify spammers at the user-level, we
also examine several account attributes (i.e., account age, tweet rate, etc.),
which are most prominent for spammer detection (Thomas et al. 2011; Yang et
al. 2020).

We note that the above-defined classification techniques are no match to
Twitter’s actual countermeasure mechanism. Rather, we posit these methods as
high-precision approaches — which utilize language models and keyword matching
to avoid false-positives. The detected violations can be regarded as the
lower-bound for actual ensued violations, only to increase with more
comprehensive approaches.

### RQ2: Political Ideology of Suspended Users

We infer political leaning based on the political bias of the shared media
outlets in the tweets. Similar to previous work on studying political ideology
on Twitter (Badawy et al. 2019), we curate a list of “politically inclined”
media outlets based on publicly available data from (AllSides 2021; MediaBias
2021). Additionally, if a user retweets one of the presidential candidates
without adding a quote, we consider it as ideological endorsement (Ferrara et
al. 2020).

### RQ3: Conversational topics and shared content

Twitter employs extensive countermeasure tools that consider a multitude of
factors, features, and algorithms (Twitter-Measures 2018); which is beyond the
scope of any third-party observer to reproduce. However, through the lens of
Twitter’s suspension policy, we can identify platform violators’ targeted
topics as a passive sensing mechanism for detecting online malice. Towards
that, we contrast the conversational topics of Suspended and Control users. In
particular, we consider (1) top uni-grams and bi-grams – to infer the
commonality of discussion language; (2) hashtags – which are used for
signaling and discoverability purposes (Bruns and Burgess 2011) and have been
instrumental in several political and social movements (Arif, Stewart, and
Starbird 2018). Additionally, Twitter is often used as an amplifier and
fishing platform to disseminate news and multimedia content. Hence, we also
examine the shared URL-domains to examine the online content platforms
utilized by platform violators.

To examine the uniqueness across these dimensions, we use a generative text
modeling method known as Sparse Additive Generative Models of Text, or SAGE
(Eisenstein, Ahmed, and Xing 2011). We use SAGE as a text differentiation
technique where each class label or latent topic is endowed with a model of
the deviation in log-frequency from a constant background distribution. We
utilize SAGE to identify the highly used distinctive word-grams, hashtags, and
URL-domains across Suspended and Control user’s tweet corpus.

##  5 Results

Measure | Suspended | Control | d | t | KS
---|---|---|---|---|---
Suspension rule (Safety)
Hateful (%) | 0.78 | 0.43 | 0.05 | 77.73*** | 0.003***
Offensive (%) | 6.45 | 5.21 | 0.05 | 91.62*** | 0.01***
Suspension rule (Authenticity)
Civic Integrity (%) | 0.40 | 0.30 | 0.02 | 31.46*** | 0.001***
Spam (%) | 0.56 | 0.38 | 0.03 | 46.83*** | 0.002***
Account Properties
Active days | 964.0 | 1972.9 | -0.74 | -151.77*** | 0.24***
Tweets per Day | 33.5 | 20.82 | 0.25 | 50.20*** | 0.14***
Followers Count | 1491.5 | 3337.2 | -0.04 | -8.54*** | 0.11***
Friends Count | 1112.5 | 1263.7 | -0.03 | -6.74*** | 0.11***
Political Ideology (% Tweets)
Left Leaning | 3.97 | 5.65 | -0.08 | -137.9*** | 0.02***
Right Leaning | 7.25 | 6.00 | 0.05 | 87.21*** | 0.01***

Table 2: Summary of differences in quantitative measures across Suspended  and
Control  users. We report average occurrences across matched clusters, effect
size (Cohen’s $d$), independent sample $t$-statistic, and $KS$-statistic.
$p$-values are reported after Bonferroni correction (* $p$<0.05, ** $p$<0.01,
*** $p$<0.001).

### RQ1: Inferring Suspension Reason

In this subsection, we quantify the differences in the suspension rules
between Suspended and Control users. We calculate effect size (Cohen’s $d$)
and use independent sample $t$-tests to evaluate statistical significance in
the differences. We perform Koglomorov-Smirnov ($KS$) test to test against the
null hypothesis that the distribution of suspension rules for the Suspended
and Control users are drawn from the same distribution (Saha et al. 2021). We
summarize these differences in Table 5.

Hateful Conduct and Offensive Behavior. Suspended users are twice more likely
to post hateful tweets than Control users ($t$=77.73, $p$<0.05). Also,
Suspended users post more offensive tweet than Control users ($t$=91.62,
$p$<0.05). These findings are in coherence with Twitter’s suspension policy.

Civic Integrity and Spam. We find that Suspended users are more likely to use
hashtags related to conspiracy theories and share news from media sites with
questionable authenticity ($t$=31.46, $p$<0.05). Also, Suspended users are 50%
more likely to post spam-tweets ($t$=46.83, $p$<0.05).

Account Properties. We find significant difference in the active days between
Suspended and Control users ($t$=-151.77, $p$<0.05). The Control users are, on
average, roughly three years older than Suspended users. Contrastingly, these
short-lived Suspended users post 50% more tweets compared to Control users
($t$=50.20, $p$<0.05). The Suspended users have less follower count, on
average 100% less than Control users ($t$=-8.54, $p$<0.05). However, both
Suspended and Control users have similar friends count ($t$=-6.74, $p$<0.05).
These findings resonate with previous works studying spamming and suspension
on Twitter (Thomas et al. 2011; Chowdhury et al. 2020), which identified that
the rules violating users are generally short-lived, posts more tweet, and
have a smaller follower base.

### RQ2: Political Ideology of Suspended Users

In Table 5, we observe $40$% higher left-leaning tweets among Control users
than Suspended users ($t$=-$137.9$, $p$<$0.05$). In contrast, we observe
higher right-leaning tweets among Suspended users than Control users
($t$=$87.21$, $p$<$0.05$). Our finding shows that both left-leaning and right-
leaning users engaged in violating Twitter’s rules and policies, with $100$%
higher presence of right-leaning tweets among Suspended users than Control
users.

### RQ3: Conversational topics and shared content

Category |  Words
---|---
Control |  transistion, health care, amy coney barrett, flynn, senate, sidney powell, absentee, graham, judge, legal, rigged, mail, ballot, rudy giuliani, fraudulent
Suspended |  traitor, dumb, communist, biden family, idiot, seanhannity, fu*k, liar, stupid, breitbartnews, ukraine, treason, terrorist, evil, leftist
Table 3: Highly used fifteen distinctive words per user-group obtained using
SAGE.

Word Usage. In Table 3, we present the top 15 most distinctive words used in
per group’s tweet as obtained from the SAGE technique. We observe that Control
users distinctly used words relating to different event-driven election-
related topics (i.e., mail, ballot, rigged, fraudulent). However, we observe a
large presence of swear words (i.e., idiot, dumb) and sensitive words
(traitor, treason, terrorist) among Suspended users’ unique words, which
supports the higher hate-speech detection among suspended users.

Category |  Hashtags
---|---
Control |  pentagon, bigtech, corruptkelly, quidproquo, doj, justicematters, climatechange, flipthesenate, michiganhearing, cnntapes
Suspended |  stevebannon, bidenfamilycorruption, warroompandemic, russia, hunterbidenemails, hunterbidenlaptop, democratsaredestroyingamerica, bidencrimesyndicate, chinajoe, chinabitchbiden
Table 4: Highly used ten distinctive hashtags per user-group obtained using
SAGE.

Hashtag Usage. Table 4 presents the top 10 most distinctively used hashtags by
Suspended and Control users. Similar to word usage, the unique hashtags among
Control users were related to specific events (i.e., cnntapes, corruptkelly,
etc) and general election issues (i.e., bigtech, climatechange). In contrast,
distinct hashtags from Suspended users were mostly related to the defamation
of Democratic presidential candidate Joe Biden (i.e., bidencrimesyndicate,
chinajoe, chinabitchbiden) and issues related to his son Hunter Biden (i.e.,
hunterbidenemails, hunterbidenlaptops).

Category |  Domain
---|---
Control |  democracydocket.com, buildbackbetter.gov, www.infobae.com, latimes.com, texastribune.com, citizensforethics.org, theatlantic.com, motherjones.com, nytimes.com, npr.org
Suspended |  usfuturenews.com, trumpsports.org, techfinguy.com, mostafadahroug.com, ovalofficeradio.com, wuestdevelopment.de, queenofsixteens.com, truenewshub.com, einnews.com, thefreeliberty.com
Table 5: Highly shared ten distinctive URL-domain per user-group obtained
using SAGE.

Shared Content. In Table 5, we show the top 10 distinct shared domain names
per user group. Among the Control users, we observe the presence of few
moderately neutral news outlets (i.e., nytimes.com, npr.org), independent
political monitoring organization (i.e., democracydocekt.com,
citizenforethics.org), and few left-leaning news outlets (theatlantic.com,
motherjones.com). However, among Suspended users, we notice several heavily
right-leaning non-mainstream news-propaganda sites (i.e., usfuturenews.com,
ovalofficeradio.com, trunewshub.com, thefreeliberty.com).

##  6 Discussion and Conclusion

Implications. Our study bears an implication in shedding light on the
transparency about Twitter’s content moderation policy. Although we cannot
ascertain any quantitative estimation towards how far or through what means
Twitter’s rules followed, our study makes insightful findings of the
statistically significant occurrences of hateful, offensive, and
misinformative content among the users whose accounts were suspended after a
while. These findings support theoretical, empirical, and anecdotal evidence
about Twitter’s moderation policies (TwitterRules 2021), which had only gained
significant attention since January 2021 when Twitter suspended the U.S.
President Donald Trump’s Twitter account owing to inciteful and unrest-
provocative content (Trump-Ban 2020).

Limitations and Future Work. Our Twitter data collection has potential biases
as we initialize our seed keywords manually. While investigating plausible
suspension reasons, we use simple, interpretable, and high-precision
approaches - which are no match to Twitter’s complex and multi-faceted
safeguard mechanisms. We do not infer the exact reason for suspension for
individual users; rather, we quantify violations at tweet level. Future
research can use causal inference methods like matching (Saha and Sharma 2020)
to minimize confounds and draw causal claims about why certain accounts were
suspended. Moreover, we utilize several publicly available datasets that might
suffer from biases.

We argue to situate our work as an initial step towards understanding malice,
misinformation, and subsequent moderation related to the 2020 U.S.
presidential election on online platforms. Our presented insights and the
derived information can instigate further in-depth examination. For example,
the shared news articles’ content can be analyzed to understand the nature of
propaganda news. To facilitate such research, we make these news URLs publicly
available and other summary statistics (Website 2021). Similarly, future works
can investigate the dynamics of propaganda hashtags and news articles unique
to suspended users to understand their impact and influence. Additionally,
interactions among suspended users can be explored to identify potential
coordination.

Conclusion. In this work, we perform a computational study to analyze
Twitter’s suspension policy situated in the context of the 2020 U.S.
presidential election. We facilitate our work by collecting large-scale tweet
dataset during the election period and subsequently identifying the suspended
users. By designing a Case-Control experimental study and devising high-
precision classification approaches, we quantify associated factors related to
the suspension. Additionally, we explore the political ideology and targeted
topics of suspended users. We aim to motivate more rigorous and in-depth
future works through our presented insights and shared datasets.

## References

  * Abu-El-Rub and Mueen (2019) Abu-El-Rub, N.; and Mueen, A. 2019.  Botcamp: Bot-driven interactions in social campaigns.  In _The World Wide Web Conference_ , 2529–2535.
  * AllSides (2021) AllSides. 2021.  https://www.allsides.com/media-bias/media-bias-ratings.
  * Amleshwaram et al. (2021) Amleshwaram, A. A.; Reddy, A. N.; Yadav, S.; Gu, G.; and Yang, C. 2021.  CATS: Characterizing automation of Twitter spammers.
  * Arif, Stewart, and Starbird (2018) Arif, A.; Stewart, L. G.; and Starbird, K. 2018.  Acting the part: Examining information operations within# BlackLivesMatter discourse.  _Proceedings of the ACM on Human-Computer Interaction_ 2(CSCW): 1–27.
  * Badawy et al. (2019) Badawy, A.; Addawood, A.; Lerman, K.; and Ferrara, E. 2019.  Characterizing the 2016 Russian IRA influence campaign.  _Social Network Analysis and Mining_ 9(1): 31.
  * Badawy, Ferrara, and Lerman (2018) Badawy, A.; Ferrara, E.; and Lerman, K. 2018.  Analyzing the digital traces of political manipulation: The 2016 russian interference twitter campaign.  In _2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_ , 258–265. IEEE.
  * Benevenuto et al. (2010) Benevenuto, F.; Magno, G.; Rodrigues, T.; and Almeida, V. 2010.  Detecting spammers on twitter.
  * Bessi and Ferrara (2016) Bessi, A.; and Ferrara, E. 2016.  Social bots distort the 2016 US Presidential election online discussion.  _First Monday_ 21(11-7).
  * Bias (2016) Bias. 2016.  https://www.usatoday.com/story/tech/news/2016/11/18/conservatives-accuse-twitter-of-liberal-bias/94037802/.
  * Bias (2020) Bias. 2020.  https://www.wired.co.uk/article/twitter-political-account-ban-us-mid-term-elections.
  * Bruns and Burgess (2011) Bruns, A.; and Burgess, J. E. 2011.  The use of Twitter hashtags in the formation of ad hoc publics.  In _Proceedings of the 6th European consortium for political research (ECPR) general conference 2011_.
  * Chowdhury et al. (2020) Chowdhury, F. A.; Allen, L.; Yousuf, M.; and Mueen, A. 2020.  On Twitter Purge: A Retrospective Analysis of Suspended Users.  In _Companion Proceedings of the Web Conference 2020_ , 371–378.
  * Congress-Hearing (2017) Congress-Hearing. 2017.  https://www.govinfo.gov/content/pkg/CHRG-115shrg27398/pdf/CHRG-115shrg27398.pdf.
  * Davidson et al. (2017) Davidson, T.; Warmsley, D.; Macy, M.; and Weber, I. 2017.  Automated hate speech detection and the problem of offensive language.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 11.
  * Eisenstein, Ahmed, and Xing (2011) Eisenstein, J.; Ahmed, A.; and Xing, E. P. 2011.  Sparse additive generative models of text .
  * Facebook-Update (2017) Facebook-Update. 2017.  https://about.fb.com/news/2017/09/information-operations-update/.
  * FactCheck (2021) FactCheck. 2021.  https://www.factcheck.org/2017/07/websites-post-fake-satirical-stories/.
  * Ferrara (2017) Ferrara, E. 2017.  Disinformation and social bot operations in the run up to the 2017 French presidential election.  _arXiv preprint arXiv:1707.00086_ .
  * Ferrara et al. (2020) Ferrara, E.; Chang, H.; Chen, E.; Muric, G.; and Patel, J. 2020.  Characterizing social media manipulation in the 2020 US presidential election.  _First Monday_ .
  * Founta et al. (2018) Founta, A.; Djouvas, C.; Chatzakou, D.; Leontiadis, I.; Blackburn, J.; Stringhini, G.; Vakali, A.; Sirivianos, M.; and Kourtellis, N. 2018.  Large scale crowdsourcing and characterization of twitter abusive behavior.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 12.
  * Gil de Zúñiga, Jung, and Valenzuela (2012) Gil de Zúñiga, H.; Jung, N.; and Valenzuela, S. 2012.  Social media use for news and individuals’ social capital, civic engagement and political participation.  _Journal of computer-mediated communication_ 17(3): 319–336.
  * Im et al. (2020) Im, J.; Chandrasekharan, E.; Sargent, J.; Lighthammer, P.; Denby, T.; Bhargava, A.; Hemphill, L.; Jurgens, D.; and Gilbert, E. 2020.  Still out there: Modeling and identifying russian troll accounts on twitter.  In _12th ACM Conference on Web Science_ , 1–10.
  * Le et al. (2019) Le, H.; Boynton, G.; Shafiq, Z.; and Srinivasan, P. 2019.  A postmortem of suspended Twitter accounts in the 2016 US presidential election.  In _2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_ , 258–265. IEEE.
  * MediaBias (2021) MediaBias. 2021.  https://mediabiasfactcheck.com/.
  * Mueller-Report (2019) Mueller-Report. 2019.  https://www.justice.gov/storage/report.pdf.
  * Olteanu et al. (2015) Olteanu, A.; Castillo, C.; Diakopoulos, N.; and Aberer, K. 2015.  Comparing events coverage in online news and social media: The case of climate change.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 9.
  * Olteanu et al. (2014) Olteanu, A.; Castillo, C.; Diaz, F.; and Vieweg, S. 2014.  Crisislex: A lexicon for collecting and filtering microblogged communications in crises.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 8.
  * Politifact (2021) Politifact. 2021.  https://www.politifact.com/article/2017/apr/20/politifacts-guide-fake-news-websites-and-what-they/.
  * Rivers and Lewis (2014) Rivers, C. M.; and Lewis, B. L. 2014.  Ethical research standards in a world of big data.  _F1000Research_ 3\.
  * Saha et al. (2021) Saha, K.; Liu, Y.; Vincent, N.; Chowdhury, F. A.; Neves, L.; Shah, N.; and Bos, M. W. 2021.  AdverTiming Matters: Examining User Ad Consumption for Effective Ad Allocations on Social Media.  In _Proc. CHI_.
  * Saha and Sharma (2020) Saha, K.; and Sharma, A. 2020.  Causal Factors of Effective Psychosocial Outcomes in Online Mental Health Communities.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 14, 590–601.
  * Schulz and Grimes (2002) Schulz, K. F.; and Grimes, D. A. 2002.  Case-control studies: research in reverse.  _The Lancet_ 359(9304): 431–434.
  * Thomas et al. (2011) Thomas, K.; Grier, C.; Song, D.; and Paxson, V. 2011.  Suspended accounts in retrospect: an analysis of twitter spam.  In _Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference_ , 243–258.
  * Trump-Ban (2020) Trump-Ban. 2020.  https://blog.twitter.com/en_us/topics/company/2020/suspension.html.
  * Twitter-Integrity (2021) Twitter-Integrity. 2021.  https://help.twitter.com/en/rules-and-policies/election-integrity-policy.
  * Twitter-Measures (2018) Twitter-Measures. 2018.  https://blog.twitter.com/en_us/topics/company/2018/how-twitter-is-fighting-spam-and-malicious-automation.html.
  * Twitter-Policy (2021) Twitter-Policy. 2021.  https://blog.twitter.com/en_us/topics/company/2020/2020-election-changes.html.
  * Twitter-Safety (2021) Twitter-Safety. 2021.  https://blog.twitter.com/en_us/topics/company/2018/how-twitter-is-fighting-spam-and-malicious-automation.html.
  * Twitter-Update (2018) Twitter-Update. 2018.  https://blog.twitter.com/en_us/topics/company/2018/2016-election-update.html.
  * TwitterRules (2021) TwitterRules. 2021.  https://help.twitter.com/en/rules-and-policies/twitter-rules.
  * Website (2021) Website. 2021.  https://sites.google.com/view/us-election20-twitter-suspend.
  * Woolley and Howard (2018) Woolley, S. C.; and Howard, P. N. 2018.  _Computational propaganda: political parties, politicians, and political manipulation on social media_.  Oxford University Press.
  * Yang et al. (2020) Yang, K.-C.; Varol, O.; Hui, P.-M.; and Menczer, F. 2020.  Scalable and generalizable social bot detection through data selection.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 1096–1103.
  * Zannettou et al. (2019) Zannettou, S.; Caulfield, T.; De Cristofaro, E.; Sirivianos, M.; Stringhini, G.; and Blackburn, J. 2019.  Disinformation warfare: Understanding state-sponsored trolls on Twitter and their influence on the web.  In _Companion proceedings of the 2019 world wide web conference_ , 218–226.