# Mobility driven coexistence of living organisms

B.F. de Oliveira  M.V. de Moraes  D. Bazeia  and A. Szolnoki  Departamento de
Física, Universidade Estadual de Maringá, 87020-900 Maringá, PR, Brazil
Departamento de Física, Universidade Federal da Paraíba, 58051-970 João
Pessoa, PB, Brazil  Institute of Technical Physics and Materials Science,
Centre for Energy Research, P.O. Box 49, H-1525 Budapest, Hungary

###### Abstract

We propose a minimal off-lattice model of living organisms where just a very
few dynamical rules of growth are assumed. The stable coexistence of many
clusters is detected when we replace the global restriction rule by a locally
applied one. A rich variety of evolving patterns is revealed where players
movement has a decisive role on the evolutionary outcome. For example,
intensive individual mobility may jeopardize the survival of the population,
but if we increase players movement further then it can save the population.
Notably, the collective drive of population members is capable to compensate
the negative consequence of intensive movement and keeps the system alive.
When the drive becomes biased then the resulting unidirectional flow alters
the stable pattern and produce a stripe-like state instead of the previously
observed hexagonal arrangement of clusters. Interestingly, the rotation of
stripes can be flipped if the individual movement exceeds a threshold value.

###### keywords:

clustering, drive, pattern formation

††journal: Physica A

##  1 Introduction

Clusters are essential and abundant patterns in wide variety of living systems
ranging from the simplest organizations, such as bacterias, to more complex
ones, like insects, fishes, or birds [1, 2, 3]. But mammals and even humans
can also be observed as they form the mentioned shape [4]. Evidently, there
are several and often independent reasons why clusters emerge and maintain
because external conditions and governing dynamics may differ significantly
[5]. For example, staying together may minimize predation risk, but seeking
for food could also be more advantageous in groups [6, 7, 8]. Notably, such an
arrangement of individuals play a decisive role in the evolution of
cooperation, too, because it can reveal the sharp contrast between cooperator
and defector strategies [9]. Namely, while the defectors cannot benefit from
the clustering with akin players, cooperators enjoy the close company of
similar fellows and this difference is in the heart of several ways of
reciprocity [10, 11, 12, 13].

In a previous paper we studied a simple model of clustering in which female
and male individuals followed a basic rule of reproduction, die and movement
and demonstrated that a uniformly distributed population can transform into a
state where species form a huge single cluster [14]. While the centre of this
aggregation moves randomly its size follows a power law behavior in terms of
the number of individuals in the whole population. In our present work we
alter some element of former model definition slightly and demonstrate that it
causes dramatic change in pattern formation. In particular, we do not apply a
global restriction for the maximum value of individuals. Instead, we apply a
local constraint which maximizes the number of individuals within a certain
distance of parents species. Furthermore, we distinguish two characteristic
lengths, which are the length of movement ($\ell_{mov}$) and the range of
reproduction ($\ell_{rep}$). This extension make us possible to study the
proper consequence of individual mobility on the evolutionary outcome. As
result, we can observe the emergence of muti-clustered pattern in the stable
phases and explore how the intensity of individual movement influences the
survival of the whole population.

Beside the mentioned extensions we also study the possible consequences of
collective movement, when the motion of species is not completely random, but
there is a general drive in the population. This condition can be observed in
nature frequently when floating individuals are in a stream or in a river, but
currents in oceans can also offer examples for similar collective drift [15].
Notably, the potential impact of a drive on the final outcome is not
restricted to cases when it is a given natural condition, but it could also be
an artificial tool to manipulate the evolving solution of a competing system
[16, 17, 18]. In this way to explore the potential link between emerging
patterns and the intensity of flow could be a promising device to design a
desired solution in a complex system.

##  2 The model

In our minimal off-lattice model of living organisms we do not assume any
particular interaction between individuals and the pattern formation is
controlled solely by some very basic rules. At the beginning we release $N/2$
female and $N/2$ male individuals who are distributed randomly on a square-
shaped box of linear size $L=1$. To avoid problems originated from finite size
we apply periodic boundary conditions.

At each time step a single individual (active) is chosen randomly to move in a
random direction with a step size $\ell_{mov}$. Furthermore, one of the two
competing processes is executed with a certain probability. More precisely, an
individual is chosen to die and removed from the simulation with probability
$p_{d}$. Alternatively, a reproduction process is executed with probability
$p_{r}=1-p_{d}$. In the latter case we explore the neighborhood of the focal
individual within a distance $\ell_{rep}$. If there is an individual of the
opposite sex within the circle then a newborn is settled whose position and
gender are chosen randomly. Importantly, the new individual is settled only if
the total number of individuals in the neighborhood (within a distance
$R=0.1$) does not exceed a threshold value $M$. This local constraint of
maximum number of individuals is a significant difference from our previous
model where only a global constraint for the maximum number of total
population was assumed [14]. Another important change comparing to our
previous model is $\ell_{mov}$ and $\ell_{rep}$ could be different. In this
way we can study the possible impact of individual’s mobility properly.

In most of the simulations we used $p_{r}=0.7$ and $p_{d}=0.3$ but results of
other probability pairs are also discussed. In the stationary state, which is
typically reached within 500 generations, we have measured different
quantities as described later. For the requested accuracy we have averaged our
data over 500 independent runs.

Beside the random walks of individuals we have also considered biased movement
when species are drifting along a specific direction collectively. Motivated
by previous self-driven models [19, 20, 21] we span between the random and
completely biased movement by using a driving parameter $\eta$. When $\eta=1$
individuals move randomly while at $\eta=0$ all of them move toward a specific
direction. We have chosen this direction horizontally from left to right,
which is connected to $\phi=0$ angle in a polar coordinate system. When the
value of $\eta$ is between these two extreme cases then individuals have a
limited access of choosing a direction to jump, where the $(-\phi,+\phi)$
range of available directions is proportional to the value of $\eta$. As we
already mentioned, collective movement of living species is a very common
phenomenon in nature which might have a specific role on the emergence of a
certain pattern. The main goal of present paper is to clarify the possible
connections between individual movement and emerging global patterns.

##  3 RESULTS

###  3.1 Random movement

Figure 1: Typical snapshots of the spatial distribution of females (red) and
males (blues) after $500$ generations when the evolution is started from a
random initial condition with $N=10^{4}$ individuals. Panels from (a) to (c)
show the stable stationary patterns at $p_{d}=0.05,0.25$ and $0.41$
respectively. For higher $p_{d}$ values the population goes extinct. In every
cases we used the same $M=160$, $\ell_{mov}=\ell_{rep}=0.01$ parameter values
for proper comparison. The applied local constraint to the maximum number of
individuals result is a multi-clustered pattern where the spatial arrangement
of clusters depicts a hexagonal rotation symmetry.

We first present some results obtained at small mobility values where
individuals chose all directions with the same probability. Figure 1 shows
three typical snapshots of the population for low, intermediate and relatively
high probability of dying. For proper comparison the rest of the parameters,
namely the characteristic lengths of movement and reproduction and the maximum
number of individuals in a neighborhood, are identical.

When the probability of die is low, shown in panel (a), then a reasonably high
number of individuals are present in the available space. As we increase
$p_{d}$, the total number of survivors decays gradually. First those
individuals become vulnerable who are far away from the centre of a cluster.
But above a threshold value of $p_{d}$, however, all individuals go extinct
and the population cannot survive no matter how large initial $N$ value was
used. Evidently, the critical $p_{d}$ value depends on the value of $M$, which
is $p_{d}=0.42$ for $M=160$.

The most striking difference between present results and those obtained in a
former case [14] is the stable presence of several clusters in our present
model. This is a direct consequence of the fact that we modified the
restriction of maximum number of surviving individuals from a global to local
one. As the previous work demonstrated, the application of a global
restriction law resulted in a single-cluster final state. This behavior can be
understood because the globally applied rule generated an effective
interaction between competing clusters. More precisely, when parents in a
specific cluster tried to give birth to a descendant then its success depended
on the actual state of the population far in another cluster. Accordingly, the
newborn was aborted if the global number of individual exceeded the threshold
value $N$. In this way the growth of a cluster was not independent on the
evolution of another competing cluster. But the lack of a newborn also implies
the decay of the mentioned cluster because the alternative process, which is a
random die of group members with a given probability, works freely. Evidently,
an initially larger cluster has a higher chance to survive and after it can
produce a huge singular aggregation to reach the maximal allowed population
size. This effective interaction between the competing clusters makes the game
biased because the cluster which has an initial advantage is capable to
enlarge the difference and survive alone. However, when we switched the global
restriction rule to a local one then clusters can evolve independently where
the only restriction is to avoid too crowded spot locally. As a result,
several clusters remain alive where the emerging pattern is the result of a
delicate balance between the competing processes of reproduction and die.

We stress that individuals cannot survive everywhere, but just only in close
neighborhood with others, which is needed to compensate natural lost. This is
a fundamental condition of cluster formation where the actual value of $p_{d}$
determines their prevalence. The spatial distribution of cluster, however,
always depicts a hexagonal rotation symmetry independently how many of them
are present, as it is illustrated in Fig. 1.

Figure 2: Stationary snapshots for different values of individual mobility for
$\ell_{mov}=0.005$ (a), $\ell_{mov}=0.015$ (b), and $\ell_{mov}=0.025$ (c).
The remaining parameters, $p_{d}=0.30$, $\ell_{rep}=0.01$, and $M=150$, are
fixed for all cases. The comparison suggests that intensive individual
movement destroys the cluster ordering.

