Phys. Rev. E 93, 062311 (2016) - Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Go Mobile »
Access by University of Bath Library

Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes

Owen T. Courtney and Ginestra Bianconi

Phys. Rev. E 93, 062311 – Published 16 June 2016

Abstract

Simplicial complexes are generalized network structures able to encode interactions occurring between more than two nodes. Simplicial complexes describe a large variety of complex interacting systems ranging from brain networks to social and collaboration networks. Here we characterize the structure of simplicial complexes using their generalized degrees that capture fundamental properties of one, two, three, or more linked nodes. Moreover, we introduce the configuration model and the canonical ensemble of simplicial complexes, enforcing, respectively, the sequence of generalized degrees of the nodes and the sequence of the expected generalized degrees of the nodes. We evaluate the entropy of these ensembles, finding the asymptotic expression for the number of simplicial complexes in the configuration model. We provide the algorithms for the construction of simplicial complexes belonging to the configuration model and the canonical ensemble of simplicial complexes. We give an expression for the structural cutoff of simplicial complexes that for simplicial complexes of dimension $d = 1$ reduces to the structural cutoff of simple networks. Finally, we provide a numerical analysis of the natural correlations emerging in the configuration model of simplicial complexes without structural cutoff.

Received 12 February 2016

DOI:https://doi.org/10.1103/PhysRevE.93.062311

©2016 American Physical Society

Physics Subject Headings (PhySH)

Complex systems Network structure

Networks

Authors & Affiliations

Owen T. Courtney and Ginestra Bianconi

School of Mathematical Sciences, Queen Mary University of London, E1 4NS, London, United Kingdom

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand

Issue

Vol. 93, Iss. 6 — June 2016

Reuse & Permissions

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

Examples of simplicial complexes of dimension (panel A) and (panel B) are shown. Simplicial complexes of dimension are simple networks. Simplicial complexes of dimension characterize interactions occurring between more than two nodes (specifically interactions occurring between nodes).
The figure shows the construction of two different dimensional simplicial complexes belonging to the same configuration model of simplicial complexes. In panel (a) the nodes are shown together with stubs, indicating their generalized degree. In panel (b) triples of stubs are matched together to form two-dimensional simplices. In panel (c) the corresponding simplicial complex is visualized. In panels (d) and (e) a different matching of the stubs is shown together with its corresponding simplicial complex. As is evident from the figure, a given generalized degree sequence of the nodes can give rise to different simplicial complexes. The logarithm of the total number of simplicial complexes that can be constructed from a given generalized degree sequence of the nodes is the Gibbs entropy of the configuration model.
A scheme representing the algorithm for the construction of the configuration model is shown for the case . Panel A represents steps (i), (ii), and (iii). To each node with we assign stubs. The nodes are represented with black circles. A set of auxiliary factor nodes (cyan triangles) is considered. Each factor node has stubs. Subsequently, an allowed matching of the stubs is found. Panel B shows how from the matching of the stubs we can construct a simplicial complex by adding a simplex between all of the nodes connected to a common factor node in panel A.
Two examples of forbidden moves are shown. In panel A the same set of nodes is selected more than once to form a simplex. In panel B the set of nodes selected to form a simplex is not formed by distinct nodes. Here the forbidden moves are shown for the configuration model of simplicial complexes of dimension .
The subsequent matching of the node stubs with the stubs of the factor nodes is shown here in order to justify Eq. () evaluating the asymptotic number of matchings in the absence of forbidden moves. First a random stub of a node is matched with a stub of an arbitrary unmatched factor node (panel A). Subsequently, all the remaining stubs of the factor node are matched with stubs of the nodes (panel B). At this point the unmatched factor nodes are reduced by one. An unmatched node-stub is matched to a stub of an arbitrary unmatched factor node (panel C). Subsequently, all the remaining stubs of the second factor node are matched with stubs of the nodes (panel D). This procedure continues in the absence of forbidden moves, until all of the stubs of the nodes are matched with all the stubs of the factor nodes. By calculating the probability of these moves, as describe in Sec. we can derive Eq. ().
The average degree of the neighbors of the nodes of degree and the average clustering coefficient of the nodes of degree , for simplicial complexes of dimension constructed according to the configuration model with distribution of the generalized degrees of the nodes given by Eq. () and . The simplicial complexes have nodes, and . The data are averaged over 100 realizations.

Sign up to receive regular email alerts from Physical Review E