| Presentation | 2020-08-04 Landmark Decision Method Combining Random Walk and Betweenness Centrality Tsuyoshi Yamashita, Kunitake Kaneko, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Abstract Highly reproducible presentations of important nodes near the node of interest are useful in determin- ing landmarks in large graphs. However, the cost of obtaining graphs for high reproducibility is expensive, if graphs are stored and managed in autonomous distributed environment. We propose a landmark decision algorithm combining random walk and betweenness centrality computation. We evaluated the method with dataset of real world web graphs and found that obtaining 0.5% of all graphs is enough to present highly reproducible landmarks. And we compared landmark determined with partial graphs by our method and that with all graphs. We found that the result converged by 1% of random walk and is influenced by the number of candidates for landmarks. We also evaluated the cost of obtaining graphs and found that in a case the number of random walk count is 1%, the cost will be reduced by a factor of 400. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | autonomous distributed graph / graph algorithm / betweenness centrality |
| Paper # | IN2020-19 |
| Date of Issue | 2020-07-27 (IN) |
| Conference Information | |
| Committee | IN / CCS |
|---|---|
| Conference Date | 2020/8/3(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| Chair | Kenji Ishida(Hiroshima City Univ.) / Shigeki Shiokawa(Kanagawa Inst. of Tech.) |
| Vice Chair | Kunio Hato(INTERNET MULTIFEED CO.) / Tetsuya Asai(Hokkaido Univ.) / Megumi Akai(Hokkaido Univ.) |
| Secretary | Kunio Hato(Hiroshima City Univ.) / Tetsuya Asai(KDDI Research) / Megumi Akai(NTT) |
| Assistant | / Hidehiro Nakano(Tokyo City Univ.) / Hiroyasu Ando(Tsukuba Univ.) / Takashi Matsubara(Kobe Univ.) / Kosuke Sanada(Mie Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Networks / Technical Committee on Complex Communication Sciences |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Landmark Decision Method Combining Random Walk and Betweenness Centrality |
| Sub Title (in English) | |
| Keyword(1) | autonomous distributed graph |
| Keyword(2) | graph algorithm |
| Keyword(3) | betweenness centrality |
| 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 | 2020-08-04 |
| Paper # | IN2020-19 |
| Volume (vol) | vol.120 |
| Number (no) | IN-125 |
| Page | pp.pp.59-64(IN), |
| #Pages | 6 |
| Date of Issue | 2020-07-27 (IN) |