グラフエントロピーによる中心性指標のロバスト性推定－ノードの中心性指標のノイズに対する順位不変性の推定

摘要

現実の世界に存在する大規模で複雑なネットワークの持つ特徴や性質の究明を目的とする複雑ネットワーク分析が活発に行われている。通常、複雑ネットワーク分析において分析対象となるグラフには、様々な種類のノイズが含まれている。そのため、ノイズがノードの中心性指標にどのような影響を与えるかを調査し、複雑ネットワーク分析におけるノードの中心性指標の信頼性を明らかにすることが重要な研究課題となっている。本研究では、ノードの中心性指標の信頼性を明らかにするための最初のステップとして、グラフに含まれるノイズに対するノードの中心性指標のロバスト性をグラフの構造から推定するという課題に取り組む。本稿では、ノードの中心性指標のロバスト性を推定する指標として、グラフエントロピーに着目する。グラフエントロピーが、ノイズに対するノードの中心性指標のロバスト性を推定するのにどの程度有用であるかを、実験により明らかにする。実験の結果、（1）グラフエントロピーは、グラフにおけるノードおよびリンクの追加·削除に対するノードの中心性指標のロバスト性の推定に有用であること、（2）代表的な4種類の中心性指標（近接中心性、媒介中心性、次数中心性、固有ベクトル中心性）のノイズに対するロバスト性の推定に、グラフエントロピーが有用であること、などを示す。