Next we explore the possible role of individual mobility on the pattern
formation. In our previous model $\ell_{mov}$ and $\ell_{rep}$ had the same
value, but this equality prevents us to explore the proper consequence of
individual mobility. More precisely, if we enlarge both typical length scales
simultaneously then there is no chance for players to leave their parents or
descendants and the increase of the single characteristic length does not
change the neighborhood of individuals relevantly. However, if we vary
$\ell_{mov}$ unilaterally by keeping $\ell_{rep}$ fixed then individuals may
arrive into a new environment where descendants or parents are not necessarily
present. This extension, as it is illustrated in Fig. 2, has huge consequence
on the spatial distribution of species. In the mentioned plot we show some
typical patterns for the cases of minimal, mild and more intensive individual
mobility. As the patterns show the contour of disjunct clusters diminishes by
more intensive player’s movement.

Previously we argued that clustering is an essential condition for the
population to survive therefore the lost of clusters can easily jeopardize the
survival chance of individuals. Indeed, one may observe less individuals in
panel (c) of Fig. 2 where the movement of players is the most intensive. To
quantify this effect we measure the global density of individuals in
dependence of $\ell_{mov}$ and the results are summarized in Fig. 3. This plot
confirms our previous observation, namely the average number of individuals
decreases by increasing the mobility of players. Nevertheless, this decay is
not continuous, but falls to zero level at a specific mobility value. This
result suggests that too intensive movement of individuals could be
detrimental for the survival chance of the whole population.

Figure 3: Average density of the population in dependence of individual
mobility for $M=160$, $\ell_{rep}=0.01$, and $p_{d}=0.31$. At a threshold
value of $\ell_{mov}=0.027$ the system goes extinct. It suggests that
intensive individual mobility could be harmful for the whole population.
Figure 4: Survival probability of the population ($P$) in dependence of
individual mobility $\ell_{mov}$. Other parameters are $M=160$,
$\ell_{rep}=0.01$, and $p_{d}=0.3$. Simulations were started from a random
distribution of $N=10^{4}$ individuals and each point was calculated from
$10^{3}$ independent runs after 500 generations. A moderate strength of
individual mobility can destroy the population, but a more intensive movement
is able to recover the surviving chance.

One may argue, however, that if the mobility is high enough then individuals
may reach another cluster and in this way they get a second chance to be
mated. It could be the case but only if the $p_{d}$ probability of die is not
too high hence players survive the journey to the next aggregation. This
effect is illustrated in Fig. 4 where we present the survival probability of
the whole population in dependence of the intensity of player’s movement. In
agreement with the previous plot shown in Fig. 3 slow movement of individuals
does not harm the chance of survival, but longer jumps away from the original
cluster members can easily kill the whole population. Increasing further the
distance of jumps, hence the intensity of mobility, can give a reasonable
chance to survive and it becomes practically a sure event for large
$\ell_{mov}$. The significant difference between the case shown here and in
our previous plot is a bit lower value of $p_{d}$ which allows players to
arrive safe to the next harbor when movement was intensive. It is easy to
understand that similar impact can also be reached by increasing the $M$
threshold value of locally maximum individuals at a fixed value of $p_{d}$
because in this case there are more players on the stage hence there could be
someone to mate in the neighborhood which keeps the population alive.

If we accept the above described explanation how pattern is forming in the
presence of player’s mobility then it is a straightforward consequence that by
decreasing $p_{d}$ further we can avoid the extinction of the population even
for more intensive individual movement. Indeed, the results plotted in Fig. 5
confirm our claim where the population does not go extinct no matter how
intensive mobility was applied. Naturally, by increasing $\ell_{mov}$ from a
minimal value does lower the average concentration because some player escapes
from the chance of mating, but eventually they will find a new partner to
produce new members who can compensate the natural loss of the population. In
this way the strength of mobility becomes second-order important and the
average concentration level saturates which value depends exclusively on the
values of $M$ and $p_{d}$.

Figure 5: Average density of the population in dependence of individual
mobility for $M=160$, $\ell_{rep}=0.01$, and $p_{d}=0.29$. When we increase
$\ell_{mov}$ from a minimal value then the concentration level decays a bit
because there are players who escape from a chance of mating. But if the
mobility exceeds a certain level then the possibility to find a new partner
becomes viable hence the global population is not reducing further.
Accordingly, the total number becomes independent of the value of
$\ell_{mov}$.

###  3.2 Collective driven movement

In the rest of this paper we consider the case when the players movement are
not completely random, but follow a kind of ordering where limited jumping
directions are allowed only. Here the value of $0\leq\eta\leq 1$ determines
the available portion of jumping directions from the whole $[-\pi,+\pi]$
interval.

Our first principal observation is that restricted movement alone is capable
to improve the chance of survival if all other circumstances remain unchanged.
This effect is summarized in Fig. 6 where we plotted the survival probability
as a function of individual mobility for different values of drive.
Importantly, all remaining parameters are equal for all cases. As we already
noted, certain strength of mobility can be harmful for the population if
players jump randomly in all directions. But as we reduce the range of
available jumping directions the survival chance becomes better for more and
more mobility values. In the extreme case, when the individual movement
becomes completely biased then the population survives irrespectively of the
value of $\ell_{mov}$.

Figure 6: Survival probability of the population ($P$) in dependence of
individual mobility $\ell_{mov}$ for different values of drive. Here $\eta$
parameter determines the portion of available jumping directions for
individuals, where $\eta=1$ denotes random jumps to the whole $[-\pi,+\pi]$
range, while $\eta=0$ marks a completely reduced, hence ordered, movement
along the $x$-axis exclusively. Other parameters are $M=160$,
$\ell_{rep}=0.01$, and $p_{d}=0.3$. This comparison suggests that by
increasing the ordering of individual movement we can improve the survival
chance of the population even in the case where intensive mobility would
dictate extinction in the random movement case.

In the following we present some representative snapshots of spatial
arrangement of individuals for different drive values. The key point is
summarized in Fig. 7 where we plotted both the extreme cases and a sample for
an intermediate drive value. In agreement with our previous observations the
individuals are gathered in clusters whose arrangement show the mentioned
hexagonal symmetry when players move randomly. As we introduce a drive and
increase its value then the shape of the cluster becomes squeezed.
Furthermore, the relative spatial positions of these clusters also change and
the new order breaks the original hexagonal symmetry. Instead, squeezed
clusters order into stripes which are parallel to the direction of the drive.

The above described pattern formation helps to understand why a collective
driving promotes the survival of the whole population. When the individual
movement is not random, but tends toward a specific direction then it keeps
traveling individuals together, which always offer a higher chance of mating.
Therefore in this case the negative consequence of individual mobility becomes
not as crucial as in the previously discussed section. Evidently, the stronger
the drive the smaller the spreading of former partners, hence movement plays
no fundamental role anymore.

Figure 7: Typical spatial distribution of individuals for different driving
values of $\eta$. Panels from (a) to (c) show snapshots for $\eta=0,0.2$, and
$0.9$ respectively. For proper comparison all other parameter values, namely
$M=160$, $p_{d}=0.30$, and $\ell_{mov}=\ell_{rep}=0.01$, are fixed for all
cases. As we increase the drive, means reduce the range of jumping direction,
the shape of the clusters becomes squeezed and the original hexagonal symmetry
of spatial arrangement eventually becomes a simple stripe-like pattern where
the stripes are along the direction of the drive.

As a consequence of the above described phenomenon, in the $\eta=0$ limit we
cannot talk about clusters anymore, but instead parallel stripes. It is a
natural expectation that the orientation of the stripes is parallel to the
direction of the drive. In other words, the flow of individuals generates a
characteristic spatial patterns. We note that a similar selection from
possible patterns by an externally flow was already observed in driven
diffusive systems earlier [22, 23]. But in the latter case the short range
interaction among particles established the potential ordered state of the
system. In our present case, however, there is no similar kind of interaction
among players, they interact via the dynamical rules of die and reproduction
only.

Quite surprisingly, the orientation of stripes does depend on the intensity of
individual movement. More precisely, until a threshold level of $\ell_{mov}$
the stripes are parallel to the flow of players, but above this specific value
the direction of the stripes flips and they become perpendicular to the
original ordering. This phenomenon is illustrated in Fig. 8, where we present
some typical snapshots for different values of individual jumps. Here the
first two panels were taken at small and moderate $\ell_{mov}$ values, while
the remaining two panels show the pattern for more intensive individual
movement. Importantly, all other parameter values, like $\eta$, $M$,
$\ell_{rep}$, or $p_{d}$, are equal for all cases. One may notice that the
contour of stripes becomes sharper as we leave the threshold value, which
happens for low and large $\ell_{mov}$ values, while the stripes become
blurred in the vicinity of the transition point. The number of stripes may
also change because, as we pointed out earlier, the total number of individual
becomes independent of the strength of movement and it practically depends on
the value of $p_{d}$. Hence if we have wider stripes then their numbers should
decrease simultaneously.

Figure 8: Typical spatial distribution of individuals for different strength
of movement for unidirectional drive at $\eta=0.1$ Panels from (a) to (d) show
snapshots for $\ell_{mov}=0.020$, $0.070$, $0.095$, and $0.100$ respectively.
Other parameters, such as $M=160$, $p_{d}=0.30$, and $\ell_{rep}=0.01$, are
fixed for all cases. When we increase the intensity of players movement the
orientation of stripes flips perpendicular to the direction of drive.

To quantify the ordering process we utilize that fact that when stripes are
parallel to the drive then the horizontal position of individuals has no
relevance. On the contrary, when stripes are perpendicular to the drive then
there is a certain ordering in the horizontal positions of players: there are
crowded and deserted intervals as we vary horizontal coordinates. This
difference makes us possible to introduce an order parameter which measures
the difference between the horizontal and vertical ordering. In particular, we
measure the horizontal positions of all individuals and make a histogram of
the frequency of their values. Evidently, the number of disjunct intervals
should exceed the number of stripes, but if we choose the former large enough
then the profile function of the histogram will not change relevantly. As we
argued above, there is a huge difference between the profile functions if the
ordering of the stripes is horizontal or vertical. The difference is
summarized in Fig. 9 where we present two representative patterns and the
related histograms. As panel (a) illustrates, the horizontal positions of
players show a uniform distribution when stripes are horizontal and the
related frequencies fluctuates slightly around an average value. When the
stripes are vertical, however, the mentioned frequency profile becomes
strongly periodic where large and zero values occur periodically, which
reflects a horizontal ordering faithfully. Therefore, if we measure the
variance of the frequency profiles then we get a small or high $\sigma_{f}$
value depending on the horizontal or vertical directions of the stripes.

