# Reproducing the $UVJ$ Color Distribution of Star-forming Galaxies at
$0.5<z<2.5$
with a Geometric Model of Dust Attenuation

Leah D. Zuckerman Center for Astrophysics $|$ Harvard & Smithsonian, 60 Garden
St., Cambridge, MA 02138, USA  Brown University, Providence, RI 02912, USA
Sirio Belli  Center for Astrophysics $|$ Harvard & Smithsonian, 60 Garden St.,
Cambridge, MA 02138, USA  Joel Leja Department of Astronomy & Astrophysics,
The Pennsylvania State University, University Park, PA 16802, USA  Institute
for Computational & Data Sciences, The Pennsylvania State University,
University Park, PA, USA  Institute for Gravitation and the Cosmos, The
Pennsylvania State University, University Park, PA 16802, USA  Sandro
Tacchella  Center for Astrophysics $|$ Harvard & Smithsonian, 60 Garden St.,
Cambridge, MA 02138, USA  Department of Physics, Ulsan National Institute of
Science and Technology (UNIST), Ulsan 44919, Republic of Korea

###### Abstract

We analyze the distribution of rest-frame $U-V$ and $V-J$ colors for star-
forming galaxies at $0.5<z<2.5$. Using stellar population synthesis,
stochastic star formation histories, and a simple prescription for the dust
attenuation that accounts for the shape and inclination of galaxies, we
construct a model for the distribution of galaxy colors. With only two free
parameters, this model is able to reproduce the observed galaxy colors as a
function of redshift and stellar mass remarkably well. Our analysis suggests
that the wide range of dust attenuation values measured for star-forming
galaxies at a given redshift and stellar mass is almost entirely due to the
effect of inclination; if all galaxies at a given stellar mass were observed
edge-on, they would show very similar dust attenuation. This result has
important implications for the interpretation of dust attenuation
measurements, the treatment of UV and IR luminosity, and the comparison
between numerical simulations and observations.

High-redshift galaxies, Galaxy evolution, Galaxy colors, Two-color diagrams,
Extinction

##  1 Introduction

Much of our knowledge about the physical properties of distant galaxies
derives from fitting models to multi-band photometric observations (Conroy,
2013, and references therein). By combining high-quality panchromatic
photometry with modern fitting techniques it is now possible to study
individual galaxies in great detail, and constrain realistic physical models
with a large number of free parameters (e.g., Johnson et al., 2021).

A complementary approach is to consider a small number of filters or colors
and study their _distribution_ for a galaxy population. This is typically done
using color-color diagrams; among these, the most popular one is the $UVJ$
diagram, i.e. rest-frame $U-V$ versus $V-J$ (Wuyts et al., 2007; Williams et
al., 2009). The combination of these two colors is able to break the
degeneracy between age and dust reddening, and is therefore particularly
effective at separating quiescent and star-forming galaxies. However, the
$UVJ$ diagram has been used for more than merely grouping galaxies into two
categories. For example, $UVJ$ colors have been used to infer the star
formation rate and dust attenuation for star-forming systems (Fang et al.,
2018), and the stellar ages for quiescent systems (Belli et al., 2019). This
is possible because galaxies follow scaling relations, so that their
properties are tightly correlated and span only a small region of the
available parameter space. In other words, the $UVJ$ diagram reveals more
about the physical properties than what can be gathered by the analysis of the
$U-V$ and the $V-J$ colors alone (Leja et al., 2019).

The regularity observed in the distribution of UVJ galaxy colors, however, is
still poorly understood. For example, the most advanced simulations of galaxy
formation still struggle to reproduce the observed color distribution of star-
forming galaxies (e.g., Donnari et al., 2019; Akins et al., 2021). The goal of
the present work is to develop a simple, empirical model that is able to
reproduce the observed distribution of star-forming galaxies on the $UVJ$
diagram as a function of redshift and stellar mass.

##  2 Data

We use the 3D-HST catalog (Brammer et al., 2012; Skelton et al., 2014;
Momcheva et al., 2016) of galaxies detected in _Hubble Space Telescope_ (HST)
imaging from the five fields of the CANDELS survey (Grogin et al., 2011;
Koekemoer et al., 2011). We select galaxies with redshift (obtained by a joint
fit to grism spectroscopy and photometry) in the range $0.5<z<2.5$ and with
stellar mass (derived from a fit to the photometry) in the range
$9.5<\log(M_{\ast}/M_{\odot})<11$. This selection yields a sample of 19553
galaxies that is more than 90% complete (Tal et al., 2014). We then remove
galaxies with bad photometry (via the use_phot flag provided in the catalog),
bad fit ($\chi^{2}>5$), or a bad measurement of the axis ratio $q$ in the van
der Wel et al. (2014) catalog. This leaves us with a final sample of 15073
galaxies.

For these galaxies we retrieve the rest-frame $U-V$ and $V-J$ colors from the
3D-HST catalog, which are derived from the observed photometry using the EAZY
code (Brammer et al., 2008). We show the distribution of the sample on the
$UVJ$ diagram in Figure 1, split into three stellar mass bins and four
redshift bins, and color-coded by axis ratio. The black line shows the
definition of the quiescent box: $U-V>1.3$ and $U-V>0.88(V-J)+0.59$ (Muzzin et
al., 2013; Belli et al., 2019). We use these criteria to select the star-
forming population, which lies below the black line.

##  3 Model

In order to understand the distribution of galaxies on the $UVJ$ diagram we
develop a simple Monte Carlo simulation (described below) which includes
stochastic star formation histories (SFHs), stellar population synthesis, and
a geometric model for the effect of dust attenuation.

###  3.1 Star Formation Histories

We adopt the stochastic model of Caplar & Tacchella (2019) to generate SFHs
that are realistic but require minimal physical assumptions. In this model,
galaxies are assumed to fluctuate about the star-forming main sequence, which
describes the typical star formation rate as a function of stellar mass
(Noeske et al., 2007). Since we are interested only in galaxy colors and not
in the absolute fluxes, the normalization of the main sequence does not matter
and we assume that the typical star formation rate for all galaxies, at all
redshifts, is $1~{}\mathrm{M}_{\odot}~{}\mathrm{yr}^{-1}$.

This approach neglects the fact that the normalization of the main sequence
declines with cosmic time. As we explain below, this assumption should not
have a strong effect on the distribution of synthetic colors. Other work
supports this model, for example Iyer et al. (2020) find that at fixed stellar
mass, galaxies in the IllustrisTNG simulation have roughly a constant star
formation rate (except at high stellar masses where the effect of quenching,
which we do not consider in this work, is important).

In the Caplar & Tacchella (2019) model, a stochastic SFH is fully
characterized by the power spectrum density (i.e., the power as a function of
frequency) of its fluctuations around the main sequence. The power spectrum
density is assumed to be constant on timescales longer than a break timescale
$\tau_{\rm x}$, below which the power spectrum follows a power law with
exponent $\alpha=-2$, corresponding to a damped random walk. Tacchella et al.
(2020) show that this power spectrum density can be obtained by solving the
gas regulator model (Lilly et al., 2013) when the gas accretion is a white
noise process. Moreover, a broken power law with a break timescale of
approximately 1 Gyr is consistent with the results of numerical simulations
(Iyer et al., 2020). For this reason we adopt a fixed value of $\tau_{x}$ = 1
Gyr.

We begin the Monte Carlo simulation by generating 100 stochastic SFHs with a
time sampling of 1 Myr and a duration equal to the current age of the
universe. This library of SFHs constitutes the core of our model.

Figure 1: Rest-frame $U-V$ versus $V-J$ colors for galaxies in the CANDELS
fields, split into mass and redshift bins. Galaxies are color-coded according
to their axis ratio. The blue line in the first panel is a single dust-free
synthetic galaxy track; the red distribution is the histogram of many
individual tracks like this one. The black arrow in the bottom left panel
represents the color shift due to an attenuation $A_{V}$ of one magnitude,
assuming the Calzetti et al. (2000) law.

###  3.2 Stellar Population Synthesis

To produce synthetic galaxy colors we rely on the Flexible Stellar Population
Synthesis (FSPS) library (Conroy et al., 2009; Conroy & Gunn, 2010). We assume
a Kroupa (2001) initial mass function, zero dust attenuation, and we include
nebular emission as described in Byler et al. (2017). Then we calculate the
synthetic photometry in the rest-frame Johnson $U$, Johnson $V$, and 2MASS $J$
filters (the same ones used for the observed galaxies) at each time step of
our stochastic SFHs. The blue line in the first panel of Figure 1 shows an
example of synthetic evolutionary track obtained in this way. The track
features a high degree of variability, reflecting the fact that the SFH is, by
construction, a stochastic process. The model galaxy reaches the bluest colors
when experiencing a peak in star formation rate, while in times of relative
quiescence its colors become redder.

Observations of galaxies, however, are unable to constrain the track of
individual systems across cosmic time, but can only measure the color
distribution for a galaxy population. We therefore build a synthetic
population of galaxies by drawing 10 different random values of stellar
metallicity (which has a smaller effect on the colors compared to the SFH),
uniformly distributed over $-0.5<\log Z/Z_{\odot}<0.2$, for each of the 100
stochastic SFHs. This gives a sample of 1000 synthetic galaxy tracks, each of
which includes hundreds of points on the $UVJ$ diagram. The resulting two-
dimensional distribution is shown in red in Figure 1. In each bin we only
consider ages between zero and the age of the universe at that redshift. The
model distributions are quite similar at all redshifts despite the substantial
difference in the maximum stellar age considered. This is not surprising,
since the photometry of star-forming galaxies is mainly driven by the younger,
more luminous stars, and is not very sensitive to the past history. It is
likely, then, that the simplifying assumption of a non-evolving main sequence
has a negligible effect on our conclusions.

Figure 2: Illustration of our geometric model of dust attenuation for two
examples: a thin disk with $D=0.2$ (top row) and a thick disk with $D=0.8$
(bottom row); in both cases $A_{\textrm{Vmax}}=2$. _Left:_ dust attenuation as
a function of the inclination angle. _Center:_ distribution of dust
attenuation for an ensemble of galaxies with random inclinations. _Right:_
variation of the $UVJ$ colors as a function of inclination angle; where the 2D
representations of galaxies have inclination angles of 10∘ and 90∘.

###  3.3 Dust Attenuation

The synthetic distributions in Figure 1 clearly do not provide a good fit to
the data, and this is because the effect of dust reddening has so far been
neglected. We illustrate the expected color shift caused by an attenuation of
one magnitude in the $V$ band ($A_{V}=1$) in the bottom left panel of Figure
1. The exact direction of this dust arrow depends on the dust attenuation law;
we assume the widely used Calzetti et al. (2000) law. This attenuation law
appears to produce a color shift along the direction connecting the synthetic
colors to the observed ones. For this reason, and to keep the model as simple
as possible, we assume the Calzetti law for all the synthetic galaxies, even
though in principle some variation between galaxies is expected (Salim &
Narayanan, 2020).

Dust attenuation is clearly fundamental in shifting galaxies along the
diagonal direction of the $UVJ$ diagram. However, Figure 1 also shows a strong
trend of the observed axis ratio along the diagonal direction. In particular,
among star-forming galaxies those that are found at the reddest edge of the
UVJ distribution are mostly edge-on, a fact first noticed by Patel et al.
(2012).This suggests that the dust attenuation in each galaxy strongly depends
on the geometry of the system, consistent with previous work (e.g., Giovanelli
et al., 1995).

Several studies have sought to determine the effect of inclination in a
variety of ways, for example using the thickness of the Tully-Fisher relation
(e.g., Verheijen, 2001), galaxy SED fitting (e.g., Kauffmann et al., 2003), or
by examining how the color of individual galaxies change as a function of
inclination (e.g., Maller et al., 2009). Instead, in this work we choose to
capture this correlation with a simple geometric model in which each galaxy is
represented by an oblate spheroid with half-radii $a$, $b$, $c$ with $a=b>c$,
and where $D=c/a$ is the galaxy thickness. We define the inclination angle
$\theta$ so that a fully face-on galaxy has $\theta=0^{\circ}$ and a fully
edge-on galaxy has $\theta=90^{\circ}$. We then make the assumption that the
dust is uniformly distributed in the galaxy, so that the optical depth as a
function of inclination can be calculated from the geometry of the model:
$\tau(\theta)\propto a\,(\sin^{2}\theta+D^{-2}\cos^{2}\theta)^{-1/2}$. By
assuming that the attenuation $A_{\mathrm{V}}$ is proportional to the optical
depth along the line-of-sight (and therefore neglecting the emission from
stars that are mixed with the dust), we obtain the following relation:

$A_{\mathrm{V}}(\theta)=\frac{A_{\textrm{Vmax}}}{\sqrt{\sin^{2}\theta+D^{-2}\cos^{2}\theta}}\;,$
(1)

where $A_{\textrm{Vmax}}$ is the attenuation when the galaxy is viewed edge-
on.

To illustrate the effect of galaxy geometry on the dust attenuation, in Figure
2 we show the results of our model for a thin disk ($D=0.2$, top row) and for
a thick disk ($D=0.8$, bottom row), assuming $A_{\textrm{Vmax}}=2$. The first
column illustrates the relation between $A_{\mathrm{V}}$ and inclination given
in Equation 1. As expected, the inclination effect is strong for thin galaxies
and less important for thicker galaxies; in the limit of a spherical galaxy
($D=1$) there would be no difference between face-on and edge-on attenuation.
The central panels show the expected distribution of dust attenuation for an
ensemble of identical galaxies observed from random lines of sight. Thin
galaxies feature a peak around the minimum value of attenuation (which, in our
model, is given by $A_{\mathrm{V}}=D\cdot A_{\textrm{Vmax}}$), while thick
galaxies experience a substantially smaller dynamic range in attenuation.
Finally, the panels on the right show the effect of dust attenuation on the
$UVJ$ colors. We conclude that, in this simple model, the galaxy shape (i.e.
the thickness parameter $D$) and the dust content (parameterized with
$A_{\textrm{Vmax}}$) play a fundamental role in determining the distribution
of a galaxy population on the $UVJ$ diagram.

Our geometric model of dust attenuation is substantially more flexible than
the often-used slab model (where $\tau\propto 1/\cos\theta$), while at the
same time being conceptually simpler and requiring less assumptions than some
of the more advanced models (e.g., Chevallard et al., 2013). The key feature
of our approach is the presence of a free parameter describing the galaxy
thickness; see Padilla & Strauss (2008) for a similar approach.

Figure 3: Best-fit models (red) and observed galaxies (blue; only star-forming
systems are shown) on the $UVJ$ diagram. The best-fit values of the two model
parameters, $A_{\textrm{Vmax}}$ and $\sigma_{\mathrm{max}}$, are listed in
each bin.

##  4 Results

###  4.1 Monte Carlo Modeling of Galaxy Populations

Central to our analysis is the application of the geometric model to the
synthetic $UVJ$ colors: this requires the parameters $\theta$, $D$, and
$A_{\textrm{Vmax}}$ for each synthetic track. Since galaxies are randomly
oriented in space, we draw the inclination $\theta$ from a random distribution
uniform in $\cos\theta$. For the galaxy thickness $D$ we use the results of
van der Wel et al. (2014), who derived the intrinsic shape of star-forming
galaxies from the distribution of axis ratios measured for the 3D-HST sample.
They provide the mean and standard deviation for the distribution of $D$,
assumed to be Gaussian, in each redshift and stellar mass bin. We use these
distributions to draw a random value of $D$ for each synthetic track. Finally,
we assume that the $A_{\textrm{Vmax}}$ parameter of all the galaxies in a
given bin follows a Gaussian distribution with free mean and dispersion
values, which represent the only two free parameters of our Monte Carlo model.

###  4.2 Model Fitting

For each bin in mass and redshift, we divide the $UVJ$ plane into $n$ cells
and calculate the observed probability distribution $p_{i}$ (where
$i=1,2,...,n$ is the cell index) representing the fraction of observed
galaxies that lie in each cell. Then we generate a grid of Monte Carlo models
by varying the two free parameters: $A_{\textrm{Vmax}}=$ 0, 0.3, 0.6, 0.9, 1,
1.5, 2, 2.5 and $\sigma_{\mathrm{max}}=$ 0.02, 0.06, 0.1, 0.15, 0.2, 0.3, 0.4,
0.5, 0.6, controlling respectively the mean and dispersion of the maximum
(i.e., edge-on) dust attenuation. At each point of the model grid we calculate
the model probability distribution
$q_{i}(A_{\textrm{Vmax}},\sigma_{\mathrm{max}})$ using the same $UVJ$ cells as
for the observations. We also include a small Gaussian scatter of width 0.1
magnitude that represents the typical observational uncertainty on the colors.
We then compare the data and the model using the K-L divergence (Kullback &
Leibler, 1951):

