| Presentation | 2019-09-06 A Study on Modeling Branching Random Walk on Random Regular Graph Takuro Mayaguchi, Ryota Sakaguchi, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Several popular problems in information networking and social networking such as search, distribution, and dis- semination can be modeled by random walk of single or multiple agents on a graph. As an approach to remedy the redundancy in multiple random walks, Branching Random Walk (BRW) has been proposed, in which the number of agents of random walks is dynamically changed by the branching-and-aggregation mechanism. An agent starting its walk from an originating node randomly selects b nodes among its neighbor nodes, and it activates those neighbor nodes (branching). If multiple agents simultaneous visit the same node, those agents are unified into a single agent (aggregation). BRW is a relatively new mobility model on a graph. Hence, to the best of our knowledge, understanding of its mathematical properties is quite limited. In this paper, we describe the dynamics of BRW on a random regular graph, and clarify the relation between the branching parameter b and the mean and the distribution of hitting times and the mean cover time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Branching Random Walk / Mobility Model on Graph / Dynamical Process / Hitting Time / Cover Time |
| Paper # | IA2019-17 |
| Date of Issue | 2019-08-29 (IA) |
| Conference Information | |
| Committee | IA |
|---|---|
| Conference Date | 2019/9/5(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hokkaido Univ. Humanities and Social Sciences Classroom Bldg, W102 |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Internet Operation and Management, etc. |
| Chair | Hiroyuki Osaki(Kwansei Gakuin Univ.) |
| Vice Chair | Rei Atarashi(IIJ) / Toru Kondo(Hiroshima Univ.) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| Secretary | Rei Atarashi(Kwansei Gakuin Univ.) / Toru Kondo(KDDI Research) / Hiroshi Yamamoto(NEC) |
| Assistant | Kenji Ohira(Osaka Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) / Ryohei Banno(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Internet Architecture |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on Modeling Branching Random Walk on Random Regular Graph |
| Sub Title (in English) | |
| Keyword(1) | Branching Random Walk |
| Keyword(2) | Mobility Model on Graph |
| Keyword(3) | Dynamical Process |
| Keyword(4) | Hitting Time |
| Keyword(5) | Cover Time |
| 1st Author's Name | Takuro Mayaguchi |
| 1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 2nd Author's Name | Ryota Sakaguchi |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 3rd Author's Name | Hiroyuki Ohsaki |
| 3rd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2019-09-06 |
| Paper # | IA2019-17 |
| Volume (vol) | vol.119 |
| Number (no) | IA-197 |
| Page | pp.pp.33-37(IA), |
| #Pages | 5 |
| Date of Issue | 2019-08-29 (IA) |