| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-08-04 14:55 ランダムウォークと媒介中心性演算を組み合わせたランドマーク決定手法 ○山下剛志・金子晋丈（慶大）  IN2020-19 |
|
| 抄録 | （和） | 大規模グラフの理解において注目ノード近傍の重要ノードの提示に高い再現性があるとランドマークとし て有用である.しかし，分散管理されたグラフにおいて，特に注目ノード近傍のグラフがまとまって保存されていな い場合，高い再現性を得るためのグラフ取得コストは高くなる.そこでランダムウォークを用いたグラフの概形の探 索と厳密な媒介中心性計算を組み合わせたランドマーク決定アルゴリズムを提案する.実世界の 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 / / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 125, IN2020-19, pp. 59-64, 2020年8月. | |
| 資料番号 | IN2020-19 | |
| 発行日 | 2020-07-27 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2020-19 |
|
| 研究会情報 | |
| 研究会 | IN CCS |
| 開催期間 | 2020-08-03 - 2020-08-04 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2020-08-IN-CCS |
| 本文の言語 | 日本語 |
| タイトル（和） | ランダムウォークと媒介中心性演算を組み合わせたランドマーク決定手法 |
| サブタイトル（和） | |
| タイトル（英） | Landmark Decision Method Combining Random Walk and Betweenness Centrality |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 自律分散グラフ / autonomous distributed graph |
| キーワード(2)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(3)（和/英） | 媒介中心性 / betweenness centrality |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-08-04 14:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2020-19 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.125 |
| ページ範囲 | pp.59-64 |
| ページ数 | 6 |
| 発行日 | 2020-07-27 (IN) |
[研究会発表申込システムのトップページに戻る]