$D_{KL}(p_{i},q_{i})=\left\\{\begin{array}[]{ll}p_{i}\log(p_{i}/q_{i})&\quad\mathrm{if\
}p_{i}>0,\ q_{i}>0\\\ 0&\quad\mathrm{if\ }p_{i}=0,\ q_{i}>0\\\
\infty&\quad\mathrm{if\ }p_{i}>0,\ q_{i}=0\end{array}\right.$ (2)

The K-L divergence is infinity for cells where no model galaxies, but at least
one observed galaxy is present. In principle this eliminates models that are
clearly inconsistent with the data, but we need some flexibility to account
for systematic uncertainties (such as photometric redshift errors). We
therefore assign, in each model, a small probability to all $UVJ$ cells that
represents the rare possibility of substantial outliers. We can then calculate
the total K-L divergence between the data and a specific model by integrating
over all the $UVJ$ cells:

$D_{KL}=\sum_{i=1}^{n}D_{KL}(p_{i},q_{i})\;.$ (3)

For a large number of galaxies $N$, $D_{KL}=-1/N\log\mathcal{L}$, where
$\mathcal{L}$ is the likelihood of obtaining the data if the model is correct
(see, e.g., Shlens, 2014). Thus, the model that minimizes the K-L divergence
is also the model that maximizes the likelihood, and we call this the “best
fit”.

Figure 4: The top panel shows the best-fit $A_{\textrm{Vmax}}$ values as a
function of redshift, and the vertical bars represent $\sigma_{\mathrm{max}}$,
the scatter on $A_{\textrm{Vmax}}$ in each galaxy population. In the second
and third panels we show the redshift evolution of the galaxy triaxiality and
thickness measured by van der Wel et al. (2014), again with vertical bars
showing the standard deviation on each parameter.

###  4.3 Dust Attenuation across Mass and Redshift

We show the results of the fit in Figure 3. In each redshift and stellar mass
bin the observed galaxies are shown in blue and the best-fit model in red.
Considering that our simple model has only two free parameters, it is able to
reproduce the data remarkably well across the mass and redshift range. The
best-fit values of the model parameters are listed in each panel, and are also
plotted in the top panel of Figure 4 as a function of redshift, with the
vertical bars representing the scatter $\sigma_{\mathrm{max}}$. We find that
the scatter is low compared to $A_{\textrm{Vmax}}$, particularly for systems
with intermediate and high stellar masses. This means that, at fixed mass and
redshift, all star-forming galaxies have roughly the same intrinsic amount of
dust, and the wide observed range in $A_{\mathrm{V}}$ and color is mostly due
to inclination, confirming the result of Patel et al. (2012). We also find
that the dust content of galaxies grows with cosmic time and stellar mass, in
agreement with previous studies (e.g., Fang et al., 2018).

The bottom two panels of Figure 4 show the redshift trend for the galaxy
triaxiality and thickness measured by van der Wel et al. (2014). Most galaxies
are relatively thin disks with $D\sim 0.25$ and a small scatter. However, low-
mass systems at high redshift are also highly triaxial, which suggests that
our oblate spheroid model (which has zero triaxiality) is not appropriate in
this regime. Interestingly, Figure 3 shows that the model does not fit this
population of low-mass, high-redshift galaxies well, with the best-fit model
extending on the diagonal rather than the horizontal direction of the $UVJ$
diagram. However, the fact that the best-fit dust attenuation is negligible
for this population may also indicate a problem with the assumed SFH, such as
the strength or timescale of its stochastic fluctuations.

Additionally, our model appears insufficient to reproduce the observations at
the opposite end of the parameter space, i.e. for high-mass, low-redshift
galaxies. In this case the model produces too many galaxies with low
$A_{\mathrm{V}}$. This is likely connected to the simplistic assumptions
regarding the spatial distribution of stars in our model. If one were to
consider the contribution from stars that are uniformly mixed with the dust,
then the model would need a much higher $A_{\textrm{Vmax}}$ to reproduce the
dustier systems, and as a consequence the face-on galaxies would also appear
more attenuated.

##  5 Discussion

Figure 5: Galaxies from the COSMOS2015 catalog in the $UVJ$ plane, color-coded
by $L_{\mathrm{IR}}$/M∗ (left) and $L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$
(right). Galaxy properties are derived by fits to the UV-to-IR photometry
(Leja et al., 2020). Only galaxies with at least two $Herschel$ detections are
shown.

###  5.1 Dust attenuation versus dust mass

The main result of this work is that the observed variation in UVJ colors of
star-forming systems at a given stellar mass can be attributed almost entirely
to variation in viewing angle rather than variation in intrinsic dust mass.
This brings several implications for galaxy studies. Most importantly, we
conclude that the $UVJ$ diagram is not a good tool for identifying “dusty”
galaxies. Colors that appear reddened might only indicate higher inclinations
(or thicker galaxies, as illustrated in Figure 2), and not intrinsically
higher dust content. On the other hand, if color is a useful indicator of
inclination, our model could be used to select galaxies of a given inclination
solely based on the photometry, instead of more difficult morphological
measurements.

###  5.2 The interpretation of IR and UV emission

Another important consequence of our results is related to the use of
$L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$ (i.e., the ratio of IR and UV luminosity)
to estimate the proportion of star formation that is obscured. This method is
based on the assumption that $L_{\mathrm{IR}}$ represents the obscured star
formation while $L_{\mathrm{UV}}$ traces the unobscured star formation.
However, in our model the dust attenuation in the UV is strongly dependent on
inclination, while the IR luminosity is not affected by inclination since dust
attenuation in the IR is negligible. This means that the ratio
$L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$ at a given stellar mass is mostly a
measurement of inclination, and not of the intrinsic fraction of obscured star
formation. For example, adopting $D=0.25$, $A_{\textrm{Vmax}}=2.5$, and the
Calzetti law, our model predicts a difference in the edge-on versus face-on
attenuation of 4 magnitudes in the UV, meaning that the
$L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$ ratio can vary by a factor of $\sim 40$
solely due to inclination effects.

We test this prediction of our model using a small sample of galaxies with
available far-IR data. We select galaxies from the COSMOS2015 catalog (Laigle
et al., 2016) with $0.5<z<0.8$ and $10.5<\log(M_{\ast}/M_{\odot})<11$ that are
detected in Herschel. Figure 5 shows this sample on the $UVJ$ diagram, color-
coded by $L_{\mathrm{IR}}$/M∗ (left) and $L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$
(right). Moving along the diagonal direction towards redder, more dust-
attenuated systems, the $L_{\mathrm{IR}}$/$L_{\mathrm{UV}}$ ratio varies by
almost two orders of magnitude, while the total infrared luminosity
(normalized by stellar mass) is virtually constant. This finding is consistent
with our main result: at a given stellar mass, a galaxy’s position along the
dust vector in $UVJ$ space is determined primarily by galaxy orientation and
does not correlate with the true amount of dust in the galaxy (see also
Arnouts et al. 2013 for a similar analysis).

The fact that inclination has dramatically different effects on
$L_{\mathrm{IR}}$ and $L_{\mathrm{UV}}$ should be taken into account in many
other contexts; for example, when deriving star formation rates using the
“UV+IR” method. Similarly, when imposing energy balance in photometric fits
that include both UV and IR observations, if the inclination angle can be
estimated from imaging then it is possible, in principle, to calculate
inclination-dependent corrections (see Doore et al. 2021 for a first attempt
in this direction).

###  5.3 Understanding the $UVJ$ colors of galaxies

Advanced cosmological simulations are still unable to reproduce the full
extent of the $UVJ$ colors of star-forming galaxies, particularly at the red
end (Donnari et al., 2019; Akins et al., 2021). Our results can greatly help
in understanding this discrepancy, and suggest that both the line-of-sight
used to calculate the colors and the galaxy shapes are crucial for a
meaningful comparison. Moreover, the fact that we are able to reproduce most
of the observations using stochastic SFHs suggests that galaxy colors have
limited constraining power on the history of star-forming galaxies, in
agreement with the results of recent studies (Chaves-Montero & Hearin, 2020;
Hahn et al., 2021).

Our work can be considered the first step towards a fully quantitative
understanding of the distribution of galaxies on the $UVJ$ diagram. Future
developments should include a more realistic treatment of SFH, stellar
metallicity, dust extinction law, and galaxy geometry, and should be extended
to the quiescent population. Such a comprehensive empirical model of how
galaxy colors evolve as a function of mass and redshift will provide new
constraints on the formation, growth, and quenching of galaxies.

##  6 Acknowledgements

We acknowledge support from the SAO REU program, which is funded in part by
the National Science Foundation REU and Department of Defense ASSURE programs
under NSF Grant no. AST-1852268, and by the Smithsonian Institution. S.B.
acknowledges support from the Clay Fellowship. S.T. is supported by the
Smithsonian Astrophysical Observatory through the CfA Fellowship and by the
2021 Research Fund 1.210134.01 of UNIST (Ulsan National Institute of Science &
Technology).

## References

  * Akins et al. (2021) Akins, H. B., Narayanan, D., Whitaker, K. E., et al. 2021, arXiv e-prints, arXiv:2105.12748.  https://arxiv.org/abs/2105.12748
  * Arnouts et al. (2013) Arnouts, S., Le Floc’h, E., Chevallard, J., et al. 2013, A&A, 558, A67, doi: 10.1051/0004-6361/201321768
  * Belli et al. (2019) Belli, S., Newman, A. B., & Ellis, R. S. 2019, The Astrophysical Journal, 874, 17, doi: 10.3847/1538-4357/ab07af
  * Brammer et al. (2008) Brammer, G. B., van Dokkum, P. G., & Coppi, P. 2008, ApJ, 686, 1503, doi: 10.1086/591786
  * Brammer et al. (2012) Brammer, G. B., Sánchez-Janssen, R., Labbé, I., et al. 2012, ApJ, 758, L17, doi: 10.1088/2041-8205/758/1/L17
  * Byler et al. (2017) Byler, N., Dalcanton, J. J., Conroy, C., & Johnson, B. D. 2017, The Astrophysical Journal, 840, 44, doi: 10.3847/1538-4357/aa6c66
  * Calzetti et al. (2000) Calzetti, D., Armus, L., Bohlin, R. C., et al. 2000, ApJ, 533, 682, doi: 10.1086/308692
  * Caplar & Tacchella (2019) Caplar, N., & Tacchella, S. 2019, MNRAS, 487, 3845, doi: 10.1093/mnras/stz1449
  * Chaves-Montero & Hearin (2020) Chaves-Montero, J., & Hearin, A. 2020, MNRAS, 495, 2088, doi: 10.1093/mnras/staa1230
  * Chevallard et al. (2013) Chevallard, J., Charlot, S., Wandelt, B., & Wild, V. 2013, MNRAS, 432, 2061, doi: 10.1093/mnras/stt523
  * Conroy (2013) Conroy, C. 2013, ARA&A, 51, 393, doi: 10.1146/annurev-astro-082812-141017
  * Conroy & Gunn (2010) Conroy, C., & Gunn, J. E. 2010, ApJ, 712, 833, doi: 10.1088/0004-637X/712/2/833
  * Conroy et al. (2009) Conroy, C., Gunn, J. E., & White, M. 2009, ApJ, 699, 486, doi: 10.1088/0004-637X/699/1/486
  * Donnari et al. (2019) Donnari, M., Pillepich, A., Nelson, D., et al. 2019, MNRAS, 485, 4817, doi: 10.1093/mnras/stz712
  * Doore et al. (2021) Doore, K., Eufrasio, R. T., Lehmer, B. D., et al. 2021, arXiv e-prints, arXiv:2109.05039.  https://arxiv.org/abs/2109.05039
  * Fang et al. (2018) Fang, J. J., Faber, S. M., Koo, D. C., et al. 2018, ApJ, 858, 100, doi: 10.3847/1538-4357/aabcba
  * Giovanelli et al. (1995) Giovanelli, R., Haynes, M. P., Salzer, J. J., et al. 1995, AJ, 110, 1059, doi: 10.1086/117586
  * Grogin et al. (2011) Grogin, N. A., Kocevski, D. D., Faber, S. M., et al. 2011, ApJS, 197, 35, doi: 10.1088/0067-0049/197/2/35
  * Hahn et al. (2021) Hahn, C., Starkenburg, T. K., Anglés-Alcázar, D., et al. 2021, arXiv e-prints, arXiv:2106.09741.  https://arxiv.org/abs/2106.09741
  * Iyer et al. (2020) Iyer, K. G., Tacchella, S., Genel, S., et al. 2020, MNRAS, 498, 430, doi: 10.1093/mnras/staa2150
  * Johnson et al. (2021) Johnson, B. D., Leja, J., Conroy, C., & Speagle, J. S. 2021, ApJS, 254, 22, doi: 10.3847/1538-4365/abef67
  * Kauffmann et al. (2003) Kauffmann, G., Heckman, T., White, S., et al. 2003, Monthly Notices of the Royal Astronomical Society, 341, 33, doi: 10.1046/j.1365-8711.2003.06291.x
  * Koekemoer et al. (2011) Koekemoer, A. M., Faber, S. M., Ferguson, H. C., et al. 2011, ApJS, 197, 36, doi: 10.1088/0067-0049/197/2/36
  * Kroupa (2001) Kroupa, P. 2001, MNRAS, 322, 231, doi: 10.1046/j.1365-8711.2001.04022.x
  * Kullback & Leibler (1951) Kullback, S., & Leibler, R. A. 1951, Ann. Math. Statist), 22, doi: 10.1214/aoms/1177729694
  * Laigle et al. (2016) Laigle, C., McCracken, H. J., Ilbert, O., et al. 2016, ApJS, 224, 24, doi: 10.3847/0067-0049/224/2/24
  * Leja et al. (2020) Leja, J., Speagle, J. S., Johnson, B. D., et al. 2020, ApJ, 893, 111, doi: 10.3847/1538-4357/ab7e27
  * Leja et al. (2019) Leja, J., Tacchella, S., & Conroy, C. 2019, ApJ, 880, L9, doi: 10.3847/2041-8213/ab2f8c
  * Lilly et al. (2013) Lilly, S. J., Carollo, C. M., Pipino, A., Renzini, A., & Peng, Y. 2013, ApJ, 772, 119, doi: 10.1088/0004-637X/772/2/119
  * Maller et al. (2009) Maller, A., Berlind, A., Blanton, M., & Hogg, a. 2009, The Astrophysical Journal, 691, 394, doi: 10.1088/0004-637X/691/1/394
  * Momcheva et al. (2016) Momcheva, I. G., Brammer, G. B., van Dokkum, P. G., et al. 2016, ApJS, 225, 27, doi: 10.3847/0067-0049/225/2/27
  * Muzzin et al. (2013) Muzzin, A., Marchesini, D., Stefanon, M., et al. 2013, The Astrophysical Journal, 777, 18, doi: 10.1088/0004-637x/777/1/18
  * Noeske et al. (2007) Noeske, K. G., Weiner, B. J., Faber, S. M., et al. 2007, ApJ, 660, L43, doi: 10.1086/517926
  * Padilla & Strauss (2008) Padilla, N. D., & Strauss, M. A. 2008, MNRAS, 388, 1321, doi: 10.1111/j.1365-2966.2008.13480.x
  * Patel et al. (2012) Patel, S. G., Holden, B. P., Kelson, D. D., et al. 2012, Astrophys. J. Lett., 748, L27, doi: 10.1088/2041-8205/748/2/L27
  * Salim & Narayanan (2020) Salim, S., & Narayanan, D. 2020, ARA&A, 58, 529, doi: 10.1146/annurev-astro-032620-021933
  * Shlens (2014) Shlens, J. 2014, arXiv e-prints, arXiv:1404.2000.  https://arxiv.org/abs/1404.2000
  * Skelton et al. (2014) Skelton, R. E., Whitaker, K. E., Momcheva, I. G., et al. 2014, ApJS, 214, 24, doi: 10.1088/0067-0049/214/2/24
  * Tacchella et al. (2020) Tacchella, S., Forbes, J. C., & Caplar, N. 2020, MNRAS, 497, 698, doi: 10.1093/mnras/staa1838
  * Tal et al. (2014) Tal, T., Dekel, A., Oesch, P., et al. 2014, ApJ, 789, 164, doi: 10.1088/0004-637X/789/2/164
  * van der Wel et al. (2014) van der Wel, A., Chang, Y.-Y., Bell, E. F., et al. 2014, ApJ, 792, L6, doi: 10.1088/2041-8205/792/1/L6
  * Verheijen (2001) Verheijen, M. A. W. 2001, ApJ, 563, 694, doi: 10.1086/323887
  * Williams et al. (2009) Williams, R. J., Quadri, R. F., Franx, M., van Dokkum, P., & Labbé, I. 2009, ApJ, 691, 1879, doi: 10.1088/0004-637X/691/2/1879
  * Wuyts et al. (2007) Wuyts, S., Labbé, I., Franx, M., et al. 2007, ApJ, 655, 51, doi: 10.1086/509708


11institutetext:  LIPN, CNRS UMR 7030, Université Sorbonne Paris Nord,
Villetaneuse, France
22institutetext: Department of Electronics and Computer Science, Pontificia
Universidad Javeriana, Cali, Colombia
33institutetext: CNRS-LIX, École Polytechnique de Paris, France

# Unified Opinion Dynamic Modeling as Concurrent Set Relations in Rewriting
Logic ††thanks: The work of Olarte, Ramírez, Rocha and Valencia was partially
supported by the Minciencias (Ministerio de Ciencia Tecnologá e Innovación,
Colombia) project PROMUEVA (BPIN 2021000100160).

Carlos Olarte 11 Carlos Ramírez 22 Camilo Rocha 22 Frank Valencia 3322

###### Abstract

Social media platforms have played a key role in weaponizing the polarization
of social, political, and democratic processes. This is, mainly, because they
are a medium for opinion formation. Opinion dynamic models are a tool for
understanding the role of specific social factors on the acceptance/rejection
of opinions because they can be used to analyze certain assumptions on human
behaviors. This work presents a framework that uses concurrent set relations
as the formal basis to specify, simulate, and analyze social interaction
systems with dynamic opinion models. Standard models for social learning are
obtained as particular instances of the proposed framework. It has been
implemented in the Maude system as a fully executable rewrite theory that can
be used to better understand how opinions of a system of agents can be shaped.
This paper also reports an initial exploration in Maude on the use of
reachability analysis, probabilistic simulation, and statistical model
checking of important properties related to opinion dynamic models.

###### Keywords:

Concurrent set relations opinion dynamic models social interaction systems
belief revision rewriting logic formal verification

##  1 Introduction

Social media platforms have played a key role in the polarization of social,
political, and democratic processes. Social uprisings in the Middle East,
Asia, and Central and South America have led to sudden changes in the
structure and nature of society during this past decade [20, 12, 6, 15, 30,
19]. Polarization across the globe has paved the way to the divergence of
political attitudes away from the center, towards ideological extremes,
sometimes resulting in fractured institutions, erratic policy making,
incipient political dialog, and the resurgence of old regimes [13, 18, 22, 20,
11, 16]. Democracy, viewed as a system of power controlled by the people, has
been made vulnerable by severe polarization as opposing sides are seen as
adversaries that compete against an enemy needing to be vanquished. As a
result, popular election campaigns –including presidential ones– have
compromised the basic principles of democratic election in some countries [4,
29, 28, 3]. All these scenarios have a common factor: social media interaction
as a medium for _opinion formation_ fueling polarization.

