Complex hypergraphs

Abstract

Providing an abstract representation of natural and human complex structures is a challenging problem. Accounting for the system heterogenous components while allowing for analytical tractability is a difficult balance. Here I introduce complex hypergraphs (chygraphs), bringing together concepts from hypergraphs, multi-layer networks, simplicial complexes and hyperstructures. To illustrate the applicability of this combinatorial structure I calculate the component sizes statistics and identify the transition to a giant component. To this end I introduce a vectorization technique that tackles the multi-level nature of chygraphs. I conclude that chygraphs are a unifying representation of complex systems allowing for analytical insight.

I Introduction

Graphs are structural abstractions of many-particle systems, with vertices representing particles and edges the pairwise interactions between them Albert and Barabási (2002). Hypergraphs are an extension allowing for interactions between two or more vertices Ghoshal et al. (2009); Vazquez (2009); Coutinho et al. (2020); Civilini et al. (2021); Sun and Bianconi (2021). Multiplex networks introduce layers accounting for different interaction types Gómez et al. (2013). Simplicial complexes extend connectivity to hierarchical structures of inclusion Petri and Barrat (2018); Courtney and Bianconi (2018); Iacopini et al. (2019).

There are self-referential constructions as well. Joslyn and Nowak introduced ubergraphs Joslyn and Nowak (2017), a combinatorial structure where edges can contain other edges. ubergraphs has been used to organize relations in knowledge databases Yadati et al. (2021). At a higher level of abstraction, Baas introduced higher order structures, also called hyperstructures, using concepts from category theory Baas (2019).

In practice what is a suitable representation is a matter of balance. We would like the flexibility of hypergraphs to go beyond pairwise interactions, the possibility of multiple layers and the hierarchical inclusion structure of simplicial complexes and hyperstructures. In turn we would like the simplicity of graphs to calculate aggregate properties, such as the size of the giant component.

Here I introduce complex hypergraphs as a flexible combinatorial structure. General enough to include a big volume of previous work and new applications. Simple enough to allow for analytical calculations. The work is organized as follows. In Sect. II I define complex hypergraphs and comment on its relation with other structures. In Sects. III and IV I provide analytical methods to characterize the emergence of the chygraph giant component, using a generating function formalism. I discuss particular cases and provide numerical examples validating the analytical results. I finish with some key conclusions in Sec.V.

II Key definitions

II.1 Motivation

Complex systems are simplified to facilitate their analysis. Gradually we remove some of the simplifications and move closer to the real system. For example, the system of scientific publications has been represented by different network structures depending on the question asked Newman (2001); Barabási et al. (2002). Citation networks indicate the flow of knowledge along publications Redner (1998); Lehmann et al. (2003). In citation networks nodes are publications and citations are represented by directed links. Co-authorship networks are better suited when focusing on collaborations. Authors-publications networks can be further expanded to explicitly represent authors and publications, resulting in the bipartite graph Newman (2001). The same authors-publications relations can be represented as an authors hypergraph, where publications are hyperedges associating one, two or more authors Vasilyeva et al. (2021). These networks and hypergraphs are simplifications loosing some aspects of the original system. We need a more complete representation with a richer combinatorial structure. A scientific publication contains both authors and references. The document internal structure can be represented by a hypergraph with two edges, the list of authors and references. On top of that, the publication is a vertex in a higher order structure where the building blocks are authors and publications. Informally speaking, a hypergraph of hypergraphs, a complex hypergraph.

II.2 Complex systems

Here I use the term complex in the structural sense: made of different parts. I make a distinction between the parts that are not decomposable into other parts, the atoms, and the complexes that are made of other parts, including atoms. The atoms could have a finer structure, but they have been chosen as the primary building blocks. These preliminaries lead to the self-consistent definition of complex system.

Definition. A complex system is a set of atoms and complexes, where complexes are made of atoms and other complexes.

The latter serves as a philosophical definition of complex system. For practical applications we need a precise mathematical construction. The choice depends on the internal structure of the complex.

II.3 Hypergraphs

A hypergraph $\mathscr{H}(V,E)$ is a vertex set $V$ and a hyperedge set $E$, where a hyperedge is a subset of $V$. Just for the sake of illustration, I rewrite this definition based on the wording of complex systems introduced above. A hypergraph $\mathscr{H}(A,C)$ is an atom set $A$ and a complex set $C$, where the complexes are subsets (hyperedges) of $A$. Obviously hypergraphs do not posses the self-referential property of complex systems. They are simple structures.

