| 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 | 2021-05-28 11:45 An Evaluation of Tracking Performance of Personalized PageRank Using Random Walk in Dynamic Graphs Tsuyoshi Yamashita, Kunitake Kaneko (Keio Univ.)  IN2021-5 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | By combining graphs managed by multiple services, we can create an autonomous distributed graph that enables multiple services to traverse the graph. In autonomous distributed graphs, a random walk (RW) is commonly used to obtain non-managed graph information. As a graph metric that can be computed by RW, Personalized PageRank (PPR) quantifies the importance of each node with respect to an arbitrary source node. Executing RW for every PPR query is expensive, thus it is required to calculate PPR by pre-executing RW. However, after updating the graph, it is not clear how much of the RW results executed before the update can be utilized. In this study, we aim to quantify how much the PPR values change, and how much pre-executed random walks need to be updated, when graph is updated. We evaluated using real-world Web graphs and found that up to 40% of the pre-executed random walks need to be updated, when a single adjacent node of a low-degree source node is updated, or neighborhood of a source node is updated intensively. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Dynamic Graph / Random Walk / Personalized PageRank / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 121, no. 42, IN2021-5, pp. 25-30, May 2021. | |
| Paper # | IN2021-5 | |
| Date of Issue | 2021-05-20 (IN) | |
| 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 | IN2021-5 |
|
| Conference Information | |
| Committee | RCS IN NV |
| Conference Date | 2021-05-27 - 2021-05-28 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Ad-Hoc/Sensor Networks/MANET, Mobile Networks, M2M/IoT Communications, Wi-Fi, IEEE802.15(ZigBee) and others |
| Paper Information | |
| Registration To | IN |
| Conference Code | 2021-05-RCS-IN-NV |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Evaluation of Tracking Performance of Personalized PageRank Using Random Walk in Dynamic Graphs |
| Sub Title (in English) | |
| Keyword(1) | Dynamic Graph |
| Keyword(2) | Random Walk |
| Keyword(3) | Personalized PageRank |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Tsuyoshi Yamashita |
| 1st Author's Affiliation | Keio University (Keio Univ.) |
| 2nd Author's Name | Kunitake Kaneko |
| 2nd Author's Affiliation | Keio University (Keio 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 | 2021-05-28 11:45:00 |
| Presentation Time | 25 minutes |
| Registration for | IN |
| Paper # | IN2021-5 |
| Volume (vol) | vol.121 |
| Number (no) | no.42 |
| Page | pp.25-30 |
| #Pages | 6 |
| Date of Issue | 2021-05-20 (IN) |
[Return to Top Page]