| Presentation | 2023-03-03 Top-k Personalized PageRank Computation without Re-indexing for Graph Updates Tsuyoshi Yamashita, Naoki Matsumoto, Kunitake Kaneko, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Top-k Personalized PageRank (PPR) is graph analysis method to determine k important nodes with respect to a source node. To realize fast Top-k PPR computations, indexing for each node and using them during computations is effective. However, to ensure accuracy on dynamic graphs, re-indexing at part of nodes is required for every graph update, and the computation is costly. In this research, we proposed a method which don't ensure accuracy, but achieves sufficient accuracy for practical use. Specifically, focusing on the fact that indexes that are more easily referred to during computations are less likely to change by graph updates, we proposed a method that completely eliminates re-indexing for graph updates. Evaluation of the proposed method with real-world graph dataset shows that accuracy of Top-128 PPR decreases by only up to 0.1% comparing to existing accuracy ensuring method, even when the number of edges double. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Dynamic Graphs / Personalized PageRank / Index / Random Walks |
| Paper # | IN2022-117 |
| Date of Issue | 2023-02-23 (IN) |
| Conference Information | |
| Committee | IN / NS |
|---|---|
| Conference Date | 2023/3/2(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Okinawa Convention Centre + Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | General |
| Chair | Kunio Hato(Internet Multifeed) / Tetsuya Oishi(NTT) |
| Vice Chair | Tsutomu Murase(Nagoya Univ.) / Takumi Miyoshi(Shibaura Insti of Tech.) |
| Secretary | Tsutomu Murase(KDDI Research) / Takumi Miyoshi(Nagaoka Univ. of Tech.) |
| Assistant | / Kotaro Mihara(NTT) |
| Paper Information | |
| Registration To | Technical Committee on Information Networks / Technical Committee on Network Systems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Top-k Personalized PageRank Computation without Re-indexing for Graph Updates |
| Sub Title (in English) | |
| Keyword(1) | Dynamic Graphs |
| Keyword(2) | Personalized PageRank |
| Keyword(3) | Index |
| Keyword(4) | Random Walks |
| 1st Author's Name | Tsuyoshi Yamashita |
| 1st Author's Affiliation | Keio University(Keio Univ.) |
| 2nd Author's Name | Naoki Matsumoto |
| 2nd Author's Affiliation | Keio University(Keio Univ.) |
| 3rd Author's Name | Kunitake Kaneko |
| 3rd Author's Affiliation | Keio University(Keio Univ.) |
| Date | 2023-03-03 |
| Paper # | IN2022-117 |
| Volume (vol) | vol.122 |
| Number (no) | IN-407 |
| Page | pp.pp.305-310(IN), |
| #Pages | 6 |
| Date of Issue | 2023-02-23 (IN) |