Figure 9: Typical spatial distribution of individuals from both sides of the
transition point. Panel (b) shows the pattern at $\ell_{mov}=0.035$, while
panel (d) at $\ell_{mov}=0.100$. To distinguish them we measured the frequency
of individuals in dependence of their horizontal positions and the related
histograms are shown in panel (a) and (c) respectively. As the histograms
show, when stripes are horizontal then the profile function $f$ fluctuates
slightly around an average level, which is marked by dashed line. In case of
vertical stripes, however, there are huge differences in the profile function
as we vary the horizontal coordinate. This makes possible to introduce an
order parameter which measures the variance of the profile function.

Indeed, if we measure $\sigma_{f}$ in dependence of $\ell_{mov}$ then we can
detect quantitatively the flipping transition we reported above. This function
is shown in Fig. 10 where we reduced all $\sigma_{f}$ values by the value
obtained at small $\ell_{mov}$ where horizontal stripes are present. In this
way the positive value and the magnitude of the reduced $\sigma_{f}$
characterizes the measure of ordering into vertical stripes. When this value
is low then the difference of ordering between the two directions is not
relevant, but when the mentioned value is high then we have a decent vertical
ordering of stripes. This plot identifies clearly a transition point when the
flip of ordering starts. Evidently the critical point of this transition
depends on the value of $M$ and $p_{d}$, but it is robust and can always be
detected when we apply a biased movement of individuals.

Figure 10: The order parameter which characterizes the flipping transition in
dependence of $\ell_{mov}$ at $\eta=0.1$, $M=160$, $p_{d}=0.30$,
$\ell_{rep}=0.01$. Note that $\sigma_{f}$ is not completely zero even for
horizontal ordering because there is some noise driven fluctuation in the $f$
profile as it is shown in panel (a) of Fig. 9. Furthermore, a smaller bulge
can also be detected in the $0.052<\ell_{mov}<0.066$ interval where the
stripes are still horizontal but there are some empty gaps in them which makes
the mentioned profile fluctuating. For $\ell_{mov}<0.08$, however, the
tendency is clear that is a mark of the transition in the orientation of the
stripes.

##  4 DISCUSSION AND CONCLUSIONS

In this work we have explored the possible consequences of individual mobility
on the pattern formation in a simple model of living organisms. Our principal
goal was to clarify whether the intensity of movement is crucial and check its
impact on the collective behavior in various conditions. We should stress that
our model is very simple and general, hence it could be adopted for wide range
of realistic systems [24].

As a key observation, we pointed out that a multi-cluster pattern emerges if
we leave the global constraint of maximum number of living individuals and
replace it by a locally applied restriction. Despite of the fact that we used
a numerically demanding off-lattice simulation, the resulting pattern can be
described by a hexagonal symmetry in a broad range of parameter values. This
behavior justifies the widely used assumption which states that triangular
host lattice is an adequate topology to simplify biological system during a
discrete-modeling [25, 26, 27].

We also found that intensive random individual mobility could be harmful for
the whole population because it reduces the occasions when partners with
opposite sex meet and produce a descendant. However, if the players movement
is intensive enough then the mentioned negative consequence can be fixed and
the stability of the population is restored.

Furthermore, when the individual motion is systematic and a collective
macroscopic movement emerges due to an external bias then the above mentioned
negative consequence of intensive mobility cannot be observed. Hence we can
conclude that a flow of participants stabilize the living conditions of an
organism where departing from others would easily jeopardize the whole
community otherwise.

The flow towards a specific direction has an additional role on the emerging
pattern, too, because it alters the spatial symmetry of the cluster
distribution. In particular, the original hexagonal symmetry is replaced by a
two-fold symmetry where individuals are organized into parallel stripes.
Interestingly, the direction of the stripes can be flipped if the individual
movement exceeds a threshold value. Above it the perpendicular ordering
becomes typical where the transition can be characterized by an appropriately
chosen order parameter.

We would like to stress that the above mentioned external bias may not
necessarily be a given natural condition, but could also be a human controlled
arrangement. The latter makes possible to utilize the flow of individual to
design and manipulate emerging patterns. Such efforts have already been
applied in engineered structure to study microfabricated habitats [28], but
fluid advection was also used to study emerging patterns in interacting
microbial communities [29]. We hope that our present work will be useful and
inspiring for future experimental works.

B.F.O. and M.V.M. thank CAPES - Finance Code 001, Fundação Arau-cária, and
INCT-FCx (CNPq/FAPESP) for financial and computational support. D.B.
acknowledges Conselho Nacional de Desenvolvimento Científico e Tecnológico
(CNPq, Grants nos. 303469/2019-6 and 404913/2018-0) and Paraíba State Research
Foundation (FAPESQ-PB, Grant no. 0015/2019) for financial support.

## References

  * Lui et al. [2013] L. T. Lui, X. Xue, C. Sui, A. Brown, D. I. Pritchard, N. Halliday, K. Winzer, S. M. Howdle, F. Fernandez-Trillo, N. Krasnogor, C. Alexander,  Bacteria clustering by polymers induces the expression of quorum-sensing-controlled phenotypes,  Nat. Chem. 5 (2013) 1058–1065.
  * Agarwala and Dixon [1993] B. K. Agarwala, A. F. G. Dixon,  Why do ladybirds lay eggs in clusters?,  Functional Ecology 7 (1993) 541–548.
  * Camazine et al. [2001] S. Camazine, J.-L. Deneubourg, N. R. Franks, J. Sneyd, G. Theraulaz, E. Bonabeau, Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ, 2001.
  * Vicsek [2010] T. Vicsek,  Closing in on evaders,  Nature 466 (2010) 43–44.
  * Javarone and Marinazzo [2017] M. A. Javarone, D. Marinazzo,  Evolutionary dynamics of group formation,  PLos ONE 12 (2017) e0187960.
  * Parrish and Edelstein-Keshet [1999] J. K. Parrish, L. Edelstein-Keshet,  Complexity, pattern, and evolutionary trade-offs in animal aggregation,  Science 284 (1999) 99–101.
  * Szolnoki et al. [2012] A. Szolnoki, Z. Wang, M. Perc,  Wisdom of groups promotes cooperation in evolutionary social dilemmas,  Sci. Rep. 2 (2012) 576.
  * Martinig et al. [2020] A. R. Martinig, M. Riaz, C. C. S. Clair,  Temporal clustering of prey in wildlife passages provides no evidence of a prey-trap,  Sci. Rep. 10 (2020) 11489.
  * Nowak and May [1992] M. A. Nowak, R. M. May,  Evolutionary games and spatial chaos,  Nature 359 (1992) 826–829.
  * Szolnoki and Perc [2015] A. Szolnoki, M. Perc,  Conformity enhances network reciprocity in evolutionary social dilemmas,  J. R. Soc. Interface 12 (2015) 20141299.
  * Szabó and Fáth [2007] G. Szabó, G. Fáth,  Evolutionary games on graphs,  Phys. Rep. 446 (2007) 97–216.
  * Floría et al. [2009] L. M. Floría, C. Gracia-Lázaro, J. Gómez-Gardeñes, Y. Moreno,  Social network reciprocity as a phase transition in evolutionary cooperation,  Phys. Rev. E 79 (2009) 026106.
  * Szolnoki and Chen [2018] A. Szolnoki, X. Chen,  Reciprocity-based cooperative phalanx maintained by overconfident players,  Phys. Rev. E 98 (2018) 022309.
  * Bazeia et al. [2020] D. Bazeia, M. V. de Moraes, B. F. de Oliveira,  Model for clustering of living species,  EPL 129 (2020) 28002\.
  * Vicsek and Zafeiris [2012] T. Vicsek, A. Zafeiris,  Collective motion,  Phys. Rep. 517 (2012) 71–140.
  * Drescher et al. [2014] K. Drescher, C. D. Nadell, H. A. Stone, N. S. Wingreen, B. L. Bassler,  Solutions to the public goods dilemma in bacterial biofilms,  Current Biology 24 (2014) 50–55.
  * Javarone [2016] M. A. Javarone,  Statistical physics of the spatial prisoner’s dilemma with memory-aware agents,  The European Physical Journal B 89 (2016).
  * Armano and Javarone [2017] G. Armano, M. A. Javarone,  The beneficial role of mobility for the emergence of innovation,  Scientific Reports 7 (2017).
  * Vicsek et al. [1995] T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, O. Shochet,  Novel type of phase transition in a system of self-driven particles,  Phys. Rev. Lett. 75 (1995) 1226–1229.
  * Avelino et al. [2018] P. P. Avelino, D. Bazeia, L. Losano, J. Menezes, B. F. de Oliveira,  Spatial patterns and biodiversity in off-lattice simulations of a cyclic three-species lotka-volterra model,  EPL 121 (2018) 48003\.
  * Avelino et al. [2020] P. P. Avelino, B. F. de Oliveira, J. V. O. Silva,  Rock-paper-scissors models with a preferred mobility direction,  EPL (Europhysics Letters) 132 (2020) 48003.
  * Szabó and Szolnoki [1990] G. Szabó, A. Szolnoki,  Transport-driven reorientation in a square lattice-gas model,  Phys. Rev. A 41 (1990) 2235–2238.
  * Szabó et al. [1992] G. Szabó, A. Szolnoki, G. Ódor,  Orientation in a driven lattice gas,  Phys. Rev. B 46 (1992) 11432–11438.
  * Dürrenberger et al. [1991] M. B. Dürrenberger, W. Villiger, T. Bächi,  Conjugational junctions: Morphology of specific contacts in conjugating Escherichia coli bacteria,  J. Struct. Biol. 107 (1991) 146–156.
  * Mouritsen [1984] O. G. Mouritsen, Computer Studies of Phase Transitions and Critical Phenomena, Springer-Verlag, Berlin, 1984.
  * Newman and Barkema [1999] M. E. J. Newman, G. T. Barkema, Monte Carlo Methods in Statistical Physics, Oxford University Press, Oxford, UK, 1999\.
  * Szolnoki and Szabó [2004] A. Szolnoki, G. Szabó,  Phase transitions for rock-scissors-paper game on different networks,  Phys. Rev. E 70 (2004) 037102.
  * Keymer et al. [2008] J. E. Keymer, P. Galajda, G. Lambert, D. Liao, R. H. Austin,  Computation of mutual fitness by competing bacteria,  Proc. Natl. Acad. Sci. U.S.A. 105 (2008) 20269–202073.
  * Uppal and Vural [2018] G. Uppal, D. C. Vural,  Shearing in flow environment promotes evolution of social behavior in microbial populations,  eLife 7 (2018) e34862.


# Entity Graphs for Exploring Online Discourse

Nicholas Botzer  University of Notre Dame, Notre Dame, IN  Tim Weninger
University of Notre Dame, Notre Dame, IN  Corresponding author:
<EMAIL_ADDRESS>
###### Abstract

Vast amounts of human communication occurs online. These digital traces of
natural human communication along with recent advances in natural language
processing technology provide for computational analysis of these discussions.
In the study of social networks the typical perspective is to view users as
nodes and concepts as flowing through and among the user-nodes within the
social network. In the present work we take the opposite perspective: we
extract and organize massive amounts of group discussion into a concept space
we call an _entity graph_ where concepts and entities are static and human
communicators move about the concept space via their conversations. Framed by
this perspective we performed several experiments and comparative analysis on
large volumes of online discourse from Reddit. In quantitative experiments, we
found that discourse was difficult to predict, especially as the conversation
carried on. We also developed an interactive tool to visually inspect
_conversation trails_ over the entity graph; although they were difficult to
predict, we found that conversations, in general, tended to diverge to a vast
swath of topics initially, but then tended to converge to simple and popular
concepts as the conversation progressed. An application of the spreading
activation function from the field of cognitive psychology also provided
compelling visual narratives from the data.

##  1 Introduction

In any conversation, members continuously track the topics and concepts that
are being discussed. The colloquialism “train-of-thought” is often used to
describe the path that a discussion takes, where a conversation may “derail,”
or “come-full-circle,” etc. An interesting untapped perspective of these ideas
exists within the realm of the Web and Social Media, where a train-of-thought
could be analogous to a trail over a graph of concepts. With this perspective,
an individual’s ideas as expressed through language can be mapped to explicit
entities or concepts, and, therefore, a single argument or train-of-thought
can be treated as a path over the graph of concepts. Within a group
discussion, the entities, concepts, arguments, and stories can be expressed as
a set of distinct paths over a shared concept space, what we call an entity
graph.

Scholars have long studied discourse and the flow of narrative in group
conversations, especially in relation to debates around social media [32] and
intelligence [29]. The study of language and discourse is rooted in psychology
[7] and consciousness [6].

Indeed, the linguist Wallace Chafe considered “…conversation as a way separate
minds are connected into networks of other minds.” [7] Looking at online
conversations from this angle, a natural hypothesis arises: If we think of
group discussion as a graph of interconnected ideas, then can we learn
patterns that are descriptive and predictive of the discussion?

Fortunately, recent developments in natural language processing, graph mining,
and the analysis of discourse now permit the algorithmic modelling of human
discussion in interesting ways by piecing them together. This is a broad goal,
but in the present work we provide a first step towards graph mining over
human discourse.

Another outcome of the digital age is that much of human discourse has shifted
to online social systems. Interpersonal communication is now observable at a
massive scale. Digital traces of emails, chat rooms, Twitter or other threaded
conversations that approximate in person communication are commonly available.
A newer form of digital group discussion can be seen in the dynamics of
Internet fora where individuals (usually strangers) discuss and debate a
myriad of issues.

Technology that can parse and extract information from these conversations
currently exists and operates with reasonable accuracy. From this large body
of work, the study of _entity linking_ has emerged as a way to ground
conversational statements to well-defined entities, such as those that
constitute knowledge bases and knowledge graphs [41]. Wikification, i.e.,
where entities in prose are linked to Wikipedia-entries as if it was written
for Wikipedia, is one example of entity linking [9]. The Information
Cartography project is another example that uses these NLP-tools to create
visualizations that help users understand how related news stories are
connected in a simple, yet meaningful manner [40, 39, 25]. But because entity
linking techniques have been typically trained from Wikipedia or long-form
Web-text, they have a difficult time accurately processing conversational
narratives, especially from social media [13]. Fortunately, recent progress in
_Social-NLP_ has made considerable strides in recent years [35] providing the
ability to extract grounded information from informal, threaded online
discourse [27].

Figure 1:  Illustration of an entity graph created from threaded conversations
from r/politics (blue-edges) and r/conservative (red-edges). The x-axis
represents the (threaded) depth at which each entity was mentioned within
conversations, extracted from Reddit, rooted at Joe_Biden. The y-axis
represents the semantic space of each entity, i.e., similar entities are
closer than dissimilar entities on the y-axis. Edge colors denote whether the
transition from one entity set to another occurs more often from one groups
conversations than another. Node colors represent equivalent entity sets along
the x-axis. In this visualization we observe a pattern of affective
polarization as comments coming from /r/Conservative are more likely to drive
the conversation towards topics related to the opposing political party.

Taking this perspective, the present work studies and explores the flow of
entities in online discourse through the lens of _entity graphs_. We focus our
attention on discussion threads from Reddit, but these techniques should
generalize to online discussions on similar platforms so long as the entity
linking system can accurately link the text to the correct entities. The
threaded conversations provide a clear indication of the reply-pattern, which
allows us to chart and visualize conversation-paths over entities.

To be clear, this perspective is the opposite of the conventional social
networks approach, where information and ideas traverse over user-nodes; on
the contrary, we consider discourse to be humans traversing over a graph of
entities. The conventional approach to social networks is important for areas
such as influence maximization [26] and the spread of behaviors [5]. Instead,
the goal of our alternative perspective is to discover this network of minds
and uncover patterns of how they think over topics. This alternative
perspective is motivated by the large number of influence campaigns [37],
information operations [44], and the effectiveness of disinformation [18].
These campaigns often operate by seeding conversations in order to exploit
conversation patterns and incite a particular group. Another motivation for
our proposed methodology is humans attraction towards homophily and the large
number of echo chambers that have been created online [10, 17]. Prior works
[17] looking at echo chambers in political discourse rely on this notion of
the ideas spreading between user-nodes. Other works looking at morality [4]
also follow this notion of how moral text spreads throughout a user network.
We stress here that our entity graph will allow for a flipped perspective of
having users move across the graph of entities in various types of
conversations. This position allows for a different form of analysis into how
different groups or communities think as a whole.

Our way of thinking is illustrated in Fig. 1, which shows a subset of path
traversals, which we describe in detail later, from thousands of conversations
in /r/politics and /r/conservative that start from the entity Joe_Biden. As a
brief preview, we find that conversations starting with Joe_Biden tend to lead
towards United_States in conversations from the /r/conservative subreddit
(indicated by a red edge), but commonly lead towards mentions of the
Republican_Party in conversations from /r/politics (indicated by blue-purple
edge). From there the conversations move onward to various other entities and
topics that are cropped from Fig 1 to maintain clarity.

In the present work, we describe how to create entity graphs and use them to
answer questions about the nature of online, threaded discourse. Specifically,
we ask three research questions:

  1. RQ1

How predictable is online discourse? Can we accurately determine where a
conversation will lead?

  2. RQ2

What do entity graphs of Reddit look like? In general, does online discourse
tend to splinter, narrow, or coalesce? Do conversations tend to deviate or
stay on topic?

  3. RQ3

Can cognitive-psychological theories on spreading activation be applied to
further illuminate and compare online discourse?

We find that entity graphs provide a detailed yet holistic illustration of
online discourse in aggregate that allow us to address our proposed research
questions. Conversations have an enormous, visually random, empirical
possibility space, but attention tends to coalesce towards a handful of common
topics as the depth increases. Prediction is difficult, and gets more
difficult the longer a conversation goes on. Finally, we show that entity
graphs present a particularly compelling tool by which to perform comparative
analysis. For example, we find, especially in recent years, that conservatives
and liberals both tend to focus their conversations on the out-group – a
notion known as _affective polarization_ [22]. We also find that users also
tend to stick to the enforced topics of a subreddit as shown by how r/news
tends towards entities from the United States and r/worldnews tends towards
non-US topics.

##  2 Methodology

###  2.1 Online Discourse Dataset

Of all the possible choices from which to collect online discourse, we find
that Reddit provides exactly the kind of data that can be used for this task.
It is freely and abundantly available [1], and it has a large number of users
and a variety of topics. Reddit has become a central source of data for many
different works [30]. For example, recent studies on the linguistic analysis
of Schizophrenia [48], hate speech [8], misogyny [15], and detecting
depression related posts [42] all make substantial use of Reddit data.

The threading system that is built into Reddit comment-pages is important for
our analysis. Each comment thread begins with a high level topic (the post
title), that is often viewed as the start of a conversation around a specific
topic. Users often respond to the post with their own comments. These can be
viewed as direct responses to the initial post, and then each of these
comments can have replies. This threading system generates a large tree
structure where the root is the post title. Of course, such a threading system
is only one possible realization of digital discussion, but this system
provides the ability to understand how conversations move as users respond to
each other in turn. Twitter, Facebook, and Youtube also have discussion
sections, but it is very difficult to untangle who is replying to whom in
these (mostly) unthreaded systems.

Reddit contains a large variety of subreddits, which are small communities
focused on a specific topic. We limit our analysis to only a small number of
them, but for each selection we obtain their complete comment history from
January 2017 to June 2021. In total we selected five subreddits: /r/news,
/r/worldnews, /r/Conservative, /r/Coronavirus and /r/politics. We selected
these subreddits because they are large and attract a lot of discussion
related to current events, albeit with their own perspectives and guidelines.
These subreddits also contain a large number of entities, which we plan to
extract and analyze.

Like most social sites, Reddit post-engagement follows the 90-9-1 rule of
Internet engagement. Simply put, most users don’t post or comment, and most
posts receive almost no attention [30]. Because of this we limit our data to
include only those threads that are in the top 20% in terms of number of
comments per post. Doing so ensures that we mostly collect larger discussions
threads that have an established back and forth. We also ignore posts from the
well-known bot accounts, (_e_.g., AutoMod, LocationBot) to ensure we get
actual user posts in the conversation.

###  2.2 Entity Linking

Figure 2: (Left) Example comment thread with the post title as the root, two
immediate child comments, one of which has two additional child comments.
Entity mentions are highlighted in yellow. (Right) The resulting entity tree
where each comment is replaced by their entity set. Note the case where the
mention-text Trump in the comment thread is represented by the standardized
entity-label Donald_Trump in the entity tree.

We use entity linking tools to extract the entities from each post title and
comment in the dataset (_c.f._ [41]). Entity linking tools seek to determine
parts of free form text that represent an entity (a mention) and then map that
mention to the appropriate entity-listing in a knowledge base
(disambiguation), such as Wikipedia. Existing models and algorithms rely
heavily on character matching between the mention-text and the entity label,
but more-recent models have employed deep representation learning to make this
task more robust [38].

An example of entity linking on a comment thread is illustrated in Fig. 2.
Each comment thread $T$ contains a post $R$ which serves as the root of the
tree $c_{r}\in T$ and comments $c_{x}\in T$, where subscript $r$ and $x$ serve
to index the post title and a specific comment. Each comment can reply to the
root $c\rightarrow r$ or to another comment $c_{x}\rightarrow c_{y}$ thereby
determining a comment’s depth $\ell\in[0,\ldots,L]$. Comments and post titles
may or may not contain one or more entities $S(c)$. These entity sets are
likewise threaded, such that $S(c_{x})\rightarrow S(c_{y})$ means that the
entities in $c_{x}$ were responded to with the entities in $c_{y}$, _i.e._ ,
$c_{x}$ is the parent of $c_{y}$. With this formalism, the entity linking task
transforms a comment threads into an _entity tree_ as seen in Fig. 2.

Specifically, we utilize the End-to-End (E2E) neural model created by
Kolitaskas et. al. [27] to perform entity linking on our selected subreddits.
Previous work has shown that entity linking on Reddit can be quite challenging
due to the wide variety of mentions used [3]. The E2E model we use has been
shown to have a high level of precision on Reddit but lacks a high recall [3].
We find using this model appropriate as we want to ensure that the entities we
find are correct and reliable, but acknowledge that it may miss a portion of
the less well-known entities, as well as missing any new entities that arise
from entity drift. The choice of this entity linker also influenced our
decision to analyze the selected subreddits as the performance is better in
these selected subreddits. We also experimented with the popular REL entity
linker [43]. Although it did retrieve many more entities from the comments, we
found a large number of the entities to be incorrect.

Table 1: Reddit discourse dataset. Top 20% of posts in terms of number of comments from five subreddits between January 2017 to June 2021. | # Posts | # Comments | Total Entities | Unique Entities
---|---|---|---|---
/r/news | 7,299 | 106,428 | 240,009 | 10,573
/r/worldnews | 16,056 | 263,227 | 692,735 | 12,840
/r/politics | 15,596 | 326,958 | 756,576 | 11,908
/r/Conservative | 3,093 | 41,439 | 100,756 | 4,308
/r/Coronavirus | 18,469 | 252,303 | 509,632 | 10,246

Using the E2E model we extract entities from each post title and comment
individually and construct the entity tree as illustrated in Fig 2. Table 1
shows a breakdown of the post, comment, and entity statistics for each
subreddit considered in the present work.

###  2.3 Entity Graph

Given an entity tree, our next task is to construct a model that can be used
to make predictions about the shape and future of the conversation, but also
can be used as a visual, exploratory tool. Although entity trees may provide a
good picture for a single conversation, we want to investigate patterns in a
broader manner. To do this we consider conversations coming from a large
number of entity trees in aggregate. This model takes the form of a weighted
directed graph $G=(V,E,w)$ where each vertex $v\in V$ is a tuple of an entity
set $S(c)$ and it’s associated depth $\ell$ in the comment tree
$v=(S(c),\ell)$. Each directed edge in the graph $e\in E$ connects two
vertices $e=(v_{1},v_{2})$ such that the depth , $\ell$ of $v_{1}$ must be one
less than the depth of $v_{2}$. Each edge in the graph $e\in E$ also contains
a weight $w:E\rightarrow\mathbb{R}$ that represents the frequency of the
transition from one entity set to another. This directed graph captures not
only the specific concepts and ideas mentioned within the discourse, but also
the conversational flow over those concepts.

Figure 3: Paths extracted from the entity tree in Fig. 2(b) represented by
directed edges over entity sets.

Continuing the example from above, Fig. 3 shows three individual paths $P$
representing the entity tree from Fig. 2(b). Each entity set moves from one
depth to the next, representing the progression of the discussion.

During the construction of the entity paths, we remove comments that do not
have any replies. Short paths, those with a length less than three, do not
offer much information in terms of how the conversation will progress, because
the conversation empirically did not progress. It may be useful to analyze why
some topics resulted in no follow-on correspondence, but we leave this as a
matter for future work.

Because we wish to explore online discourse in aggregate, this is the point
where we aggregate across many comment threads $T\in\mathcal{T}$ where
$\mathcal{T}$ represents an entire subreddit or an intentional mixture of
subreddits depending on the task. We extract all of the conversation paths
from our comment threads $\mathcal{T}$ to now have a group of conversation
paths $\mathcal{P}$. To generate our graph we iterate over our group of paths
$\mathcal{P}$ and aggregated them together to construct our entity graph. For
every instance of an entity set transition in a conversation path we increment
the weight $w$ of it’s respective edge in our entity graph. One key aspect of
this is that we count this transition only once per each comment thread $T$.
This ensures that entity transitions do not get over counted, by virtue of the
thread being larger and containing more conversation paths overall.

One of the limitations of the current graph structure is that the graph does
not capture conversation similarities if some of the entities overlap between
two different vertices. For instance, another entity tree may result in having
an entity set $S(c_{r})$ that contains a subset of the entities in a given
vertex. This new entity set may have a similar conversational flow but will
not be captured in our current entity graph because the model does not allow
for any entity overlap.

To help alleviate this issue we borrow from the notion of a hypergraph and
perform a star-expansion on our graph $G$ [47]. A hypergraph is defined as
$\mathcal{H}=(X,E)$ where $X$ is the set of vertices and $E$ is a set of non-
empty subsets of $X$ called hyperedges. The star expansion process turns a
hypergraph into a simple, bipartite graph. It works by generating a new vertex
in the graph for each hyperedge present in the hypergraph and then connects
each vertex to each new hyperedge-vertex. This generates a new graph $G(V,E)$
from $\mathcal{H}$ by introducing a new vertex and edge for each hyperedge
such that $V=\mathcal{E}\cup\mathcal{P}$.

While our model is a graph we can treat each entity set $S(c)$ as a hyperedge
in our case to perform this star expansion. This will give us new vertices to
represent each individual entity and allow us to capture transitions from one
entity set to another if they share a subset of entities. An example of the
resulting graph after performing a star-expansion can be seen in Fig. 4. This
helps to provide valid transition paths that would otherwise not exist without
the star expansion. When the star expansion operation is performed the edge
weights between the new individual entity vertices and their respective entity
sets is set to the number of times that entity set occurred at a given depth
$l$. Although the star expansion process will generate a much larger graph due
to the large number of vertices, it proves to be useful for prediction and
aligning entity set vertices in a visual space.

Figure 4: Entity graph constructed from a star-expansion of the entity tree in
Fig 2(b) and the conversation paths in Fig. 3(c) This model represents the
entities, their frequent combinations, and the paths frequently used in their
invocation.

This graph-model therefore represents the entities, their frequent
combinations, and the paths frequently used in their invocation over a set of
threaded conversations.

##  3 Conversation Prediction

Having generated these entity graphs we turn our attention to the three
research questions. RQ1 first asks if these entity graphs can be used to
predict where a conversation may lead. Clearly this is a difficult task, but
recent advances in deep learning and language models have led to major
improvements and interest in conversational AI [34], which has further lead to
the development of a number of models that utilize entities and knowledge
graphs [45] from various sources including Reddit [46]. The main motivation of
these tools is to use the topological structure of the knowledge graphs
(entities and their relationships) to improve a conversational agents’ ability
to more-naturally select the next entity in the conversation. The typical
methodology in related machine learning papers seeks to predict the next
entity in some conversation [31]. In these cases, a dataset of paths through a
knowledge graph is constructed from actual human conversations as well as one
or more AI models. Then a human annotator picks the entity that they feel is
most natural [31, 23].

Our methodology varies from these as we are not focused on making a machine
learning model to accurately predict these entities precisely. Our goal is to
demonstrate more broad patterns of people conversing over and through the
topics. To this end, we do not evaluate with a standard machine learning
paradigm aiming to optimize for metrics such as accuracy, precision, recall,
etc. To demonstrate that our entity graph captures broad patterns that can be
further explored we perform two tasks: (1) the generalization task and (2) a
similarity prediction task. Each task uses 5-fold cross validation where we
split the entity graph into 80/20 splits for $\mathcal{H}_{\textrm{train}}$
and $\mathcal{H}_{\textrm{test}}$ respectively. We perform this cross
validation in a disjoint manner with the Reddit threads that we have
extracted. This creates 5 different entity graphs, one for each split, and
validates the model’s generalization to unseen Reddit threads. Although this
disjoint split ensures the threads are separate, we do not consider the
temporal aspect of these threads.

$2$$4$$6$$8$$0.6$$0.8$$1$Conversation Depth ($\ell$)Percentage of Valid
Entities/r/news/r/worldnews/r/politics/r/coronavirus/r/conservative Figure 5:
Percent of the predictions made on the testing set that, on average, exist in
the training set for 5-folds. Higher is better.

The first task: generalization, gets at the heart of our broader question on
the predictability of conversation paths. In this task we simply calculate the
number of entity sets, at each level in $\mathcal{H}_{\textrm{test}}$ that
also appear in the same level in $\mathcal{H}_{\textrm{train}}$ of our entity
graph. Formally, we measure generalization as
$1-\frac{\|S_{\ell}\in\mathcal{H}_{\textrm{test}}\setminus
S_{\ell}\in\mathcal{H}_{\textrm{train}}\|}{\|S_{\ell}\in\mathcal{H}_{\textrm{test}}\|}$
for each $\ell$.

In simple terms, generalization tells us, given an unseen conversation
comment, if the model can make a prediction from the given comment by matching
at least one entity in our entity graph model. This task therefore validates
how well the model captures general conversation patterns by matching at the
entity level. Results of this analysis are shown in Fig. 5 where color and
shape combinations indicate the subreddit and $\ell$ is represented along the
x-axis. Error bars represent the 95% confidence interval of the mean across
the 5 folds. We find that the entity graph captures much more of the
information early in conversations. As the depth increases to three and
beyond, we note a sharp drop in the overlap between the test and training
sets. The widening confidence interval also indicates that the amount of
information varies based on the test set. From these results, we conclude that
analyzing the flow of an unseen conversation early-on is reasonable, but
findings from deeper in the conversation may be difficult because key entities
may be missing from the entity graph.

The second task: similarity prediction looks to measure the similarity between
a predicted entity set and the actual entity set. This methodology uses the
entity embeddings from the E2E entity linking model to represent the entities
in the vector space. For each root in $\mathcal{H}_{\textrm{test}}$ we find
its matching root in the $\mathcal{H}_{\textrm{train}}$; if a match does not
exist, we discard and start again. Then we make the Markovian assumption and
perform probabilistic prediction for each path in the training set via
$Pr(S_{\ell+1}(c_{y})|S_{\ell}(c_{x}))$, _i.e._ , the empirical probability of
a conversation moving to $S_{\ell+1}(c_{y})$ given the conversation is
currently at $S_{\ell}(c_{x})$ in $\mathcal{H}_{\textrm{train}}$. The
probability for each transition is based on the edge weights that we captured
during the graph construction step. As determined in the previous experiment,
entity sets are increasingly unlikely to match exactly as the depth increases;
so rather than a 0/1 loss, we measure the word movers distance (WMD) between
the predicted entities and the actual entities [28].

$0$$2$$4$$6$$8$$0$$2$$4$$6$Conversation Depth
($\ell$)WMD/r/news$0$$2$$4$$6$$8$Conversation Depth
($\ell$)/r/worldnews$0$$2$$4$$6$$8$Conversation Depth ($\ell$)/r/politics
Figure 6: Box plot of Word Movers Distance (WMD) as a function of the
conversation depth $\ell$. Lower is better. Box plots represent WMD-error of
entity representations predicted by the narrative hypergraph over all
entities, over all depth, over five folds.

Results for this comparison are shown in Fig. 6 for three of the larger
subreddits. We again find that as the depth of the conversation increases the
distance between our predicted tree and the ground truth entities rises. These
results indicate that as a conversation continues, the variety of topics
discussed tends to increase. Therefore, predictions are likely to not align
well very to those of the true conversation. This is most clearly seen in the
/r/politics plot in Fig. 6, where we note a sharp increase in the later parts
of the conversation. If the variety of topics was consistent, then we would
expect the WMD to stay relatively flat throughout the conversation depth.

##  4 Conversation Traversals

Next, we investigate RQ2 through a visualization of the entity graph. Recall
that the entity graph contains entity sets over the depths of the
conversation. Specifically, we seek to understand what conversations on Reddit
look like. Do they splinter, narrow, or behave in some other way? We call the
set of visual paths _conversation traversals_ because they indicate how users
traverse the entity graph.

We generate these visual conversation traversals using a slightly modified
force directed layout [16]. Graph layout algorithms operate like graph
embedding algorithms LINE, node2vec, etc, but rather than embedding graphs
into a high dimension space, visual graph layout tools embed nodes and edges
into a 2D space. In our setting we do make some restrictions to the algorithm
in order to force topics to coalesce into a visually meaningful and
standardized space. Specifically, we fix the position of each vertex in our
graph on the x-axis according to $\ell$. As in Fig. 4, individual entity
vertices always occur to the left of entity set vertices, making the
visualization illustrate how conversations flow from the start to finish in a
left to right fashion.

This restriction forces the embedding algorithm to adjust the position only on
the y-coordinate, and this is necessary to allow the individual entity to
entity set edges from the star-expansion to pull entity set vertices close
together if and only if they share many common entities. Loosely connected or
disconnected entities will therefore not be pulled together. As a result, the
y-axis tends to cluster entities and entity-sets together in a semantically
meaningful way.

Embedding algorithms are typically parameterized with a learning rate
parameter that determines how much change can happen to the learned
representation at each iteration. Because we want entities to be consistent
horizontally, we modify the learning rate function to increasingly dampen
embedding updates over 100 iterations per depth. For example, given a entity
graph of depth $L=10$, we would expect 1,000 iterations total. We initially
allow all entities and entity sets to update according to the default learning
rate, but as the iterations increase to 100 the learning rate of the entities
and entity sets at $\ell=1$ will slowly dampen and eventually lock into place
at iteration 100. When these entities and entity sets lock we also lock those
same entities and entity sets at all other depths. This ensures that each of
these entities and entity sets will be drawn as a horizontal line at the given
y position.

Then, from iterations 100-200, the learning rate of the entities and entity
sets at $\ell=2$ will slowly dampen and eventually lock into place at
iteration 200. Meanwhile the entities and entity sets at deep levels will
continue to be refined. In this way, the semantically meaningful y-coordinates
tend to propagate from left to right as the node embedding algorithm iterates.

One complication is that the sheer number of entities and the conversation
paths over the entities is too large to be meaningful to an observer. So we do
not draw the entity-nodes generated by the star-expansion and instead opt to
rewire entities sets based on the possible paths through the individual entity
nodes. We also tune the edge opacity based on the edge weights.

Figure 7: Entity graph showing the visual conversation traversals from
/r/news. This illustration shows the paths of conversations over entity sets.
The x-axis represents the depth of the conversation; entity sets are clustered
into a semantically meaningful space along the y-axis. Inset graph highlights
five example entity sets and their connecting conversation paths. Node colors
represent equivalent entity sets. In this example we highlight how entity sets
are placed in meaningful semantic positions in relation to one another.

We draw the resulting graph with D3 to provide an interactive visualization
[2].

Conversation traversals of the entity graph generated from /r/news is
illustrated in Fig. 7. This illustration is cropped to remove the four deepest
vertical axes (on the right) and is also cropped to show the middle half of
the illustration. A zoomed in version highlights some interesting entity sets
present in the /r/news conversation. Recall that the entity sets are
consistent horizontally so that both red circles on the left and the right of
the inset plot both indicate the entity set with Donald_Trump; likewise the
blue circles on the left and the right of the insert both represent
Barack_Obama. Edges moving visually left to right indicate topical paths found
in online discourse. In the /r/news subreddit, which tracks only US news,
Donald_Trump and Barack_Obama are frequent visits, but so too are national
entities like United_States (not highlighted), Iraq, and others. It is
difficult to see from this illustration, but the expanded interactive
visualization shows a common coalescing pattern where large sets of entities
and unique combinations of ideas typically coalesce into more simple singleton
entities like Barack_Obama or United_States.

Figure 8: Entity graph example of spreading activation on /r/news when
Barack_Obama is selected as the starting entity. The x-axis represents the
(threaded) depth at which each entity was mentioned within conversations
rooted at Barack_Obama. The y-axis represents the semantic space of each
entity, i.e., similar entities are closer than dissimilar entities on the
y-axis. Node colors represent equivalent entity sets. In this example, we
observe that conversations starting from Barack_Obama tend to center around
the United_States, political figures such as Donald_Tump, and discussion
around whether his religion is Islam.

###  4.1 Spreading Activation

Next, we adapt the illustration of conversation traversals to begin to answer
RQ3. Specifically, we are interested in how the differences in starting
points, at the roots of the comment tree, have any impact on the eventual
shape of the conversation. For example, given a conversation starting with
Donald_Trump how will the conversation take shape for liberals and how might
that conversation be different among conservatives? This kind of analysis
provides endless possibilities in the analysis of how different groups of
people think and articulate ideas a given topic.

To help answer this question, we employ tools from the study of _spreading
activation_ [11]. Spreading activation is a concept from cognitive psychology
that has been used to model how ideas spread and propagate in the brain from
an initial source. A popular use for spreading activation has been on semantic
networks to find the relatedness between different concepts. Formally,
spreading activation works by specifying two parameters: (1) a firing
threshold $F\in[0,\ldots,1]$ and (2) a decay factor $D\in[0,\ldots,1]$. The
vertex/entity set selected by a user will be given an initial activation
$A_{i}$ of 1. This is then propagated to each connected vertex as $A_{i}\times
w_{j}\times D$ where $w_{j}$ is the weight of each edge connection to the
corresponding vertex. Each vertex will then acquire its own activation value
$A_{i}$ based on the total amount of signal received from all incoming edges.
If a vertex has acquired enough activation to exceed the firing threshold $F$,
it too will fire further propagating forward through the graph. In the common
setting, vertices are only allowed to fire once and the spreading will end
once there is no more vertices to activate.

In our work we use spreading activation as a method for a user to select a
starting topic/entity set within the illustration of conversation traversals.
The spreading activation function will then propagate the activation of
entities along the conversation paths to highlight those that are mostly
likely to activate from a given starting point. Because we permit the entity
graph to be constructed (and labeled) from multiple subreddits, we can also
use the spreading activation function to compare and contrast how users from
different subreddits activate in response to a topic.

After spreading activation has been calculated, our interactive visualization
tool removes all vertices and links that are not part of the activated portion
of the graph. All of the vertices involved in spreading activation will have
their size scaled based on how much activation they received. An example of
this is cropped and illustrated in Fig. 8, which shows how spreading
activation occurs when the entity set Barack_Obama is activated within
/r/news. Here we see that conversations starting with (only) Barack_Obama tend
to move towards discussions about the United_States. We also note that the
Islam entity is semantically far away from Barack_Obama and Donald_Trump as
indicated its placement on the y-axis. The results from using spreading
activation allow for a much more granular investigation of conversational
flow. These granular levels of conversational flow demonstrate that an
individual can search for patterns related to influence campaigns, echo
chambers and other social media maladies across a number of topics.

##  5 Comparative Analysis

The visual conversation traversals appears to be helpful for investigating
trends within a group. But, our final goal is to use these to compare and
contrast how different groups move through the conversation space. Our first
attempt at this was to use and overlay separate plots and attempt to compare
the trends. This would be challenging though because it would fail to capture
the magnitude in any differences between the groups for various entity set
transitions. Our second attempt, instead, modified the entity graph creation
process to take in data from two different subreddits. By using both
communities we can capture how often an entity transition occurs in each
subreddit and use color gradients to indicate the relative strength of each
transition probability based on the edge weight we find in each subreddit.
This visually shows if correlations occur between subreddits. In the present
work, we examined three different scenarios among the subreddits in our
dataset.

#### Scenario 1: liberals and conservatives

Determining how motivated groups communicate about and respond to various
topics is of enormous importance in modern communication studies. For example,
communication specialists and political scientists are interested in
understanding how users respond to coordinated influence campaigns that flood
social media channels with the same message [33]. Repetition is key for the
idea to stick, and we would expect then that these forms of messaging would
begin to appear in the entity graphs and possibly visually indicated in the
conversation traversals.

Although a full analysis of this difficult topic is not within the purvue of
the current work, we do perform a comparative analysis of /r/Conservative and
/r/politics as proxies for comparing conservative and liberal groups,
respectively. We pay particular attention to determining the particular topics
and entities that each group tends to go towards later (deeper) in the
conversation. Such a comparative analysis may be key to understanding how
coordinated influence campaigns orient the conversation of certain groups or
de-rail them.

The comparative illustration using spreading activation was used at the
beginning of the paper in Fig. 1 and is not re-illustrated in this section.
The illustration yields some interesting findings. While one might expect
/r/Conservative to discuss members or individuals related to the republican
party, we instead find that conversations tend to migrate toward mentions of
liberal politicians (_e.g._ , Joe_Biden) indicated by red lines in Fig. 1. The
reverse holds true as well: mentions of Joe_Biden leads towards mentions of
the Republican_Party by the liberal group, as indicated by the blue line
connecting the two. A brief inspection of the underlying comments reveals that
users in each subreddit tend to talk in a negative manner towards the other
party’s politicians. This is a clear example of affective polarization [22]
being captured by our visualization tool. Affective polarization is where
individuals organize around principles of dislike and distrust towards the
out-group (the other political party) even moreso than trust in their in-
group.

Another finding we observe is the more pronounced usage of the United_States
by conservatives than liberals. This observation could be explained by the
finding that conservatives show a much larger degree of overt patriotism than
liberal individuals [20], which has more recently lead to a renewed interest
in populism and nationalism [12].

#### Scenario 2: US news and Worldnews

In our second scenario, we compare the conversations from /r/news (red) and
/r/worldnews (blue), which are geared towards US-only news and non-US news
respectively.

The comparison between these subreddits reveals unsurprising findings. A much
larger portion of the entity sets come from /r/worldnews as they discuss a
much broader range of topics. Many of the entity transitions that are
dominated by /r/worldnews come from discussions of other countries, events,
and people outside of the United States. The aspects that are shown to come
primarily from /r/news are topics surrounding the United States, China, and
major political figures from the United States. An example of this can be seen
in Fig. 9 which illustrates spreading activation starting from White_House.
Here, the dominating red lines, which reflects transitions from within
conversations on /r/news, converge to United_States, even after topics like
Russia or Islam are discussed. An interesting side note is that many of the
unlabeled entities entering the conversation via blue lines (/r/worldnews) in
$\ell=5$ and $\ell=6$ represent other countries such as Canada, Japan, Mexico,
and Germany. The findings from this comparative analysis do not show any
extremely interesting results but, it does show that the entity graph is able
to capture what one would see as the assumed patterns to find from comparing
these two subreddits of interest.

Figure 9: Illustration of an entity graph created from threaded conversations
from /r/news (red-edges) and r/worldnews (blue-edges). The x-axis represents
the (threaded) depth at which each entity set was mentioned within
conversations rooted at White_House. The y-axis represents the semantic space
of each entity, i.e., similar entities are closer than dissimilar entity sets
on the y-axis. Nodes colors represent equivalent entity sets. Conversations in
/r/news tends to coalesce to United_States, while conversations in
/r/worldnews tend to scatter into various other countries (unlabeled black
nodes connected by thin blue lines)

#### Scenario 3: COVID and Vaccines

Our final analysis focuses on comparing a single subreddit, /r/Coronavirus,
but during two different time periods. There is a large amount of work that
has been done analyzing Covid online looking at partisanship [36], user
reaction to misinformation [24], and differences in geographic concerns [19].
The first segment (highlighted in red) comes from the period of January
through June in 2020, which was during the emergence of the novel Coronavirus.
Although the /r/Coronavirus subreddit had existed for many years prior, it
became extremely active during this time. The second segment was from the
following year January - June 2021. This time period corresponded to the
development, approval and early adoption of vaccines.

Our analysis of this visualization yielded some interesting findings related
to the coronavirus pandemic that we illustrate in Fig. 10. If we begin
spreading activation from the perspective of United_States we find that most
of the discussion leads to China and Italy in 2020, which appears reasonable
because of China and Italy’s early struggles with virus outbreaks. In
comparison, the 2021 data appeared more likely to mention Sweden, India, and
Germany, which had severe outbreaks during those months. Our findings from
spreading activation allow us to capture the shifting changes in countries of
interest from 2020 to 2021 as the pandemic progressed.

Figure 10: Comparison between the first 6 months of /r/Coronavirus from 2020
to 2021. Illustration of an entity graph created from threaded conversations
from /r/Coronavirus in Jan–June of 2020 (red-edges) and from Jan–June of 2021
(blue-edges). The x-axis represents the (threaded) depth at which each entity
set was mentioned within conversations rooted at United_States. The y-axis
represents the semantic space of each entity set, i.e., similar entity sets
are closer than dissimilar entity sets on the y-axis. Node colors represent
equivalent entity sets. Conversations tended to focus on China and Italy early
in the pandemic, but turn towards a broader topic space later in the pandemic.

##  6 Discussion

In the current work we presented a new perspective by which to view and think
about online discourse. Rather than taking the traditional social networks
view where information flows over the human participants, our view is to
consider human conversations as stepping over a graph of concepts and
entities. We call these discourse maps _entity graphs_ and we show that they
present a fundamentally different view of online human communication.

Taking this perspective we set out to answer three research questions about
(1) discourse prediction, (2) illustration, and (3) behavior comparisons
between groups. We found that discourse remains difficult to predict, and this
prediction gets harder the deeper into the conversation we attempt
predictions. We demonstrate that the visual conversation traversals provide a
view of group discourse, and we find that online discourse tends to coalesce
into narrow, simple topics as the conversation deepens – although those topics
could be wildly different from starting topic. Finally, we show that the
spreading activation function is able to focus the visualization to provide a
comparative analysis of competing group dynamics.

###  6.1 Limitations

While the work in its current state is helpful for better understanding
conversations, it is not without its limitations. Foremost, in the present
work we only considered conversations on Reddit. Another limitation is that
the entity linking method we chose is geared towards high-precision at the
cost of low-recall. This means that we can be confident that the entities
extracted in the conversations are mostly correct, but we have missed some
portion of entities. The recall limitation does inhibit the total number of
entities we were able to collect; a better system would provide for better
insights in our downstream analysis. This issue can also be highlighted with
the long tail distribution of entities and the challenges this poses to
current methods [21]. An entity linking model that focuses on recall may still
result in useful graphs as prior works have found that many of the entities
are considered “close enough” even when they are not a perfect match to ground
truth data [14]. Using a different entity linking model could lead to
different patterns extracted from our method. For a model that optimizes for
higher recall it could create a much larger entity graph, though it would
likely contain a fair amount of noise due to the precision-recall trade off.

Another limitation inherent to the present work is the consideration of
conversations as threaded trees. This is an imperfect representation of
natural, in-person conversation, and still different from unthreaded
conversations like those found on Twitter and Facebook, which may require a
vastly different entity graph construction method. Finally, the interactive
visualization tool is limited in its ability to process enormous amounts of
conversation data because of its reliance on JavaScript libraries and
interactive browser rendering.

