本研究では, グラフにおける「k-辺連結誘導部分グラフ」を効率的に列挙するための新しいフレームワークを提案する. k-辺連結誘導部分グラフとは, 任意の頂点対の間に少なくとも k 本の辺素パスが存在する, 頑健な部分ネットワークである. 基盤として用いる SSD (Superset–Subset–Disjoint) 集合システムは, 解とその差分構造に基づいて定義される集合族であり, k-辺連結部分グラフを誘導する頂点集合族も SSD に属する. 本研究ではこの構造的性質を利用し, 従来は時間量が大きかった部分グラフ列挙を, より体系的かつ効率的に実行できることを示す. また, 辺連結性解析に用いられるグラフ分解手法との関係を整理し, 各 k に対して適切なオラクルを構築することで, 高次の連結度にも対応できることを明らかにした. 本成果は, ネットワークの脆弱性解析や信頼性評価など, 多様な分野での応用が期待される.
本手法で列挙されるk-辺連結誘導部分グラフは, 複数経路で結ばれた頑健な部分ネットワークを抽出できるため, 通信ネットワークの耐故障性解析, 電力網・交通網の冗長経路抽出, 重要箇所のリスク評価に有用である. また, ソーシャルネットワークの安定コミュニティ検出や大規模グラフ解析基盤への組込みなど, 多様な応用が期待される. SSD に基づく体系的手法により, 従来より高速かつ網羅的な構造列挙が可能になる.
| 氏名 | コース | 研究室 | 役職/学年 |
|---|---|---|---|
| 庄田 寛 | 数理工学コース | 離散数理分野 | 博士1回生 |
| 原口和也 | 数理工学コース | 離散数理分野 | 准教授 |