Network Topology Recovery Method using Sparse Modeling

点击翻译按钮获取中文摘要

2022 年度において、まず、ネットワーク理論における代表的な問題の一つであるネットワークトポロジ復元問題の定式化が完了した。ネットワークトポロジの種類・規模・密度がそれぞれ観測されたネットワークトポロジと同じである教師グラフからリンクが欠損している無向グラフを復元する、ネットワークトポロジ復元問題を定式化した。また、定式化したネットワークトポロジ復元問題の解法であるネットワークトポロジ復元法 TRSM (Topology Recovery with Sparse Modeling) の提案が完了した。スパース表現化のための既存の代表的な過完全辞書構築アルゴリズム K-SVD 法と教師グラフによって構築したネットワークトポロジの辞書を用いてリンクが欠損した無向グラフを復元する手法を考案し、実装した。提案手法の基本的なアイデアは、観測されたネットワークトポロジと同じ種類である多数の教師ネットワークトポロジからトポロジの特徴を抽出し、観測されたネットワークトポロジのスパース表現化および逆スパース表現化を用いて外乱 (例えば、確率的に削除されたリンクなど) を除去する、というものである。さらに、提案手法である TRSM を利用することで、特定のネットワークトポロジから確率的に削除されたリンクをどの程度復元できるのかを明らかにした。実験を通して、スケールフリー性を有した、特徴のあるネットワークトポロジ上の欠損したリンクの復元に対して特に有効であり、例えば、現実の通信ネットワークの一つである CAIDA ネットワークトポロジのグラフを 80% 以上復元できることなどを示した。また、提案手法のリンク復元精度は既存手法のリンク予測精度よりも、おおよそ 10--20% 高いことなどを示した。