B05

数理・論理・量子情報/考え方をかんがえる

Computation, Logic, Quantum information

多様な価値観の比較

A comparison of diverse values

ネットワークにおける頂点の重要度の感度解析

Sensitivity Analysis of Network Centralities

代表者名

𠮷田悠一

Yuichi Yoshida

共同発表者名

村井翔悟

Shogo Murai

所属分野

情報学プリンシプル研究系

Principles of Informatics Research Division

pdf-image

要旨

重要な頂点を明らかにすることは、ネットワーク分析の基本的な作業である。そのために多くの指標が提案されており、総称して「中心性」と呼ぶ。しかしあまりに多くの中心性が研究されており、その違いが不明瞭になっている。そこで本研究では、グラフの変化に対する感度に基づいて中心性を比較する。具体的には、近接中心性、調和中心性、媒介中心性、終点媒介中心性、PageRank、全域木中心性の6つの主要な中心性について感度の理論的な分析を行った。人工グラフと実グラフを用いた実験により、理論解析で予測された傾向を確認した。

Revealing important vertices is a fundamental task in network analysis. As such, many indicators have been proposed for doing so, which are collectively called centralities. However, the abundance of studies on centralities blurs their differences. In this work, we compare centralities based on their sensivitity to modifications in the graph. We conducted a theoretical analysis of the edge sensitivities of six major centralities: the closeness centrality, harmonic centrality, betweenness centrality, endpoint betweenness centrality, PageRank, and spanning tree centrality. Our experimental results on synthetic and real graphs confirm the tendency predicted by the theoretical analysis.

関連動画