お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2018-03-05 15:30
媒介中心性のグラフ分解を用いた効率的な計算およびその実ネットワークへの適用
伊野波竜矢阪府大)・定兼邦彦東大)・宇野裕之阪府大)・米林悠真東大COMP2017-51
抄録 (和) 媒介中心性はグラフの中でどの頂点が中心的な役割を果たしているかを測る中心性とよばれる指標のうち, 最もよく用いられる重要な指標の一つである. 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 / / / /  
文献情報 信学技報, vol. 117, no. 474, COMP2017-51, pp. 35-42, 2018年3月.
資料番号 COMP2017-51 
発行日 2018-02-26 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2017-51

研究会情報
研究会 COMP  
開催期間 2018-03-05 - 2018-03-05 
開催地(和) 大阪府立大学 
開催地(英) Osaka Prefecture Univ. 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2018-03-COMP 
本文の言語 日本語 
タイトル(和) 媒介中心性のグラフ分解を用いた効率的な計算およびその実ネットワークへの適用 
サブタイトル(和)  
タイトル(英) 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  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第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)
第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著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2018-03-05 15:30:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2017-51 
巻番号(vol) IEICE-117 
号番号(no) no.474 
ページ範囲 pp.35-42 
ページ数 IEICE-8 
発行日 IEICE-COMP-2018-02-26 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会