Optimal subgraphs in geometric scale-free random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914766766735360 |
|---|---|
| author | Michielan, Riccardo Stegehuis, Clara Walter, Matthias |
| author_facet | Michielan, Riccardo Stegehuis, Clara Walter, Matthias |
| contents | Geometric scale-free random graphs are popular models for networks that exhibit as heavy-tailed degree distributions, small-worldness and high clustering. In these models, vertices have weights that cause the heavy-tailed degrees and are embedded in a metric space so that close-by groups of vertices tend to cluster. The interplay between the vertex weights and positions heavily affects the local structure of the random graph, in particular the occurrence of subgraph patterns, but the dependencies in these structures and weights make them difficult to analyze. In this paper we investigate subgraph counts using a \textit{divide et impera} strategy: first counting the number of subgraphs in specific classes of vertices; then computing which class yields maximum contribution. Interestingly, the scaling behavior of induced and general subgraphs in such geometric heavy-tailed random graphs is closely related to the solution of a mixed-integer linear program which also shows that subgraphs appear predominantly on vertices with some prescribed degrees and inter-distances. Finally, we derive precise asymptotics for trees and Hamiltonian subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14972 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal subgraphs in geometric scale-free random graphs Michielan, Riccardo Stegehuis, Clara Walter, Matthias Probability 05C60, 05C82, 90C11, 05C80 Geometric scale-free random graphs are popular models for networks that exhibit as heavy-tailed degree distributions, small-worldness and high clustering. In these models, vertices have weights that cause the heavy-tailed degrees and are embedded in a metric space so that close-by groups of vertices tend to cluster. The interplay between the vertex weights and positions heavily affects the local structure of the random graph, in particular the occurrence of subgraph patterns, but the dependencies in these structures and weights make them difficult to analyze. In this paper we investigate subgraph counts using a \textit{divide et impera} strategy: first counting the number of subgraphs in specific classes of vertices; then computing which class yields maximum contribution. Interestingly, the scaling behavior of induced and general subgraphs in such geometric heavy-tailed random graphs is closely related to the solution of a mixed-integer linear program which also shows that subgraphs appear predominantly on vertices with some prescribed degrees and inter-distances. Finally, we derive precise asymptotics for trees and Hamiltonian subgraphs. |
| title | Optimal subgraphs in geometric scale-free random graphs |
| topic | Probability 05C60, 05C82, 90C11, 05C80 |
| url | https://arxiv.org/abs/2404.14972 |