Mixing patterns in graphs with higher-order structure Peter MannLei Fang and Simon Dobson School of Computer Science University of St Andrews St Andrews Fife KY16 9SX United Kingdom

2025-04-29 0 0 633.26KB 15 页 10玖币

侵权投诉

Mixing patterns in graphs with higher-order structure

Peter Mann,∗Lei Fang, and Simon Dobson

School of Computer Science, University of St Andrews, St Andrews, Fife KY16 9SX, United Kingdom

(Dated: October 7, 2022)

In this paper we examine the percolation properties of higher-order networks that have non-trivial

clustering and subgraph-based assortative mixing (the tendency of vertices to connect to other

vertices based on subgraph joint degree). Our analytical method is based on generating functions.

We also propose a Monte Carlo graph generation algorithm to draw random networks from the

ensemble of graphs with ﬁxed statistics. We use our model to understand the eﬀect that network

microstructure has, through the arrangement of clustering, on the global properties. Finally, we

use an edge disjoint clique cover to represent empirical networks using our formulation, ﬁnding the

resultant model oﬀers a signiﬁcant improvement over edge-based theory.

I. INTRODUCTION

Traditional network theory is limited to pairwise in-

teractions. Higher-order, non-dyadic interactions lead to

fresh insight into collective dynamics that cannot be de-

scribed by edge-based theory [1–4]. Theoretical models

that include higher-order interactions become increas-

ingly complicated compared to edge-based models and

generalisations of the deﬁnitions of traditional concepts,

such as assortativity or clustering are often required.

The ability to generate a random graph from an en-

semble of random graphs that have statistically equiva-

lent properties allows us to model, and subsequently to

understand, the topological features that drive the be-

haviour of dynamical processes that occur over networks.

Topological features can be extrinsic (ﬁnite-size eﬀects),

whilst others are intrinsic, such as the clustering coeﬃ-

cient, C[5, 6], or the degree assortativity [7–9]. Some

properties are locally deﬁned, and as such are subject

to local anisotropy; whilst others characterise global at-

tributes of the network that are averaged over all vertices.

Finally, ensemble properties manifest for a collection of

graphs that are statistically equivalent in some manner.

Often, the intrinsic properties of networks are not inde-

pendent of one another. For instance, two networks with

equivalent clustering coeﬃcients could exhibit diﬀerent

responses to a given dynamical process due to the organ-

isation of their triangles. Clustering is known to increase

the critical point of the bond percolation process and

reduce the size of the expected giant connected compo-

nent (GCC) [10–18]. However, vertices involved in many

triangles that tend to connect to other vertices with a

high triangle count may induce assortative correlations

among the overall degrees. In turn, the critical point

of positively assorted networks is reduced compared to

the neutral model [7] and other properties can also be

aﬀected [19]. The observed behaviour of a percolation

process depends on the interplay between the clustering

and the assortativity [6]. Therefore, it is important to

model both the role of clustering as well as the role of

degree assortativity.

One modelling framework is the conﬁguration model

(CM) that enables the construction of a particular lo-

cally tree-like random graph from a distribution of de-

grees [20]. CM networks are regarded to be inﬁnitely

large, such that ﬂuctuations from ensemble averages do

not eﬀect the statistics of the model. This model has

received signiﬁcant attention in the literature, and has

been extended to the so-called generalised conﬁguration

model (GCM) to incorporate non-trivial clustering and

higher-order structure among vertices [21]. In the GCM,

a set ~τ of substrate motifs is deﬁned (such as cliques

or chordless cycles of diﬀerent sizes) and the number of

edge-disjoint motifs of each topology that a given vertex

belongs to is described by a tuple, known as its joint de-

gree that takes values in Zn

≥0where nis the number of

distinct motif topologies in the model. For example, for

a model containing only 2- and 3-cliques, a vertex that

belongs to 3 ordinary edges, 2 triangles has joint degree

(s, t) = (3,2), see Fig 1. Vertex joint degrees are drawn

from a multivariate distribution of joint degrees, ps,t,h,...,

that deﬁnes the probability that a vertex belongs to s

ordinary edges, ttriangles, h4-cycles etc. When ~τ is cho-

sen to contain only ordinary edges (2-cliques), the GCM

collapses to the standard CM. The CM is known to cre-

(2,1)

(1,0)

(3,0)

(0,1)

(2,1)

FIG. 1. A snapshot of a 2- and 3-clique clustered graph with

vertices labelled with their joint degree tuples (s, t).

ate networks with no assortativity among the degrees of

neighbouring vertices due to the stochastic nature of the

construction algorithm [21]; vertex degrees are indepen-

dent random variables. Assortativity can be inserted, in

a controlled manner, into the CM via a degree-preserving

Markov Chain Monte Carlo (MCMC) rewiring algorithm

where the correlations converge to a target value [7, 8].

arXiv:2210.02528v1 [physics.soc-ph] 5 Oct 2022