II.4 ubergraphs

To make hypergraphs self-referential, Joslyn and Nowak introduced ubergraphs Joslyn and Nowak (2017), a combinatorial structure where hyperedges can contain other hyperedges. Here I redefine them using the wording of complex systems introduced above.

Definition. An ubergraph $𝒰(A,C)$ is a set of atoms $A$ and a set of complexes $C$, where the complexes are subsets (hyperedges) of $A\cup C$.

Figure 1: A chygraph example. This chygraph is a representation of the system of scientific publications, with atoms representing authors, complexes publications and inclusions citations.

II.5 Complex hypergraphs

To add more internal structure I choose hypergraphs. That leads to the definition of complex hypergraphs.

Definition. A complex hypergraph (chygraph) $\chi (A,C)$ is a set of atoms $A$ and a set of complexes $C$, where the complexes are hypergraphs with vertex sets in $A\cup C$.

Let us unravel this definition with some examples. A graph $𝒢(V,E)$ is represented by the chygraph $\chi (V,E)$ where the complexes are edges. A multiplex graph Gómez et al. (2013) with layer graphs $G_l(V,E_l)$, $l=1,\mathrm{\dots },L$, is represented by the chygraph $\chi (V,{\cup }_{l=1}^L{E}_l)$ plus some partition structure discussed below. The system of scientific publications is represented by the chygraph $\chi (A,\{{\mathscr{H}}_i(A_i\cup R_i,\{A_i,R_i\})\})$, where atoms are authors, complexes are publications, the publications are represented by a hypergraph with two edges ($A_i$ for the authors and $R_i$ for the references) and the index $i$ runs across all publications. The two edges have no overlap and therefore the complexes representing scientific publications have two internal components (Fig. 1).

We can think of chygraphs as ubergraphs with two edge types: the edges in the complexes associated hypegraphs and the complexes. The complex act as a special edge that we designate as the basic unit of inclusion. In turn, ubergraphs are chygraphs where all intra-complex hypergraphs contain a single edge. Obviously in this case the intra-complex hypergraph has only one component with a size equal to the hyperedge cardinality. Therefore, all results derived in the following sections are valid for ubergraphs, after replacing component size by hyperedge cardinality.

II.6 Chygraphs properties

Many properties of graphs/hypergraphs are carried on to chygraphs. To make a distinction from the metrics associated with the complexes hypergraph structure, I will use greek letters to name quantities at the chygraph level. Given a complex $j$, let $\mathscr{H}(V_j,E_j)$ be its associated hypergraph. Let $i\in A\cup C$ be an atom or complex, where $i=1,\mathrm{\dots },n$ and $n=|A\cup C|$. I will use the notation $i\in C_j$ as equivalent to $i\in V_j$. The chy-adjacency matrix $\alpha$ is the $n\times n$ matrix with matrix elements

(1)

where $i,j\in A\cup C$. The associated vertex chy-degrees

$${\kappa }_i=\sum _j{\alpha }_{ij}.$$ (2)

Additional metrics are needed to characterize potential multi-level structure. Chygraphs may contain multiple levels of inclusion. At the lower level we have atoms, whose fine structure is null or not specified. One level above we have complexes, their internal structure being specified as hypergraph containing atoms and/or other complexes as vertices. In some systems it makes sense to define higher levels of inclusions. For example, when describing human populations by location, we speak of neighborhoods, cities, countries, continents and the world. This inclusion hierarchy leads to the definition of chygraph length.

Definition: chygraph length $L(\chi )$. Let $\chi (A,C=\{{\mathscr{H}}_i(V_i,E_i)\})$ be a chygraph. Let $\mathrm{\Pi }={\mathrm{\Pi }}_1\cup \mathrm{\dots }\cup {\mathrm{\Pi }}_l$ be a partition of $C$ that is non-intercepting (${\mathrm{\Pi }}_i\cap {\mathrm{\Pi }}_j=\mathrm{\varnothing }$ for $i\ne j$), hierarchical (if $C_i\in {\mathrm{\Pi }}_j$ then $V_i\subset A\cup ({\cup }_{k\le j}{\mathrm{\Pi }}_k)$) and complexes within the same partition have similar statistical properties. The chygraph length, denoted by $L(\chi )$, is the maximum $l$ among all such partitions.

The differentiation of partitions by statistical properties allows for the specification of multi-type structures. This is the case in multiplex graphs and hypergraphs. In this context two layers may have the same vertex set but the complexes may have different statistical properties depending on the layer.

As in the case of higher order networks De Domenico et al. (2013), we could extend other metrics such as the clustering coefficient and the entropy to chygraphs. Here I have limited my attention to metrics that are needed in the following sections.

III Percolation theory I: no intra-layer inclusions

In spite of its complexity the chygraph combinatorial structure is suitable for analytical treatment. I focus on percolation, a central problem in graph theory.

The generating functions technique has been used to solve percolation problems in graphs and hypergraphs Callaway et al. (2000); Ghoshal et al. (2009); Coutinho et al. (2020); Sun and Bianconi (2021). It follows a simple recipe: express the generating function of the component sizes distribution as a recursive function of itself, modulated by the generating functions of other relevant distributions. In the context of chygraphs, the key quantities are the component sizes ${\sigma }^l$ and excess component sizes ${\overline{\sigma }}^{ml}$ when the components are sampled from layer $l$ at random or coming from another layer $m$, respectively. Here we need to be precise about how we arrive from another layer.

We can arrive to a reference complex in two different ways. From the complexes it includes (coming from below) or from the complexes where it is included (coming from above). If there are no intra-layer connections the notation ${\overline{\sigma }}^{ml}$ does not require any further specification. When it is clear we are arriving from below. In contrast, when $m>l$ we are arriving from above. In this section I assume there are no intra-layer connections. The case with intra-layer connections will be the subject of next section.

The component sizes depend on the joint distribution of chy-degrees ${\widehat{\kappa }}_l$, in-complex hypergraph component sizes ${\check{s}}^l$ and their excess equivalents ${\check{\overline{\kappa }}}_l^m$ and ${\check{\overline{s}}}_l^m$ when reached from layer $m$. The notation ${\check{s}}_l=(s_{l0},s_{l1}\mathrm{\dots },s_{ll-1}$) indicates that a component within a complex at layer $l$ is composed of vertices from $A,{\mathrm{\Pi }}_1,\mathrm{\dots },{\mathrm{\Pi }}_{l-1}$. In turn, ${\widehat{\kappa }}_l=({\kappa }_{ll+1},\mathrm{\dots },{\kappa }_{lL})$ indicates that the chy-degree of a vertex at layer $l$ is decomposed into chy-degrees to vertices in layers ${\mathrm{\Pi }}_{l+1},\mathrm{\dots },{\mathrm{\Pi }}_L$. The probability generating functions of ${\widehat{\kappa }}_l$, ${\check{\overline{\kappa }}}_{ml}$, ${\check{s}}^l$, ${\check{\overline{s}}}^{ml}$, ${\sigma }^l$ and ${\overline{\sigma }}^{ml}$ are denoted by ${\mathrm{\Phi }}^l({\widehat{x}}_l)$, ${\mathrm{\Psi }}^{ml}({\widehat{x}}_l)$, $G^l({\check{x}}_l)$, $U^{ml}({\check{x}}_l)$, ${\mathrm{\Gamma }}^l(x)$ and ${\mathrm{{\rm Y}}}^{ml}(x)$, respectively. Since they are generating functions of probability distributions, they are all equal to 1 when evaluated at $x=1$ and their first derivatives are equal to the corresponding expected values.

III.1 Mean component size

The definition of chygraph is translated into a set of self-consistent equations for the component size generating functions. As a guideline, we arrive to a reference complex and from the complex we navigate the chygraph. Following the chygraph adjacency matrix, leading us to complexes including the reference complex, or going through the complexes included in the reference complex hypergraph. More precisely,

${\mathrm{\Gamma }}^l(x)$ $=$ $x{\mathrm{\Phi }}^l[{\mathrm{{\rm Y}}}^{ll+1}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}^{lL}(x)]$ (3)

$\times$ $G^l[{\mathrm{{\rm Y}}}^{l0}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}^{ll-1}(x)],$

${\mathrm{{\rm Y}}}^{ml}(x)$ $=$ $x{\mathrm{\Psi }}^{ml}[{\mathrm{{\rm Y}}}^{ll+1}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}^{lL}(x)]$ (4)

$\times$ $U^{ml}[{\mathrm{{\rm Y}}}^{l0}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}^{ll-1}(x)],$

where $l=0,\mathrm{\dots },L(\chi )$. Note that the first $x$ in the right hand side of these equations corresponds to the reference complex, the terms containing ${\mathrm{\Phi }}^l[\mathrm{\cdots }]$ and ${\mathrm{\Psi }}^{ml}[\mathrm{\cdots }]$ to navigations using the chygraph adjacency matrix (complexes including the reference complex) and the terms containing $G^l[\mathrm{\cdots }]$ and $U^{ml}[\mathrm{\cdots }]$ to navigations through the complexes in the reference complex hypergraph.

III.2 Mean component size

The mean excess component sizes ${⟨\overline{\sigma }⟩}^{ml}={\dot{\mathrm{{\rm Y}}}}^{ml}(1)$ can be calculated from Eq. (4), resulting in

$${⟨\overline{\sigma }⟩}^{ml}=1+\sum _{k=l+1}^L{⟨\overline{\kappa }⟩}_{lk}^m{⟨\overline{\sigma }⟩}^{lk}+\sum _{k=0}^{l-1}{⟨\overline{s}⟩}_{lk}^m{⟨\overline{\sigma }⟩}^{lk},$$ (5)

where $l,m=0,\mathrm{\dots },L$. Note that ${⟨\overline{\kappa }⟩}_{lk}^m\ne {⟨\kappa ⟩}_{lk}$ and ${⟨\overline{s}⟩}_{lk}^m\ne {⟨s⟩}_{lk}$ only when $k=m$. When we come from a layer $m$ into a layer $l$ and then return to layer $m$. Now comes the vectorization trick.

The matrix equation (5) can be solved by the vectorization method for matrix equations Horn et al. (1994). The vectorization operator $\mathrm{vec}X$ transform a $(M,N)$ matrix into a $M\times N$ column vector by stacking the columns of $X$. For example,

$$\mathrm{vec}{X}^{(2,2)}=\left[\begin{array}{c}{X}^{00}\\ X^{10}\\ X^{01}\\ X^{11}.\end{array}\right]$$ (6)

To handle tensors with four indexes I generalize the vectorization operator. The vectorization operator acting on the $X_{(O,P)}^{(M,N)}$ tensor creates a $(M\times N,O\times P)$ matrix by stacking the upper indexes along columns and lower indexes along rows. For example,

(7)

Applying vectorization Eq. (5) is transformed to

$$\mathrm{vec}\{A\}\mathrm{vec}\{⟨\overline{\sigma }⟩\}=\mathrm{vec}\{B\},$$ (8)

where

$$A_{nk}^{ml}={\delta }_{mn}{\delta }_{lk}-{⟨\overline{\kappa }⟩}_{nk}^m{\mathrm{\Theta }}_{k-n}{\delta }_{nl}-{⟨\overline{s}⟩}_{nk}^m{\mathrm{\Theta }}_{n-k}{\delta }_{nl},$$ (9)

$$B^{ml}=1,$$ (10)

and ${\mathrm{\Theta }}_i$ is an integer Heaviside step function (${\mathrm{\Theta }}_i=1$ if $i>0$ or 0 otherwise). The linear systems of equations (8) has Cramer’s rule as a formal solution

$$\mathrm{vec}{\{⟨\overline{\sigma }⟩\}}_i=\frac{det(\mathrm{vec}{\{A\}}_i)}{det(\mathrm{vec}\{A\})},$$ (11)

where $\mathrm{vec}{\{A\}}_i$ is derived from $\mathrm{vec}\{A\}$ by replacing the $i$th column by $\mathrm{vec}\{B\}$. This solution is valid provided that $A$ is not singular. When $det(A)\to 0^{+}$ the mean component sizes diverge and the system achieve percolation. Therefore, the chygraph critical percolation condition is given by

$$det(\mathrm{vec}\{A\})=0.$$ (12)

III.3 Giant component

The equation for the mean component sizes (8) is valid provided $det(\mathrm{vec}\{A\})>0$. In the following I demonstrate that $det(\mathrm{vec}\{A\})>0$ corresponds with the subcritical phase. Let $P^l$ be the probability that a vertex from layer $l$ selected at random does not belong to the giant component and let $Q^{ml}$ be the probability that a vertex at layer $l$ selected from a complex at layer $m$ does not belong to the giant component. These probabilities satisfy the self-consistent equations

$$P^l={\mathrm{\Phi }}^l[Q^{ll+1},\mathrm{\dots },Q^{lL}]G^l[Q^{0l},\mathrm{\dots },Q^{l-1l}],$$ (13)

$$Q^{ml}={\mathrm{\Psi }}^{ml}[Q^{ll+1},\mathrm{\dots },Q^{lL}]U^{ml}[Q^{0l},\mathrm{\dots },Q^{l-1l}].$$ (14)

This system of equations does not have an explicit analytic solution. A solution can be found by successive approximations, where the left hand side is interpreted as the $t+1$ iteration after plugging in iteration $t$ into the right hand side. In particular, in the absence of a giant component, Eqs. (13) and (14) admit the solution $P^l=Q^{ml}=1$. Let us assume that $Q^{lm}=1-x^{ml}$, where $x^{ml}\to 0$. Keeping terms up to first order in $x^{ml}$ in Eq. (14) results in the recursive approximation equations

$$\mathrm{vec}\{x\}(t+1)=(I-\mathrm{vec}\{A\})\mathrm{vec}\{x\}(t).$$ (15)

The linear map (15) converges to $\mathrm{vec}\{x\}=0$ if and only if $\mathrm{\Lambda }(\mathrm{vec}\{A\})>0$, where $\mathrm{\Lambda }(\mathrm{vec}\{A\})$ is the largest eigenvalue of $\mathrm{vec}\{A\}$. Therefore $\mathrm{\Lambda }(\mathrm{vec}\{A\})$ is the control parameter for the existence of a giant component. In the subcritical (supercritical) phase $\mathrm{\Lambda }>0$ () there is not (there is) a giant component and $P^l=1$ (). The percolation transition takes place at the criticality condition $\mathrm{\Lambda }(\mathrm{vec}\{A\})=0$, which is equivalent to the Eq. (12).

III.4 $L=1$

When there is only one complex layer ($L(\chi )=1$) then $\mathrm{vec}\{A\}$ in Eq. (9) is reduced to

(16)

with determinant

$$det(\mathrm{vec}\{A\})=1-A_{01}^{10}{A}_{10}^{01}=1-{\overline{k}}_{01}^1{\overline{s}}_{10}^0.$$ (17)

A hypergraph $\mathscr{H}(V,E)$ is mapped to a one layer chygraph where the complexes are the hypergraph edges: $\chi (V,\{\mathscr{H}(V,e_l),e_l\in E\})$. In this case the excess component sizes ${\overline{s}}_{10}^0$ is the excess hyperedges cardinality $⟨\overline{c}⟩$ and the excess atoms degree ${\overline{k}}_{01}^1$ is the vertices excess degree $⟨\overline{k}⟩$. Substituting into Eq. (17) one obtains the critical condition for hypergraphs: $⟨\overline{c}⟩⟨\overline{k}⟩=1$, in agreement with the result of Coutinho et al Coutinho et al. (2020). Furthermore, graphs are hypergraphs with excess cardinality 1 and, therefore, the criticality condition reduces to $⟨\overline{k}⟩=1$, as previously reported by Molloy and Reed Molloy and Reed (1998) and Callaway et al Callaway et al. (2000).

III.5 $L=2$

When there are two complex layers ($L(\chi )=2$) then $\mathrm{vec}\{A\}$ in Eq. (9) is reduced to

(18)

with determinant

(19)

We could expand the determinant but it would lead to a complicated algebraic expression. For most practical purposes it is best to work with the explicit matrix form in Eq. (19), including numerical calculations. Further simplifications are obtained when we consider combinatorial constructions with additional constraints.

III.6 Hierarchical inclusion

There are many systems where inclusion follows a hierarchy. Geographical zooming for example Okabe and Sadahiro (1996). It is straightforward to build hierarchical inclusion in chygraphs: atoms included in layer 1 complexes, layer 1 complexes included in layer 2 complexes, … , layer $L-1$ complexes included in layer $L$ complexes. In this context the tensor elements of $A_{nk}^{ml}$ are zero if $|m-l|\ne 1$ or $|n-k|\ne 1$ For the case $L=2$ this constraint leads to the elimination of the second and fifth row and the second and fifth column in Eq. (19), resulting in

(20)

Expanding the latter determinant and substituting the explicit form of the tensor $A$ (Eq. (9)) we obtain

