A class of models for random hypergraphs Marc Barthelemy Universit e Paris-Saclay CEA CNRS Institut de Physique Th eorique 91191 Gif-sur-Yvette France and

2025-04-30 0 0 1MB 11 页 10玖币
侵权投诉
A class of models for random hypergraphs
Marc Barthelemy
Universit´e Paris-Saclay, CEA, CNRS, Institut de Physique Th´eorique, 91191, Gif-sur-Yvette, France and
Centre d’Analyse et de Math´ematique Sociales (CNRS/EHESS) 54 Avenue de Raspail, 75006 Paris, France
Despite the recently exhibited importance of higher-order interactions for various processes, few
flexible (null) models are available. In particular, most studies on hypergraphs focus on a small
set of theoretical models. Here, we introduce a class of models for random hypergraphs which
displays a similar level of flexibility of complex network models and where the main ingredient
is the probability that a node belongs to a hyperedge. When this probability is a constant, we
obtain a random hypergraph in the same spirit as the Erdos-Renyi graph. This framework also
allows us to introduce different ingredients such as the preferential attachment for hypergraphs,
or spatial random hypergraphs. In particular, we show that for the Erdos-Renyi case there is
a transition threshold scaling as 1/EN where Nis the number of nodes and Ethe number of
hyperedges. We also discuss a random geometric hypergraph which displays a percolation transition
for a threshold distance scaling as r
c1/E. For these various models, we provide results for the
most interesting measures, and also introduce new ones in the spatial case for characterizing the
geometrical properties of hyperedges. These different models might serve as benchmarks useful for
analyzing empirical data.
INTRODUCTION
Complex networks became increasingly important for
describing a large number of processes and were the sub-
ject of many studies for more than 20 years now [1–3].
Recent analysis of complex systems [4–7] however showed
that networks provide a limited view. Indeed networks
(or graphs) describe a set of pairwise interactions and
exclude any higher-order interactions involving groups of
more than two units. With the increasing amount of data
many higher-order interactions were observed in a large
variety of context, from systems biology [8], face-to-face
systems [9], collaboration teams and networks [10, 11],
ecosystems [12], the human brain [13, 14], document
clusters in information networks, or multicast groups in
communication networks, etc. [15, 16]. Modeling these
higher-order interactions with graphs might lead to er-
roneous interpretations, calling for the need of a more
flexible framework. In addition, these higher-order inter-
actions are highly relevant for all possible processes that
take place in these systems [6]. These processes include
contagion where a disease can spread in a non-dyadic way
[17–19], diffusion [20, 21], cooperative processes [22], or
synchronization [23–25]. Models for hypergraphs - null,
or spatial for example, are then much needed for analyz-
ing processes that involve the interaction between more
than two nodes.
In order to go beyond usual graphs, a natural extension
consists in allowing edges that can connect an arbitrary
number of nodes. These ‘hyperedges’ constructed over a
set of vertices define what is called a hypergraph [26, 27].
More formally, a hypergraph H= (V, E) where Vis a
set of elements (the vertices or nodes) and Eis the set
of hyperedges where each hyperedge is defined as a non-
empty subset of V(a simple example is shown in Fig. 1).
For a directed hypergraph, the hyperedges are not sets,
but an ordered pair of subsets of V, constituting the tail
and head of the hyperedge [28–30].
Hyperedge 0
Hyperedge 1
Hyperedge 2
FIG. 1. Classical representation of a hypergraph. We have
here |V|=N= 10 vertices and E= 3 hyperedges. The
hyperedges are e0={0,1},e1={2,3,4,5,8}, and e2=
{0,6,7,9,10}, with sizes 2, 5, and 5, respectively. All the
nodes have degree k= 1, except for nodes 0,1,2,8 which
have a degree k= 2.
The number N=|V|of vertices is called the order of
the hypergraph, and the number of hyperedges M=|E|
is usually called the size of the hypergraph. The size
of an hyperedge |ei|is the number of its vertices. The
degree of a vertex is then simply given by the number
of hyperedges to which it is connected. A simpler hy-
pergraph considered in many studies is obtained when
all hyperedges have the same cardinality dand is then
called a d-uniform hypergraph (the rank of a hypergraph
is r= maxE|e|and the anti-rank r= minE|e|, and when
both quantities are equal the hypergraph is uniform). A
2-uniform hypergraph is then a standard graph.
Many measures are available for hypergraphs. Walks,
paths and centrality measures can be defined and other
arXiv:2210.12698v3 [cond-mat.stat-mech] 17 Dec 2022
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 ie. The main
Vertices
Hyperedges
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>
1
<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>
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: e1e2={3},e1e3={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(ve) 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 ieand 0 other-
wise. This connection probability can be written under
the form
P(ve) = 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(ve) = 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
3
depends on the size of the hyperedge. We then end this
paper by considering cases where the nodes are in a 2d
space (we will mainly consider the d= 2 case but the
generalization to larger dimensions is trivial) and where
the function Fdepends on a distance (to be defined)
between the vertex vand the edge e. For all these models,
we will present the result for usual measures but also
develop new measures tailored to spatial hypergraphs.
Throughout this work, we denote by Nthe order of
the hypergraph (which is the number of nodes) and E
the number of hyperedges. For all the models considered
here, we will assume that the number Eof hyperedges is
given. Once an initial set of hyperedges is given (in cases
studied here, the initial hyperedges comprise single nodes
chosen at random), we can iterate over all nodes and ap-
ply Eq. 1. Once all nodes are tested, we get the final hy-
pergraph that we measure. The simplest measure is the
degree kiof a node i(which is the number of hyperedges
to which it belongs). The degree can also be computed
as the sum of row elements of the incidence matrix Iie:
ki=PeIie (see for example the review [5]). The size
ml=|el|of the hyperedge lis the number of nodes it
contains. Naturally, the average degree and size (and the
distribution of kand m) are important quantities, and it
should be noted that they are not independent. Indeed,
if we use the links in the bipartite representation of the
hypergraph (i.e. there is a link between node iand hy-
peredge eif ie, see Fig. 2), their number Lcan be
expressed in two different ways as L=Piki=Pj|ej|.
This relation can be rewritten as
Nhki=Ehmi(3)
where hkidenotes the average degree and hmithe aver-
age size of hyperedges. The distributions P(k) and P(m)
are then natural objects to study. We will also focus
on other quantities: the intersection between two hyper-
edges (a quantity that is trivial for graphs and equal to
one), and for spatial hypergraphs the spatial extension
s(e) of a hyperedge e. We will also discuss connectivity
properties of these hypergraphs and in particular we will
focus on abrupt structural changes characterized by the
emergence of a giant component (that will need to be
defined) scaling with N.
THE SIMPLEST RANDOM HYPERGRAPH
Definition
There is no unique definition of random hypergraphs
and various generalization of the classical Erdos-Renyi
graph were proposed (see for example [11]). In particular,
mathematicians like to think of a set of all possible hyper-
graphs - given some parameters (number of nodes, etc) -
and to consider a uniform distribution over this set [46].
More specifically, many papers focus on k-uniform hy-
pergraph for which the size of hyperedges is constant and
equal to k. Given a set of Vvertices and a set of subsets
of these vertices we can construct the natural analogue
of Erdos-Renyi graphs [45]: each k-tuple of vertices is a
hyperedge with probability p[47] (more formally, the set
Hk(n, p) denotes the random k-uniform hypergraph with
vertex set [n] = {1,2, ..., n}in which each of the n
kpos-
sible edges is present independently with probability p).
In other studies, every hypergraph of Ehyperedges on N
nodes has the same probability [48] (the classical Erdos-
Renyi random graph is then recovered in the case k= 2).
This type of model was discusssed by mathematicians in
particular about the phase transition for the giant com-
ponent [4, 46, 47, 49–51]. For k= 2, we recover usual
graphs and from Erdos and Renyi [45], we know that
there is a transition for E=cN with c= 1/2 (which
corresponds to an average degree hki= 2E/M = 1).
This transition is characterized by an abrupt structural
change with the emergence of a giant component scal-
ing. The general result for hypergraphs obtained in [49]
is similar and states that a giant component appears for
c= 1/k(k1). We refer the reader interested in some
mathematical aspects of this problem to the book [52].
Here, we will construct a ‘Erdos-Renyi hypergraph’ in
the context of Eq. 1. For the usual Erdos-Renyi graph,
the connection probability between two nodes is constant
and similarly for the hypergraph we will then assume that
for each vertex vVand for each hyperedge e, there
is a constant probability pthat vbelongs to e. If this
probability is constant and equal to p, we can then write
P(ve) = p(4)
where p[0,1]. Starting from a set of Nnodes, we
choose a random set of Ehyperedges (which are Enodes
chosen at random), and add recursively nodes to these
hyperedges following the rule Eq. 4.
Degree and size
This random hypergraph is a very simple model and
most properties are trivial. In particular, the degree k
and size mdistributions are easy to compute and are
binomials
P(ki=k) = E
kpk(1 p)Nk(5)
P(|ei|=m) = N
mpm(1 p)Em(6)
and the average degree is then hki=pE and the average
hyperedge size hmi=pN.
If nodes are in space - in the disk of radius r0for exam-
ple (we will see below in more details examples of spatial
摘要:

AclassofmodelsforrandomhypergraphsMarcBarthelemyUniversiteParis-Saclay,CEA,CNRS,InstitutdePhysiqueTheorique,91191,Gif-sur-Yvette,FranceandCentred'AnalyseetdeMathematiqueSociales(CNRS/EHESS)54AvenuedeRaspail,75006Paris,FranceDespitetherecentlyexhibitedimportanceofhigher-orderinteractionsforvariou...

展开>> 收起<<
A class of models for random hypergraphs Marc Barthelemy Universit e Paris-Saclay CEA CNRS Institut de Physique Th eorique 91191 Gif-sur-Yvette France and.pdf

共11页,预览3页

还剩页未读, 继续阅读

声明:本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知玖贝云文库,我们立即给予删除!
分类:图书资源 价格:10玖币 属性:11 页 大小:1MB 格式:PDF 时间:2025-04-30

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务
/ 11
客服
关注