Jordan centre in random trees: persistence and distance to root
| Autor: | Dhruti Shah, Nikhil Karamchandani, Sarath Pattathil |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Persistence (psychology)
0303 health sciences Root (linguistics) Control and Optimization Computer Networks and Communications Computer science Applied Mathematics Management Science and Operations Research 01 natural sciences 010305 fluids & plasmas 03 medical and health sciences Computational Mathematics Agronomy 0103 physical sciences 030304 developmental biology |
| Zdroj: | Journal of Complex Networks. 8 |
| ISSN: | 2051-1329 |
| DOI: | 10.1093/comnet/cnz035 |
| Popis: | The Jordan centre of a graph is defined as a vertex whose maximum distance to other nodes in the graph is minimal, and it finds applications in facility location and source detection problems. We study properties of the Jordan centre in the case of random growing trees. In particular, we consider a regular tree graph on which an infection starts from a root node and then spreads along the edges of the graph according to various random spread models. For the Independent Cascade (IC) model and the discrete Susceptible Infected (SI) model, both of which are discrete-time models, we show that as the infected subgraph grows with time, the Jordan centre persists on a single vertex after a finite number of timesteps. As a corollary of our results, we also establish that the distance between the Jordan centre and the infection source (root node) is finite. Finally, we also study the continuous-time version of the SI model and bound the maximum distance between the Jordan centre and the root node at any time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|