文献

J-GLOBAL ID：201802243573726433   整理番号：18A0226434

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

著者 (3件)： 荒巻和治 (電通大 大学院情報理工学研究科) ,  KITSUWAN Nattapong (電通大 大学院情報理工学研究科) ,  大木英司 (京大 大学院情報学研究科)
資料名： 電子情報通信学会論文誌 B(Web)
巻： J100-B  号： 11  ページ： 934-939 (WEB ONLY)  発行年： 2017年11月01日 
JST資料番号： U0471A  ISSN： 1881-0209  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文はグラフの各点の媒介中心性を求める計算手法を提案する。それは次数が1である点をグラフから除き,圧縮されたグラフで計算する。提案手法が,従来の手法の次数が1である点が存在するグラフで生じる冗長な計算を回避し,計算量を削減することを示す。(著者抄録)

シソーラス用語： *グラフ ,  *圧縮 ,  *指標 ,  *計算 ,  *図式解法 ,  計算量 ,  通信網
準シソーラス用語： *媒介中心性 ,  ネットワークグラフ

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (6件)：

• L.C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol.40, no.1, pp.35-41, 1977.
• U. Brandes, “A faster algorithm for betweenness centrality,” J. Math. Sociology, vol.25, no.2, pp.163-177, 2001.
• L. Wang, F. Yang, L. Zhuang, H. Cui, F. Lv, and X. Feng, “Articulation points guided blackundancy elimination for betweenness centrality,” Proc. 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2016.
• D.A. Bader, S. Kintali, K. Madduri, and M. Mihail, “Approximating betweenness centrality,” Algorithms and Models for the Web-Graph. WAW 2007. Lecture Notes in Computer Science, ed. A. Bonato, F.R.K. Chung, pp.124-137, Springer, San Diego, Dec. 2007.
• M. Kas, M. Wachs, K.M. Carley, and L.R. Carley, “Incremental algorithm for updating betweenness centrality in dynamically growing networks,” Proc. IEEE/ACM Int. Conf. on Advances in Social Netw. Analysis and Mining, Ontario Canada, pp.33-40. Aug. 2013.

タイトルに関連する用語 (3件)： グラフ ,  計算 ,  手法