###  6.2 Future Work

These limitations leave open avenues for further exploration in future work.
Our immediate goals are to use the entity graphs to better understand how
narratives are crafted and shaped across communities. Improvements in the
entity linking process and addition of concept vertices, pronoun anaphora
resolution, threaded information extraction and other advances in SocialNLP
will serve to improve the technology substantially. We also plan to ingest
other threaded conversational domains such as Hackernews, 4chan, and even
anonymized email data. Extensions of this work could also include capturing
more information between entity transitions such as the sentiment overlayed on
a given entity or group of entities. This extra information could allow us to
create entity graphs that not only show the transition but also how various
groups speak and feel about those specific entities.

##  7 Acknowledgements

The authors would like to thank Yifan Ding and Justus Hibshman for their
feedback on the paper. This work is supported in part by the Defense Advanced
Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract
No. W911NF-21-C-0002.

## References

  * [1] Baumgartner, J., Zannettou, S., Keegan, B., Squire, M., and Blackburn, J. The pushshift reddit dataset.  Proceedings of the international AAAI conference on web and social media, 2020.
  * [2] Bostock, M., Ogievetsky, V., and Heer, J. D3 data-driven documents.  IEEE transactions on visualization and computer graphics 17, 12 (2011), 2301–2309.
  * [3] Botzer, N., Ding, Y., and Weninger, T. Reddit entity linking dataset.  Information Processing & Management 58, 3 (2021), 102479.
  * [4] Brady, W. J., Crockett, M. J., and Van Bavel, J. J. The mad model of moral contagion: The role of motivation, attention, and design in the spread of moralized content online.  Perspectives on Psychological Science 15, 4 (2020), 978–1010.
  * [5] Centola, D. The spread of behavior in an online social network experiment.  science 329, 5996 (2010), 1194–1197.
  * [6] Chafe, W. Discourse, consciousness, and time: The flow and displacement of conscious experience in speaking and writing.  University of Chicago Press, 1994.
  * [7] Chafe, W. Language and the flow of thought.  The new psychology of language (2017), 93–111.
  * [8] Chandrasekharan, E., Pavalanathan, U., Srinivasan, A., Glynn, A., Eisenstein, J., and Gilbert, E. You can’t stay here: The efficacy of reddit’s 2015 ban examined through hate speech.  Proceedings of the ACM on Human-Computer Interaction 1, CSCW (2017), 1–22.
  * [9] Cheng, X., and Roth, D. Relational inference for wikification.  Empirical Methods in Natural Language Processing, 2013.
  * [10] Cinelli, M., De Francisci Morales, G., Galeazzi, A., Quattrociocchi, W., and Starnini, M. The echo chamber effect on social media.  Proceedings of the National Academy of Sciences 118, 9 (2021), e2023301118.
  * [11] Collins, A. M., and Loftus, E. F. A spreading-activation theory of semantic processing.  Psychological review 82, 6 (1975), 407.
  * [12] De Cleen, B. Populism and nationalism.  The Oxford handbook of populism 1 (2017), 342–262.
  * [13] Derczynski, L., Maynard, D., Rizzo, G., Van Erp, M., Gorrell, G., Troncy, R., Petrak, J., and Bontcheva, K. Analysis of named entity recognition and linking for tweets.  Information Processing & Management 51, 2 (2015), 32–49.
  * [14] Ding, Y., Botzer, N., and Weninger, T. Posthoc verification and the fallibility of the ground truth.  arXiv preprint arXiv:2106.07353 (2021).
  * [15] Farrell, T., Fernandez, M., Novotny, J., and Alani, H. Exploring misogyny across the manosphere in reddit.  Proceedings of the 10th ACM Conference on Web Science, 2019.
  * [16] Fruchterman, T. M., and Reingold, E. M. Graph drawing by force-directed placement.  Software: Practice and experience 21, 11 (1991), 1129–1164.
  * [17] Garimella, K., De Francisci Morales, G., Gionis, A., and Mathioudakis, M. Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship, 2018.
  * [18] Glenski, M., Ayton, E., Mendoza, J., and Volkova, S. Multilingual multimodal digital deception detection and disinformation spread across social platforms.  arXiv preprint arXiv:1909.05838 (2019).
  * [19] Guntuku, S. C., Buttenheim, A. M., Sherman, G., and Merchant, R. M. Twitter discourse reveals geographical and temporal variation in concerns about covid-19 vaccines in the united states.  Vaccine 39, 30 (2021), 4034–4038.
  * [20] Huddy, L., and Khatib, N. American patriotism, national identity, and political involvement.  American journal of political science 51, 1 (2007), 63–77.
  * [21] Ilievski, F., Vossen, P., and Schlobach, S. Systematic study of long tail phenomena in entity linking.  Proceedings of the 27th International Conference on Computational Linguistics, 2018.
  * [22] Iyengar, S., Lelkes, Y., Levendusky, M., Malhotra, N., and Westwood, S. J. The origins and consequences of affective polarization in the united states.  Annual Review of Political Science 22 (2019), 129–146.
  * [23] Jung, J., Son, B., and Lyu, S. Attnio: Knowledge graph exploration with in-and-out attention flow for knowledge-grounded dialogue.  Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
  * [24] Kalantari, N., Liao, D., and Motti, V. G. Characterizing the online discourse in twitter: Users’ reaction to misinformation around covid-19 in twitter, 2021.
  * [25] Keith Norambuena, B. F., and Mitra, T. Narrative maps: An algorithmic approach to represent and extract information narratives.  Proceedings of the ACM on Human-Computer Interaction 4, CSCW3 (2021), 1–33.
  * [26] Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through a social network.  Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003.
  * [27] Kolitsas, N., Ganea, O.-E., and Hofmann, T. End-to-end neural entity linking.  arXiv preprint arXiv:1808.07699 (2018).
  * [28] Kusner, M., Sun, Y., Kolkin, N., and Weinberger, K. From word embeddings to document distances.  International conference on machine learning, 2015.
  * [29] Mateas, M., and Sengers, P. Narrative intelligence.  J. Benjamins Pub., 2003.
  * [30] Medvedev, A. N., Lambiotte, R., and Delvenne, J.-C. The anatomy of reddit: An overview of academic research.  Dynamics on and of Complex Networks, 2017.
  * [31] Moon, S., Shah, P., Kumar, A., and Subba, R. Opendialkg: Explainable conversational reasoning with attention-based walks over knowledge graphs.  Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
  * [32] Page, R. The narrative dimensions of social media storytelling.  The handbook of narrative analysis (2015), 329–347.
  * [33] Paul, C., and Matthews, M. The russian “firehose of falsehood” propaganda model.  Rand Corporation 2, 7 (2016), 1–10.
  * [34] Ram, A., Prasad, R., Khatri, C., Venkatesh, A., Gabriel, R., Liu, Q., Nunn, J., Hedayatnia, B., Cheng, M., Nagar, A., et al. Conversational ai: The science behind the alexa prize.  arXiv preprint arXiv:1801.03604 (2018).
  * [35] Ran, C., Shen, W., and Wang, J. An attention factor graph model for tweet entity linking.  Proceedings of the 2018 World Wide Web Conference, 2018.
  * [36] Rao, A., Morstatter, F., Hu, M., Chen, E., Burghardt, K., Ferrara, E., Lerman, K., et al. Political partisanship and antiscience attitudes in online discussions about covid-19: Twitter content analysis.  Journal of medical Internet research 23, 6 (2021), e26692.
  * [37] Schia, N. N., and Gjesvik, L. Hacking democracy: managing influence campaigns and disinformation in the digital age.  Journal of Cyber Policy 5, 3 (2020), 413–428.
  * [38] Sevgili, O., Shelmanov, A., Arkhipov, M., Panchenko, A., and Biemann, C. Neural entity linking: A survey of models based on deep learning.  arXiv preprint arXiv:2006.00575 (2020).
  * [39] Shahaf, D., and Guestrin, C. Connecting the dots between news articles.  Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010.
  * [40] Shahaf, D., Yang, J., Suen, C., Jacobs, J., Wang, H., and Leskovec, J. Information cartography: creating zoomable, large-scale maps of information.  Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, 2013.
  * [41] Shen, W., Wang, J., and Han, J. Entity linking with a knowledge base: Issues, techniques, and solutions.  IEEE Transactions on Knowledge and Data Engineering 27, 2 (2014), 443–460.
  * [42] Tadesse, M. M., Lin, H., Xu, B., and Yang, L. Detection of depression-related posts in reddit social media forum.  IEEE Access 7 (2019), 44883–44893.
  * [43] van Hulst, J. M., Hasibi, F., Dercksen, K., Balog, K., and de Vries, A. P. Rel: An entity linker standing on the shoulders of giants, 2020.
  * [44] Weedon, J., Nuland, W., and Stamos, A. Information operations and facebook.  Retrieved from Facebook: https://fbnewsroomus. files. wordpress. com/2017/04/facebook-and-information-operations-v1. pdf (2017).
  * [45] Yu, W., Zhu, C., Li, Z., Hu, Z., Wang, Q., Ji, H., and Jiang, M. A survey of knowledge-enhanced text generation.  arXiv preprint arXiv:2010.04389 (2020).
  * [46] Zhang, H., Liu, Z., Xiong, C., and Liu, Z. Grounded conversation generation as guided traverses in commonsense knowledge graphs.  arXiv preprint arXiv:1911.02707 (2019).
  * [47] Zien, J. Y., Schlag, M. D., and Chan, P. K. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes.  IEEE Transactions on computer-aided design of integrated circuits and systems 18, 9 (1999), 1389–1399.
  * [48] Zomick, J., Levitan, S. I., and Serper, M. Linguistic analysis of schizophrenia in reddit posts.  Proceedings of the Sixth Workshop on Computational Linguistics and Clinical Psychology, 2019.