Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2411.02898 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916468480802816 |
|---|---|
| author | Jung, Hamin |
| author_facet | Jung, Hamin |
| contents | A significant generalization of the Erdös-Rényi random graph model is an `inhomogeneous' random graph where the edge probabilities vary according to vertex types. We identify the threshold value for this random graph with a finite number of vertex types to be connected and examine the model's behavior near this threshold value. In particular, we show that the threshold value is $c \frac{\log n }{n}$ for some $c>0$ which is explicitly determined, where $n$ denotes the number of vertices. Furthermore, we prove that near the threshold, the graph consists of a giant component and isolated vertices. We also investigate the phase transition and provide an alternative proof of the results by Bollobás et al. [Random Struct. Algorithms, 31, 3-122 (2007)]. Our proofs are based on an exploration process that corresponds to the graph, and instead of relying heavily on branching processes, we employ a random walk constructed from the exploration process. We then apply a large deviations theory to show that a reasonably large component is always significantly larger, a strategy used in both connectivity and phase transition analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02898 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The connectivity and phase transition in inhomogeneous random graphs of finite types Jung, Hamin Probability A significant generalization of the Erdös-Rényi random graph model is an `inhomogeneous' random graph where the edge probabilities vary according to vertex types. We identify the threshold value for this random graph with a finite number of vertex types to be connected and examine the model's behavior near this threshold value. In particular, we show that the threshold value is $c \frac{\log n }{n}$ for some $c>0$ which is explicitly determined, where $n$ denotes the number of vertices. Furthermore, we prove that near the threshold, the graph consists of a giant component and isolated vertices. We also investigate the phase transition and provide an alternative proof of the results by Bollobás et al. [Random Struct. Algorithms, 31, 3-122 (2007)]. Our proofs are based on an exploration process that corresponds to the graph, and instead of relying heavily on branching processes, we employ a random walk constructed from the exploration process. We then apply a large deviations theory to show that a reasonably large component is always significantly larger, a strategy used in both connectivity and phase transition analysis. |
| title | The connectivity and phase transition in inhomogeneous random graphs of finite types |
| topic | Probability |
| url | https://arxiv.org/abs/2411.02898 |