Entropy of the ensemble of acyclic graphs

Edson A. Soares () and André A. Moreira
Additional contact information
Edson A. Soares: Departamento de Física, Universidade Federal do Ceará, Caixa Postal 6030, Campus do Pici, 60455-760 Fortaleza, Ceará, Brazil
André A. Moreira: Departamento de Física, Universidade Federal do Ceará, Caixa Postal 6030, Campus do Pici, 60455-760 Fortaleza, Ceará, Brazil

International Journal of Modern Physics C (IJMPC), 2024, vol. 35, issue 02, 1-10

Abstract: The structural phase transition in complex network models is known to yield knowledge relevant for several problems of practical application. Examples include resilience of artificial networks, dynamics of epidemic spreading, among others. The model of random graphs is probably the simplest model of complex networks, and the solution of this model falls into the universality class mean field percolation. In this work, we concentrate on a similar problem, namely, the structural phase transition in the ensemble of random acyclic graphs. It should be noted that several approaches to the problem of random graphs, such as generating functions or the Molloy–Reed criterion, rely on the fact that before the critical point, cycles should not be present in random graphs. In this way, up to the critical point our solution should produce results that are equivalent to these other methods. Our approach takes advantage of the fact that acyclic graphs allow for an exact combinatorial enumeration of the whole ensemble, what leads to an exact expression for the entropy of this system. With this definition of entropy we can determine the onset of the critical transition as well as the critical exponents associated with the transition. Our results are illustrated with Monte-Carlo results and are discussed within the context of general random graphs, as well as in comparison with another model of acyclic graphs.

Keywords: Random graphs; networks; percolation problems; exact results; classical phase transitions (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183124500177
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:35:y:2024:i:02:n:s0129183124500177

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183124500177

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().