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)