Presentation | 2019-11-14 [Poster Presentation] Investigation on the First Meeting Time of Random Walk Agents with Heterogeneous Transition Probability for Optimal Rendezvous Search Fumiya Toyoda, Yusuke Sakumoto, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In an unstructured network~(e.g., unstructured P2P network, socialnetwork, and MANET), there is a restriction that each node can onlyaccess its own adjacent nodes. In such an unstructured network, therendezvous search using random walks is discussed for quickly findingthe node's location. The time required for the rendezvous search isdetermined by the first meeting time that is the time until the randomwalk agents starting from different nodes in a network first meet atthe same node. Although the first meeting time depends on transitionprobability of a random walk agent, the effect is not clarified yet. In this paper, as the first step to make clear the effect, weinvestigate the effect of the heterogeneity of the transitionprobability on the first meeting time. We clarify that theheterogeneity of transition probability does not have a good effect onthe first meeting time. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Spectral Graph TheoryLaplacian MatrixFirst Meeting TimeRandom WalkRendezvous Search |
Paper # | IA2019-31 |
Date of Issue | 2019-11-07 (IA) |
Conference Information | |
Committee | IA |
---|---|
Conference Date | 2019/11/14(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Kwansei Gakuin University, Tokyo Marunouchi Campus (Sapia Tower) |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | IA2019 - Workshop on Internet Architecture and Applications 2019 |
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 |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | [Poster Presentation] Investigation on the First Meeting Time of Random Walk Agents with Heterogeneous Transition Probability for Optimal Rendezvous Search |
Sub Title (in English) | |
Keyword(1) | Spectral Graph TheoryLaplacian MatrixFirst Meeting TimeRandom WalkRendezvous Search |
1st Author's Name | Fumiya Toyoda |
1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
2nd Author's Name | Yusuke Sakumoto |
2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
Date | 2019-11-14 |
Paper # | IA2019-31 |
Volume (vol) | vol.119 |
Number (no) | IA-291 |
Page | pp.pp.43-46(IA), |
#Pages | 4 |
Date of Issue | 2019-11-07 (IA) |