大会名称 |
---|
2020年 ソサイエティ大会 |
大会コ-ド |
2020S |
開催年 |
2020 |
発行日 |
2020/9/1 |
セッション番号 |
B-16 |
セッション名 |
インターネットアーキテクチャ |
講演日 |
2020/9/16 |
講演場所(会議室等) |
Meeting 15 |
講演番号 |
B-16-18 |
タイトル |
グラフの最短経路長と粗視化グラフの最短経路長の関係に関する一検討 |
著者名 |
◎岩田丈了, 北浦敬太, 松尾涼太郎, 大崎博之, |
キーワード |
粗視化グラフ, 最短経路長 |
抄録 |
近年、ソーシャルネットワークにおける交流関係などグラフ構造を有する大規模データが生成・収集・利用されており、このような大規模グラフに対するデータマイニング技術の一つとして、グラフの粗視化 (coarsening) が活発に研究されている。大規模グラフの特徴を有したたまデータの次元数を削減する手法であるグラフの粗視化手法は、グラフ分割問題のような複雑な問題を高速に解くための手段として検討されているが、グラフの最短経長問題にも応用できる可能性があると考えられる。そこで本稿では、大規模グラフにおける任意の二頂点間の最短経路長を、粗視化したグラフにおいて対応する頂点間最短経路長によってどの程度推定できる可能性があるかを調査する。 |
本文pdf |
PDF download
|