Social learning and opinion dynamic models have been developed to understand
the role of specific social factors on the acceptance/rejection of opinions,
such as the ones communicated via social media (see, e.g., [14, 2, 17, 8]).
They are often used to validate how certain assumptions on human behaviors can
explain alternative scenarios, such as opinion consensus, polarization and
fragmentation. In their micro-level approach, the one followed in the present
work, users are considered as agents that can share opinions on a given topic.
They update their opinion by interacting with a selected group of users that
have some influence on them (e.g., influencers, their family and friends).
These dynamics take place at discrete time steps at which (some) agents update
their opinion. For instance, an opinion model can deterministically update the
opinion of all agents in such a time-step, while another one can non-
deterministically update the opinion of a single agent. Depending on the model
of choice, which usually defines its own update function for the individual
agents, phenomena under different assumptions can be observed. The ultimate
goal is to understand how the opinions of the agents, as a social system, are
shaped after a certain number of steps.

This work proposes a framework that uses concurrent set relations as the
formal basis to specify, simulate, and analyze social interaction systems with
dynamic opinion models. The framework uses influence graphs to specify the
structure of agent interactions in the social system under study: vertices
represent agents and a directed weighted edge from $a$ to $b$ represents the
weighted influence of agent’s $a$ opinion over the opinion of agent $b$. In
the sense of set relations in [25], the framework comprises two main
mechanisms that are combined via closures for specifying opinion dynamics over
the graphs: namely, an atomic set relation and a strategy. The atomic set
relation updates the opinion of a single vertex w.r.t. a set of edges (and the
corresponding vertices) incident to it. The strategy selects the edges that
will be used to update in parallel (i.e., synchronously) the opinion
associated to the vertices with edges incident to it in the given set. As a
consequence, dynamic opinion models can be formalized as a concurrent set
relation system, with parametric update function, using the composition of an
atomic relation and a strategy via closures. An important observation is that
the determinism or non-determinism inherent to a given opinion dynamic model
is exactly captured by the deterministic or non-deterministic nature of the
corresponding concurrent set relation.

Standard models for social learning are obtained as particular instances of
the proposed framework. The classical DeGroot opinion model [9] is obtained as
the synchronous closure under the maximal redices strategy of a given atomic
set relation. In a similar fashion, gossip-based models that use pairwise
interactions to represent the opinion formation process (see, e.g., [10]) are
obtained via the asynchronous closure where the strategy selects single edges
for the given atomic set relation. Other opinion models can be obtained via
the synchronous closure of an atomic set relation, as midpoints between De
Groot and gossip-based models.

The proposed framework has been implemented in the Maude system [7]. It is a
rewriting logic theory that exploits the reflective capabilities of rewriting
logic and that can be particularized to the opinion model of interest. A state
is an object-like configuration representing the structure of the system and
its opinion values. An object is either an agent $u$ with its opinion $o_{u}$,
specified as $\left\langle{u}:{o_{u}}\right\rangle$, or the influence of agent
$u$ over agent $v$ with weight $i_{uv}$, specified as
$\left\langle{(u,v)}:{i_{uv}}\right\rangle$. The update function $\mu$ of each
specific model is to be defined equationally. The implementation of both the
atomic set relation and the strategy is inspired by the ideas in [24]. The
atomic set relation is axiomatized as a (non-executable) rewrite rule that
takes as input an agent $\left\langle{u}:{o_{u}}\right\rangle$ and a set of
edges $A\subseteq E$ in the current state. For a given state, it updates the
opinion $o_{u}$ to a new opinion $o_{u}^{\prime}$ using $\mu$, and the opinion
and influence of agents adjacent to it w.r.t. $A$. As a result, each atomic
step rewrites a single object $\left\langle{u}:{o_{u}}\right\rangle$ to its
updated version $\left\langle{u}:{o_{u}^{\prime}}\right\rangle$. The metalevel
is used to apply the atomic rewrite rule over the agents in a state according
to the edges selected by the given strategy: only agents appearing as targets
of the directed edges have their opinion updated. This strategy is defined
equationally by the user and computes a collection of subsets of $E$: a
parallel rewrite step under the maximal redices strategy is performed for each
subset $A$ of edges. Since the atomic rewrite relation is deterministic, the
strategy is the only source of non-determinism in the system and a concurrent
step is made for each identified subset $A$.

The implementation of the proposed framework results in a fully executable
top-most object-like rewrite theory in Maude that can be used to better
understand how opinions of a system of agents are shaped –and to ultimately
understand polarization— using formal methods techniques, such as reachability
analysis and temporal model checking.

This work is part of a broader effort to make available computational ideas
and approaches for analyzing phenomena in social networks, such as
polarization, consensus, and fragmentation. They include concurrency models,
modal and probabilistic logics, and formal methods frameworks, techniques, and
tools. In this context, the work presented here is a first step towards the
use of rewriting logic for such purposes. As it is explained in the sections
that follow, one major problem a opinion dynamic model may face is that of
state explosion. An initial exploration on the use of probabilistic simulation
and statistical analysis is reported in this work. However, the extension of
the proposed framework to a fully probabilistic setting, in which –e.g.– the
strategy selects the set of edges according to a probability distribution
function, falls outside the scope of this work. It needs to be further
explored as future work as it may open the door to statistical model checking
of novel properties using a new breed of measures and thus pave the way to the
analysis of quantitative properties beyond the reach of techniques currently
available for opinion dynamic models.

##### Organization.

After recalling the notion of set relations in Section 3, Section 4 shows how
different models for social learning can be seen as particular instances
(atomic set relation and strategy) of this framework. The implementation in
Maude is described in Section 5, while different analyses performed on the
proposed rewrite theory are introduced in Section 6. Section 7 concludes the
paper. The full Maude specification supporting the set relations framework is
available at [23], as companion tool to the paper.

##  2 Overview of Rewriting Logic and Maude

A _rewrite theory_ [21] is a tuple $\mathcal{R}=(\Sigma,E,L,R)$ such that:
$(\Sigma,E)$ is an equational theory where $\Sigma$ is a signature that
declares sorts, subsorts, and function symbols; $E$ is a set of (conditional)
equations of the form $t=t^{\prime}\mbox{ {if} }\psi$, where $t$ and
$t^{\prime}$ are terms of the same sort, and $\psi$ is a conjunction of
equations; $L$ is a set of _labels_ ; and $R$ is a set of labeled
(conditional) rewrite rules of the form $l:q\longrightarrow r\mbox{ {if}
}\psi$, where $l\in L$ is a label, $q$ and $r$ are terms of the same sort, and
$\psi$ is a conjunction of equations. Condition $\psi$ in equations and
rewrite rules can be more general than conjunction of equations, but this
extra expressiveness is not needed in this paper.

$T_{\Sigma,s}$ denotes the set of ground terms of sort $s$, and
$T_{\Sigma}(X)_{s}$ denotes the set of terms of sort $s$ over a set of sorted
variables $X$. $T_{\Sigma}(X)$ and $T_{\Sigma}$ denote all terms and ground
terms, respectively. A substitution $\sigma:X\rightarrow T_{\Sigma}(X)$ maps
each variable to a term of the same sort, and $t\sigma$ denotes the term
obtained by simultaneously replacing each variable $x$ in a term $t$ with
$\sigma(x)$.

A _one-step rewrite_ $t\longrightarrow_{\mathcal{R}}t^{\prime}$ holds if there
is a rule $l:q\longrightarrow r\mbox{ {if} }\psi$, a subterm $u$ of $t$, and a
substitution $\sigma$ such that $u=q\sigma$ (modulo equations), $t^{\prime}$
is the term obtained from $t$ by replacing $u$ with $r\sigma$, and
$v\sigma=v^{\prime}\sigma$ holds for each $v=v^{\prime}$ in $\psi$. The
reflexive-transitive closure of $\longrightarrow_{\mathcal{R}}$ is denoted as
$\longrightarrow_{\mathcal{R}}^{\ast}$.

A rewrite theory $\mathcal{R}$ is called _topmost_ iff there is a sort
$\mathit{State}$ at the top of one of the connected components of the subsort
partial order such that for each rule $l:q\longrightarrow r\mbox{ {if} }\psi$,
both $q$ and $r$ have the top sort $\mathit{State}$, and no operator has sort
$\mathit{State}$ or any of its subsorts as an argument sort.

Maude [7] is a language and tool supporting the specification and analysis of
rewrite theories. A Maude module (mod M is … endm) specifies a rewrite theory
$\mathcal{R}$. Sorts and subsort relations are declared by the keywords sort
and subsort; function symbols, or _operators_ , are introduced with the op
keyword: op $f$ : $s_{1}$ … $s_{n}$ -> $s$, where $s_{1}$, …, $s_{n}$ are the
sorts of its arguments, and $s$ is its (value) sort. Operators can have user-
definable syntax, with underbars ‘`_`’ marking each of the argument positions
(e.g., `_+_`). Some operators can have equational attributes, such as assoc,
comm, and id:$\;t$, stating that the operator is, respectively, associative,
commutative, and/or has identity element $t$. Equations are specified with the
syntax eq $t$ = $t^{\prime}$ or ceq $t$ = $t^{\prime}$ if $\psi$; and rewrite
rules as rl [$l$] : $u$ => $v$ or crl [$l$] : $u$ => $t^{\prime}$ if $\psi$.
The mathematical variables in such statements are declared with the keywords
var and vars.

Maude provides a large set of analysis methods, including computing the normal
form of a term $t$ (command red $t$), simulation by rewriting (rew $t$),
reachability analysis (search $t$ =>* $t^{\prime}$ such that $\psi$), and
rewriting according to a given rewrite strategy (srew $t$ using $str$). Basic
such rewrite strategies include $r\mathtt{[}\sigma\mathtt{]}$ (apply rule with
label $r$ once with the optional ground substitution $\sigma$), idle
(identity), fail (empty set), and match $P$ s.t. $C$, which checks whether the
current term matches the pattern $P$ subject to the constraint $C$. Compound
strategies can be defined using concatenation ($\alpha\,;\,\beta$),
disjunction ($\alpha\,|\,\beta$), iteration ($\alpha\,\mathtt{*}$),
$\alpha\texttt{ or-else }\beta$ (execute $\beta$ if $\alpha$ fails), etc.

The Unified Maude model-checking tool [26] (umaudemc) allows for the use of
different model checkers to analyze Maude specifications. Besides being an
interface for the standard LTL model checker of Maude, it also offers the
possibility of interfacing external CTL and probabilistic model checkers. For
the purpose of this paper, the command scheck [27] is used to assign
probabilities to the transition system generated by an initial term $t$, and
perform statistical model checking to estimate quantitive expressions written
in the QuaTEx language. Hence, it is possible to compute, e.g., the expected
value of the number of communication or interactions needed to reach a
consensus in a network.

##### Meta-programming.

Maude supports _meta-programming_ , where a Maude module $M$ (resp., a term
$t$) can be (meta-)represented as a Maude _term_ $\overline{M}$ of sort Module
(resp. as a Maude term $\overline{t}$ of sort Term) in Maude’s META-LEVEL
module. Maude provides built-in functions such as metaRewrite, and metaSearch,
which are the “meta-level” functions corresponding to “user-level” commands to
perform rewriting and search, respectively.

##  3 Set Relations

This section introduces set relations and their notation, as used in this
paper. It defines the asynchronous, parallel, and synchronous set relations as
closures of an atomic set relation. This section is based, mainly, on [25].

Let $\mathcal{U}$ be a set whose elements are denoted $A,B,\ldots$ and let
$\rightarrow$ be a binary relation on $\mathcal{U}$. An element $A$ of
$\mathcal{U}$ is called a $\rightarrow$-redex iff there exists
$B\in\mathcal{U}$ such that the pair
$\left\langle{A};{B}\right\rangle\mathop{\in}\rightarrow$. The expressions
${A}\mathop{\rightarrow}{B}$ and ${A}\mathop{\not\rightarrow}{B}$ denote
$\left\langle{A};{B}\right\rangle\mathop{\in}\rightarrow$ and
$\left\langle{A};{B}\right\rangle\mathop{\not\in}\rightarrow$, respectively.
The identity and reflexive-transitive closures of $\rightarrow$ are defined as
usual and denoted $\stackrel{{\scriptstyle 0}}{{\rightarrow}}$ and
$\stackrel{{\scriptstyle*}}{{\rightarrow}}$, respectively.

It is assumed that $\mathcal{U}$ is the family of all nonempty finite subsets
of an abstract and possibly infinite set $T$ whose members are called elements
(i.e., $\mathcal{U}\subseteq\mathcal{P}\left({T}\right)$,
$\emptyset\not\in\mathcal{U}$, and if $A\in\mathcal{U}$, then
$\mathrm{card}\left({A}\right)\in\mathbb{N}$ ). Therefore, $\rightarrow$ is a
binary relation on finite subsets of elements in $T$. When it is clear from
the context, curly brackets are omitted from set notation; e.g.,
${a,b}\mathop{\rightarrow}{b}$ denotes
${\\{a,b\\}}\mathop{\rightarrow}{\\{b}\\}$. Because this convention, the
symbol ‘,’ is overloaded to denote set union. For example, if $A$ denotes the
set $\\{a,b\\}$, $B$ the set $\\{c,d\\}$, and $D$ the set $\\{d,e\\}$, the
expression ${A,B}\mathop{\rightarrow}{B,D}$ denotes the pair
${a,b,c,d}\mathop{\rightarrow}{c,d,e}$.

Given a set of elements, in the asynchronous set relation exactly one redex is
selected to be updated.

######  Definition 1 (Asynchronous Set Relation)

The _asynchronous relation_ $\stackrel{{\scriptstyle\square}}{{\rightarrow}}$
is defined as the asynchronous closure of $\rightarrow$, i.e., the set of
pairs $\left\langle{A};{B}\right\rangle\in\mathcal{U}\times\mathcal{U}$ such
that ${A}\mathop{\stackrel{{\scriptstyle\square}}{{\rightarrow}}}{B}$ iff
there exists a $\rightarrow$-redex $A^{\prime}\subseteq A$ and an element
$B^{\prime}\in\mathcal{U}$ such that
${A^{\prime}}\mathop{\rightarrow}{B^{\prime}}$ and $B=(A\setminus
A^{\prime})\cup B^{\prime}$.

In the parallel set relation, a non-empty collection of redices is identified
to be updated in parallel (i.e., without interleaving).

######  Definition 2 (Parallel Set Relation)

The _parallel relation_ $\stackrel{{\scriptstyle{||}}}{{\rightarrow}}$ is
defined as the parallel closure of $\rightarrow$, i.e., the set of pairs
$\left\langle{A};{B}\right\rangle\in\mathcal{U}\times\mathcal{U}$ such that
${A}\mathop{\stackrel{{\scriptstyle{||}}}{{\rightarrow}}}{B}$ iff there exist
$\rightarrow$-redices $A_{1},\ldots,A_{n}\subseteq A$ (nonempty) pairwise
disjoint and elements $B_{1},\ldots,B_{n}$ in $\mathcal{U}$ such that
${A_{i}}\mathop{\rightarrow}{B_{i}}$, for $1\leq i\leq n$, and
$B=\left(A\setminus\bigcup_{1\leq i\leq n}A_{i}\right)\cup\left(\bigcup_{1\leq
i\leq n}B_{i}\right)$.

The synchronous set relation $\stackrel{{\scriptstyle{s}}}{{\rightarrow}}$
applies as many atomic reductions as possible, in parallel. However, in
contrast to the previous two closures, the redices are selected with the help
of a strategy $s$, namely, a function that identifies a non-empty subset of
redices. As a consequence, the synchronous set relation is a subset of the
parallel set relation. It is important to note that the notion of strategy
used for defining the synchronous closure of the atomic set relation is
different to the one introduced in Section 1 for the framework; the name used
in this section is kept from [25].

######  Definition 3 ($\rightarrow$-strategy)

A _$\rightarrow$ -strategy_ is a function $s$ that maps any element
$A\in\mathcal{U}$ into a set
$s(A)\subseteq\mathcal{P}\left({\rightarrow}\right)$ such that if
$s(A)=\\{\left\langle{A_{1}};{B_{1}}\right\rangle,\ldots\left\langle{A_{n}};{B_{n}}\right\rangle\\}$,
then $A_{i}\subseteq A$ and ${A_{i}}\mathop{\rightarrow}{B_{i}}$, for $1\leq
i\leq n$, and $A_{1},\ldots,A_{n}$ are pairwise disjoint.

######  Definition 4 (Synchronous Relation)

Let $s$ be a $\rightarrow$-strategy. The _synchronous relation_
$\stackrel{{\scriptstyle{s}}}{{\rightarrow}}$ is defined as the synchronous
closure of $\rightarrow$ w.r.t. $s$, i.e., the set of pairs
$\left\langle{A};{B}\right\rangle\in\mathcal{U}\times\mathcal{U}$ such that
${A}\mathop{\stackrel{{\scriptstyle{s}}}{{\rightarrow}}}{B}$ iff
$B=\left(A\setminus\bigcup_{1\leq i\leq n}A_{i}\right)\cup\left(\bigcup_{1\leq
i\leq n}B_{i}\right)$ where
$s(A)=\\{\left\langle{A_{1}};{B_{1}}\right\rangle,\ldots\left\langle{A_{n}};{B_{n}}\right\rangle\\}$.

This section is concluded with an example that illustrates the notions
introduced so far.

####  3.0.1 Vaccine Example.

Consider the directed weighted graph $G=(V,E,i)$ in Figure 1. It represents a
social system with six agents $V=\\{a,b,c,d,e,f\\}$ and twelve opinion
influences. The label $i(u,v)$ associated to each edge $(u,v)$ from agent $u$
to agent $v$ denotes the opinion influence $i_{uv}=i(u,v)$ of agent $u$ over
the opinion of agent $v$ (about a given topic): these values are in the real
interval $[0,1]$ (i.e., ${i}:{E}\rightarrow{[0,1]}$); the higher the value,
the stronger the influence. In this example, the influence of $f$ over $a$ is
the strongest possible. Notice that agents may also have _self-influence_ ,
representing agents whose opinion need not be completely influenced by the
opinion of the others.

The initial opinions (or beliefs) of the agents are depicted within the box
below each node. They are specified by a function ${o}:{V}\rightarrow{[0,1]}$,
which is assumed to represent the opinion value $o_{u}=o(u)$ of each agent $u$
on the given topic. The greater the value, the stronger (weaker) the agreement
(disagreement) with the proposition, and $0$ represents total disagreement. In
this example such a proposition is _vaccines are safe_. Intuitively, the
agents $a$, $b$, and $c$ are in strong disagreement with vaccines being safe
(the anti-vaxxers) and the rest are in strong agreement (the pro-vaxxers).

Notice that although $a$ is the most extreme anti-vaxxer, the most extreme
pro-vaxxer $f$ has a strong influence over $a$. Hence, it is expected that the
evolution of $a$’s opinion will be highly influenced by the opinion of $f$. In
general, an agent’s opinion evolution takes into account a subset of its
influences, as will be explained shortly.

Figure 1: Graph representing opinion and influence interaction in a social
system. Initial opinions are given within the box below each node. The labels
on each edge $(u,v)$ represent the influence value of agent $u$ over agent
$v$.

Recall the object-like notation in Section 1. The set of elements $T$ is made
of pairs of the form $\left\langle{u}:{r}\right\rangle$ or
$\left\langle{(u,v)}:{r}\right\rangle$, with $u,v\in V$, $(u,v)\in E$, and
$r\in[0,1]$. The graph in Figure 1 can be specified as the set of elements
$\Gamma$:

$\displaystyle\Gamma=\\{$
$\displaystyle\left\langle{a}:{0.0}\right\rangle,\left\langle{b}:{0.1}\right\rangle,\left\langle{c}:{0.15}\right\rangle,\left\langle{d}:{0.82}\right\rangle,\left\langle{e}:{0.89}\right\rangle,\left\langle{f}:{0.92}\right\rangle,$
$\displaystyle\left\langle{(a,b)}:{0.6}\right\rangle,\left\langle{(a,c)}:{0.4}\right\rangle,\left\langle{(b,d)}:{0.6}\right\rangle,\left\langle{(c,e)}:{0.6}\right\rangle,\left\langle{(d,c)}:{0.2}\right\rangle,\left\langle{(d,f)}:{0.4}\right\rangle,$
$\displaystyle\left\langle{(e,f)}:{0.6}\right\rangle,\left\langle{(f,a)}:{1.0}\right\rangle,\left\langle{(b,b)}:{0.4}\right\rangle,\left\langle{(c,c)}:{0.4}\right\rangle,\left\langle{(d,d)}:{0.4}\right\rangle,\left\langle{(e,e)}:{0.4}\right\rangle\\}.$

The atomic relation $\rightarrow_{A}$ is defined over elements representing
agents and is parametric on a set $A$ of elements representing edges in
$\Gamma$. In this example, it follows the pattern

$\left\langle{u}:{o_{u}}\right\rangle\rightarrow_{A}\left\langle{u}:{\sum_{\left\langle{(x,u)}:{i_{xu}}\right\rangle\in
A}o_{x}\cdot\frac{i_{xu}}{\sum_{\left\langle{(y,u)}:{i_{yu}}\right\rangle\in
A}i_{yu}}}\right\rangle,$ (1)

where the summation in the denominator is assumed to be non-zero. The opinion
$o_{u}$ of an agent $u$ w.r.t. to $A$ is updated to be the weighted average of
the opinion values of those agents adjacent to $u$ and whose influence is
present in $A$. For instance, let
$A=\\{\left\langle{(a,b)}:{0.6}\right\rangle,\left\langle{(b,b)}:{0.4}\right\rangle,\left\langle{(c,e)}:{0.6}\right\rangle\\}$.
Then, the atomic set relation $\rightarrow_{A}$ has the following two pairs:

$\displaystyle\left\langle{b}:{0.1}\right\rangle\rightarrow_{A}\left\langle{b}:{0.04}\right\rangle$
$\displaystyle\left\langle{e}:{0.89}\right\rangle\rightarrow_{A}\left\langle{e}:{0.15}\right\rangle.$

In the case of agent $b$, its opinion is updated to
$0.04=0.0\cdot\frac{0.6}{1.0}+0.1\cdot\frac{0.4}{1.0}$ because, w.r.t. $A$, it
is influenced both by itself and by agent $a$, whose opinion value is $0.0$
and influence over $b$ is $0.6$. In the case of agent $e$, its opinion is
influenced only by agent $c$. The value is updated to
$0.15=0.15\cdot\frac{0.6}{0.6}$. It can be said that, w.r.t. $A$, agent $e$
acts like a _puppet_ whose own opinion is not taken into account when it is
updated.

The asynchronous closure of $\rightarrow_{A}$ has exactly two pairs, one for
each redex determined by $\rightarrow_{A}$ (i.e., one for agent $b$ and
another for agent $e$):

$\displaystyle\Gamma\stackrel{{\scriptstyle\square}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{b}:{0.1}\right\rangle\\}\right)\cup\\{\left\langle{b}:{0.04}\right\rangle\\}$
$\displaystyle\Gamma\stackrel{{\scriptstyle\square}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{e}:{0.89}\right\rangle\\}\right)\cup\\{\left\langle{e}:{0.15}\right\rangle\\}.$

The parallel closure $\stackrel{{\scriptstyle{||}}}{{\rightarrow}}$ has three
pairs: one in which the opinions of both $b$ and $e$ are updated, in addition
to the same two pairs present in the asynchronous closure:

$\begin{array}[]{lll}\Gamma\stackrel{{\scriptstyle{||}}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{b}:{0.1}\right\rangle\\}\right)\cup\\{\left\langle{b}:{0.04}\right\rangle\\}&&\Gamma\stackrel{{\scriptstyle{||}}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{e}:{0.89}\right\rangle\\}\right)\cup\\{\left\langle{e}:{0.15}\right\rangle\\}\\\
\lx@intercol\Gamma\stackrel{{\scriptstyle{||}}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{b}:{0.1}\right\rangle,\left\langle{e}:{0.89}\right\rangle\\}\right)\cup\\{\left\langle{b}:{0.04}\right\rangle,\left\langle{e}:{0.15}\right\rangle\\}.\hfil\lx@intercol\end{array}$

Finally, to illustrate the synchronous closure of $\rightarrow$, let $s=A$ be
the strategy. That is, all redices in $\rightarrow_{A}$ are identified to be
reduced. Therefore, this relation has the only pair in which the opinions of
both $b$ and $e$ are updated in parallel:

$\displaystyle\Gamma\stackrel{{\scriptstyle{s}}}{{\rightarrow}}_{A}\left(\Gamma\setminus\\{\left\langle{b}:{0.1}\right\rangle,\left\langle{e}:{0.89}\right\rangle\\}\right)\cup\\{\left\langle{b}:{0.04}\right\rangle,\left\langle{e}:{0.15}\right\rangle\\}.$

