| 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 | 2022-12-13 10:40 On the Impact of Random Walk Laziness on Efficiency of Graph Exploration in Dynamic Graphs Daiki Nakagawa, Takeaki Iwata, Ryotaro Matsuo, Hiroyuki Ohsaki (Kwansei Gakuin Univ.)  IA2022-57 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Graph exploration with a random walk has a wide range of engineering applications, and its mathematical properties have been actively studied. In recent years, not only random walks on static graphs (topology structure does not change over time), but also random walks on dynamic graphs (topology structure changes over time) have attracted a lot of attention. It has been shown that on an evolving graph (a type of dynamic graphs), the cover time of a random walk can be reduced to polynomial time by introducing laziness to a simple random walk. However, to the best of our knowledge, the effect of random walk laziness on the properties of the cover time of the random walk under a typical environment have not been sufficiently clarified. In this study, we therefore investigate the effect of random walk laziness on the random walk properties for a variety of evolving graphs with different sizes and densities. Specifically, we artificially generate Markov evolving graphs by generating various graphs with different structure, size, and density using seven different graph generation models and randomly rearranging the links in these graphs by rate τ, and we compare the mean cover time and mean first passage time of a lazy random walk on its Markovian dynamic graph with those of a simple random walk. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Random Walk / Lazy Random Walk / Evolving Graph / Mean First Passage Time / Mean Cover Time / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 122, no. 306, IA2022-57, pp. 50-55, Dec. 2022. | |
| Paper # | IA2022-57 | |
| Date of Issue | 2022-12-05 (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 | IA2022-57 |
|
| Conference Information | |
| Committee | IN IA |
| Conference Date | 2022-12-12 - 2022-12-13 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Higashi-Senda campus, Hiroshima Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| Paper Information | |
| Registration To | IA |
| Conference Code | 2022-12-IN-IA |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Impact of Random Walk Laziness on Efficiency of Graph Exploration in Dynamic Graphs |
| Sub Title (in English) | |
| Keyword(1) | Random Walk |
| Keyword(2) | Lazy Random Walk |
| Keyword(3) | Evolving Graph |
| Keyword(4) | Mean First Passage Time |
| Keyword(5) | Mean Cover Time |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Daiki Nakagawa |
| 1st Author's Affiliation | Kwansei Gakuin University (Kwansei Gakuin Univ.) |
| 2nd Author's Name | Takeaki Iwata |
| 2nd Author's Affiliation | Kwansei Gakuin University (Kwansei Gakuin Univ.) |
| 3rd Author's Name | Ryotaro Matsuo |
| 3rd Author's Affiliation | Kwansei Gakuin University (Kwansei Gakuin Univ.) |
| 4th Author's Name | Hiroyuki Ohsaki |
| 4th Author's Affiliation | Kwansei Gakuin University (Kwansei Gakuin Univ.) |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2022-12-13 10:40:00 |
| Presentation Time | 25 minutes |
| Registration for | IA |
| Paper # | IA2022-57 |
| Volume (vol) | vol.122 |
| Number (no) | no.306 |
| Page | pp.50-55 |
| #Pages | 6 |
| Date of Issue | 2022-12-05 (IA) |
[Return to Top Page]