Emergence of Bending Power Law in Higher-Order Networks

Zhaohua Guo, Yuan Yuan, Rui Miao, Jin-Li Guo, Forrest, JeffreyarXiv 2023 · DOI · arXiv

Abstract

In the past two decades, a series of important results have been established in the empirical and theoretical modeling of complex networks, although considered are mainly pairwise networks. However, with the development of science and technology, an increasing number of higher-order networks with many-body interactions have gradually moved to the center stage of research when real-life systems are investigated. In the paper, the concept of higher-order degree is introduced to higher-order networks, and a bending power law (BPL) model with continuous-time growth is proposed. The evolution mechanism and topological properties of the general higher-order network are studied. The batch effect of low dimensional simplex is considered. The model is analyzed by using the mean-field method and Poisson process theory. The stationary average higher-order degree distribution of simplices is expressed analytically. The obtained analytical results agree well with those observed through simulations. In particular, this paper shows that the higher-order degree distribution of simplices in the network processes a property of bending power law, and the scale-free property of the higher-order degree is controlled by the higher-order edge, the simplex dimension and the feature parameter of the model. The BPL model of higher-order networks not only generalizes the NGF model, but also the famous scale-free model of complex networks to higher-order networks.

Introduction: Beyond Pairwise Interactions

For decades, network science has focused on pairwise interactions—graphs where an edge connects exactly two nodes. However, real-world systems are rarely that simple. In an ecosystem, three species might compete for the same territory; in a research paper, five authors collaborate simultaneously. These are "higher-order" interactions that are better represented as simplicial complexes (triangles, tetrahedrons, etc.) rather than simple edges.

Growth of a simplicial complex where new triangles (higher-order interactions) are added to existing faces.

While models like the Barabási-Albert (BA) model explain why many networks are "scale-free" (having a few highly connected hubs), they don't easily translate to these higher-order structures. Existing models, such as Network Geometry with Flavor (NGF), are often too rigid. This research addresses the need for a more flexible, generalized growth model that can explain why real-world higher-order data often shows a "bend" in its power-law distribution on a log-log plot, rather than a perfect straight line.

The Bending Power Law (BPL) Model

The authors propose the Bending Power Law (BPL) model, which evolves based on two main rules:

  1. Continuous-Time Growth: The network starts with a small set of $d$-dimensional simplices. New nodes arrive according to a Poisson process. When a node arrives, it creates a "batch" of $m$ new $d$-dimensional simplices by connecting to existing $(d-1)$-dimensional faces.
  2. Non-Homogeneous Preferential Attachment: Unlike standard models where a node's chance of getting a new connection is strictly proportional to its current degree, the BPL model uses a non-homogeneous linear function: $\Pi(h) \propto ph + q$. Here, $p$ is a feature parameter that tunes the "attractiveness" of a simplex.
Evolution of the BPL model showing the addition of new nodes and simplices over time.

To analyze the model, the researchers employed mean-field theory and Poisson process theory to derive analytical expressions for the stationary average higher-order degree distribution. These mathematical predictions were then validated using numerical simulations of the BPL model with parameters such as $d=2$ (triangles) and $m=2$ (two new simplices per step).

Key Insights and Results

The study reveals several critical properties of higher-order network evolution:

  • The "Bend" as a Mathematical Consequence: The characteristic "bending" in the power law is not noise but a result of the non-homogeneous attachment rule ($ph + q$). By adjusting the parameter $p$, researchers can model distributions that transition from classic power laws to exponential decays.
  • Dimensional Sensitivity: The "scale-free" property of the network is highly sensitive to the dimension of the simplices involved. Higher-dimensional simplices are more affected by the model’s feature parameters than lower-dimensional ones.
  • Unification of Models: The BPL model acts as a generalized framework. By setting specific parameters (e.g., $p=1, d=1$), it collapses into the classic BA model. With other restrictions, it becomes the NGF model.
  • Scale-Free Control: The authors proved that the power-law exponent is $\gamma + 1$, where $\gamma$ is a function of the dimension $d$, the number of added simplices $m$, and the parameter $p$. Numerical simulations showed a near-perfect overlap with these theoretical curves.

Conclusion and Future Work

The BPL model provides a robust theoretical foundation for understanding many-body interactions. While the current study focuses on growth through adding nodes and edges, future work could incorporate "internal" evolution, such as edge deletion or rewiring. A logical next step is applying the BPL model to empirical datasets, such as brain connectomes or co-authorship hypergraphs, to see if the observed "bend" in those systems can be used to reverse-engineer their underlying growth parameters.

Summary updated

Abstract

In the past two decades, a series of important results have been established in the empirical and theoretical modeling of complex networks, although considered are mainly pairwise networks. However, with the development of science and technology, an increasing number of higher-order networks with many-body interactions have gradually moved to the center stage of research when real-life systems are investigated. In the paper, the concept of higher-order degree is introduced to higher-order networks, and a bending power law (BPL) model with continuous-time growth is proposed. The evolution mechanism and topological properties of the general higher-order network are studied. The batch effect of low dimensional simplex is considered. The model is analyzed by using the mean-field method and Poisson process theory. The stationary average higher-order degree distribution of simplices is expressed analytically. The obtained analytical results agree well with those observed through simulations. In particular, this paper shows that the higher-order degree distribution of simplices in the network processes a property of bending power law, and the scale-free property of the higher-order degree is controlled by the higher-order edge, the simplex dimension and the feature parameter of the model. The BPL model of higher-order networks not only generalizes the NGF model, but also the famous scale-free model of complex networks to higher-order networks.
BibTeX
@misc{guo2023emergence,
  author = {Zhaohua Guo and Yuan Yuan and Rui Miao and Jin-Li Guo and Forrest, Jeffrey},
  title = {{Emergence of Bending Power Law in Higher-Order Networks}},
  year = {2023},
  eprint = {2305.11907},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.11907},
}
Figure