| 講演名 | 2018-03-05 媒介中心性のグラフ分解を用いた効率的な計算およびその実ネットワークへの適用 伊野波 竜矢(阪府大), 定兼 邦彦(東大), 宇野 裕之(阪府大), 米林 悠真(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 媒介中心性はグラフの中でどの頂点が中心的な役割を果たしているかを測る中心性とよばれる指標のうち, 最もよく用いられる重要な指標の一つである. Brandesのアルゴリズムは媒介中心性を計算するための高速なアルゴリズムとして知られ, 頂点数$n$, 枝数$m$の重みなしグラフのすべての頂点の媒介中心性を${rm O}(nm)$時間で計算することができる. しかし, 大規模な実ネットワークではBrandesのアルゴリズムでさえも多大な計算時間を要するため, より高速なアルゴリズムが望ましい. 本研究の目的は, Brandesのアルゴリズムにグラフ分解を導入することで効率化を図ることと, その手法を実装して実ネットワークに対して適用し, グラフ分解を用いた手法の効率を検証することである. |
| 抄録(英) | Betweenness centrality is one of the most significant and commonly used centralities which is a notion of measuring the importance of nodes. Brandes proposed an algorithm for computing betweenness centrality efficiently, and it can compute its value for all nodes in ${rm O}(nm)$ time for unweighted graph, where $n$ and $m$ denote the number of nodes and edges, respectively. However, even Brandes' algorithm is not fast enough for large-scale real-world networks, and therefore, much faster algorithms are expected for computing betweenness centrality. The purpose of this research is to improve the efficiency by introducing graph decompositions for Brandes' algorithm, and to verify the effectiveness of our approaches by implementing them as computer programs and applying them to real-world networks. |
| キーワード(和) | 媒介中心性 / Brandesのアルゴリズム / BC木 / SPQR木 |
| キーワード(英) | betweenness centrality / Brandes' algorithm / BC tree / SPQR tree |
| 資料番号 | COMP2017-51 |
| 発行日 | 2018-02-26 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/3/5(から1日開催) |
| 開催地（和） | 大阪府立大学 |
| 開催地（英） | Osaka Prefecture Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) |
| 委員長氏名（英） | Hiro Ito(Univ. of Electro-Comm.) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(九工大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kyushu Inst. of Tech.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 媒介中心性のグラフ分解を用いた効率的な計算およびその実ネットワークへの適用 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Computation of Betweenness Centrality by Graph Decompositions and their Applications to Real-world Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 媒介中心性 / betweenness centrality |
| キーワード(2)（和/英） | Brandesのアルゴリズム / Brandes' algorithm |
| キーワード(3)（和/英） | BC木 / BC tree |
| キーワード(4)（和/英） | SPQR木 / SPQR tree |
| 第 1 著者 氏名（和/英） | 伊野波 竜矢 / Tatsuya Inoha |
| 第 1 著者 所属（和/英） | 大阪府立大学(略称：阪府大) Osaka Prefecture University(略称：Osaka Pref. Univ.) |
| 第 2 著者 氏名（和/英） | 定兼 邦彦 / Kunihiko Sadakane |
| 第 2 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. of Tokyo) |
| 第 3 著者 氏名（和/英） | 宇野 裕之 / Yushi Uno |
| 第 3 著者 所属（和/英） | 大阪府立大学(略称：阪府大) Osaka Prefecture University(略称：Osaka Pref. Univ.) |
| 第 4 著者 氏名（和/英） | 米林 悠真 / Yuuma Yonebayashi |
| 第 4 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. of Tokyo) |
| 発表年月日 | 2018-03-05 |
| 資料番号 | COMP2017-51 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | COMP-474 |
| ページ範囲 | pp.35-42(COMP), |
| ページ数 | 8 |
| 発行日 | 2018-02-26 (COMP) |