The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909845919105024 |
|---|---|
| author | Benjert, Zylan Lakis, Kostas Lengler, Johannes Ravi, Raghu Raman |
| author_facet | Benjert, Zylan Lakis, Kostas Lengler, Johannes Ravi, Raghu Raman |
| contents | We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is $Θ(\log n)$. This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter.
The GIRG model exhibits many properties empirically found in real-world networks, and the runtime of various practical algorithms has empirically been found to scale in the same way for GIRG and for real-world networks, in particular related to computing distances, diameter, clustering, cliques and chromatic numbers. Thus the GIRG model is a promising candidate for deriving insight about the performance of algorithms in real-world instances.
The diameter was previously only known in the one-dimensional case, and the proof relied very heavily on dimension one. Our proof employs a similar Peierls-type argument alongside a novel renormalization scheme. Moreover, instead of using topological arguments (which become complicated in high dimensions) in establishing the connectivity of certain boundaries, we employ some comparatively recent and clearer graph-theoretic machinery. The lower bound is proven via a simple ad-hoc construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12543 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs Benjert, Zylan Lakis, Kostas Lengler, Johannes Ravi, Raghu Raman Probability Social and Information Networks We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is $Θ(\log n)$. This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter. The GIRG model exhibits many properties empirically found in real-world networks, and the runtime of various practical algorithms has empirically been found to scale in the same way for GIRG and for real-world networks, in particular related to computing distances, diameter, clustering, cliques and chromatic numbers. Thus the GIRG model is a promising candidate for deriving insight about the performance of algorithms in real-world instances. The diameter was previously only known in the one-dimensional case, and the proof relied very heavily on dimension one. Our proof employs a similar Peierls-type argument alongside a novel renormalization scheme. Moreover, instead of using topological arguments (which become complicated in high dimensions) in establishing the connectivity of certain boundaries, we employ some comparatively recent and clearer graph-theoretic machinery. The lower bound is proven via a simple ad-hoc construction. |
| title | The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs |
| topic | Probability Social and Information Networks |
| url | https://arxiv.org/abs/2510.12543 |