| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2018-11-28 14:40 A Study on the Cooperative Search Using Multiple Random Walks in Unstructured Network Yusuke Sakumoto (Tokyo Metropolitan Univ.), Hiroyuki Ohsaki (Kwansei Gakuin Univ.)  IA2018-36 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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) |
| (in English) | Spectral Graph Theory / Node Search / Flooding / Random Walk / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 118, no. 326, IA2018-36, pp. 1-8, Nov. 2018. | |
| Paper # | IA2018-36 | |
| Date of Issue | 2018-11-21 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | IA2018-36 |
|
| Conference Information | |
| Committee | IA |
| Conference Date | 2018-11-28 - 2018-11-28 |
| 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) |
| Paper Information | |
| Registration To | IA |
| Conference Code | 2018-11-IA |
| Language | Japanese |
| 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 |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 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.) |
| 3rd Author's Name | |
| 3rd Author's Affiliation | () |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2018-11-28 14:40:00 |
| Presentation Time | 25 minutes |
| Registration for | IA |
| Paper # | IA2018-36 |
| Volume (vol) | vol.118 |
| Number (no) | no.326 |
| Page | pp.1-8 |
| #Pages | 8 |
| Date of Issue | 2018-11-21 (IA) |
[Return to Top Page]