要約
リンク予測はグラフ理論における基本的な問題であり、レコメンデーションシステムやコミュニティ検出、誤った接続の同定など、多岐にわたる応用を持つ。特徴に基づく手法は高い精度を達成するが、ノード属性に依存するため、特徴のないグラフへの適用性に制限がある。このようなグラフに対しては、共通近傍に基づく手法や次数依存型の構造ベースのアプローチが一般的に用いられる。しかしながら、これらの手法の有効性はグラフの密度に依存しており、共通近傍に基づくアルゴリズムは密度の高いグラフにおいて優れた性能を発揮する一方、次数依存型の手法は疎なグラフや木構造に近いグラフに適している。しかし、これまでの研究では、密度の高いグラフと疎なグラフを明確に区別するための基準が不足していた。本論文では、グラフの密度を評価するための基準として「平均クラスタリング係数」を提案し、リンク予測手法の選定を支援する。また、実証分析に用いるデータセットの不足を補うために、バラバシ・アルベルトモデルに基づく新たなグラフ生成手法を提案する。この手法により、構造的不均一性を保持しつつ、グラフの密度を制御可能に変化させることができる。合成データおよび実世界データを用いた包括的な実験を通じて、有効なリンク予測手法の選定を可能にする平均クラスタリング係数の経験的閾値を確立した。