Hasegawa et al [16] examined the role of clustering

and assortativity in the percolating component of tree-

triangle networks. Recently, Mann et al investigated the

inter-subgraph correlation properties that arise naturally

in the percolating component of GCM networks that are

composed of arbitrary sized cliques that have neutral

mixing patterns in the substrate graph [22].

In this paper, we extend that work to examine the

inter-subgraph properties of GCM networks that have

arbitrary clique clustering and subgraph correlations in

the substrate network. To do this, we develop an analyt-

ical method based on generating functions and introduce

an MCMC rewiring algorithm to simulate such networks.

These steps allow the synthesis of random graphs drawn

from an ensemble of graphs with a given clustering coeﬃ-

cient Cand correlation structure among the joint degree

tuples. This model can be used to probe the role that

both clustering and assortativity have on the properties

of the bond percolation process and will likely lead to the

detailed study of higher-order structure for other kinds

of dynamical processes on networks beyond the percola-

tion model. Additionally, our model allows the cluster-

ing and correlation structure from an empirical network

to be gathered through means of an edge-disjoint clique

cover [22, 23]. Through our MCMC algorithm, synthetic

networks, possibly containing additional vertices to the

empirical network, can then be created. In this way, our

model allows ensemble representations with ﬁxed statis-

tics of empirical networks to be created and studied. We

remark, that the information in our model can readily be

compressed from inter-subgraph correlations to correla-

tions between overall degrees; however, there is a corre-

sponding information loss following this process.

II. THEORETICAL

Correlations can arise via three distinct processes in

GCM networks. Firstly, correlation between the joint

degrees of neighbouring vertices that belong to the same

clique type. For instance, three vertices in a triangle must

all have t6= 0. In this manner, vertices with membership

of a given 3-clique are somewhat assorted together; they

will never connect to vertices that don’t belong to trian-

gles. However, this correlation does not extend beyond

the scope of the motif to which the edge belongs and so,

we refer to it as the trivial correlation. In other words,

the excess joint degrees (the remaining joint degree tu-

ples excluding the motif to which the edge belongs) of two

vertices at the ends of a randomly selected edge are not

correlated in the default GCM construction. And, ex-

cluding the trivial assortativity due to belonging to the

same motif, there are no speciﬁc correlations between

vertices at play.

We can also discuss assortativity between the overall

degrees of vertices in the GCM. The overall degree of

a vertex that belongs to s2-cliques, t3-cliques, w4-

cliques (and so on) is given by k=s+ 2t+ 3c+. . . .

This assortativity often arises in an uncontrolled man-

ner. For example, a GCM network composed of 2-cliques

and 10-cliques may be absent of any correlation structure

among the distribution in the numbers of cliques a vertex

belongs to; however, by virtue of the increase in overall

degree, vertices that belong to 10-cliques will likely be of

higher-degree than vertices that belong to just 2-cliques,

and as a result, will exhibit positive correlations among

the overall degrees if this is the case [10, 16].

Finally, we can inject correlation into GCM networks

deliberately, in a detailed and controlled fashion, by spec-

ifying how likely it is that a vertex with a given joint de-

gree tuple (s0, t0, . . . , c0) has a neighbour with a certain

joint degree tuple (s0, t0, . . . , c0). In general, this probabil-

ity is diﬀerent depending on the topology of the edge (to

which clique it belongs to). This kind of correlation is the

most general of the three types that arise in the GCM;

since the other correlation types are subsets of this; and

so, it is the focus of this paper.

We restrict our attention to GCM networks that are

composed of 2- and 3-cliques, symbolised by ~τ ={⊥,∆},

respectively. Let eτ,s0t0,s0t0be the probability that a ran-

domly chosen τ-edge leads to vertices with excess (re-

maining) joint degrees of (s0, t0) and (s0, t0) where sand

tare the numbers of 2- and 3-cliques, respectively, that

each vertex belongs to, see Fig 2. The joint excess joint

degree distribution is the data input to the model; other

familiar quantities such as excess joint degree distribu-

tion, qτ,s,t and the joint degree distribution, ps,t can be

derived from these information-rich function.

FIG. 2. The joint excess joint degree distribution of topology

τis created by selecting all τ-edges and measuring the joint

excess degrees of the terminal vertices, excluding the motif

the selected edge belongs to. In the example, the selected

edge (yellow dashed) has vertices of excess joint degrees (2,1)

and (1,1).

There is an eτ,s0t0,s0t0function for each τ∈~τ; since, we

can follow card(~τ) distinct edge-topologies. We assume

that

s0X

t0X

s0X

eτ,s0t0,s0t0= 1,(1)

with all indices running from 0,...,∞unless otherwise

stated. We can recover the excess joint degree distribu-

tion, which is the probability that an edge of topology τ

is chosen at random and leads to a vertex of remaining

degree (s0, t0), as

