  We introduce a class of random graphs that we argue meets many of the
desiderata one would demand of a model to serve as the foundation for a
statistical analysis of real-world networks. The class of random graphs is
defined by a probabilistic symmetry: invariance of the distribution of each
graph to an arbitrary relabelings of its vertices. In particular, following
Caron and Fox, we interpret a symmetric simple point process on
$\mathbb{R}_+^2$ as the edge set of a random graph, and formalize the
probabilistic symmetry as joint exchangeability of the point process. We give a
representation theorem for the class of random graphs satisfying this symmetry
via a straightforward specialization of Kallenberg's representation theorem for
jointly exchangeable random measures on $\mathbb{R}_+^2$. The distribution of
every such random graph is characterized by three (potentially random)
components: a nonnegative real $I \in \mathbb{R}_+$, an integrable function $S:
\mathbb{R}_+ \to \mathbb{R}_+$, and a symmetric measurable function $W:
\mathbb{R}_+^2 \to [0,1]$ that satisfies several weak integrability conditions.
We call the triple $(I,S,W)$ a graphex, in analogy to graphons, which
characterize the (dense) exchangeable graphs on $\mathbb{N}$. Indeed, the model
we introduce here contains the exchangeable graphs as a special case, as well
as the "sparse exchangeable" model of Caron and Fox. We study the structure of
these random graphs, and show that they can give rise to interesting structure,
including sparse graph sequences. We give explicit equations for expectations
of certain graph statistics, as well as the limiting degree distribution. We
also show that certain families of graphexes give rise to random graphs that,
asymptotically, contain an arbitrarily large fraction of the vertices in a
single connected component.
