| Presentation | 2022-03-11 A Method for Generating Random Walk Paths Focusing Only on Updates Near A Source Node in Dynamic Distributed Graphs Tsuyoshi Yamashita, Kunitake Kaneko, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In graph calculations with a lot of random walks (RWs), some long RWs become bottlenecks, and thus pre-execution of RWs is required. However, in dynamic graphs, using pre-execution results on the graphs before updates causes a decrease in accuracy. In this research, we focus on the fact that updates of nodes visited in the early stage of RWs have a larger impact on the calculation results than updates of nodes visited in the middle or later stages of RWs. Then, we propose a method to generate RW paths by connecting paths generated in the graph after updateswith paths pre-executed in the graph before updates. This method enables to avoid long RWs and decrease in accuracy simultaneously. Evaluation using real-world Web-graphs shows that proposed method can achieve sufficient calculation accuracy even when only 28 - 56 % of RWs are completed. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Random Walks / Dynamic Graphs / Distributed Graphs / Personalized PageRank |
| Paper # | IN2021-48 |
| Date of Issue | 2022-03-03 (IN) |
| Conference Information | |
| Committee | NS / IN |
|---|---|
| Conference Date | 2022/3/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | General |
| Chair | Akihiro Nakao(Univ. of Tokyo) / Kenji Ishida(Hiroshima City Univ.) |
| Vice Chair | Tetsuya Oishi(NTT) / Kunio Hato(Internet Multifeed) |
| Secretary | Tetsuya Oishi(NTT) / Kunio Hato(Chuo Univ.) |
| Assistant | Kotaro Mihara(NTT) |
| Paper Information | |
| Registration To | Technical Committee on Network Systems / Technical Committee on Information Networks |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Method for Generating Random Walk Paths Focusing Only on Updates Near A Source Node in Dynamic Distributed Graphs |
| Sub Title (in English) | |
| Keyword(1) | Random Walks |
| Keyword(2) | Dynamic Graphs |
| Keyword(3) | Distributed Graphs |
| Keyword(4) | Personalized PageRank |
| 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.) |
| Date | 2022-03-11 |
| Paper # | IN2021-48 |
| Volume (vol) | vol.121 |
| Number (no) | IN-434 |
| Page | pp.pp.103-108(IN), |
| #Pages | 6 |
| Date of Issue | 2022-03-03 (IN) |