| 講演名 | 2020-08-04 ランダムウォークと媒介中心性演算を組み合わせたランドマーク決定手法 山下 剛志(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 大規模グラフの理解において注目ノード近傍の重要ノードの提示に高い再現性があるとランドマークとし て有用である.しかし，分散管理されたグラフにおいて，特に注目ノード近傍のグラフがまとまって保存されていな い場合，高い再現性を得るためのグラフ取得コストは高くなる.そこでランダムウォークを用いたグラフの概形の探 索と厳密な媒介中心性計算を組み合わせたランドマーク決定アルゴリズムを提案する.実世界の Web グラフのデータ セットを用いた手法の評価を行い，全グラフの 0.5% 程のグラフ取得量で，再現性のあるランドマークを決定できるこ とが明らかになった.また，全グラフを取得した際のランドマークに対する正確性を評価し，ランダムウォーク回数 が全グラフの 1% 程度でランドマークの一致率は収束し，ランドマークとなりうるノードの候補数によって，正確さ が影響を受けることを示した.最後にグラフ取得コストを評価し，ランダムウォーク回数が全グラフの 1% 程度の場 合，グラフ取得コストは平均 400 倍削減されることを示した. |
| 抄録(英) | 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. |
| キーワード(和) | 自律分散グラフ / グラフアルゴリズム / 媒介中心性 |
| キーワード(英) | autonomous distributed graph / graph algorithm / betweenness centrality |
| 資料番号 | IN2020-19 |
| 発行日 | 2020-07-27 (IN) |
| 研究会情報 | |
| 研究会 | IN / CCS |
|---|---|
| 開催期間 | 2020/8/3(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 委員長氏名（和） | 石田 賢治(広島市大) / 塩川 茂樹(神奈川工科大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Shigeki Shiokawa(Kanagawa Inst. of Tech.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 浅井 哲也(北大) / 赤井 恵(北大) |
| 副委員長氏名（英） | Kunio Hato(INTERNET MULTIFEED CO.) / Tetsuya Asai(Hokkaido Univ.) / Megumi Akai(Hokkaido Univ.) |
| 幹事氏名（和） | 小畑 博靖(広島市大) / 樫原 俊太郎(KDDI総合研究所) / 谷口 展郎(NTT) / 星野 文学(NTT) / 川喜田 佑介(神奈川工科大) / 中田 一紀(TDK) |
| 幹事氏名（英） | Hiroyasu Obata(Hiroshima City Univ.) / Shuntaro Kashihara(KDDI Research) / Noburo Taniguchi(NTT) / Fumitaka Hoshino(NTT) / Yusuke Kawakita(Kanagawa Inst. of Tech.) / Kazuki Nakada(TDK) |
| 幹事補佐氏名（和） | / 中野 秀洋(東京都市大) / 安東 弘泰(筑波大) / 松原 崇(神戸大) / 眞田 耕輔(三重大学) |
| 幹事補佐氏名（英） | / Hidehiro Nakano(Tokyo City Univ.) / Hiroyasu Ando(Tsukuba Univ.) / Takashi Matsubara(Kobe Univ.) / Kosuke Sanada(Mie Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Complex Communication Sciences |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ランダムウォークと媒介中心性演算を組み合わせたランドマーク決定手法 |
| サブタイトル（和） | |
| タイトル（英） | Landmark Decision Method Combining Random Walk and Betweenness Centrality |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自律分散グラフ / autonomous distributed graph |
| キーワード(2)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(3)（和/英） | 媒介中心性 / betweenness centrality |
| 第 1 著者 氏名（和/英） | 山下 剛志 / Tsuyoshi Yamashita |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2020-08-04 |
| 資料番号 | IN2020-19 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IN-125 |
| ページ範囲 | pp.59-64(IN), |
| ページ数 | 6 |
| 発行日 | 2020-07-27 (IN) |