| Presentation | 2018-11-28 A Study on the Cooperative Search Using Multiple Random Walks in Unstructured Network Yusuke Sakumoto, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | To begin the communication between two nodes, the node with the communication request must specify the location of the partner node. If the network is unstructured where each node can access some nodes (adjacent node), the request node should search the partner node by tracing adjacent nodes. Random walk search is the method using multiple agents to perform random work starting from the request node. The previous works show that the cost of the random walk search is smaller than that of the well-known flooding search, and the expected search time has the inverse relationship to the degree of the partner node. Because of the inverse relationship, when node degrees vary largely, the random walk search has the advantage that the minimum of the expected search time is small, but the disadvantage that the average of the expected search time is long. In this paper, we discuss the cooperative search using random walks starting from the request node and the partner node, and show that the cooperative search alleviates the disadvantage of the conventional random walk search while keeping its advantage. We derive that the order of the average search time of the cooperative search, and clarify that the order is O(1/log n) smaller than that of the conventional random walk search. Through the simulation experiment, we verify the derived order, and investigate the efficiency of the cooperative search. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Spectral Graph Theory / Node Search / Flooding / Random Walk |
| Paper # | IA2018-36 |
| Date of Issue | 2018-11-21 (IA) |
| Conference Information | |
| Committee | IA |
|---|---|
| Conference Date | 2018/11/28(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Akihabara Convention Hall, 5th Floor (Conference Room 5B) |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Student Sessions, etc. (cosponsored by JSPS 163rd Committee on Internet Technology) |
| Chair | Katsuyoshi Iida(Hokkaido Univ.) |
| Vice Chair | Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Toru Kondo(Hiroshima Univ.) |
| Secretary | Rei Atarashi(Tokyo Metropolitan Univ.) / Hiroyuki Osaki(TOYOTA-IT) / Toru Kondo(NEC) |
| Assistant | Kenji Ohira(Tokushima Univ.) / Ryohei Banno(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Internet Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on the Cooperative Search Using Multiple Random Walks in Unstructured Network |
| Sub Title (in English) | |
| Keyword(1) | Spectral Graph Theory |
| Keyword(2) | Node Search |
| Keyword(3) | Flooding |
| Keyword(4) | Random Walk |
| 1st Author's Name | Yusuke Sakumoto |
| 1st Author's Affiliation | Tokyo Metropolitan University(Tokyo Metropolitan Univ.) |
| 2nd Author's Name | Hiroyuki Ohsaki |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2018-11-28 |
| Paper # | IA2018-36 |
| Volume (vol) | vol.118 |
| Number (no) | IA-326 |
| Page | pp.pp.1-8(IA), |
| #Pages | 8 |
| Date of Issue | 2018-11-21 (IA) |