Eur. Phys. J. B (2015) 88: 266
https://doi.org/10.1140/epjb/e2015-60249-4

Regular Article

Models of random graph hierarchies

¹ Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00662 Warsaw, Poland
² ITMO University, 19 Kronverkskiy av., 197101 Saint Petersburg, Russia

^a e-mail: jholyst@if.pw.edu.pl

Received: 27 March 2015
Received in final form: 2 July 2015
Published online: 19 October 2015

Abstract

We introduce two models of inclusion hierarchies: random graph hierarchy (RGH) and limited random graph hierarchy (LRGH). In both models a set of nodes at a given hierarchy level is connected randomly, as in the Erdős-Rényi random graph, with a fixed average degree equal to a system parameter c. Clusters of the resulting network are treated as nodes at the next hierarchy level and they are connected again at this level and so on, until the process cannot continue. In the RGH model we use all clusters, including those of size 1, when building the next hierarchy level, while in the LRGH model clusters of size 1 stop participating in further steps. We find that in both models the number of nodes at a given hierarchy level h decreases approximately exponentially with h. The height of the hierarchy H, i.e. the number of all hierarchy levels, increases logarithmically with the system size N, i.e. with the number of nodes at the first level. The height H decreases monotonically with the connectivity parameter c in the RGH model and it reaches a maximum for a certain c_max in the LRGH model. The distribution of separate cluster sizes in the LRGH model is a power law with an exponent about − 1.25. The above results follow from approximate analytical calculations and have been confirmed by numerical simulations.