qτ,s0t0=X

s0X

eτ,s0t0,s0t0.(2)

We can invert qτ,s,t to obtain pst for each τ∈ {⊥,∆}.

For the tree-triangle model this is given by

p⊥

s,t =q⊥,s−1,ts

P

s0t0

q⊥,s0−1,ts0,(3a)

p∆

s,t =q∆,s,t−1t

P

s0t0

q∆,s0,t−1t0,(3b)

which can be veriﬁed by inserting q⊥,s,t =

(s+ 1)ps+1,t/hsiinto Eq 3a or q∆,s,t = (t+ 1)ps,t+1/hti

into Eq 3b where hsiis the average number of 2-cliques

a vertex belongs to

hsi=X

sps,t,(4)

and similarly for hti. We remark that, in general, the

inverted distributions, pτ

s,t, are not numerically equiva-

lent to one another, nor do they necessarily contain all

(s, t) tuples. This is because, the excess joint degree dis-

tributions are not equivalent to one another for diﬀerent

topologies. To see this, q⊥,s,t, (the joint excess distribu-

tion obtained from randomly selected 2-clique edges) can

yield no information on the marginal distribution of how

vertices with zero 2-cliques, but non-zero 3-clique counts

interact; and vice versa for q∆,s,t; since, we cannot follow

a 2-clique edge to a vertex with no 2-cliques. However,

the actual joint degree distribution, ps,t, can be recovered

by multiplying each partially observed joint degree distri-

bution by the fraction of the network (by vertex count)

that was used to create the observation. For instance,

ps,t =nτpτ

s,t where nτare the fraction of vertices that

belong to at least one τmotif. For a coherent model, we

have nτpτ

s,t =nνpν

s,t for a given (s, t) joint degree and for

τ, ν ∈~τ. Each nτcan readily be found as one minus the

fraction of vertices that do not belong to any τcliques;

for instance n⊥= 1 −Ptp0,t. When all vertices belong

to both 2- and 3-cliques, nτ=nν, and the inverted joint

distributions coincide. Finally, it should be noted that we

can obtain the joint excess degree distribution between

overall degrees ej,k from eτ,s0t0,s0t0by application of a

Kronecker delta

ej,k =X

s0,t0X

s0t0

w⊥e⊥,s0t0,s0t0δj,s0+2t0δk,s0+2t0

s0,t0X

s0t0

w∆e∆,s0t0,s0t0δj,s0+2t0+1δk,s0+2t0+1.(5)

The +1 terms in the ﬁnal two delta functions account

for the contribution of the other edge within the 3-clique

towards the overall degree. The weighting factors wτac-

count for the required renormalisation from the indepen-

dently normalised distributions to a single distribution.

These are given by

w⊥=P

spst

spst + 2 P

tpst

,(6)

and

w∆=

tpst

spst + 2 P

tpst

.(7)

This expression compresses the information available

from the model and collapses to the formulation derived

in [8]. Additionally, the overall degree distribution pk

can readily be found from a joint degree distribution [6]

pk=X

pstδk,s+2t.(8)

A. G0generating function

We can use eτ,s0t0,s0t0to ﬁnd ensemble properties

by deriving a generating function formulation for the

model. Suppose that a vertex of joint degree (s0, t0)

is chosen from the network. Now suppose that we

traverse the s02-clique edges and record the excess

joint degrees (s0, t0) of those neighbouring vertices. Let

{r⊥}={r⊥,s1,t1, . . . , r⊥,sn,tn}be the conﬁguration of

those neighbour joint degrees we might record; such that

there are r⊥,s0,t0neighbours of excess joint degree (s0, t0).

The probability of a given conﬁguration of excess joint

degrees surrounding the focal vertex following s02-clique

edges is

P({r⊥} | s0) = s0!Y

s,t

r⊥,st!





e⊥,s0−1,t0,s,t

s,t

e⊥,s0−1,t0,s,t 





r⊥,st

.(9)

Similarly, let us traverse each of the 2t03-clique edges from the focal vertex to the neighbours along the corners of

each triangle and record the excess joint degree of those vertices. We record the number of each unique excess joint

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Mixingpatternsingraphswithhigher-orderstructurePeterMann,LeiFang,andSimonDobsonSchoolofComputerScience,UniversityofStAndrews,StAndrews,FifeKY169SX,UnitedKingdom(Dated:October7,2022)Inthispaperweexaminethepercolationpropertiesofhigher-ordernetworksthathavenon-trivialclusteringandsubgraph-basedassort...

展开>> 收起<<

Mixing patterns in graphs with higher-order structure Peter MannLei Fang and Simon Dobson School of Computer Science University of St Andrews St Andrews Fife KY16 9SX United Kingdom.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Mixing patterns in graphs with higher-order structure Peter MannLei Fang and Simon Dobson School of Computer Science University of St Andrews St Andrews Fife KY16 9SX United Kingdom

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: