# Quantifying Human Priors over Social and Navigation Networks

Gecia Bravo-Hermsdorff

###### Abstract

Human knowledge is largely implicit and relational — do we have a friend in
common? can I walk from here to there? In this work, we leverage the
combinatorial structure of graphs to quantify human priors over such
relational data. Our experiments focus on two domains that have been
continuously relevant over evolutionary timescales: social interaction and
spatial navigation. We find that some features of the inferred priors are
remarkably consistent, such as the tendency for sparsity as a function of
graph size. Other features are domain-specific, such as the propensity for
triadic closure in social interactions. More broadly, our work demonstrates
how nonclassical statistical analysis of indirect behavioral experiments can
be used to efficiently model latent biases in the data.

human priors, relational data, graphs, inductive biases, social networks,
navigation networks

##  1 Brains Rely on Efficient Priors

A foundational result in the fields of artificial intelligence, neuroscience,
and psychology is the establishing of the central role played by inductive
biases or priors in learning (Shiffrin et al., 2020; Wolpert, 2021). The
importance of priors cannot be understated; indeed, their quantification
elucidates many aspects of our perception and cognition.

The efficient coding hypothesis.  Examples of how priors inform neuroscience
can often be understood through the lens of the “efficient coding hypothesis”,
which states that neural representations have adapted to efficiently encode
the relevant statistics of our environment (Barlow et al., 1961).

Several decades of work investigating and refining this hypothesis have
contributed to major advances in our understanding of the neural code
(Manookin & Rieke, 2023). For example, many properties of mammalian visual
cells (such as sensitivity to orientation and spatial frequency) have been
shown to be optimized for transmitting information about natural scenes
(Simoncelli, 2003; Field, 1989).

Likewise, the mammalian cochlea and auditory nerve fibers have properties that
allow for efficient representation of the acoustic structure of speech and
other natural sounds (Lewicki, 2002; McDermott et al., 2013). Other
computations, such as visual attention (Orbán et al., 2008) and working memory
(Mathy & Feldman, 2012; Brady et al., 2009), display analogous properties.

Visual priors color our perception.  This principle of efficient coding also
explains several well-known visual illusions (Howe & Purves, 2005; Howe et
al., 2005), evidentiating a general and important computational tradeoff in
biology: priors cannot be both exhaustive and efficient. That is, by
efficiently distinguishing relevant visual information, our priors render us
blind to insignificant differences. Might there be similar “illusions” with
respect to our priors over the structure of connections?

##  2 Tasks are Often Relational

From roads between places, websites on the internet, words in a text, and
friendships between people, humans are routinely confronted with a web of
things (nodes) structured in terms of their relations (edges). Despite the
pervasiveness of networks in our lives, knowledge of our priors about them is
rather sparse.

However, one notable paradigm is the learning of network structure from random
walks (Lynn & Bassett, 2020; Klishin & Bassett, 2022). This approach typically
consists of showing nodes to participants in a temporal sequence that respects
the structure of the network (such as samples of random walks), and comparing
the ease with which they learn these transitions for several different
networks (Schapiro et al., 2013; Tompson et al., 2019).

Complementing these detailed experiments on specific networks, our work
focuses on quantifying humans’ initial beliefs about all such networks. The
motivating question is: given a set of $n$ things and minimal or no
information about how they relate, what is the prior likelihood assigned to
each of the many possible patterns of connections?

Why we focus on navigation and social networks.  Tasks related to spatial
navigation and social interaction have been quotidian over evolutionary
timescales. Thus, our brains have likely adapted to efficiently encode them.
Indeed, there is much evidence supporting this hypothesis. For example, the
hippocampus encodes a spatial map of the environment (Maguire et al., 2003;
Eichenbaum, 2017). Likewise, there are brain regions specialized in the
processing of social information and theory of mind (i.e., the modeling of
others’ mental states) (Richardson, 2019; Devaine et al., 2014).

Additionally, these two domains are qualitatively different: spatial
navigation networks are constrained by physical space, whereas social networks
are more abstract and interconnected. Comparing the similarities and
differences of our priors in these domains could aid in building a more
complete understanding of their associated neural processes.

Key contributions.  We develop a framework for quantifying human priors over
relational data (sections 3 and 4), and summarize the results in a meaningful
way (section 5).

##  3 Overview of our Framework

The number of unique configurations of connections between $n$ nodes grows
superexponentially111For a feeling for the scaling, see table 3 (appendix
B.2). (Sloane, 1964). This poses several difficulties in quantifying human
priors over such graphs:

  1. 1.

engaging human attention in experiments that involve reasoning about such a
large number of possibilities;

  2. 2.

properly sampling the space of graphs; and

  3. 3.

meaningfully summarizing and comparing priors over such a high-dimensional
space.

We now provide a brief overview of how our framework overcomes these
challenges, expanding on the details in the subsequent sections.

###  3.1 Engaging Human Attention

We built an online experimental platform that allowed participants to easily
draw their inferences about obscured relations in a graph (demo video and fig.
1). In brief, participants were shown “partial graphs”, containing all the
nodes, but only some of the pairwise relations between them, and were then
asked to infer the existence (or absence) of the remaining relations. The
meaning of these graphs was given by one of the four cover stories that served
as the context for our experiments (table 1).

Deploying this platform in MTurk (Amazon Web Services, 2010), we carefully
curated a large amount of human data in experiments involving social and
spatial navigation networks (over $1200$ participants and $15000$ data
points). To ensure that the final design was as engaging and intuitive as
possible, we ran a variety of pilot experiments (over $300$ participants).
This effort paid off: for the final experiments, the post-questionnaire
feedback was quite positive (several MTurk workers even sent personal emails
about how enjoyable the “game” was!), and the data were of high quality (see
appendix A.4 for details).

Table 1: Content of the four cover stories of our experiments. Participants
were asked to infer the presence or absence of
obscured relations between pairs of nodes in a context.  domain | context | nodes | relations
---|---|---|---
social | class | students | friendships
work | coworkers | friendships
navigation | city | neighborhoods | borders
park | nature sites | trails

Figure 1:  Screenshots of our main experimental interface for two cover
stories: social class (left) and navigation park (right).
Our online platform allowed participants to easily “draw” their inferences
about the obscured relations of a graph (demo video). Note that the two images
above are nearly identical: to make the comparisons as fair as possible, we
made the experiments identical in every aspect, except for the text
specifically related to each cover story. See appendix A for a detailed
description of these experiments and high-resolution versions of these images
(figs. 7 class and 8 park).

###  3.2 Sampling the Space of Graphs

For the first participants, we initialized our experiments using graphs
spanning a wide range of edge densities. From these, we generated partial
graphs, and asked participants to infer the remaining relations. We then
repeatedly used the responses from the previous participants to generate
partial graphs for the next participants (fig. 2). In essence, our online
platform instantiates a “Markov Chain Monte Carlo algorithm with People
(MCMCP)”, with multiple chains being built in parallel.

Standard implementations of MCMCP experiments model the (shared) prior of the
participants by sampling (some of) their responses from (sufficiently long)
experimental chains. Here, we use the data more efficiently (figs. 12 and 13)
by leveraging the graphical structure to fit the aggregated responses of
participants to a natural Bayesian model (section 5.2). In particular, we
parameterize their priors using a hierarchical family of maximum entropy
distributions over graphs (sections 5.3 and 5.4), which offer “smooth”222In
the sense that graphs that differ by fewer edges are assigned similar
probabilities. low-dimensional parameterizations of the high-dimensional space
of graphs (figs. 14 and 15).

###  3.3 Summarizing and Interpreting Priors over Graphs

Graph cumulants (Bravo-Hermsdorff et al., 2021; Gunderson & Bravo-Hermsdorff,
2020) capture what is typically meant by “substructure” or “motif”: a subgraph
$g$ whose prevalence in a distribution over graphs is statistically different
from that which would be expected due to the prevalence of smaller subgraphs
contained in $g$. Here, we compare the inferred priors using the scaled
version of graph cumulants, which additionally takes into account the density
of connections (figs. 4 and 5).

##  4 Experimental Design

In this section, we provide a brief overview of the literature on MCMC with
People (sections 4.1.1 and 4.1.2), the general framework to which our method
can be applied. We then describe our experiments (sections 4.1.3 and 4.2).

###  4.1 Markov Chain Monte Carlo with People (MCMCP)

####  4.1.1 Related Work

Iterated learning refers to the process whereby a participant learns from data
generated by another participant, who themselves learned it the same way, and
so on. It is a highly-researched and ubiquitous psychological phenomenon —
language and cultural evolution being two important examples (Kirby et al.,
2014; Morgan et al., 2020). Under some assumptions (see appendix D), iterated
learning can be modelled as a Markov Chain Monte Carlo algorithm instantiated
by the Participants (algorithm 1) that has as its stationary distribution
their shared prior over the relevant space (Griffiths & Kalish, 2007).

Algorithm 1 Generic MCMCP Experiment

Initialize: $h\text{ypothesis}$0

for $t=1$ to $T$ do

$e\text{vidence}$t $=$ Expmnt$($$h\text{ypothesis}$t-1$)$

$h\text{ypothesis}$t $=$ Ptcpntt$($$e\text{vidence}$t$)$

end for

This MCMCP model has been employed to quantify human priors in a variety of
contexts, such as: locations in visual scenes (Langlois et al., 2021);
variations in facial features (Uddenberg & Scholl, 2018); strengths of causal
relationships (Yeung & Griffiths, 2015); moral categories of words in ethics
(Hsu et al., 2019); names of colors (Xu et al., 2013); and kernels for
Gaussian processes (Schulz et al., 2017). This framework has also been applied
to quantify priors of (non-human) large language models (Yamakoshi et al.,
2022; Marjieh et al., 2022).

####  4.1.2 The MCMCP Model

Let ${\mathcal{E}}$ be the space of all combinations of
$\mathcal{E}\text{vidence}$ participants might be given in the experiment. And
let ${\mathcal{H}}$ be the space of all $\mathcal{H}\text{ypotheses}$ that the
participants might consider when giving their responses. We assume that both
spaces are discrete and finite, and denote the space of probability
distributions over them as ${P(\mathcal{E})}$ and ${P(\mathcal{H})}$,
respectively.

The Experimentalist uses the $h\text{ypothesis}$ of the previous participant
(i.e., their response) to generate noisy/partial $e\text{vidence}$ to give to
the next participant. This process is a probabilistic map from
$\mathcal{H}\\!\rightarrow\\!\mathcal{E}$, denoted in algorithm 1 as
Expmnt$(\cdot)$, with associated probability distribution ${p(e|h)}$.

Given a prior distribution ${\pi\in P(\mathcal{H})}$, and presented with
$e\text{vidence}$ ${e\in\mathcal{E}}$, a “Bayesian” Participant will sample a
$h\text{ypothesis}$ ${h\in\mathcal{H}}$ from their posterior distribution as
their response:

$p(h|e)=\frac{p(e|h)\pi(h)}{\sum_{h\in\mathcal{H}}p(e|h)\pi(h)}$

This process is a probabilistic map from
$\mathcal{E}\\!\rightarrow\\!\mathcal{H}$, and is denoted in algorithm 1 as
Ptcpnt$(\cdot)$.

If all participants have a shared prior distribution ${\pi}$ over the
$\mathcal{H}\text{ypotheses}$, the composition of these stochastic maps
${\textsc{Ptcpnt}(\textsc{Expmnt}(\cdot))\\!:\\!P(\mathcal{H})\\!\rightarrow\\!P(\mathcal{H})}$
has this prior ${\pi}$ as its unique stationary distribution (given the
standard technical conditions on the Markov chain, see appendix D.1).

####  4.1.3 Relational MCMCP

Figure 2 illustrates our algorithm for generating MCMCP experiments on graphs.
It consists of the following steps:

  1. 0.

Initialize the chain with a graph containing $n$ nodes and $\binom{n}{2}$
pairwise relations between them (e.g., the friendships, or lack thereof,
between students in a class).

  2. 1.

Obscure a random fraction $b$ of this graph’s pairwise relations (e.g.,
$b=\nicefrac{{3}}{{10}}$ in fig. 2).

  3. 2.

Based on this “partial graph”, ask the participant to infer the obscured
relations.

  4. 3.

Update the graph based on their response.

  5. 4.

Repeat the sequence of steps 1, 2, and 3, each time with a new participant.

Our experiments focused on simple graphs: undirected unweighted graphs with no
self-loops or parallel edges.333So, a simple graph $G$ with $n$ nodes has
$\binom{n}{2}$ pairwise relations.

For a given chain of our experiment, the space of
$\mathcal{H}\text{ypotheses}$ is ${\mathcal{G}_{n}}$, the set of simple graphs
with $n$ nodes, and $G_{t}\in\mathcal{G}_{n}$ denotes the response of the
participant in the $t^{\text{th}}$ iteration/round. The space of
$\mathcal{E}\text{vidence}$ is
${\mathcal{P{\kern-2.0pt}G}_{n,\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}}}$,
the set of all partial graphs with $n$ nodes and
$\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}$ of the pairwise
relations obscured, and $P{\kern-2.0pt}G_{t}\in\mathcal{P{\kern-2.0pt}G}$
denotes the specific partial graph shown to the participant in the
$t^{\text{th}}$ iteration/round. The map
${\textsc{Expmnt}:\mathcal{G}_{n}\rightarrow\mathcal{P{\kern-2.0pt}G}_{n,\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}}}$
takes a graph on $n$ nodes, and makes a partial graph by randomly obscuring
$\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}$ pairwise relations.

Figure 2: Algorithm for generating a round of our experiment. The context of
the experiment was given by one of the four cover stories in table 1, and an
interface allowed participants to easily manipulate the graphs (see demo video
and fig. 1). Each participant did multiple rounds, corresponding to different
chains.

###  4.2 Experimental Platform and Cover Stories

We developed an online experimental platform and recruited participants using
MTurk. Our platform allows participants to easily draw their inferences about
the obscured relations in the graph (demo video) and allocates them to one of
multiple experimental chains in real time. Each experiment had one of four
different cover stories: two in the social domain and two in the navigation
domain (table 1).

In a given experiment, a participant gave responses for many rounds, where
each round was part of a different chain. A response was included in a chain
(and thereby used to generate the partial graph for the next participant) only
if it passed judiciously-chosen criteria. In appendix A, we provide a more
detailed description of the experiments, the data collection, and the data
cleaning procedures.

The experiment begins with an introduction about the particular cover story
and poses several questions to the participant to ensure their understanding.
After a video demonstration of the interactive platform, each round begins
with the partial graph at the center of the interactive interface and a list
of the “unobscured” relations at the top of the screen. Using this interface,
the participant were able to move the nodes and add/remove edges (fig. 1).

Once the participant submitted their response, a question appears about which
node(s) they thought to be the most/least important (asked in a variety of
ways). To incentivize participants to respond using their true prior, they
were told during the introduction that there is a ground truth and they would
be rewarded for correctly guessing the relations that were obscured (see
appendix A.5 for the complete text). Clearly, as there is not such a ground
truth, their responses did not influence their final payoff (though their
level of engagement did, see appendix A.4).

As the analysis assumes that the nodes are exchangeable, we aimed to make
their labels as neutral as possible. To this end, we randomly selected the
node labels from a long list of last names, while ensuring that no name was
repeated during an experiment. Participants were clearly instructed that the
node labels were fictitious names, and that they provided no information about
the “correct” answers.

##  5 Data Analysis

In this section, we describe how we analyze the data from our experiments. We
first discuss how data from MCMCP experiments is typically used to obtain
priors and some of the limitations of this standard approach. We then
introduce our method, which alleviates these issues by exploiting the Bayesian
assumption (section 5.2), and uses the combinatorial structure of graphs to
fit the data with a natural family of maximum entropy models (sections 5.3,
and 5.4). We end this section by describing how we quantify and compare
relevant characteristics of the inferred priors (sections 5.5, 5.6, and 5.7).

###  5.1 Limitations of the Standard MCMCP Approach

Typically, studies employing MCMCP experiments use the participants’ responses
towards the end of the chains as a proxy for their prior. Indeed, according to
the assumptions of the MCMCP model, the stationary distribution of (Bayesian)
participants’ responses approximates their (shared) prior over the relevant
$\mathcal{H}\text{ypotheses}$.

However, this approach wastes much of the collected data for two reasons.
First, one must discard the initial responses until the chain has
(hopefully444Determining convergence can be highly nontrivial in certain
cases, especially when the state space is large (Roy, 2020).) converged
(sufficiently close555This can also be nontrivial to determine.) to its
stationary distribution, the so-called “burn-in” period (Raftery & Lewis,
1996). Second, as the responses are correlated, one cannot treat them as
completely independent samples, and thus has fewer effective samples (Hsu et
al., 2015). Moreover, the number of iterations/rounds required for an
experimental chain to be sufficiently close to its stationary distribution
(i.e., its mixing time) is highly dependent on the probabilistic mapping
${\textsc{Expmnt}\\!:\\!\mathcal{H}\\!\rightarrow\\!\mathcal{E}}$ used to
generate the experiments, and on the participants’ (unknown) prior ${\pi}$
(see figs. 10 and 11).

While this might not always be a problem (such as when samples can be
efficiently generated by a computer), using human participants to generate
samples in MCMCP often presents a significant bottleneck (controlling
electrons is typically simpler than controlling human attention).

###  5.2 Leveraging the Bayesian Ansatz

Instead of using (a few of) the observed responses ${h_{t}}$ to approximate
the prior, we exploit the fact that the paired data ${(e_{t}\rightarrow
h_{t})}$ are more informative than these ${h_{t}}$ alone. Specifically, as the
traditional approach already assumes that the participants are Bayesian with
the same prior, we make explicit use of this implicit assumption by modelling
the paired data ${(e_{t}\rightarrow h_{t})}$ in terms of the transition matrix
$p(e|h)$ induced by an underlying shared prior $\pi$. In appendix E.1, we show
that this fitting approach alleviates typical problems of standard MCMCP data
analysis: estimating the mixing time (fig. 12) and correlated samples (fig.
13).

An important hurdle still remains: for this fitting approach to work, one must
be able to parameterize the priors. However, as mentioned in section 3, the
number of nonisomorphic graphs grows superexponentially in their number of
nodes ${n}$. It is thus unwise to fit a multinomial distribution to each of
these graphs, thereby, effectively treating them as incomparable variables. To
obtain informative priors, we must use a meaningful low-dimensional smooth
parameterization of probability distributions over graphs, such that graphs
that differ by fewer edges are given similar probabilities.

We now describe a natural hierarchical family of network models that provides
such a parameterization (section 5.3) and how we fit these models to the data
(section 5.4). In appendix E.2, we show that this choice of parameterization
for the priors leads to a more accurate recovery of the prior in simulated
data (where the ground truth is known) (fig. 14) and improved generalization
in real data (fig. 15).

###  5.3 Modeling the Priors using a Hierarchy of
Maximum Entropy Distributions over Graphs

Intuitively, given a set of constraints, the maximum entropy distribution is
the “simplest” of those that satisfy the constraints (Jaynes, 1957a, b).
Maximum entropy distributions appear in every corner of science; from uniform
to Gaussian, beta to binomial, gamma to Poisson and more, nearly all named
distributions maximize entropy in some sense.

For simple graphs with $n$ nodes, the simplest statistic is the edge density
$\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{{{\pgfsys@beginscope\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap{} {}
\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.5pt}{0.0pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. The maximum
entropy distribution corresponding to this statistic is the Erdős–Rényi model
$\textrm{ER}_{n,\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$, in which a
connection appears between each of the ${\binom{n}{2}}$ pairs of the nodes
independently with the same probability $\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. In particular, the
$\textrm{ER}_{n,\nicefrac{{1}}{{2}}}$ distribution assigns uniform probability
to each of the graphs with $n$ labeled nodes, and serves as the base measure
for any maximum entropy distribution over simple graphs with $n$ nodes (node-
labeled or not).

These distributions are known as Exponential Random Graphs Models (ERGMs).
They have been extensively studied theoretically (Chatterjee & Diaconis, 2013;
Cimini et al., 2019) and applied to a wide range of real networks (Lusher et
al., 2013; Lehmann et al., 2021). Although it is possible to define an ERGM by
prescribing any set of realizable constraints, a natural and frequent choice
(Lovász, 2012; Lauritzen et al., 2018) is to prescribe the counts/densities of
small subgraphs, such as edges (), “cherries” (), and triangles ().

To model the priors, we use the following family of ERGMs:

$\pi\big{(}G\big{)}\,\propto\,\textrm{ER}_{n,\nicefrac{{1}}{{2}}}\big{(}G\big{)}\,\times\,\exp\Bigg{\\{}\sum_{g:E(g)\leq
r}\beta_{g}\mu_{g}\kern-1.5pt\big{(}G\big{)}\Bigg{\\}}$ (1)

where $G$ is a simple graph with $n$ nodes; $\pi(G)$ is a distribution over
such graphs; $\mu_{g}\kern-1.5pt(G)$ is the (injective homomorphism666
Consider all injective maps (so no node overlapping) from the nodes of $g$
into the nodes of $G$, $\mu_{g}\kern-1.5pt(G)$ is the fraction of such maps
for which every edge in $g$ appears in the corresponding location in $G$
(i.e., we do not care about the absence of edges).) density of the subgraph
$g$ in the graph $G$; $\beta_{g}$ is the parameter associated with $\mu_{g}$;
and $g:E(g)\leq r$ are all subgraphs with at most $r$ edges.

That is, this model constrains the densities of all subgraphs with at most $r$
edges (hence the sum over $g:E(g)\leq r$). This choice induces a natural and
convenient hierarchy of network models for the priors. In particular, the
parameter $r$ controls the expressivity of the model. For example, $r=1$
constrains only the edge density $\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, corresponding to
the simplest network model $\textrm{ER}_{n,\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$. Likewise, $r=6$
constrains the density of all subgraphs with $6$ edges, leading to a far more
complex model for the prior (e.g., this model can exactly specify the
probability of all graphs with $4$ nodes).

###  5.4 Fitting and Selecting the Model

When fitting a model to the prior, we consider all data related to a
particular cover story and a given number of nodes. Specifically, we aggregate
data from all such chains regardless of fraction of relations obscured $b$, as
when we split the data, there were no significant differences.

For each subgraph $g$ in the model (eq. 1), there is a corresponding
(conjugate) parameter $\beta_{g}$. We fit these parameters numerically by
maximizing the log-likelihood of the data:

$\displaystyle\mathcal{L}(\smash{\vec{\beta}})={\sum_{t}}\log\frac{\textrm{ER}_{n,\nicefrac{{1}}{{2}}}\kern-1.0pt\Big{(}\kern-1.0ptG_{t}\kern
1.0pt\big{|}\kern 1.0ptP{\kern-2.0pt}G_{t}\kern-1.0pt\Big{)}\kern
3.0pt\exp\\!\Big{\\{}\kern-1.0pt\smash{\vec{\beta}}\cdot\smash{\vec{\mu}}(G_{t})\\!\Big{\\}}}{{\sum}\limits_{G^{\prime}\in\mathcal{G}_{\kern-1.0ptn}}\kern-2.0pt\textrm{ER}_{n,\nicefrac{{1}}{{2}}}\kern-1.0pt\Big{(}\kern-1.0ptG^{\prime}\kern
1.0pt\big{|}\kern 1.0ptP{\kern-2.0pt}G_{t}\kern-1.0pt\Big{)}\kern
3.0pt\exp\\!\Big{\\{}\kern-1.0pt\smash{\vec{\beta}}\cdot\smash{\vec{\mu}}(G^{\prime})\\!\Big{\\}}}$

where $G_{t}$ denotes the participant’s response to being shown the partial
graph $P{\kern-2.0pt}G_{t}$; and the distribution
$\textrm{ER}_{n,\nicefrac{{1}}{{2}}}\big{(}G^{\prime}\kern 1.0pt\big{|}\kern
1.0ptP{\kern-2.0pt}G_{t}\big{)}$ is that which would be obtained by including
edges i.i.d. with probability $\nicefrac{{1}}{{2}}$ for each of the obscured
relationships in $P{\kern-2.0pt}G_{t}$.777Indeed, this is how participants
would reply if their prior were $\textrm{ER}_{n,\nicefrac{{1}}{{2}}}$
(corresponding to $\smash{\vec{\beta}}=\smash{\vec{0}}$).

We employed Newton’s method to obtain the parameters $\beta_{g}$ for which
$\partial\mathcal{L}/\partial\smash{\vec{\beta}}=0$, and selected the model
complexity $r$ using cross-validation and various sanity checks and robustness
tests (see appendix B.1).

###  5.5 Interpreting the Data using Graph Cumulants

Just as the classical cumulants (e.g., mean, variance, covariance, skew,
kurtosis) can be derived from the classical moments, so too can graph
cumulants be obtained from the subgraph densities (the analogue of moments for
graphs Bickel et al. (2011)). Graph cumulants are a principled and intuitive
family of subgraph-based statistics that naturally captures the propensity (or
aversiveness) for any substructure of interest (see Bravo-Hermsdorff et al.
(2021) for a concise application or Gunderson & Bravo-Hermsdorff (2020) for
more details).

Intuitively, the graph cumulant $\kappa_{g}$ quantifies the difference between
the observed density $\mu_{g}$ of subgraph $g$ and the density that would be
expected by chance due to the densities of smaller subgraphs within $g$. For
example, for the cherry cumulant $\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, a term involving
the edge density $\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ is subtracted from
the cherry density: $\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}=\mu_{\leavevmode\hbox
to5.27pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}-\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{2}$. For
$\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{} {}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{4.18948pt}{0.15652pt}\pgfsys@curveto{4.2327pt}{0.07008pt}{4.18938pt}{0.0pt}{4.09273pt}{0.0pt}\pgfsys@lineto{0.175pt}{0.0pt}\pgfsys@curveto{0.07835pt}{0.0pt}{0.03503pt}{0.07008pt}{0.07825pt}{0.15652pt}\pgfsys@lineto{1.68665pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{0.89442}{-0.89442}{0.44722}{1.68665pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, terms involving
both the edge and cherry densities, $\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and
$\mu_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, are subtracted.
For the simplest random graph $\textrm{ER}_{n,\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$, which has no
graphical structure beyond the presence of edges, all graph cumulants (aside
from $\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$888Just as the mean
is the first moment and the first cumulant, the edge density
$\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ is likewise the
first graph moment $\mu_{g}$ and the first graph cumulant $\kappa_{g}$.) are
exactly zero, reflecting the fact that larger subgraphs do not require more
explanation than just the edge density.

###  5.6 Scaling the Graph Cumulants Accounts for Sparsity

If one randomly deletes edges i.i.d. in a graph $G$ such that a fraction $x$
of the edges remain, then the resulting expected edge density
$\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ is clearly scaled
by a factor of $x$ from the original edge density. Similarly, for a subgraph
$g$ with $r$ edges, its expected subgraph density and graph cumulant are
scaled by a factor of $x^{r}$. This can make comparisons between subgraphs of
different sizes difficult, especially for sparse graph distributions. As such,
we report the scaled graph cumulants (i.e.,
$\kappa_{g}/\mu^{r}_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$) of the inferred
priors.

###  5.7 Estimating the Error in our Results

The solid curves in figures 3, 4, and 5 display (scaled) graph cumulants of
the inferred priors. To estimate our uncertainty in these measurements, we
simulated ideal Bayesian MCMCP agents using the inferred priors, and
responding to the same partial graphs seen by the participants. We then
inferred the prior for each of these synthetic datasets, and computed their
(scaled) graph cumulants. The shaded regions correspond to $\pm 1$ standard
deviation about the average of these values (for $64$ repetitions of this
process).

##  6 Results

While our analysis of participants’ data makes full use of the MCMCP
assumptions (most notably, that participants are Bayesian with the same
prior), we are not claiming that they exactly hold in practice. Nevertheless,
the results we present below are remarkably robust (as evidenced by model
selection, sensitivity analysis, and robustness checks), suggesting that the
general conclusions are still meaningful.

###  6.1 Substructures with Noticeable Trends in the Priors

We now present the results for: edge density $\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ (fig. 3), scaled
cherry cumulant $\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{2}$ (fig. 4), and
scaled triangle cumulant $\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{} {}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{4.18948pt}{0.15652pt}\pgfsys@curveto{4.2327pt}{0.07008pt}{4.18938pt}{0.0pt}{4.09273pt}{0.0pt}\pgfsys@lineto{0.175pt}{0.0pt}\pgfsys@curveto{0.07835pt}{0.0pt}{0.03503pt}{0.07008pt}{0.07825pt}{0.15652pt}\pgfsys@lineto{1.68665pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{0.89442}{-0.89442}{0.44722}{1.68665pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{3}$ (fig. 5) for
each of the four cover stories as a function of the number of nodes in the
prior.999Despite number of nodes clearly being a discrete variable, we plot
the results as curves to aid in the visualization of the trends.

Intuitively, these statistics quantify well-known tendencies of real networks:
sparsity, degree heterogeneity, and clustering, respectively. It is perhaps
then not a coincidence that the subgraphs associated with these statistics
were those that displayed the most discernible trends across the priors.

Priors favor sparsity.  As shown in figure 3, we find that the edge density
($\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$) systematically
decreases as the number of nodes increases. The number of connections per
node, however, appears to be a slowly increasing function of the number of
nodes. This result is remarkably similar for all the four different cover
stories.

Figure 3: Priors over larger graphs have lower edge density.
Markers in the solid curves correspond to the inferred edge density
($\mu_{\leavevmode\hbox to3.13pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$) of participants’
priors, using the aggregated data of a single cover story with that number of
nodes. Shading corresponds to $\pm 1$ standard deviation of the average value
that would have been obtained if participants all had this inferred prior, and
behaved according to the assumptions of the MCMCP model. Note that the result
of this procedure is not necessarily centered around the empirical values
(i.e., the solid curves).

Priors favor uniform degrees in small graphs.  As shown in figure 4, we find
that the preference for degree heterogeneity (i.e., a few “hub” nodes with
many of connections) increases as the number of nodes increases. The scaled
cherry cumulant ($\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{3.82051pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{-0.89442}{0.89442}{0.44722}{3.82051pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{2}$) changes from
negative (for graphs with $4$ or $5$ nodes) to positive (for graphs with $6$
or more nodes). This suggests that human priors for small graphs favor a
notably uniform distribution of node degrees, switching to a preference for
heterogeneous node degrees for larger graphs. Again, this result is remarkably
consistent for all four cover stories.

Figure 4: Priors over smaller graphs have fewer hubs.
The analysis is the same as in fig. 3, but the statistic measured is the
scaled cherry cumulant ($\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.4472pt}{0.89442pt}\pgfsys@lineto{2.06343pt}{4.12686pt}\pgfsys@curveto{2.10233pt}{4.20465pt}{2.1654pt}{4.20465pt}{2.2043pt}{4.12686pt}\pgfsys@lineto{3.82053pt}{0.89442pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.4472}{-0.89442}{0.89442}{-0.4472}{0.4472pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{-0.89442}{0.89442}{0.4472}{3.82053pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{2}$), which
quantifies preference for degree heterogeneity. A negative value indicates
that the prior has edges distributed more uniformly than what would be
expected by chance (i.e., in an $\textrm{ER}_{n,\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ distribution with
the same number of nodes $n$ and edge density $\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$).

Priors over social interactions favor triangles.  As shown in figure 5, the
scaled triangle cumulant ($\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{} {}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{2.05562pt}{4.1112pt}\pgfsys@curveto{2.09883pt}{4.19765pt}{2.1689pt}{4.19765pt}{2.21211pt}{4.1112pt}\pgfsys@lineto{4.18948pt}{0.15652pt}\pgfsys@curveto{4.2327pt}{0.07008pt}{4.18938pt}{0.0pt}{4.09273pt}{0.0pt}\pgfsys@lineto{0.175pt}{0.0pt}\pgfsys@curveto{0.07835pt}{0.0pt}{0.03503pt}{0.07008pt}{0.07825pt}{0.15652pt}\pgfsys@lineto{1.68665pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.44722}{0.89442}{-0.89442}{0.44722}{1.68665pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{3}$) reveals that
the priors for the social domain have a notably higher preference for
clustering.101010For measuring clustering in bipartite graphs, one should use
the scaled square cumulant $\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{} {}{} {}{} {}{}
{}{} {}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{1.0pt}{0.0pt}\pgfsys@lineto{0.175pt}{0.0pt}\pgfsys@curveto{0.07835pt}{0.0pt}{0.0pt}{0.07835pt}{0.0pt}{0.175pt}\pgfsys@lineto{0.0pt}{4.09273pt}\pgfsys@curveto{0.0pt}{4.18938pt}{0.07835pt}{4.26773pt}{0.175pt}{4.26773pt}\pgfsys@lineto{4.09273pt}{4.26773pt}\pgfsys@curveto{4.18938pt}{4.26773pt}{4.26773pt}{4.18938pt}{4.26773pt}{4.09273pt}\pgfsys@lineto{4.26773pt}{0.175pt}\pgfsys@curveto{4.26773pt}{0.07835pt}{4.18938pt}{0.0pt}{4.09273pt}{0.0pt}\pgfsys@lineto{0.175pt}{0.0pt}\pgfsys@curveto{0.07835pt}{0.0pt}{0.0pt}{0.07835pt}{0.0pt}{0.175pt}\pgfsys@lineto{0.0pt}{3.26773pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.0}{1.0}{-1.0}{0.0}{0.0pt}{3.26773pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{4}$. In contrast to
the edge () and cherry (), this motif () clearly distinguishes between the
social and navigation domains.

Indeed, Tompson et al. (2019) found experimental evidence that humans learn
community structure differently when the network is social vs. non-social.
Moreover, the prevalence of triadic closure in social networks (i.e., one’s
friends tend to be friends with each other) is a well-established phenomenon
(Yang et al., 2016).

Figure 5: Priors over social graphs have more triangles.
The analysis is the same as in figs. 3 and 4, but the statistic measured is
the scaled triangle cumulant ($\kappa_{\leavevmode\hbox to5.27pt{\vbox
to5.27pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{} {}{} {}{} {}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.4472pt}{0.89442pt}\pgfsys@lineto{2.06343pt}{4.12686pt}\pgfsys@curveto{2.10233pt}{4.20465pt}{2.1654pt}{4.20465pt}{2.2043pt}{4.12686pt}\pgfsys@lineto{4.1973pt}{0.14087pt}\pgfsys@curveto{4.23619pt}{0.06308pt}{4.1972pt}{0.0pt}{4.11023pt}{0.0pt}\pgfsys@lineto{0.1575pt}{0.0pt}\pgfsys@curveto{0.07053pt}{0.0pt}{0.03154pt}{0.06308pt}{0.07043pt}{0.14087pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.4472}{-0.89442}{0.89442}{-0.4472}{0.4472pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}/\mu_{\leavevmode\hbox
to3.13pt{\vbox to5.27pt{\pgfpicture\makeatletter\hbox{\hskip
0.5pt\lower-0.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{}{{}}\pgfsys@moveto{0.44722pt}{0.89442pt}\pgfsys@lineto{1.68666pt}{3.3733pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.44722}{-0.89442}{0.89442}{-0.44722}{0.44722pt}{0.89442pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.4472}{0.89442}{-0.89442}{0.4472}{1.68666pt}{3.3733pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}^{3}$), which
quantifies preference for clustering. A negative value indicates that the
prior has fewer triangles than what would be expected by chance. In contrast
to figs. 3 and 4, there is a notable difference between the social (class and
work) and navigation (city and park) domains.

###  6.2 Generalization Between and Within Domains

In figure 6, we compare generalization within domain and between domains. In
particular, for a given number of nodes $n$ and model expressivity $r$
(equation 1) for the priors, we randomly partitioned the data from each of the
$4$ cover stories into a training set ($80\%$) and a test set ($20\%$). Then,
for each of the $4\times 4=16$ combinations of cover stories, we fit the
(order $r$) model to the training data and measured the average log-likelihood
per round (which we denote by “avgLL”) of the test data under this model. To
compare to a meaningful baseline, we subtracted the avgLL of this test data
under a “non-specialized” model that was fit to the combined training data of
all four cover stories.

The decimal numbers shown in figure 6 are the exponential of these differences
in avgLL, having “units” of a ratio of probabilities. A value of $1.00$
corresponds to the specialized model explaining the data equally as well as
the non-specialized model, while a value greater than one indicates that the
specialized model explains the data better than the non-specialized model (and
conversely for a value less than one). Figure 6 shows the average result for
$64$ repetitions of this procedure.

Larger subgraphs reveal differences between domains.  As a general trend, we
find that more complex models recover priors that are better able to
differentiate between domains and (to a lesser degree) specific cover stories.
This is reflected in figure 6 by the suggestively “block-diagonal” appearance
of the $4$-by-$4$ squares corresponding to more expressive models ($r\gtrsim
3$). The “horizontal-row” appearance of the $4$-by-$4$ squares corresponding
to $r\lesssim 2$ suggests that the quality of fit for less complex models is
determined primarily by the particular data used for testing. These results
are in agreement with our previous findings that larger motifs (and triangles
in particular) are needed in order to distinguish between the two domains
(figs. 3, 4, and 5).

A note on planar graphs.  One aspect worth mentioning is the duality between
our two spatial navigation cover stories. While both are suggestively planar,
their connectivity is of two different flavors. The trails in the park cover
story are rather analogous to vectors (a “large” trail implies a large
separation between the two nature sites), while the boundaries between
neighborhoods in the city cover story are analogous to one-forms (a “large”
boundary between neighborhoods implies that they are nearby). While in our
results, the similarity between the priors for these two navigation cover
stories is about the same as the similarity between those for the two social
cover stories, it is possible that future investigations involving weighted
graphs could reflect this difference.

Figure 6: Increasing the expressivity of the model for the priors reveals
domain-specific traits.
The $4$-by-$6$ layout divides the results by the number of nodes $4\leq n\leq
7$ (rows) and the model complexity $1\leq r\leq 6$ (columns) of the priors.
Each of these $24$ options for $n$ and $r$ contains results summarized by a
$4$-by-$4$ square of numbers. For each of these $4$-by-$4$ square, we fit $4$
“specialized” models (using the training data of each cover story separately),
as well as one “non-specialized” model (using the combined training data of
all $4$ cover stories). As seen in the amplified $4$-by-$4$ square on the
right, the $4$ columns denote the cover story of the specialized training
data, and the $4$ rows denote the cover story of the test data used to
evaluate these models. The numbers inside these squares are defined in section
6.2 and rounded to the nearest $0.01$. They can be approximately thought of as
an average odds-ratio; a value of $1\pm\varepsilon$ corresponds to the case
when the specialized model assigns a probability to an actual response of a
participant that is about $1\pm\varepsilon$ times the probability assigned by
the non-specialized model. The coloring of the squares is purely for
visualization; we scale the same range of colors to that square’s maximum and
minimum values. While the less expressive models (to the left) are in fact
much more similar than the colors suggest, the more expressive models recover
priors that are better able to differentiate between domains and (to a lesser
degree) specific cover stories.

##  7 Possible Sequels

Other structures.  In addition to weighted graphs, other extensions are also
possible. For example, one could investigate priors over bipartite graphs
representing people’s preferences over a set of items, or priors over directed
graphs modeling patterns of citations. More generally, any such MCMCP
experiment might benefit from our approach of inferring the prior by
explicitly fitting the assumed Bayesian model to the aggregated data.

Adaptive sampling.  As our method explicitly uses the MCMCP assumptions to fit
the data, there is no longer a need to collect data in chains. In fact, one
could use the current fit of the prior to inform an adaptive sampling
algorithm to select the $e\text{vidence}$ presented in each iteration. As a
simple example, we found that it was helpful to initialize many chains over a
large range of edge densities. It is entirely possible that a similar
“spreading out” over other features (like degree heterogeneity and clustering)
would likewise be helpful.

Larger graphs.  Our results suggest that properties of the priors vary with
the number of nodes. The results presented in the main text consider graphs
with at most $8$ nodes. Unfortunately, in practice, our experiments appeared
to lose human engagement for graphs with $10$ or more nodes (see discussion in
appendix B.2 and C, and fig. 9 for analysis of these data). Adapting our
methods to measure graphs over a range of sizes would be particularly
interesting, as we could compare the resulting priors with actual structure of
analogous real networks. The scaled graph cumulants we used in our analysis
are well-suited for such comparisons.

Different cultures.  It is important to note that if we are to claim that a
prior is representative of general characteristics of human cognition, it
should be representative of the full diversity of the humans. In this
direction, we have an ongoing collaboration with a linguist that works with
the Yawanawá and the Xinane aboriginal tribes in the Amazon rainforest
(Camargo Souza, 2020). In the domain of navigation, it would be interesting to
see if their priors change when the discussion is about paths versus when the
discussion is about regions. Results from the social domain may also prove
interesting; in both tribes, while parallel-cousins (i.e., their parents are
same-sex siblings) are forbidden from marriage, marriage between cross-cousins
(i.e., their parents are opposite-sex siblings) is considered ideal. Case
studies such as this could offer insight into the effects of community size
and social norms on our priors over social networks.

General message.  This paper offers a case-study about the power of carefully
constructed experiments and clever analysis. Just as neural networks benefit
from having architecture that reflects the symmetry of the data (Villar et
al., 2023), so too does the design and analysis of experiments that use people
as substrate. The results presented here demonstrate two such examples: how
the assumed Bayesian structure of the participants’ responses can be used to
more efficiently use the collected data, and how the relabelling symmetry of
relational data can be leveraged to design more computationally tractable
models for their priors.

## Acknowledgements

I did this work as part of my PhD thesis at the Princeton Neuroscience
Institute (PNI). I acknowledge PNI for the financial support during my PhD and
the Princeton’s Cognitive Science Department for an independent research
grant. The completion of this work is inextricably connected to the
discussions and support shared with me by many incredible people along the PhD
journey (see my acknowledgments in Bravo-Hermsdorff (2020)). Here, I would
like to particularly thank: Tom Griffiths; Talmo Pereira, for his essential
role in building such an amazing online game platform; and Lee M. Gunderson,
whose insights and feedback permeate every bit of this work.

## References

  * Amazon Web Services (2010) Amazon Web Services, A.  _Amazon Mechanical Turk crowdsourcing website_ , 2010.  URL mturk.com.
  * Barlow et al. (1961) Barlow, H. B. et al.  Possible principles underlying the transformation of sensory messages.  _Sensory Communication_ , 1:217–234, 1961.
  * Bartlett (1932) Bartlett, F. C.  Remembering: A study in experimental and social psychology.  _Cambridge University Press_ , 1932.
  * Bayes (1763) Bayes, T.  An essay towards solving a problem in the doctrine of chances.  _Philosophical Transactions_ , 53:370–418, 1763.
  * Bhui & Gershman (2018) Bhui, R. and Gershman, S. J.  Decision by sampling implements efficient coding of psychoeconomic functions.  _Psychological Review_ , 125(6):985, 2018.
  * Bickel et al. (2011) Bickel, P. J., Chen, A., and Levina, E.  The method of moments and degree distributions for network models.  _The Annals of Statistics_ , 39(5):2280–2301, 2011.
  * Botvinick et al. (2015) Botvinick, M., Weinstein, A., Solway, A., and Barto, A.  Reinforcement learning, efficient coding, and the statistics of natural tasks.  _Current Opinion in Behavioral Sciences_ , 5:71–77, 2015\.
  * Brady et al. (2009) Brady, T. F., Konkle, T., and Alvarez, G. A.  Compression in visual working memory: Using statistical regularities to form more efficient memory representations.  _Journal of Experimental Psychology_ , 138:487–502, 2009\.
  * Bravo-Hermsdorff (2020) Bravo-Hermsdorff, G.  _Quantifying Human Priors over Abstract Relational Structures_.  PhD thesis, Princeton University, 2020.
  * Bravo-Hermsdorff et al. (2021) Bravo-Hermsdorff, G., Gunderson, L. M., Maugis, P.-A., and Priebe, C. E.  Quantifying network similarity using graph cumulants.  _arXiv:2107.11403_ , 2021.
  * Camargo Souza (2020) Camargo Souza, L.  _Switch-reference as anaphora: A modular account_.  PhD thesis, Rutgers University, 2020.
  * Canini et al. (2014) Canini, K. R., Griffiths, T. L., Vanpaemel, W., and Kalish, M. L.  Revealing human inductive biases for category learning by simulating cultural transmission.  _Psychonomic Bulletin & Review_, 21(3):785–793, 2014.
  * Chatterjee & Diaconis (2013) Chatterjee, S. and Diaconis, P.  Estimating and understanding exponential random graph models.  _The Annals of Statistics_ , 41(5):2428–2461, Oct 2013.
  * Chazelle & Wang (2016) Chazelle, B. and Wang, C.  Self-sustaining iterated learning.  _arXiv:1609.03960_ , 2016.
  * Chazelle & Wang (2019) Chazelle, B. and Wang, C.  Iterated learning in dynamic social networks.  _Journal of Machine Learning Research_ , 20(1):979–1006, 2019.
  * Cimini et al. (2019) Cimini, G., Squartini, T., Saracco, F., Garlaschelli, D., Gabrielli, A., and Caldarelli, G.  The statistical physics of real-world networks.  _Nature Reviews Physics_ , 1(1):58, 2019.
  * Crowston (2012) Crowston, K.  Amazon mechanical turk: A research tool for organizations and information systems scholars.  In _Shaping the future of ICT research: Methods and approaches_ , pp. 210–221. Springer, 2012.
  * Deutsch (2011) Deutsch, D.  _The beginning of infinity: Explanations that transform the world_.  Penguin Books UK, 2011.
  * Devaine et al. (2014) Devaine, M., Hollard, G., and Daunizeau, J.  The social bayesian brain: Does mentalizing make a difference when we learn?  _PLoS Computational Biology_ , 10(12):e1003992, 2014.
  * Doya et al. (2007) Doya, K., Ishii, S., Pouget, A., and Rao, R. P.  _Bayesian brain: Probabilistic approaches to neural coding_.  MIT press, 2007.
  * Eichenbaum (2017) Eichenbaum, H.  The role of the hippocampus in navigation is memory.  _Journal of Neurophysiology_ , 117(4):1785–1796, 2017.
  * Field (1989) Field, D. J.  What the statistics of natural images tell us about visual coding.  _Human Vision, Visual Processing, and Digital Display_ , 1077:269–276, 1989.
  * Frydman & Jin (2022) Frydman, C. and Jin, L. J.  Efficient coding and risky choice.  _The Quarterly Journal of Economics_ , 137(1):161–213, 2022.
  * Griffiths & Kalish (2007) Griffiths, T. L. and Kalish, M. L.  Language evolution by iterated learning with bayesian agents.  _Cognitive Science_ , 31(3):441–480, 2007.
  * Gunderson & Bravo-Hermsdorff (2020) Gunderson, L. M. and Bravo-Hermsdorff, G.  Introducing graph cumulants: What is the variance of your social network?  _arXiv:2002.03959_ , 2020.
  * Harrison et al. (2020) Harrison, P., Marjieh, R., Adolfi, F., van Rijn, P., Anglada-Tort, M., Tchernichovski, O., Larrouy-Maestri, P., and Jacoby, N.  Gibbs sampling with people.  _Neural Information Processing Systems (NeurIPS)_ , 34, 2020.
  * Howe & Purves (2005) Howe, C. and Purves, D.  The Müller–Lyer illusion explained by the statistics of image–source relationships.  _Proceedings of the National Academy of Sciences_ , 102(4):1234–1239, 2005.
  * Howe et al. (2005) Howe, C., Yang, Z., and Purves, D.  The Poggendorff illusion explained by natural scene geometry.  _Proceedings of the National Academy of Sciences_ , 102(21):7707–7712, 2005.
  * Hsu et al. (2019) Hsu, A. S., Martin, J. B., Sanborn, A. N., and Griffiths, T. L.  Identifying category representations for complex stimuli using discrete Markov chain Monte Carlo with people.  _Behavior Research Methods_ , 2019.
  * Hsu et al. (2015) Hsu, D. J., Kontorovich, A., and Szepesvári, C.  Mixing time estimation in reversible Markov chains from a single sample path.  _Neural Information Processing Systems (NIPS)_ , 29, 2015.
  * Hu (2011) Hu, Y.  Algorithms for visualizing large networks.  _Combinatorial Scientific Computing_ , 5(3):180–186, 2011.
  * Huang & Rao (2011) Huang, Y. and Rao, R. P.  Predictive coding.  _Wiley Interdisciplinary Reviews: Cognitive Science_ , 2(5):580–593, 2011.
  * Jaynes (1957a) Jaynes, E. T.  Information theory and statistical mechanics.  _Physical Review_ , 106(4):620–630, 1957a.
  * Jaynes (1957b) Jaynes, E. T.  Information theory and statistical mechanics. ii.  _Physical Review_ , 108(2):171–190, 1957b.
  * Kirby et al. (2014) Kirby, S., Griffiths, T., and Smith, K.  Iterated learning and the evolution of language.  _Current Opinion in Neurobiology_ , 28:108–114, 2014.
  * Klishin & Bassett (2022) Klishin, A. A. and Bassett, D. S.  Exposure theory for learning complex networks with random walks.  _Journal of Complex Networks_ , 10(5):cnac029, 2022.
  * Lake et al. (2017) Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. J.  Building machines that learn and think like people.  _Behavioral and Brain Sciences_ , 40:e253, 2017.
  * Langlois et al. (2021) Langlois, T. A., Jacoby, N., Suchow, J. W., and Griffiths, T. L.  Serial reproduction reveals the geometry of visuospatial representations.  _Proceedings of the National Academy of Sciences_ , 118(13), 2021.
  * Lauritzen et al. (2018) Lauritzen, S., Rinaldo, A., and Sadeghi, K.  Random networks, graphical models and exchangeability.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(3):481–508, 2018.
  * Lee & Vanpaemel (2017) Lee, M. D. and Vanpaemel, W.  Determining informative priors for cognitive models.  _Psychonomic Bulletin & Review_, 25(1):114–127, 2017.
  * Lehmann et al. (2021) Lehmann, B., Henson, R., Geerligs, L., White, S., et al.  Characterising group-level brain connectivity: A framework using bayesian exponential random graph models.  _NeuroImage_ , 225:117480, 2021.
  * Lewicki (2002) Lewicki, M. S.  Efficient coding of natural sounds.  _Nature Neuroscience_ , 5(4):356, 2002.
  * Lovász (2012) Lovász, L.  _Large networks and graph limits_ , volume 60.  American Mathematical Society, 2012.
  * Lusher et al. (2013) Lusher, D., Koskinen, J., and Robins, G.  _Exponential random graph models for social networks: Theory, methods, and applications_.  Cambridge University Press, 2013.
  * Lynn & Bassett (2020) Lynn, C. W. and Bassett, D. S.  How humans learn and represent networks.  _Proceedings of the National Academy of Sciences_ , 117(47):29407–29415, 2020.
  * Maguire et al. (2003) Maguire, E. A., Spiers, H. J., Good, C. D., Hartley, T., Frackowiak, R. S., and Burgess, N.  Navigation expertise and the human hippocampus: A structural brain imaging analysis.  _Hippocampus_ , 13(2):250–259, 2003.
  * Manookin & Rieke (2023) Manookin, M. B. and Rieke, F.  Two sides of the same coin: Efficient and predictive neural coding.  _Annual Review of Vision Science_ , 9, 2023.
  * Marjieh et al. (2022) Marjieh, R., Sucholutsky, I., Langlois, T. A., Jacoby, N., and Griffiths, T. L.  Analyzing diffusion as serial reproduction.  _arXiv:2209.14821_ , 2022.
  * Mathy & Feldman (2012) Mathy, F. and Feldman, J.  What’s magic about magic numbers? Chunking and data compression in short-term memory.  _Cognition_ , 122(3):346–362, 2012.
  * McDermott et al. (2013) McDermott, J. H., Schemitsch, M., and Simoncelli, E. P.  Summary statistics in auditory perception.  _Nature Neuroscience_ , 16(4):493, 2013.
  * Modica & Poggiolini (2012) Modica, G. and Poggiolini, L.  _A first course in probability and Markov Chains_.  John Wiley & Sons, 2012.
  * Montague (2007) Montague, R.  _Your brain is (almost) perfect: How we make decisions_.  Penguin, 2007.
  * Morgan et al. (2020) Morgan, T. J., Suchow, J. W., and Griffiths, T. L.  Experimental evolutionary simulations of learning, memory and life history.  _Philosophical Transactions of the Royal Society B_ , 375(1803):20190504, 2020.
  * Orbán et al. (2008) Orbán, G., Fiser, J., Aslin, R. N., and Lengyel, M.  Bayesian learning of visual chunks by human observers.  _Proceedings of the National Academy of Sciences_ , 105(7):2745–2750, 2008.
  * Raftery & Lewis (1996) Raftery, A. E. and Lewis, S. M.  Implementing MCMC.  _Markov chain Monte Carlo in practice_ , pp. 115–130, 1996.
  * Richardson (2019) Richardson, H.  Development of brain networks for social functions: Confirmatory analyses in a large open source dataset.  _Developmental Cognitive Neuroscience_ , 37:100598, 2019\.
  * Rieke et al. (1999) Rieke, F., Warland, D., van Steveninck, R. d. R., and Bialek, W.  _Spikes: Exploring the Neural Code_.  MIT press, 1999.
  * Roy (2020) Roy, V.  Convergence diagnostics for Markov chain Monte Carlo.  _Annual Review of Statistics and Its Application_ , 7:387–412, 2020.
  * Sanborn et al. (2018) Sanborn, S., Bourgin, D., Chang, M., and Griffiths, T. L.  Representational efficiency outweighs action efficiency in human program induction.  _CoRR_ , abs/1807.07134, 2018.
  * Schapiro et al. (2013) Schapiro, A. C., Rogers, T. T., Cordova, N. I., Turk-Browne, N. B., and Botvinick, M. M.  Neural representations of events arise from temporal community structure.  _Nature Neuroscience_ , 16(4):486–492, 2013.
  * Schulz et al. (2017) Schulz, E., Tenenbaum, J. B., Duvenaud, D., Speekenbrink, M., and Gershman, S. J.  Compositional inductive biases in function learning.  _Cognitive Psychology_ , 99:44–79, 2017.
  * Shiffrin et al. (2020) Shiffrin, R. M., Bassett, D. S., Kriegeskorte, N., and Tenenbaum, J. B.  The brain produces mind by modeling.  _Proceedings of the National Academy of Sciences_ , 117(47):29299–29301, 2020.
  * Simoncelli (2003) Simoncelli, E. P.  Vision and the statistics of the visual environment.  _Current Opinion in Neurobiology_ , 13(2):144 – 149, 2003.
  * Sloane (1964) Sloane, N.  _The online encyclopedia of integer sequences (OEIS), entry A000088_ , 1964.  URL oeis.org/A000088.
  * Thompson & Griffiths (2021) Thompson, B. and Griffiths, T. L.  Human biases limit cumulative innovation.  _Proceedings of the Royal Society B: Biological Sciences_ , 288(20202752), 2021.
  * Tompson et al. (2019) Tompson, S. H., Kahn, A. E., Falk, E. B., Vettel, J. M., and Bassett, D. S.  Individual differences in learning social and nonsocial network structures.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 45(2):253, 2019.
  * Uddenberg & Scholl (2018) Uddenberg, S. and Scholl, B. J.  Teleface: Serial reproduction of faces reveals a whiteward bias in race memory.  _Journal of Experimental Psychology: General_ , 147(10):1466, 2018.
  * Villar et al. (2023) Villar, S., Hogg, D. W., Yao, W., Kevrekidis, G. A., and Schölkopf, B.  The passive symmetries of machine learning.  _arXiv:2301.13724_ , 2023.
  * Wark et al. (2007) Wark, B., Lundstrom, B. N., and Fairhall, A.  Sensory adaptation.  _Current Opinion in Neurobiology_ , 17(4):423–429, 2007.
  * Wolpert (2021) Wolpert, D. H.  What is important about the No Free Lunch theorems?  In _Black Box Optimization, Machine Learning, and No-Free Lunch Theorems_ , pp. 373–388. Springer, 2021.
  * Xu et al. (2013) Xu, J., Dowman, M., and Griffiths, T. L.  Cultural transmission results in convergence towards colour term universals.  _Proceedings of the Royal Society B: Biological Sciences_ , 280(20123073), 2013.
  * Yamakoshi et al. (2022) Yamakoshi, T., Griffiths, T. L., and Hawkins, R. D.  Probing BERT’s priors with serial reproduction chains.  _arXiv:2202.12226_ , 2022.
  * Yang et al. (2016) Yang, S., Keller, F. B., and Zheng, L.  _Social network analysis: Methods and examples_.  Sage Publications, 2016.
  * Yeung & Griffiths (2015) Yeung, S. and Griffiths, T. L.  Identifying expectations about the strength of causal relationships.  _Cognitive Psychology_ , 76:1–29, 2015.

##  Appendix A Experimental Procedure

In this section, we provide a detailed description of our experiments, and
protocols for data collection and cleaning.

###  A.1 Data Collection

All participants were recruited online using Amazon Mechanical Turk (AMT) (see
e.g. Crowston (2012) for a description of the AMT system). We only recruited
participants who doing our experiment for the first time and had at least
$90\%$ of their completed “HITs” (i.e., experiments intermediated by the AMT
crowdsourcing system) approved.

The experiments were approved by Princeton University’s Institutional Review
Board (IRB) for human subjects, and all participants provided informed consent
for the study.

The experiment lasted $38$ minutes on average and participants were paid an
average wage rate of $\$11$ per hour.

###  A.2 Experimental Design

We developed a “gamified” online experimental platform that smoothly allocates
participants to the appropriate experimental chains in real time.

The structure of the experiments was the same for all four cover stories
(table 1). In the the two social cover stories:

  1. 1.

Class: participants were asked to infer the friendships (relations) between
students (nodes) in a classroom (context).

  2. 2.

Work: participants were asked to infer the friendships (relations) between
coworkers (nodes) in a workplace (context).

And in the two navigation cover stories:

  1. 1.

Park: participants were asked to infer the trails (relations) between nature
sites (nodes) in a nature park (context).

  2. 2.

City: participants were asked to infer the borders (relations) between
neighborhoods (nodes) in a city (context).

Each experiment began with an introduction about the particular cover story.
It then posed several questions to the participant to ensure their
understanding (see appendix A.5 for the full text for each of the cover
stories). After that, the task/game started. It consisted of a series of
“rounds”.

A round proceeded as follows (see here for a demonstration video):

  * •

Main interface page (see the screenshots in figs. 7 and 8):
In the center of the screen, there was a visualization of the graph and an
interactive interface.
Using this interface, the participant could:
move the nodes, add edges to the graph, and remove edges from the graph.
The nodes were initially positioned in such a way that the nodes did not
overlap and the edges were not ambiguous.111111This was achieved using a
modified spring-electrical model for graph drawing (Hu, 2011), with an
additional penalty for edges with the same slope. Connections that were not
obscured were already placed in the graph,
along with a list of the “unobscured” relations at the top of the screen.
The most important points of the introduction for properly doing the
experiment were also recalled in this page.
Once the participant was satisfied with their modifications,
they submitted their response by clicking the “Done!” button at the bottom
right of the screen.

  * •

Post-round engagement page:
To foster engagement, once the participant submitted their response,
a question (asked in a variety of ways) appeared about which node(s) they
thought to be the most/least important.
The participant was shown the graph they had just submitted, and gave an
answer
by clicking on the node(s) they thought were the most/least important before
clicking the “Submit” button.

There were $16$ rounds in total in an experiment, i.e., a participant
(potentially)121212See appendix A.4 for the exclusion criteria we used to
decide whether to append a response to a chain. contributed to $16$ different
chains, thus completing $16$ different graphs. However, a participant could,
of course, quit the experiment at any point. In such cases, we still had their
data up to that point recorded and we compensated the participant for the work
they had completed.

These $16$ rounds consisted of $2$ rounds for each number of nodes
$n\in\\{4,5,6,7,8,10,12,15\\}$ with a varying number of relations shown $s$
(i.e., the number of relations that were not obscured out of the total number
of pairwise relations $\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{all
relations}}\in\\{6,10,15,21,28,45,66,105\\}$).

In particular, for each cover story, participants were randomly assigned to
one of the following six options for the precise sequence of rounds:

  1. 1.

$(n,s)$: $(4,2)$, $(4,4)$, $(5,3)$, $(5,7)$, $(6,5)$, $(6,7)$, $(7,6)$,
$(7,9)$, $(8,7)$, $(8,12)$, $(10,8)$, $(10,19)$, $(12,8)$, $(12,28)$,
$(15,20)$, $(15,40)$;

  2. 2.

$(n,s)$: $(4,4)$, $(4,2)$, $(5,7)$, $(5,3)$, $(6,7)$, $(6,5)$, $(7,9)$,
$(7,6)$, $(8,12)$, $(8,7)$, $(10,19)$, $(10,8)$, $(12,28)$, $(12,8)$,
$(15,40)$, $(15,20)$;

  3. 3.

$(n,s)$: $(4,5)$, $(5,5)$, $(6,7)$, $(7,9)$, $(8,12)$, $(10,19)$, $(12,28)$,
$(15,10)$, $(4,3)$, $(5,1)$, $(6,5)$, $(7,6)$, $(8,7)$, $(10,8)$, $(12,15)$,
$(15,10)$;

  4. 4.

$(n,s)$: $(4,3)$, $(5,1)$, $(6,5)$, $(7,6)$, $(8,7)$, $(10,8)$, $(12,15)$,
$(15,10)$, $(4,5)$, $(5,5)$, $(6,7)$, $(7,9)$, $(8,12)$, $(10,19)$, $(12,28)$,
$(15,10)$;

  5. 5.

$(n,s)$: $(4,3)$, $(5,9)$, $(6,7)$, $(7,9)$, $(8,12)$, $(10,19)$, $(12,15)$,
$(15,40)$, $(15,10)$, $(12,8)$, $(10,8)$, $(8,7)$, $(7,6)$, $(6,5)$, $(5,5)$,
$(4,1)$; or

  6. 6.

$(n,s)$: $(4,1)$, $(5,5)$, $(6,5)$, $(7,6)$, $(8,7)$, $(10,8)$, $(12,8)$,
$(15,10)$, $(15,40)$, $(12,15)$, $(10,19)$, $(8,12)$, $(7,9)$, $(6,7)$,
$(5,9)$, $(4,3)$.

We added participants to the chains until they contained $12$ participants.
When needed, we initialized a new chain with a new random graph, sampled in a
way that ensured that the initial graphs covered a large range of edge
densities. Only responses that passed our exclusion criteria (described in
appendix A.4) were appended to the chain.

For each of the cover stories, we ran the experiments at least until we
obtained two chains of length $12$ for all the $16$ $(n,s)$ pairs in each of
the six different sequences.131313For some of the chains over graphs with
$\gtrsim 10$ nodes, it took quite a few rounds of participants to obtain a
response. While there are no results for graphs with $10$, $12$, and $15$
nodes in the main text (for reasons discussed in appendix B.2), we were able
to model the density of connections for these larger graphs (as described in
appendix C).

Figure 7: Screenshot of the main interface page of our experiment for the
social class cover story.

Figure 8: Screenshot of the main interface page of our experiment for the
navigation park cover story.

###  A.3 Design Considerations

We performed a variety of pilot experiments (totaling more than $300$
participants), which provided valuable insight into how to make these
experiments engaging and intuitive.

For example, the first version had no visual interface for manipulating the
graphs, and the participants had to remember the relations while responding to
a series of yes/no questions. As our experiments are not particularly
concerned about short-term memory, removing this unnecessary and cognitively
taxing obstacle proved very helpful. We also added an extra question after
each graph to make it more engaging, as well as many embellishments to the
cover stories.

These and other improvements were incorporated into the final experiments,
resulting in remarkably positive feedback in the post-experiment
questionnaire, as well as several MTurk workers sending personal emails about
how they found the experiments engaging.

These pilot experiments also allowed us to devise quantitative heuristics to
clean the data (appendix A.4), thus (hopefully) only including “genuine”
responses to the chains.

###  A.4 Exclusion Criteria

Data from behavioral experiments with humans, particularly when collected
online, can be “contaminated” by participants that are not sufficiently
engaged with the experiment. Thus, we implemented a systematic method for
excluding such data from the chains. We also use this method for rewarding
participants that clearly gave thoughtful deliberation to our experiments.

Our exclusion heuristics were judiciously chosen after observing the
distribution of participants’ responses to our pilot experiments.
Specifically, we exclude all rounds that met any of the following criteria:

  1. 1.

Answered too quickly:
if the participant took less than $3$ seconds per shown relation to submit
their response.

  2. 2.

Not enough interaction:
if the participant moved fewer than $\left\lceil\frac{n}{4}\right\rceil-1$
nodes.

  3. 3.

Changed too little:
if $\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}>5$ and
$f_{\text{add}}\times n<1$,
where $\raisebox{-1.25pt}{\scalebox{1.0}{\\#}}_{\text{obs}}$ is the number of
relations obscured, $f_{\text{add}}$ is the fraction of obscured relations
that the participant choose to be edges in their response, and $n$ is the
number of nodes.

  4. 4.

Not enough practice:
if the participant had fewer than $4$ valid rounds.

The total number of rounds and the total number of participants for each cover
story before and after the exclusion criteria are displayed in table 2.

Table 2: Amount of data before and after applying our exclusion criteria.
After applying the exclusion criteria, we used approximately $90\%$ of the total number of data points (i.e., rounds).  cover story |  # participants: after out of total (% excluded) |  # rounds: after out of total (% excluded)
---|---|---
class |  $362$ out of $443$ ($18\%$) |  $4795$ out of $5340$ ($10\%$)
work |  $269$ out of $342$ ($21\%$) |  $3675$ out of $4317$ ($15\%$)
park |  $299$ out of $359$ ($17\%$) |  $3823$ out of $4163$ ($8\%$)
city |  $289$ out of $347$ ($17\%$) |  $3569$ out of $4013$ ($11\%$)

###  A.5 Detailed Instructions

In this section, we provide the entire instruction text, page by page, for
each of the four cover stories. The instructions were broken in several pages,
and participants could navigate to the next page or the previous page.

####  A.5.1 General Format

All experiments started with the same welcome page:

> Thank you and welcome to our experiment!
>
> Next, we will show you a few instructions.
> Please read them carefully,
> as you will have to correctly answer
> a few questions before moving on to the game!

After the instructions, we asked participants three multiple choice questions
to verify that they understood the task. Each question appeared on a single
page, and participants were only allowed to move to the next page once they
had answered the question correctly. If they answered correctly, they would
simply see a message displaying:

> Correct!

If they answered incorrectly, they would see a “wrong answer message page”
with a summary of the cover story they were participating in. This message was
the same for the three questions (but, of course, different for each cover
story).

For all cover stories, the correct answer for the first question was option
$2$, for the second question was option $1$, and for the third question was
option $2$.

We now provide the text specific to each cover story.

####  A.5.2 Cover Story: Class

Instructions

##### Page $\bm{1}$:

> We are studying how gossip spreads in schools.
>
> In a variety of different classes,
> we recorded the friendships between pairs of students.
>
> We are testing how well people intuit these friendship networks
> based on partial information.

##### Page $\bm{2}$:

> In each class:
>
> Some pairs of students are friends.
> So, gossip can be directly transferred between these two students
> without needing to pass through another student.
>
> Other pairs of students are not friends.
> So, for gossip to be transferred from one to the other,
> it has to pass through at least one other student.
>
> You will play the following game:
>
> We tell you whether some pairs of students are friends or not.
>
> Your goal is to reconstruct the rest of their friendship network.
>
> You win points by matching the “shape/structure” of the unknown relations!

##### Page $\bm{3}$:

> For each round of the game,
> we randomly select students from the same class,
> and display some of their relations at the top of the screen.
>
> For example:
>
>   * •
>
> “Hassen and Hernandez are friends”
>
>   * •
>
> “Miller and Fleming are NOT friends”
>
>

>
> But the list is incomplete!
>
> You need to use your social intuition and reasoning to
> decide whether the other pairs are friends or not.
>
> You will do this by drawing the rest of their friendship network
> using our graphical interface.

##### Page $\bm{4}$:

> How to draw the friendship network:
>
> [Here we had a quick video with a demo of the interface]
>
>   * •
>
> To change the location of a student, click and drag their name.
>
>   * •
>
> To connect two students, first click on one, then on the other.
> A line will appear between them, indicating that they are friends.
>
>   * •
>
> To disconnect two students,
> simply click on the line that connects them.
> The line will disappear, indicating that they are not friends.
>
>

>
> Notes:
>
> If there is no line between two students,
> it means you think they are not friends.
> Even if in your drawing they look very close to each other!
> So, if you think two students are friends,
> always make sure to connect them with a line.
>
> To make your job easier,
> we have already connected the friendship pairs from the list for you.
> And if you attempt to connect a non-friendship pair from the list,
> we indicate the error with a red “X”.
>
> We start the students at random positions,
> so make sure to move the students around,
> as this will help you visualize the network.

##### Page $\bm{5}$:

> Some important information:
>
>   * •
>
> You will play this game for several rounds,
> each time with a different class.
>
>   * •
>
> In each round, the students are randomly selected from the same class.
>
>   * •
>
> The friendships were recorded from actual classrooms,
> so to protect the students’ identities, we use fictitious names.
> Thus, the names do not provide any information
> and you should not use them to guide your answers.
>
>   * •
>
> To motivate you to do your best,
> you will be paid according to your performance, which is determined by
> how well your drawings match the actual friendship networks.
>
>   * •
>
> Precisely, we will keep a score for each round:
> You win points for correctly inferring if
> the pairs of students not presented in the list are friends or not.
> You lose points if your drawing does not respect
> the relations given in the list, which you know for sure are correct.
> The closer you match the actual friendship networks,
> the larger your bonus will be.
> We will give your total score and the resulting performance bonus
> only at the end of the experiment.
>
>   * •
>
> We will give you a chance to take a break at the end of each round.
> Please attempt to solve each round uninterrupted.
>
>

Questions after instructions

##### Wrong answer message:

> Sorry, but…
>
> We recorded the friendships between pairs of students,
> and we are testing how well people intuit these friendship networks
> based on partial information.
>
> In particular, for each round,
> we randomly select some students from the same class,
> and tell you whether some pairs of students are friends or not.
>
> Your goal is to reconstruct the rest of their friendship network.

##### Page for question $\bm{1}$:

> Before we move on,
> please answer a few quick questions to make sure you understand the game.
> Feel free to use the Previous button if you need to review the instructions.
>
> Here’s an easy one to get started:
>
> What are we asking you to draw?
>
>   1. 1.
>
> Power grid networks.
>
>   2. 2.
>
> Student friendship networks.
>
>

##### Page for question $\bm{2}$:

> What do you know about the relations between students?
>
>   1. 1.
>
> Some pairs of students are friends,
> meaning gossip can transfer directly between them.
> Other pairs are not friends,
> so gossip must pass through at least one other student to get between them.
>
>   2. 2.
>
> Some pairs of students are in the same class,
> meaning they know each other.
> Other pairs of students are in different classes,
> which means they likely do not know each other.
>
>   3. 3.
>
> Some pairs of students are in the same school,
> meaning they possibly know each other.
> Other pairs of individuals are in different schools,
> which means they do not know each other.
>
>

##### Page for question $\bm{3}$:

> What is your goal, and what are its main challenges?
>
>   1. 1.
>
> Your goal is to discover which classes are dysfunctional,
> and therefore more likely to support bullying and bad behavior.
> The main challenge is that you do not know who these students are
> or the schools they come from.
>
>   2. 2.
>
> Your goal is to reconstruct the friendship network
> of randomly selected students.
> The main challenge is that we only tell you
> whether some pairs of students are friends or not.
>
>

##### Final instruction page:

> Awesome job! You are now ready to reconstruct your first friendship network!

####  A.5.3 Cover Story: Work

Instructions

##### Page $\bm{1}$:

> We are studying how gossip spreads in workplaces.
>
> In a variety of different workplaces,
> we recorded the friendships between pairs of coworkers.
>
> We are testing how well people intuit these friendship networks
> based on partial information.

##### Page $\bm{2}$:

> In each workplace:
>
> Some pairs of coworkers are friends.
> So, gossip can be directly transferred between these two coworkers
> without needing to pass through another coworker.
>
> Other pairs of coworkers are not friends.
> So, for gossip to be transferred from one to the other,
> it has to pass through at least one other coworker.
>
> You will play the following game:
>
> We tell you whether some pairs of coworkers are friends or not.
>
> Your goal is to reconstruct the rest of their friendship network.
>
> You win points by matching the “shape/structure” of the unknown relations!

##### Page $\bm{3}$:

> For each round of the game,
> we randomly select coworkers from a single workplace,
> and display some of their relations at the top of the screen.
>
> For example:
>
>   * •
>
> “Hassen and Hernandez are friends”
>
>   * •
>
> “Miller and Fleming are NOT friends”
>
>

>
> But the list is incomplete!
>
> You need to use your social intuition and reasoning to
> decide whether the other pairs are friends or not.
>
> You will do this by drawing the rest of their friendship network
> using our graphical interface.

##### Page $\bm{4}$:

> How to draw the friendship network:
>
> [Here we had a quick video with a demo of the interface]
>
>   * •
>
> To change the location of a person, click and drag their name.
>
>   * •
>
> To connect two coworkers, first click on one, then on the other.
> A line will appear between them, indicating that they are friends.
>
>   * •
>
> To disconnect two coworkers,
> simply click on the line that connects them.
> The line will disappear, indicating that they are not friends.
>
>

>
> Notes:
>
> If there is no line between two coworkers,
> it means you think they are not friends.
> Even if in your drawing they look very close to each other!
> So, if you think two coworkers are friends,
> always make sure to connect them with a line.
>
> To make your job easier,
> we have already connected the friendship pairs from the list for you.
> And if you attempt to connect a non-friendship pair from the list,
> we indicate the error with a red “X”.
>
> We start the coworkers at random positions,
> so make sure to move them around,
> as this will help you visualize the network.