グラフ圧縮による媒介中心性の計算手法

• 荒巻, 和治

• キットスワン, ナッタポン

• 大木, 英司

書誌事項

タイトル別名

• Computation Method for Betweenness Using Graph Compression

抄録

本論文はグラフの各点の媒介中心性を求める計算手法を提案する．それは次数が1である点をグラフから除き，圧縮されたグラフで計算する．提案手法が，従来の手法の次数が1である点が存在するグラフで生じる冗長な計算を回避し，計算量を削減することを示す．

This paper proposes a computation method to find a betweenness centrality of each vertex of a graph. The method compresses the original graph by removing vertices whose degree is one from the graph. The betweenness centrality is then calculated from the compressed graph. This avoids avoid blackundancy of the computation in the conventional method without the graph compression. As a result, the calculation time is blackuced.

収録刊行物

• 電子情報通信学会論文誌 B

  電子情報通信学会論文誌 B J100-B (11), 934-939, 2017-11-01

  電子情報通信学会

キーワード

• 媒介中心性
• グラフ解析
• グラフ圧縮
• 通信ネットワーク

詳細情報

• CRID: 1050001202923854080
• NII論文ID: 120006549741
• ISSN: 18810209
• Web Site: https://uec.repo.nii.ac.jp/records/8850
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN