
2
measures such as the clustering coefficient can be ex-
tended to hypergraphs [5, 16, 31–33]. A recent study
investigated the occurence of higher-order motifs [34] and
community detection was also considered [35, 36]. New
measures can however be defined and we will discuss in
particular the statistics of the intersection between two
hyperedges as being the number of nodes they have in
common [36]. For spatial hypergraphs, the geometrical
structure of hyperedges is naturally of interest and we
will discuss some quantities that characterize it.
It was already been noted in [16] that few flexible null
models were proposed in the context of interactions oc-
curing within groups of vertices of arbitrary size. In
[16, 37], a null model for hypergraphs at fixed node de-
gree and edge dimensions is proposed. This generalizes
to hypergraphs the usual configuration model [38]. Other
models for higher-order interactions were described in the
review [5] such as bipartite models, exponential graph
models, or motifs models, but in general hypergraph
models are less developed. Most of these models are in-
troduced in the mathematical literature and are usually
thought as immediate generalizations of classical graph
models. In many of these models, it is usually assumed
that all hyperedges have the same size, which is a strong
constraint. We note that an interesting hypernetwork
growth model was proposed in [39] where both the idea
of hyperedge growth and hyperedge preferential attach-
ment were introduced.
Here, the goal is to present a mechanism that can gen-
erate (in a simple way and with low complexity) a fam-
ily of different hypergraphs and which displays the same
level of flexibility of complex network models. We pro-
pose here such a framework and introduce a class of mod-
els that relies on a single ingredient: the probability that
a node belongs to a hyperedge. We will consider vari-
ous illustrations of this class of models. We will start
with the simplest one that could be seen as some sort of
‘Erdos-Renyi hypergraph’, and also discuss preferential
attachment. We then introduce space in different ways
and in particular discuss in more detail a random geo-
metric hypergraph where the probability that a vertex
belongs to a hyperedge is 1 if its distance is less than
a threshold, 0 otherwise. For all these illustrations, we
analyse simple measures (such as the degree of vertices or
sizes of the hyperedges), the structural transition for the
giant component, and also introduce new measures. In
particular, for spatial hypergraphs, we characterize the
spatial properties of hyperedges.
A CLASS OF HYPERGRAPH MODELS
Hypergraphs can be represented as bipartite graphs
between the nodes and hyperedges (see Fig. 2 for an ex-
ample). In this representation the links between nodes
and hyperedges indicate a membership relation: there is
a link between node iand hyperedge eif i∈e. The main
e1
<latexit sha1_base64="vfqdS6lHzQ6Q+LuAqKTlLDDwq2Q=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0mqYI8FLx4r2g9oQ9lsJ+3SzSbsboQS+hO8eFDEq7/Im//GbZuDtj4YeLw3w8y8IBFcG9f9dgobm1vbO8Xd0t7+weFR+fikreNUMWyxWMSqG1CNgktsGW4EdhOFNAoEdoLJ7dzvPKHSPJaPZpqgH9GR5CFn1FjpAQfeoFxxq+4CZJ14OalAjuag/NUfxiyNUBomqNY9z02Mn1FlOBM4K/VTjQllEzrCnqWSRqj9bHHqjFxYZUjCWNmShizU3xMZjbSeRoHtjKgZ61VvLv7n9VIT1v2MyyQ1KNlyUZgKYmIy/5sMuUJmxNQSyhS3txI2pooyY9Mp2RC81ZfXSbtW9a6qtfvrSqOex1GEMziHS/DgBhpwB01oAYMRPMMrvDnCeXHenY9la8HJZ07hD5zPH+z7jYc=</latexit>
e2
<latexit sha1_base64="ClmAiYePPwc16uOUmRAHBqDOWKo=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0mqYI8FLx4r2g9oQ9lsJ+3SzSbsboQS+hO8eFDEq7/Im//GbZuDtj4YeLw3w8y8IBFcG9f9dgobm1vbO8Xd0t7+weFR+fikreNUMWyxWMSqG1CNgktsGW4EdhOFNAoEdoLJ7dzvPKHSPJaPZpqgH9GR5CFn1FjpAQe1QbniVt0FyDrxclKBHM1B+as/jFkaoTRMUK17npsYP6PKcCZwVuqnGhPKJnSEPUsljVD72eLUGbmwypCEsbIlDVmovycyGmk9jQLbGVEz1qveXPzP66UmrPsZl0lqULLlojAVxMRk/jcZcoXMiKkllClubyVsTBVlxqZTsiF4qy+vk3at6l1Va/fXlUY9j6MIZ3AOl+DBDTTgDprQAgYjeIZXeHOE8+K8Ox/L1oKTz5zCHzifP+5/jYg=</latexit>
e3
<latexit sha1_base64="wDDpmP9taYiF/PJl1dQ9Aa0490U=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0lawR4LXjxWtLXQhrLZTtqlm03Y3Qgl9Cd48aCIV3+RN/+N2zYHbX0w8Hhvhpl5QSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJR8epYthmsYhVN6AaBZfYNtwI7CYKaRQIfAwmN3P/8QmV5rF8MNME/YiOJA85o8ZK9zioD8oVt+ouQNaJl5MK5GgNyl/9YczSCKVhgmrd89zE+BlVhjOBs1I/1ZhQNqEj7FkqaYTazxanzsiFVYYkjJUtachC/T2R0UjraRTYzoiasV715uJ/Xi81YcPPuExSg5ItF4WpICYm87/JkCtkRkwtoUxxeythY6ooMzadkg3BW315nXRqVa9erd1dVZqNPI4inME5XIIH19CEW2hBGxiM4Ble4c0Rzovz7nwsWwtOPnMKf+B8/gDwA42J</latexit>
e4
<latexit sha1_base64="piqyIElbz+OXHuaayIQVt+n7jkI=">AAAB6nicbVBNS8NAEJ34WetX1aOXxSJ4Kkkt2GPBi8eK9gPaUDbbSbt0swm7G6GE/gQvHhTx6i/y5r9x2+agrQ8GHu/NMDMvSATXxnW/nY3Nre2d3cJecf/g8Oi4dHLa1nGqGLZYLGLVDahGwSW2DDcCu4lCGgUCO8Hkdu53nlBpHstHM03Qj+hI8pAzaqz0gIPaoFR2K+4CZJ14OSlDjuag9NUfxiyNUBomqNY9z02Mn1FlOBM4K/ZTjQllEzrCnqWSRqj9bHHqjFxaZUjCWNmShizU3xMZjbSeRoHtjKgZ61VvLv7n9VIT1v2MyyQ1KNlyUZgKYmIy/5sMuUJmxNQSyhS3txI2pooyY9Mp2hC81ZfXSbta8a4r1ftauVHP4yjAOVzAFXhwAw24gya0gMEInuEV3hzhvDjvzseydcPJZ87gD5zPH/GHjYo=</latexit>
e5
<latexit sha1_base64="AaFfpV7EVSXrUNJrfW+cN8/nTxw=">AAAB6nicbVBNS8NAEJ34WetX1aOXxSJ4KklV7LHgxWNF+wFtKJvtpF262YTdjVBCf4IXD4p49Rd589+4bXPQ1gcDj/dmmJkXJIJr47rfztr6xubWdmGnuLu3f3BYOjpu6ThVDJssFrHqBFSj4BKbhhuBnUQhjQKB7WB8O/PbT6g0j+WjmSToR3QoecgZNVZ6wP51v1R2K+4cZJV4OSlDjka/9NUbxCyNUBomqNZdz02Mn1FlOBM4LfZSjQllYzrErqWSRqj9bH7qlJxbZUDCWNmShszV3xMZjbSeRIHtjKgZ6WVvJv7ndVMT1vyMyyQ1KNliUZgKYmIy+5sMuEJmxMQSyhS3txI2oooyY9Mp2hC85ZdXSata8S4r1furcr2Wx1GAUziDC/DgBupwBw1oAoMhPMMrvDnCeXHenY9F65qTz5zAHzifP/MLjYs=</latexit>
<latexit sha1_base64="PMMVAj56CwSF/6ga4otp5Igdjpw=">AAAB6HicbVBNS8NAEJ34WetX1aOXxSJ4KkkV7LHgxWML9gPaUDbbSbt2swm7G6GE/gIvHhTx6k/y5r9x2+agrQ8GHu/NMDMvSATXxnW/nY3Nre2d3cJecf/g8Oi4dHLa1nGqGLZYLGLVDahGwSW2DDcCu4lCGgUCO8Hkbu53nlBpHssHM03Qj+hI8pAzaqzU9AalsltxFyDrxMtJGXI0BqWv/jBmaYTSMEG17nluYvyMKsOZwFmxn2pMKJvQEfYslTRC7WeLQ2fk0ipDEsbKljRkof6eyGik9TQKbGdEzVivenPxP6+XmrDmZ1wmqUHJlovCVBATk/nXZMgVMiOmllCmuL2VsDFVlBmbTdGG4K2+vE7a1Yp3Xak2b8r1Wh5HAc7hAq7Ag1uowz00oAUMEJ7hFd6cR+fFeXc+lq0bTj5zBn/gfP4AeOmMrw==</latexit>
2
<latexit sha1_base64="rEHzCxvbCIUsFnb9BW4eMmFoKQI=">AAAB6HicbVBNS8NAEJ34WetX1aOXxSJ4KkkV7LHgxWML9gPaUDbbSbt2swm7G6GE/gIvHhTx6k/y5r9x2+agrQ8GHu/NMDMvSATXxnW/nY3Nre2d3cJecf/g8Oi4dHLa1nGqGLZYLGLVDahGwSW2DDcCu4lCGgUCO8Hkbu53nlBpHssHM03Qj+hI8pAzaqzUrA5KZbfiLkDWiZeTMuRoDEpf/WHM0gilYYJq3fPcxPgZVYYzgbNiP9WYUDahI+xZKmmE2s8Wh87IpVWGJIyVLWnIQv09kdFI62kU2M6ImrFe9ebif14vNWHNz7hMUoOSLReFqSAmJvOvyZArZEZMLaFMcXsrYWOqKDM2m6INwVt9eZ20qxXvulJt3pTrtTyOApzDBVyBB7dQh3toQAsYIDzDK7w5j86L8+58LFs3nHzmDP7A+fwBem2MsA==</latexit>
3
<latexit sha1_base64="cOd0jNdVYgQWylXEoV8RErDIGho=">AAAB6HicbVDLTgJBEOzFF+IL9ehlIjHxRHbBRI4kXjxCIo8ENmR2aGBkdnYzM2tCNnyBFw8a49VP8ubfOMAeFKykk0pVd7q7glhwbVz328ltbe/s7uX3CweHR8cnxdOzto4SxbDFIhGpbkA1Ci6xZbgR2I0V0jAQ2Ammdwu/84RK80g+mFmMfkjHko84o8ZKzeqgWHLL7hJkk3gZKUGGxqD41R9GLAlRGiao1j3PjY2fUmU4Ezgv9BONMWVTOsaepZKGqP10eeicXFllSEaRsiUNWaq/J1Iaaj0LA9sZUjPR695C/M/rJWZU81Mu48SgZKtFo0QQE5HF12TIFTIjZpZQpri9lbAJVZQZm03BhuCtv7xJ2pWyVy1Xmjelei2LIw8XcAnX4MEt1OEeGtACBgjP8ApvzqPz4rw7H6vWnJPNnMMfOJ8/e/GMsQ==</latexit>
4
<latexit sha1_base64="YcnJlhsaMwnAtsw0E/0+gBbl6ng=">AAAB6HicbVDLTgJBEOzFF+IL9ehlIjHxRHaRRI4kXjxCIo8ENmR2aGBkdnYzM2tCNnyBFw8a49VP8ubfOMAeFKykk0pVd7q7glhwbVz328ltbe/s7uX3CweHR8cnxdOzto4SxbDFIhGpbkA1Ci6xZbgR2I0V0jAQ2Ammdwu/84RK80g+mFmMfkjHko84o8ZKzeqgWHLL7hJkk3gZKUGGxqD41R9GLAlRGiao1j3PjY2fUmU4Ezgv9BONMWVTOsaepZKGqP10eeicXFllSEaRsiUNWaq/J1Iaaj0LA9sZUjPR695C/M/rJWZU81Mu48SgZKtFo0QQE5HF12TIFTIjZpZQpri9lbAJVZQZm03BhuCtv7xJ2pWyd1OuNKulei2LIw8XcAnX4MEt1OEeGtACBgjP8ApvzqPz4rw7H6vWnJPNnMMfOJ8/fXWMsg==</latexit>
FIG. 2. Example of a small hypergraph with N= 4 vertices
and E= 5 hyperedges represented as a bipartite graph. The
degree of the vertices are k1= 2, k2= 1, k3= 3, k4= 2 and
the sizes of the hyperedges are |e1|= 2, |e2|= 1, |e3|= 3,
|e4|=|e5|= 1. There are two connected components in this
hypergraph {1,2,3}and {4}. The intersection between some
of the hyperedges is: e1∩e2={3},e1∩e3={1,3}, etc. The
sum Pikiis equal to the sum of hyperedge sizes Pj|ej|and
equal to the number of links.
idea of the class of models discussed here is to introduce
the connection probability P(v∈e) that a node vbe-
longs to a hyperedge e. This is directly related to the
incidence matrix Iof the hypergraph which is a N×E
matrix with elements Iie equal to 1 if i∈eand 0 other-
wise. This connection probability can be written under
the form
P(v∈e) = F(e, d(v, e), ...) (1)
where Fis in general a function of the hyperedge e, its
vertices, or some distance between vand e(we will see
various examples below). We note here that in contrast
with a remark in [35] that it is ‘unclear how to impose
properties on a hypergraph when a bipartite represen-
tation is used’, we actually believe that this representa-
tion provides a simple framework for introducing various
mechanisms. We could even think of a generalization of
Eq. 1 in the spirit of the hidden-variable model for net-
works. In these models, some characteristics are assigned
to nodes such as fitnesses [40, 41], or coordinates in a la-
tent space [42–44]. The connection function Fin Eq. 1
could in principle depend on these hidden variables. For
example, if each vertex vhas a fitness ηv, a hyperedge
composed of vertices vi1, vi2, . . . , vimhas then a fitness
which will be a function of the fitnesses of all its vertices
η(e) = G(ηi1, ηi2, . . . , ηim), and the connection function
could then be chosen as
P(v∈e) = F(η(e)) (2)
In this article, we will essentially consider the case where
the function depends on some properties of the hypere-
dege e, including its position in space.
This definition (Eq. 1) is obviously very general and
we will focus here on different functions. First, we will
consider the constant case F=p∈[0,1] which reminds
us of the Erdos-Renyi model [45]. We will then consider
the preferential attachment case where the function F