##  4 Opinion Dynamic Models

This section shows how opinion dynamic models can be specified as set
relations (see Section 3). In particular, a gossip-based and the classical De
Groot opinion models are introduced, as well as a generalization of De Groot
and gossip (under some conditions), here called the _hybrid opinion model_.

The three above-mentioned models are defined, as stated in Section 3, over a
directed weighted graph $G=(V,E,i)$ representing a social system, with agents
$V$, directed opinion influences $E\subseteq V\times V$, and influence values
${i}:{E}\rightarrow{[0,1]}$. A given topic (i.e., proposition) is fixed. The
weight $i_{uv}=i(u,v)$ associated to each edge $(u,v)\in E$ from agent $u$ to
agent $v$ denotes the opinion influence value of agent $u$ over the opinion
value of agent $v$ on the given topic. The opinion value $o_{u}=o(u)\in[0,1]$
associated to each agent $u\in V$ in the given topic is assumed to be known by
all agents in the system. As in Section 3, the higher the value of a opinion
(resp. influence), the stronger the agreement (resp. influence).

The set of elements $T$ in the set relations framework (see Section 3) is made
of pairs of the form $\left\langle{u}:{r}\right\rangle$ or
$\left\langle{(u,v)}:{r}\right\rangle$, with $u,v\in V$, $(u,v)\in E$, and
$r\in[0,1]$. A $G$-configuration (or configuration) is the set of elements in
$T$ that exactly represent the structure of $G$, and the values of opinions
and interactions. Therefore, in the rest of this section, it is assumed that
any configuration $\Gamma$ can be partitioned in two sets $\Gamma_{o}$ and
$\Gamma_{i}$, respectively containing elements of the form
$\left\langle{u}:{o_{u}}\right\rangle$ specifying opinions and
$\left\langle{(u,v)}:{i_{uv}}\right\rangle$ specifying influences.

A model specifies how opinions (associated to agents) can be updated. Each
model definition comprises three pieces; namely, an atomic relation, a
strategy, and an update function for opinions. Therefore, a model specifies
how a $G$-configuration $\Gamma=\Gamma_{o}\cup\Gamma_{i}$ can change to
another $G$-configuration $\Gamma^{\prime}=\Gamma_{o^{\prime}}\cup\Gamma_{i}$,
where only opinions are updated. It is important to note that the notion of
strategy introduced in this section generalizes the notion of strategy
introduced in Section 3, as will be explained later.

The atomic relation is defined in Section 4.1 for the three models. Each model
is introduced by identifying a specific strategy and a specific update
function in subsequent sections.

###  4.1 The Atomic Relation

The atomic relation $\rightarrow_{A}$ is parametric on a subset
$A\subseteq\Gamma_{i}$ and defines how the opinion of a single agent may
evolve. The set of influences $A$ directly identifies the influences (and
indirectly the opinions) to update the opinion of each agent in the
configuration $\Gamma$ (i.e., in $\Gamma_{o}$). For each one of the three
models, the atomic relation $\rightarrow_{A}$ follows the pattern:

$\left\langle{u}:{o_{u}}\right\rangle\rightarrow_{A}\left\langle{u}:{\mu(\Gamma,A,u)}\right\rangle,$
(2)

where $\mu$ is the update function specific to each model. This function takes
as input a $G$-configuration (e.g., $\Gamma$), a subset of its influences
(e.g., $A$), and the agent whose opinion is to be updated (e.g., $u$), and
outputs the new opinion for agent $u$ w.r.t. $\Gamma$ and $A$ in the
corresponding model.

###  4.2 Gossip-based Models

In a gossip-based model, single peer-to-peer interactions are used to update
the opinion of a single user at each time-step. In general, a strategy in the
proposed framework identifies a collection of subsets of interactions in
$\Gamma_{i}$. In particular, the strategy $\rho_{\text{gossip}}$ maps a
$G$-configuration to the collection of singletons made from the influences in
$\Gamma_{i}$:

$\displaystyle\rho_{\text{gossip}}(\Gamma)=\\{\\{x\\}\mid x\in\Gamma_{i}\\}.$

This means that, at each time-step, the opinion value of agent $v$ can be
updated w.r.t. the opinion value of agent $u$ for each singleton
$\\{\left\langle{(u,v)}:{i_{uv}}\right\rangle\\}$ computed by the strategy
$\rho_{\text{gossip}}(\Gamma)$.

The update function $\mu_{\text{gossip}}$ is defined for any $u\in V$ and
$A=\\{\left\langle{(v,u)}:{i_{vu}}\right\rangle\\}\in\rho_{\text{gossip}}(\Gamma)$
as:

$\displaystyle\mu_{\text{gossip}}(\Gamma,A,u)=o_{u}+(o_{v}-o_{u})\cdot
i_{vu}.$

Each singleton $A\in\rho_{\text{gossip}}(\Gamma)$ determines an atomic
relation that updates exactly one agent’s opinion in the given configuration.
Recall, from Section 4.1, that each pair in the atomic set relation
$\rightarrow_{A}$ has the form:

$\displaystyle\left\langle{u}:{o_{u}}\right\rangle\rightarrow_{A}\left\langle{u}:{\mu_{\text{gossip}}(\Gamma,A,u)}\right\rangle.$

Hence, in this model, the opinion of an agent $u$ is updated by identifying an
edge from other agent $v$ with influence $i_{vu}$ over $u$ and by adding to
its current opinion $o_{u}$ the weighted difference of opinion
$(o_{v}-o_{u})\cdot i_{vu}$ of $v$ over $u$.

A gossip-based model is identified as a binary set relation on
$G$-configurations in terms of the asynchronous closure of $\rightarrow_{A}$,
for each singleton $A\in\rho_{\text{gossip}}(\Gamma)$.

###### Definition 5

The $\rightarrow_{\text{gossip}}$ set relation is the set of pairs
$\left\langle{\Gamma};{\Gamma^{\prime}}\right\rangle$ of $G$-configurations
such that:

$\displaystyle\Gamma\rightarrow_{\text{gossip}}\Gamma^{\prime}\quad\text{iff}\quad(\exists
A\in\rho_{\text{gossip}}(\Gamma))\;\Gamma\stackrel{{\scriptstyle\square}}{{\rightarrow}}_{A}\Gamma^{\prime}.$

From the viewpoint of concurrency, the gossip-based opinion dynamic model
captured by $\rightarrow_{\text{gossip}}$ is non-deterministic in the sense
that at each state (i.e., $G$-configuration) exactly $|\Gamma_{i}|$
transitions are possible, one per edge in $E$.

###  4.3 De Groot

In the De Groot model, the opinion value of every agent in the network is
updated at each time-step. All influences are considered at the same time.

The strategy for De Groot in the proposed framework identifies the whole set
of interactions in the network, i.e., $\Gamma_{i}$. In particular, the
strategy $\rho_{\text{DeGroot}}$ maps a $G$-configuration to the singleton
whose only element is $\Gamma_{i}$:

$\displaystyle\rho_{\text{DeGroot}}(\Gamma)=\\{\Gamma_{i}\\}.$

The update function $\mu_{\text{DeGroot}}$ is defined for any $u\in V$ and
$A\in\rho_{\text{DeGroot}}(\Gamma)$ (i.e., $A=\Gamma_{i}$) as:

$\displaystyle\mu_{\text{DeGroot}}(\Gamma,A,u)=o_{u}+\sum_{\left\langle{(v,u)}:{i_{vu}}\right\rangle\in
A}(o_{v}-o_{u})\cdot\frac{i_{vu}}{\sum_{\left\langle{(x,u)}:{i_{xu}}\right\rangle\in
A}i_{xu}},$

where the summation in the denominator is assumed to be non-zero. Otherwise,
the value of this function is assumed to be $o_{u}$ (i.e., the opinion of
agent $u$ does not change).

The De Groot model is identified as a binary set relation on
$G$-configurations in terms of the synchronous closure of
$\rightarrow_{\Gamma_{i}}$ under the maximal redices strategy for
$s=\Gamma_{i}$.

###### Definition 6

The $\rightarrow_{\text{DeGroot}}$ set relation is the set of pairs
$\left\langle{\Gamma};{\Gamma^{\prime}}\right\rangle$ of $G$-configurations
such that:

$\displaystyle\Gamma\rightarrow_{\text{DeGroot}}\Gamma^{\prime}\quad\text{iff}\quad\Gamma\stackrel{{\scriptstyle\Gamma_{i}}}{{\rightarrow}}_{\Gamma_{i}}\Gamma^{\prime}.$

From the viewpoint of concurrency, the De Groot opinion dynamic model captured
by $\rightarrow_{\text{DeGroot}}$ is deterministic in the sense that, at each
state, there is exactly only one possible transition where all influences are
taken into account to update each agent’s opinion without interleaving.

###  4.4 The Hybrid Model

The hybrid model considers every possible influence scenario in the network,
i.e., any possible combination of influences are used to update the opinion of
agents that may be affected by them at each time-step. Therefore, the strategy
in the proposed framework identifies all non-empty subsets of interactions in
$\Gamma_{i}$. In particular, the strategy $\rho_{\text{hybrid}}$ maps a
$G$-configuration to the collection of non-empty subsets made from the
influences in $\Gamma_{i}$:

$\displaystyle\rho_{\text{hybrid}}(\Gamma)=\\{A\mid A\subseteq\Gamma_{i}\mbox{
and }A\neq\emptyset\\}.$

This means that, at each time-step, the opinion value of an agent $v$ can be
updated with a subset of its influencers.

The update function $\mu_{\text{hybrid}}$ is the same as function
$\rho_{\text{DeGroot}}$. That is, it is defined for any $u\in V$ and
$A\in\rho_{\text{hybrid}}(\Gamma)$ as:

$\displaystyle\mu_{\text{hybrid}}(\Gamma,A,u)=o_{u}+\sum_{\left\langle{(v,u)}:{i_{vu}}\right\rangle\in
A}(o_{v}-o_{u})\cdot\frac{i_{vu}}{\sum_{\left\langle{(x,u)}:{i_{xu}}\right\rangle\in
A}i_{xu}},$

where the summation in the denominator is assumed to be non-zero. Otherwise,
the value of this function is assumed to be $o_{u}$ (i.e., the opinion of
agent $u$ does not change). Each subset $A\in\rho_{\text{hybrid}}(\Gamma)$
determines an atomic relation that may update more that one agent’s opinion.
Hence, in this model, the opinion of an agent is updated by identifying some
edges that may have influence over it.

The hybrid model is identified as a binary set relation on $G$-configurations
in terms of the synchronous closure of $\rightarrow_{A}$, for each subset
$A\in\rho_{\text{hybrid}}(\Gamma)$.

###### Definition 7

The $\rightarrow_{\text{hybrid}}$ set relation is the set of pairs
$\left\langle{\Gamma};{\Gamma^{\prime}}\right\rangle$ of $G$-configurations
such that:

$\displaystyle\Gamma\rightarrow_{\text{hybrid}}\Gamma^{\prime}\quad\text{iff}\quad(\exists
A\in\rho_{\text{hybrid}}(\Gamma))\;\Gamma\stackrel{{\scriptstyle
A}}{{\rightarrow}}_{A}\Gamma^{\prime}.$

From the viewpoint of concurrency, the hybrid opinion dynamic model has the
maximum degree of non-determinism possible. Moreover, this model is more
general than the De Groot model.

###### Theorem 4.1

${\rightarrow_{\text{DeGroot}}}\subseteq{\rightarrow_{\text{hybrid}}}$.

###### Proof

It follows by noting that $\Gamma_{i}\in\rho_{\text{hybrid}}(\Gamma)$ and, for
each vertex $u\in V$, the equality
$\mu_{\text{DeGroot}}(\Gamma,\Gamma_{i},u)=\mu_{\text{hybrid}}(\Gamma,\Gamma_{i},u)$
holds.

It is not necessarily the case that
${\rightarrow_{\text{gossip}}}\subseteq{\rightarrow_{\text{hybrid}}}$. This is
because the update functions do not always agree when the collection of
selected influences $A$ is a singleton. In particular, for each singleton
$A=\\{\left\langle{(v,u)}:{i_{vu}}\right\rangle\\}$,
$\mu_{\text{hybrid}}(\Gamma,A,u)=o_{v}$, meaning that agent $u$ in the hybrid
model behaves always like a puppet when $u\neq v$. Note that this is not
(necessarily) the case in ${\rightarrow_{\text{gossip}}}$. Nevertheless, there
is a class of graphs for which this inclusion holds.

###### Theorem 4.2

If $G$ is such that each vertex has a self-loop and is influenced at most by
another vertex, and the summation of its incoming influences is 1, then
${\rightarrow_{\text{gossip}}}\subseteq{\rightarrow_{\text{hybrid}}}$.

###### Proof

If $\Gamma\rightarrow_{\text{gossip}}\Gamma^{\prime}$, there is a singleton
$A\in\rho_{\text{gossip}}(\Gamma)$ such that
$\Gamma\stackrel{{\scriptstyle\square}}{{\rightarrow}}_{A}\Gamma^{\prime}$.
Let $A=\\{\left\langle{(v,u)}:{i_{vu}}\right\rangle\\}$. If $u$ has exactly
one incoming edge, then $v=u$ (by the initial assumption) and
$\rho_{\text{gossip}}(\Gamma,A,u)=o_{u}=\rho_{\text{hybrid}}(\Gamma,A,u)$.
Since $A\in\rho_{\text{hybrid}}(\Gamma)$, it follows that
$\Gamma\rightarrow_{\text{hybrid}}\Gamma^{\prime}$. If $u$ has two edges, and
the self-loop is taken, the case $v=u$ is as above. Otherwise, if $u\neq v$,
the same transition is obtained in the hybrid model by taking
$A^{\prime}\in\rho_{\text{hybrid}}(\Gamma)$ where
$A^{\prime}=A\cup\\{\left\langle{(u,u)}:{1-i_{vu}}\right\rangle\\}$ (an
noticing that the denominator in $\mu_{\text{hybrid}}$ becomes $1$).

##  5 The Framework in Rewriting Logic

This section presents a rewrite theory that implements the set relations
framework in Section 3. Off-the-shelf definitions are provided to instantiate
the framework with opinion dynamic models, such as the ones introduced in
Section 4. This section assumes familiarity with rewriting logic [21] and
Maude [7] (see Section 2). The full Maude specification supporting the set
relations framework is available at [23].

A rewrite theory $\mathcal{R}$ (using Maude’s notation) is defined to
represent networks of agents and their opinions. The atomic relation (Equation
2) is defined as a non-executable rewrite rule, and the set relation framework
is implemented using the meta-programming facilities in Maude. The framework
is parametric on an update function ($\mu$) and a strategy ($\rho$), as
explained in Section 4. The rewrite theory $\mathcal{R}$ must be extended
equationally to instantiate such parameters.

###  5.1 Influences, Opinions, and State

An agent $a$ and its opinion $o_{a}$, and the influence of agent $a$ over
agent $b$ with weight $i_{ab}$, are specified with the help of the following
sorts and function symbols:

⬇

sorts Agent Opinion Edge .

op <_:_> : Agent Float -> Opinion [ctor] .

op <‘(_,_‘):_> : Agent Agent Float -> Edge [ctor] .

The user is expected to provide appropriate constructors for the sort Agent,
e.g., by extending $\mathcal{R}$ with the subsort relation subsort Nat < Agent
to use natural numbers as identifiers for agents.

Sets of agents, opinions, and edges (sorts SetAgent, SetOpinion, and SetEdge
respectively) are defined as “,”-separated sets of elements in the usual way.
A $G$-configuration $\Gamma=\Gamma_{o}\cup\Gamma_{i}$ is represented by a term
of sort Network, defining the set of agents’ opinions ($\Gamma_{o}$) and
influences ($\Gamma_{i}$) with the following sorts and function symbols:

⬇

sort Network .

op < nodes:_ ; edges:_ > : SetOpinion SetEdge -> Network [ctor] .

Analyzing opinion dynamics usually requires determining the number of
interactions between agents and the time needed to reach a given state. A term
of the form “$N~{}\texttt{in step: }t~{}\texttt{comm:}~{}nc$” of sort State
represents the state of a network $N$ at the current time-unit $t$, when a
number of interactions/communications $nc$ have taken place:

⬇

sort State .

op _ in step:_ comm:_ : Network Nat Nat -> State [ctor] .

###  5.2 Strategies and the Atomic Relation

The atomic relation $\rightarrow_{A}$ is parametric on a non-empty subset
$A\subseteq\Gamma_{i}$. A strategy identifies each one of such subsets at each
time-step. A SetSetEdge is a “;”-separated set of set of edges.

⬇

sort SetSetEdge . subsort NeSetEdge < SetSetEdge .

op mt : -> SetSetEdge [ctor] .

op _;_ : SetSetEdge SetSetEdge -> SetSetEdge [ctor assoc comm id: mt] .

Some distinguished SetSetEdges include the singleton with all the edges in the
network (De Groot model), the set containing only singletons (Gossip model)
and the set of non-empty subsets of edges (Hybrid model).

⬇

var SE : SetEdge . var E : Edge .

op deGroot : SetEdge -> SetSetEdge .

eq deGroot(SE) = SE .

op gossip : SetEdge -> SetSetEdge .

eq gossip(empty) = mt .

eq gossip((E, SE)) = E ; gossip(SE) .

op hybrid : SetEdge -> SetSetEdge .

eq hybrid(SE) = power-set(SE) \ empty .

op strategy : -> SetSetEdge . \--- user defined strategy

The operator strategy must be defined by the user to identify the subsets
$A\subseteq\Gamma_{i}$ available in each transition. This can be done, e.g.,
by adding the equation

eq strategy = gossip(edges) .

where edges is the set of edges in the network currently being modeled.

The atomic rewrite relation is captured by a non-executable rewrite rule that
updates the belief of a given AGENT ($u$ in Equation 2) when a set of EDGES
($A$) is selected and the current state of the system is STATE ($\Gamma$):

⬇

var AGENT : Agent . vars BELIEF BELIEF’ : Float . var STATE : State .

vars SETEDGE EDGES : SetEdge .

op update : State SetEdge Agent -> Float . \--- user defined $\mu$

crl [atomic] : < AGENT : BELIEF > => < AGENT : BELIEF’ >

if BELIEF’ := update(STATE, SETEDGE, AGENT) [nonexec] .

The function update ($\mu$ in Equation 2) must be specified by the user. The
framework provides instances of this function for the models presented in
Section 4.

An asynchronous, parallel, or synchronous rewrite step, depending on the
underlying strategy, is captured by the rewrite rule step below:

⬇

var SETNODE : SetNode . vars STEPS COMM : Nat .

op moduleName : -> Qid . \--- Name of the module with the user’s network

crl [step] : STATE => STATE’

if EDGES ; SSE := strategy /\

STATE’ := step([moduleName], STATE, EDGES) .

In this rule, the current STATE is updated to STATE’ by non-deterministically
selecting a set of EDGES from the set of set of edges available according to
the strategy. The function step below takes as parameters the meta-
representation of the user’s module defining the network (moduleName), the
current state, and the selected set of edges.

⬇

var SETAG : SetAgent . var SETOP : SetOpinion . var OP : Opinion .

op step : Module State SetAgent SetOpinion SetEdge -> State .

op step : Module State SetEdge -> State .

eq step(M, STATE, EDGES) = step(M, STATE, incidents(EDGES), empty, EDGES) .

eq step(M, STATE, empty, SETOP, EDGES) =

< nodes: (nodes(STATE) / SETOP) ; edges: edges(STATE) >

in step: (steps(STATE) \+ 1) comm: (comm(STATE) \+ | non-self(EDGES) |) .

eq step(M, STATE, (AGENT, SETAG), SETOP, EDGES) =

step(M, STATE, SETAG, (SETOP, next(M, AGENT, EDGES, STATE)), EDGES) .

The function step recursively computes the beliefs of the agents incident to EDGES. The updated beliefs are accumulated in the set of opinions SETOP. The opinions of the other agents remain as in STATE (operator /), and the number of steps and the number of communications are updated accordingly. The expression | non-self(.) | returns the number of edges that are not self-loops, and nodes(.) returns the opinions ($\Gamma_{o}$) in a state.

The function next computes the outcome of the transition
$\left\langle{u}:{o_{u}}\right\rangle\rightarrow_{A}\left\langle{u}:{o_{u}^{\prime}}\right\rangle$
by applying (metaApply) the rule atomic with the needed substitutions to make
this rule executable (and deterministic). Namely, it fixes the opinion to be
updated (AGENT and BELIEF), the current STATE and the set of EDGES to be
considered during the update.

⬇

op next : Module Agent SetEdge State -> Opinion .

ceq next(M, AGENT, EDGES, STATE) = OP

if SUBS := ’AGENT:Agent <- upTerm(AGENT) ;

’BELIEF:Float <- upTerm(opinion(AGENT, STATE)) ;

’STATE:State <- upTerm(STATE) ;

’EDGES:SetEdge <- upTerm(EDGES) /\

RES? := metaApply(M, upTerm(< AGENT : opinion(AGENT, STATE) >),

’atomic, SUBS, 0) /\

OP := if RES? == failure then error

else downTerm(getTerm(RES?), error) fi .

The opinion function returns the opinion of an agent in a given state.

##  6 Experimentation

This section shows how Maude and some of its tools can be used to analyze
instantiated versions of the rewrite theory $\mathcal{R}$ (see Section 5) to
better understand the evolution of opinions in networks of agents. Of special
interest is checking the (im)possibility of reaching a consensus (i.e.,
agent’s opinions converge to a given value) or stability of the systems,
computing the number of steps to reach consensus, computing an optimal
strategy to reach consensus, measuring the polarization of the system at each
time-step, among others. It is noticed that for De Groot and Gossip-like
models, there are theoretical results identifying topological conditions that
guarantee consensus. In particular, in these models, the agents reach
consensus if the graph is strongly connected and aperiodic (i.e., the greatest
common divisor of the lengths of its cycles is one) [14].

###  6.1 Finding Consensus

Let Example-DG be the module/theory extending $\mathcal{R}$ with the following
operators and equations:

⬇

op init : -> Network . \--- Initial state (as in Fig 1)

eq init = < nodes: ... ; edges: ... > in step: 0 comm: 0 .

eq moduleName = ’Example-DG . \--- Name of the theory

\--- Predefined $\mu$ for De Groot

eq update(STATE, SETEDGE, AGENT) = deGrootUpdate(STATE, SETEDGE, AGENT) .

eq strategy = deGroot(edges(init)) . \--- De Groot strategy

The following command answers the question of whether it is possible to reach
a consensus from the initial state. (Function consensus(.) checks if all
opinions $o_{i}$ and $o_{j}$ in a given state satisfy
$|o_{i}-o_{j}|<\epsilon$, where $\epsilon$ is an error bound).

⬇

Maude> search [1] init =>* STATE such that consensus(STATE) .

Solution 1 (state 34)

STATE \--> < nodes: < 0 : 4.80e-1 >, < 1 : 4.79e-1 >, < 2 : 4.79e-1 >, ...

edges: <(0,1): 5.99e-1 >, <(0,2): 4.00e-1 >, ... >

in step: 34 comm: 272

The consensus about the given proposition is approximately $0.48$ and it is
reached in 34 steps. Since in the De Groot model all the 12 edges are
considered in each interaction, there is a total of 272 = $34\times 8$
communications (the interactions on the self-loops are not considered in that
counting). Note that an application of rule step in this case is completely
deterministic (the strategy considers only one possible outcome, including all
the edges of the network).

Let Example-H be as Example-DG, but considering the strategy and update
functions for the hybrid model. As explained in Section 4.4, the Hybrid model
exhibits the maximum degree of non-determinism. Using search to check the
existence of a reachable state satisfying consensus for the system in Figure 1
(12 edges) becomes unfeasible: a state may have up to 4095 (non-empty subsets
of $\Gamma_{i}$) successor states. Certainly, for this network, a solution
must exist due to the above output of the search command and the fact that
${\rightarrow_{\text{DeGroot}}}\subseteq{\rightarrow_{\text{hybrid}}}$.

Consider the following rewrite rule and expression in Maude’s strategy
language:

⬇

crl [step’] : STATE => STATE’

if STATE’ := step([moduleName], STATE, EDGES) [nonexec] .

var STR : SetSetEdge .

strat round : SetSetEdge @ State .

sd round(EDGES ; STR) := (match STATE s.t. consensus(STATE))

or-else step’[EDGES <\- EDGES] ; round(STR) .

Unlike step, rule step’ does not use the model strategy to select the set of
EDGES that will be used to compute the next state (and hence, it is non
executable). The Maude’s strategy round checks whether the current state
satisfies consensus and stops. Otherwise, it non-deterministically chooses a
set EDGES, applies the rule step’ instantiating the set of edges with that
particular set, and it is recursively called without EDGES. In other words,
round starts with a set of possible interactions and it allows for these
interactions to happen only once. This is certainly one of the possible
behaviors that can be observed with the Hybrid model. Using this strategy, it
is possible to find some states that satisfy consensus and answer the question
whether by selecting some groups of agents (non necessarily disjoint) that,
interacting only once, may lead to a consensus. (Function filter>=(n,STR)
returns the sets in STR with cardinality at least $n$).

⬇

Maude> dsrew [1] init using round(hybrid(edges)) .

Solution 1

result State: < nodes: < 0 : 0.0 >, ... edges: ... > in step: 8 comm: 13 .

Maude> dsrew [1] init using round(filter>=(6, hybrid(edges))) .

Solution 1

result State: < nodes: < 0 : 1.50e-1 >, ... > in step: 21 comm: 88 .

As expected, because of the non-deterministic nature of the Hybrid model, the
value of consensus (and the number of steps to reach such a state) can heavily
depend on the choice of edges at each step. In the first output returned by
dsrew in the first command, all the sets considered by round included edges
where $a$ acts as an influencer and the edge
$f\allowbreak\mathrel{\mathop{\hbox to11.99998pt{\rightarrowfill}}\limits}a$
is never selected. This explains the value of the consensus, where the opinion
of $a$ was propagated to her neighbors. In the send command, larger groups are
chosen to interact, and the edge $f\allowbreak\mathrel{\mathop{\hbox
to11.99998pt{\rightarrowfill}}\limits}a$ is selected in 4 out of the 21
interactions. Hence, $a$ eventually changes her opinion.

###  6.2 Statistical Analysis

An alternative approach to deal with the inherent state explosion problem when
analyzing $\mathcal{R}$ is to perform statistical model checking. In the
following, the tool umaudemc [26] is used for such a purpose. The umaudemc
command scheck enables Monte-Carlo simulations of a rewrite theory extended
with probabilities; it estimates the value of a quantitative temporal
expression written in the query language QuaTEx [1].

Consider the following QuaTEx expression that computes the probability of
reaching a consensus before $N$ communications:

⬇

Prob-C(N) = if (s.rval("consensus(S)")) then 1.0 else

if (s.rval("comm(S)") <= N) then # Prob-C(N) else 0.0 fi fi;

The two commands below estimate the probability of reaching consensus before
30 (QuaTEx formula E[Prob(30)]) and 20 communications, respectively, in the
running example when the gossip-based model is considered. The confidence
level of these analyses is $95\%$ and the same probability is assigned to
every successor state (uniform).

⬇

umaudemc scheck ex-gossip init formula -a 0.05 -d 0.01 \--assign uniform

($\mu$ = 0.587)

umaudemc scheck ex-gossip init formula -a 0.05 -d 0.01 \--assign uniform

($\mu$ = 0.348)

As expected, reducing the maximum number of communications decreases the
changes of reaching a consensus state.

The authors in [5] hypothesize that the less dispersed opinion becomes, the
easier it will be to reach consensus. In fact the variance, a standard measure
of dispersion, is used as a measure of opinion polarization in social networks
[5]. The following commands aim at testing such a hypothesis in the running
example when considering the hybrid model:

⬇

umaudemc scheck example-H init ... \--assign uniform

($\mu$ = 0.901)

umaudemc scheck example-H init ... \--assign "term(variance(L,R))"

($\mu$ = 1.0)

umaudemc scheck example-H init ... \--assign "term(distance(L,R))"

($\mu$ = 0.987)

These commands estimate the probability of reaching consensus before 300
communications (E[Prob(300)]). In the first case, all the successor states are
assigned the same probability. In the second, successor states whose set of
chosen agents has higher variance are assigned higher probabilities. In the
third command, successor states whose set of chosen agents are more
_polarized_ , in the sense that the distance between the maximal and the
minimal opinions is bigger, are assigned higher probabilities. These results
confirm the hypothesis that it is more likely (1.0 vs 0.9) to reach consensus
sooner when communications of agents with more distant opinions is encouraged
to reduce dispersion of opinions.

##  7 Concluding Remarks

This paper presented a unified framework for dynamic opinion models. Such
models are tools to analyze the evolution of opinion values, about a given
topic, in a network of agents whose opinion may be influenced by other agents.
Set relations, which are used for specifying and analyzing concurrent behavior
in collections of agents, are the formalism used to unify the modeling of
these systems. This framework relies on two mechanisms, namely, an atomic
relation that updates the opinion of single agents based on a collection of
interactions and a strategy defining the collections of interactions to be
considered. The framework is formally specified as a rewrite theory, which is
expected to be instantiated for the opinion dynamic model of interest. Three
different dynamic opinion models (De Groot, goossip-like, and hybrid) are
shown to be instances of this framework. Experiments on these models show that
statistical model checking is a promising alternative to tackle the state
explosion problem when analyzing models with a high degree of non-determinism,
such is the case of the hybrid model. To the best of the authors’ knowledge,
this is the first documented effort to make available concurrency theory,
techniques, and tools for the specification and analysis of opinion dynamics
models and properties such as polarization and consensus.

The ultimate goal of making available computational ideas and approaches for
analyzing phenomena in social networks requires (significant) additional work.
First, a more in-depth exploration of properties related to these phenomena in
social networks is required. This may lead to the proposal of new temporal and
probabilistic properties that cannot be handled with current techniques and
approaches supporting the opinion dynamic modeling community, but that may be
highly supported by the developments in concurrency and computational logics.
Second, extensions to the current framework in terms of more general dynamic
networks (i.e., the value of influences can change), temporal networks (i.e.,
nodes and edges can appear and disappear), and the inclusion of several
topics/propositions that may share causal relations are in order. Third, more
experimental validation is required, ideally with data gathered from real
social networks. Fourth, building on the abstract relations proposed here,
techniques from concurrency theory become available for the analysis of social
systems. It is worth exploring standard concurrency techniques such as
bisimulation and testing equivalences to answer questions such as whether two
social systems ought to be equivalent and whether there is a social context,
represented as a social system, that can tell the difference between two other
social systems.

## References

  * [1] Agha, G., Meseguer, J., Sen, K.: PMaude: Rewrite-based Specification Language for Probabilistic Object Systems. ENTCS 153(2), 213–239 (May 2006)
  * [2] Alvim, M.S., Amorim, B., Knight, S., Quintero, S., Valencia, F.: A formal model for polarization under confirmation bias in social networks. Log. Methods Comput. Sci. 19(1) (2023)
  * [3] Ballard, A.O., DeTamble, R., Dorsey, S., Heseltine, M., Johnson, M.: Dynamics of polarizing rhetoric in congressional tweets. Legislative Studies Quarterly 48(1), 105–144 (2023)
  * [4] Beaufort, M.: Digital media, political polarization and challenges to democracy. Information, Communication & Society 21(7), 915–920 (2018)
  * [5] Bramson, A., Grim, P., Singer, D.J., Berger, W.J., Sack, G., Fisher, S., Flocken, C., Holman, B.: Understanding polarization: Meanings, measures, and model evaluation. Philosophy of Science 84(1), 115–159 (2017)
  * [6] Center for Strategic and International Studies: The #MilkTeaAlliance in Southeast Asia: Digital revolution and repression in Myanmar and Thailand (April 2021), https://www.csis.org/blogs/new-perspectives-asia/milkteaalliance-southeast-asia-digital-revolution-and-repression, visited 12-30-2023
  * [7] Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Talcott, C.: All About Maude - A High-Performance Logical Framework, LNCS, vol. 4350. Springer (2007)
  * [8] Das, A., Gollapudi, S., Munagala, K.: Modeling opinion dynamics in social networks. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining. p. 403–412. Association for Computing Machinery, New York, NY, USA (2014)
  * [9] Degroot, M.H.: Reaching a consensus. Journal of the American Statistical Association 69(345), 118–121 (1974)
  * [10] Fagnani, F., Zampieri, S.: Randomized consensus algorithms over large scale networks. In: 2007 Information Theory and Applications Workshop. pp. 150–159 (2007)
  * [11] Fitriani, Habib, M.: Social media and the fight for political influence in southeast asia (August 2023), https://thediplomat.com/2023/08/social-media-and-the-fight-for-political-influence-in-southeast-asia, visited 12-30-2023
  * [12] Foundation, T.A.: Violent Conflict, Tech Companies, and Social Media in Southeast Asia: Key Dynamics and Responses. The Asia Foundation, San Francisco, USA (2020)
  * [13] Garrett, R.K.: The “echo chamber” distraction: Disinformation campaigns are the problem, not audience fragmentation. Journal of Applied Research in Memory and Cognition 6 (2017)
  * [14] Golub, B., Sadler, E.: Learning in social networks. Social Science Research Network (SSRN) (02 2017), http://dx.doi.org/10.2139/ssrn.2919146
  * [15] Gordon-Zolov, T.: Chile’s estallido social and the art of protest. Sociologica 17(1), 41–55 (January 2023)
  * [16] Gupta, S., Chauhan, V.: Understanding the role of social networking sites in political marketing. Jindal Journal of Business Research 12(1), 58–72 (2023)
  * [17] Haoxiang Xia, Huili Wang, Z.X.: Opinion dynamics: A multidisciplinary review and perspective on future research. International Journal of Knowledge and Systems Science 2(4), 72–91 (2023)
  * [18] Iversen, T., Soskice, D.: Information, inequality, and mass polarization: Ideology in advanced democracies. Comparative Political Studies 48(13), 1781–1813 (2015)
  * [19] Kirby, E.: The city getting rich from fake news. BBC News Documentary (05 2017), https://www.bbc.com/news/magazine-38168281
  * [20] Lynch, M.: After the arab spring: How the media trashed the transitions. Journal of Democracy 26(4), 90–99 (2015)
  * [21] Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. Theoretical Computer Science 96(1), 73–155 (1992)
  * [22] Neverov, K., Budko, D.: Social networks and public policy: Place for public dialogue? In: Proceedings of the International Conference IMS-2017. p. 189–194. Association for Computing Machinery, New York, NY, USA (2017)
  * [23] Olarte, C., Ramírez, C., Rocha, C., Valencia, F.: Opinion dynamic modeling as concurrent set relations in rewriting logic, https://github.com/promueva/maude-opinion-model
  * [24] Rocha, C., Muñoz, C.A.: Synchronous set relations in rewriting logic. Science of Computer Programming 92, 211–228 (2014)
  * [25] Rocha, C., Muñoz, C.A., Dowek, G.: A formal library of set relations and its application to synchronous languages. Theoretical Computer Science 412(37), 4853–4866 (2011)
  * [26] Rubio, R., Martí-Oliet, N., Pita, I., Verdejo, A.: Strategies, model checking and branching-time properties in maude. J. Log. Algebraic Methods Program. 123, 100700 (2021)
  * [27] Rubio, R., Martí-Oliet, N., Pita, I., Verdejo, A.: Qmaude: Quantitative specification and verification in rewriting logic. In: Chechik, M., Katoen, J., Leucker, M. (eds.) FM 2023. LNCS, vol. 14000, pp. 240–259. Springer (2023)
  * [28] Sarma, P., Hazarika, T.: Social media and election campaigns: An analysis of the usage of twitter during the 2021 assam assembly elections. International Journal of Social Science Research and Review 6(2), 96–117 (January 2023)
  * [29] Suresh, V.P., Nogara, G., Cardoso, F., Cresci, S., Giordano, S., Luceri, L.: Tracking fringe and coordinated activity on twitter leading up to the us capitol attack (2023)
  * [30] Wikipedia Foundation: 2021 Colombian protests, https://en.wikipedia.org/wiki/2021_Colombian_protests, visited 12-30-2023