Models of random graph hierarchies

被引:1
作者
Paluch, Robert [1 ]
Suchecki, Krzysztof [1 ]
Holyst, Janusz A. [1 ,2 ]
机构
[1] Warsaw Univ Technol, Fac Phys, Ctr Excellence Complex Syst Res, Koszykowa 75, PL-00662 Warsaw, Poland
[2] ITMO Univ, St Petersburg 197101, Russia
关键词
NETWORKS;
D O I
10.1140/epjb/e2015-60249-4
中图分类号
O469 [凝聚态物理学];
学科分类号
070205 ;
摘要
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 Erdos-Renyi 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.
引用
收藏
页数:6
相关论文
共 50 条
[41]   Random walks on Fibonacci treelike models [J].
Ma, Fei ;
Wang, Ping ;
Yao, Bing .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2021, 581
[42]   Rumor spreading models with random denials [J].
Giorno, Virginia ;
Spina, Serena .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2016, 461 :569-576
[43]   A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence [J].
Bhuiyan, Hasanuzzaman ;
Khan, Maleq ;
Marathe, Madhav .
2017 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2017, :3312-3321
[44]   Uniform random sampling not recommended for large graph size estimation [J].
Lu, Jianguo ;
Wang, Hao .
INFORMATION SCIENCES, 2017, 421 :136-153
[45]   Sampling random graph homomorphisms and applications to network data analysis [J].
Lyu, Hanbaek ;
Memoli, Facundo ;
Sivakoff, David .
JOURNAL OF MACHINE LEARNING RESEARCH, 2023, 24
[46]   Linear and optimization Hamiltonians in clustered exponential random graph modeling [J].
Park, Juyong ;
Yook, Soon-Hyung .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2011,
[47]   Parameter estimation in a dynamic Chung-Lu random graph [J].
Hazra, Rajat Subhra ;
Mandjes, Michel ;
Wang, Jiesen .
PHYSICAL REVIEW E, 2025, 112 (01)
[48]   Biological applications of knowledge graph embedding models [J].
Mohamed, Sameh K. ;
Nounu, Aayah ;
Novacek, Vit .
BRIEFINGS IN BIOINFORMATICS, 2021, 22 (02) :1679-1693
[49]   Near-critical SIR epidemic on a random graph with given degrees [J].
Janson, Svante ;
Luczak, Malwina ;
Windridge, Peter ;
House, Thomas .
JOURNAL OF MATHEMATICAL BIOLOGY, 2017, 74 (04) :843-886
[50]   A random geometric graph built on a time-varying Riemannian manifold [J].
Xie, Zheng ;
Zhu, Jiang ;
Kong, Dexing ;
Li, Jianping .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2015, 436 :492-498