$det(\mathrm{vec}\{A\})$ $=$ $(1-{⟨\overline{\kappa }⟩}_{01}^1{⟨\overline{s}⟩}_{10}^0)(1-{⟨\overline{\kappa }⟩}_{12}^2{⟨\overline{s}⟩}_{21}^1)$ (21)

$-$ ${⟨\overline{\kappa }⟩}_{12}^0{⟨\overline{s}⟩}_{10}^2{⟨\overline{\kappa }⟩}_{01}^1{⟨\overline{s}⟩}_{21}^1$

Within the parentheses we have the criticality condition for each layer alone. The last term represents the interactions including both layers. The latter is the bona fide complexity of hierarchical inclusion. The terms within the first two parenthesis can be positive, meaning no standard 1 layer percolation, and $det(\mathrm{vec}\{A\})$ can become 0 due to the last interaction term.

III.7 Multiplex hypergraphs

Multiplex hypergraphs is another type of multi-layer structure Sun and Bianconi (2021). A multiplex hypergraph is a set of hypergraphs $\{{\mathscr{H}}_l(V,E_l),l=1,\mathrm{\dots },L\}$ with the same set of vertices. Note that when the statistical properties of the hypergraphs ${\mathscr{H}}_l$ are different the multiplex hypergraph is not statistically equivalent to $\mathscr{H}(V,{\cup }_{l=1}^L{E}_l)$. A multiplex hypergraph can be mapped to the chygraph $\chi (V,{\cup }_{l=1}^L{E}_l,\mathrm{\Pi }=E_1\mathrm{\dots },E_L)$, where all edges are represented by complexes and the complexes are partitioned according to the hypergraph they originated from. For the case $L=2$, the absence of inclusion of complexes into complexes leads to the elimination of the fourth and sixth row and the fourth and sixth column of (19), resulting in

(22)

Expanding the latter determinant and substituting the explicit form of the tensor $A$ (Eq. (9)) we obtain

$det(\mathrm{vec}\{A\})$ $=$ $(1-{\overline{k}}_{01}^1{\overline{s}}_{10}^0)(1-{\overline{k}}_{02}^2{\overline{s}}_{20}^0)$ (23)

$-$ ${\overline{k}}_{01}^2{\overline{s}}_{10}^0{\overline{k}}_{02}^1{\overline{s}}_{20}^0.$

Within the first two parentheses there is the contribution of each hypergraph layer alone. The last term represents the interaction between the two hypergraphs via the vertices. The latter is the bona fide complexity of multiplex hypergraphs. The terms within the first two parenthesis can be positive, meaning no standard hypergraph percolation, and $det(\mathrm{vec}\{A\})$ can become 0 due to the last interaction term.

Figure 2: Without intra-layer inclusions. Numerical estimation of (A) the giant component fraction and (B) the mean component size as a function of $-det(\mathrm{vec}\{A\})$ for a random chygraph with a multiplex structure: one layer of $n_0$ atoms, two layers of complexes with $n_1$ and $n_2$ complexes and $m_i$ inclusions of a randomly chosen atom into a randomly chosen complex in layer $i$, $i=1,2$. The model parameters are $n_0=n_1=n_2={10}^6$, two values of ${\theta }_1=m_1^2/(n_0{n}_1)$ indicated in the legend and ${\theta }_2=m_2^2/(n_0{n}_2)$ in the interval $[0.01,4]$. Average was taken over 10 random chygraphs.

III.8 Numerical example

To test the analytical results I will use a random chygraph model with a multiplex structure: one layer of $n_0$ atoms, two layers of complexes with $n_1$ and $n_2$ complexes and $m_i$ inclusions of a randomly chosen atom into a randomly chosen complex in layer $i$, $i=1,2$. Since inclusions are random both the chydegrees and the component sizes have Poisson distributions with averages $k_{0i}=m_i/n_i$ and $s_{i0}=m_i/n_0$, $i=1,2$. For the Poisson distribution the excess average coincides with the average and therefore ${\overline{k}}_{0i}^j=m_i/n_i$ and ${\overline{s}}_{i0}^j=m_i/n_0$, $i=1,2$. Substituting these values into Eq. (23) we arrive to the criticality condition

$$det(\mathrm{vec}\{A\})=(1-{\theta }_1)(1-{\theta }_2)-{\theta }_1{\theta }_2$$ (24)

where ${\theta }_i=m_i^2/n_i{n}_0$, $i=1,2$.

To test this expression I computed the giant component fraction and the mean component size excluding the giant component numerically. To this end I project the chygraph into a network where nodes represent atoms and complexes, while links represent inclusion relations. Figure 2 reports the numerical estimation of the giant component fraction and the mean component size as a function of $-det(\mathrm{vec}\{A\})$, computed using Eq. (24). There is a phase transition at $-det(\mathrm{vec}\{A\})=0$, with the emergence of a giant component and a maximum of the mean component size excluding the giant component. The agreement demonstrates the validity of the analytical results for multiplex chygraphs.

In turns out this example is a validation for the hierarchical inclusion as well. Consider another random chygraph model with the following inclusion structure: one layer of $n_0$ atoms, a layer labeled 1 with $n_1$ complexes and $m_1$ inclusions of a randomly chosen atom into a randomly chosen complex from layer 1, and a layer labeled 2 with $n_2$ complexes and $m_2$ inclusions of a randomly chosen complex from layer 1 into a randomly chosen complex from layer 2. One can check that the criticality condition for chygraphs with hierarchical inclusion in Eq. (21) is reduced to Eq. (24). Furthermore, projecting the chygraph into a network, where nodes represent atoms and complexes, while links represent inclusion relations, we obtain the same network as for the multiplex chygraph described above. Note that this equivalence holds for $L=2$. For $L>2$ there is no equivalence between random chygraphs with a multiplex or hierarchical inclusion structure. For the multiplex structure the network projection has one layer connected to $L-1$ layers. For the hierarchical inclusion the network projection has $L$ ordered layers with links between adjacent ayers only.

IV Percolation theory II: with intra-layer inclusions

We can arrive to a reference complex from the complexes it includes (from below) or where it is included (from above). When there are no intra-layer connections the pair of indexes $ml$ is sufficient to distinguish how we arrived to the reference complex. If we came from below. If $m>l$ we cam from above. However, when there are intra-layer inclusions the two indexes are not sufficient to specify how we arrived to a complex for the case $m=l$. We need an extra index. In the context of the generating function formalism that means we need two component size generating functions when arriving to a complex from an atom or another complex. I will denote them by ${\mathrm{{\rm Y}}}_{-}^{ml}$ when arriving from below and ${\mathrm{{\rm Y}}}_{+}^{ml}$ when arriving from above. With this distinction Eq. (3) and (4) are rewritten as

${\mathrm{\Gamma }}^l(x)$ $=$ $x{\mathrm{\Phi }}^l[{\mathrm{{\rm Y}}}_{-}^{ll}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}_{-}^{lL}(x)]$ (25)

$\times$ $G^l[{\mathrm{{\rm Y}}}_{+}^{l0}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}_{+}^{ll}(x)],$

${\mathrm{{\rm Y}}}_i^{ml}(x)$ $=$ $x{\mathrm{\Psi }}_i^{ml}[{\mathrm{{\rm Y}}}_{-}^{ll}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}_{-}^{lL}(x)]$ (26)

$\times$ $U_i^{ml}[{\mathrm{{\rm Y}}}_{+}^{l0}(x),\mathrm{\dots },{\mathrm{{\rm Y}}}_{+}^{ll}(x)],$

where $l=0,\mathrm{\dots },L(\chi )$ and

(27)

(28)

Note I have implicitly assumed that the chydegrees and the intra-complex hypergraph components are independent.

The mean excess component sizes ${⟨\overline{\sigma }⟩}_i^{ml}={\dot{\mathrm{{\rm Y}}}}_i^{ml}(1)$, $i=-,+$, can be calculated from Eq. (26), resulting in

$${⟨\overline{\sigma }⟩}_i^{ml}=1+\sum _{k=l}^L{⟨\overline{\kappa }⟩}_{ilk}^m{⟨\overline{\sigma }⟩}_{-}^{lk}+\sum _{k=0}^l{⟨\overline{s}⟩}_{ilk}^m{⟨\overline{\sigma }⟩}_{+}^{lk},$$ (29)

where

(30)

(31)

We can apply the vectorization trick to transform Eq. (29) into a standard linear system of equations. To do so we need to apply the vectorization trick twice. Once as done before for the indexes $(m,l,k)$ and another one for the index $i$. After the first vectorization Eq. (29) can be rewritten as

(32)

and after the second vectorization as

$${\mathrm{vec}}^2\{A\}{\mathrm{vec}}^2\{\overline{\sigma }\}={\mathrm{vec}}^2\{B\},$$ (33)

where

${(A_{--})}_{nk}^{ml}$ $=$ ${\delta }_{mn}{\delta }_{lk}-{⟨\kappa ⟩}_{nk}{\mathrm{\Theta }}_{k-n+1}{\delta }_{nl},$

${(A_{-+})}_{nk}^{ml}$ $=$ $-{⟨\overline{s}⟩}_{nk}^m{\mathrm{\Theta }}_{n-k+1}{\delta }_{nl},$

${(A_{+-})}_{nk}^{ml}$ $=$ $-{⟨\overline{\kappa }⟩}_{nk}^m{\mathrm{\Theta }}_{k-n+1}{\delta }_{nl},$

${(A_{++})}_{nk}^{ml}$ $=$ ${\delta }_{mn}{\delta }_{lk}-{⟨s⟩}_{nk}{\mathrm{\Theta }}_{n-k+1}{\delta }_{nl},$ (34)

$$B_{+}^{ml}=B_{-}^{ml}=1,$$ (35)

Finally, the criticality condition is

$$det({\mathrm{vec}}^2\{A\})=0.$$ (36)

IV.1 $L=1$

When there is only one complex layer ($L(\chi )=1$) from Eq. (34) we obtain

(37)

One can go ahead and expand the determinant. However, I have not found any grouping of the terms that leads to a compact algebraic equation. Therefore, I’ll work straight with Eq. (37).

Figure 3: With intra-layer inclusions. Numerical estimation of (A) the giant component fraction and (B) the mean component size as a function of $-det(\mathrm{vec}\{\mathrm{vec}\{A\}\})$ for a random chygraph with one layer of $n_0$ atoms, one layer of $n_1$ complexes, $m_0$ inclusions of a randomly selected atom into a randomly selected complex and $m_1$ inclusions of a randomly selected complex into a randomly selected complex. The model parameters are $n_0=n_1={10}^6$, two values of ${\theta }_0=m_0/n_0$ as indicated in the legend and ${\theta }_2=m_1/n_1$ in the interval $[0.1,2]$. Average was taken over 10 random chygraphs.

IV.2 Numerical example

To test Eq. (37) I consider a random chygraph with a layer of $n_0$ atoms, a layer of $n_1$ complexes, $m_0$ inclusions of a randomly selected atom into a randomly selected complex and $m_1$ inclusions of a randomly selected complex into a randomly selected complex. A possible realization of this model is illustrated in Fig. 1.

Since inclusions are random both the chydegrees and the component sizes have Poisson distributions with averages ${⟨\kappa ⟩}_{01}=m_0/n_0$, ${⟨\kappa ⟩}_{11}=m_1/n_1$, ${⟨s⟩}_{10}=m_0/n_1$ and ${⟨s⟩}_{11}=m_1/n_1$. For the Poisson distribution the excess average coincides with the average and therefore ${⟨\overline{\kappa }⟩}_{01}^1=m_0/n_0$, ${⟨\overline{\kappa }⟩}_{11}^1=m_1/n_1$, ${⟨\overline{s}⟩}_{10}^0=m_0/n_1$ and ${⟨\overline{s}⟩}_{11}^1=m_1/n_1$. Substituting these values into Eq. (37) we obtain

(38)

where $r=n_0/n_1$ and ${\theta }_i=m_i/n_i$, $i=0,1$.

Figure 3 reports the numerical estimation of the giant component fraction and the mean component size as a function of $-det({\mathrm{vec}}^2\{A\})=0$, computed using Eq. (38). There is a phase transition at $-det({\mathrm{vec}}^2\{A\})=0$, with the emergence of a giant component and a maximum of the mean component size excluding the giant component. The agreement demonstrates the validity of the analytical results for chygraphs with intra-layer connections.

V Conclusions

In conclusion, chygraphs are a versatile combinatorial structure to represent complex systems. They allow for encoding different types of structural heterogeneities and hierarchical constructions. The key ingredient is the fractal nature of the chygraph: a complex is composed of atoms and other complexes and it can be part of other complexes as well. I have calculated the component sizes statistics of chygraphs using vectorization. Future work is required to extend this formalism to other problems.