A mathematical analysis approach of the node clustering method in a directed graph

本研究の目的は平成22年度～24年度の科研費採択期間中に開発した有向グラフを縮約する手法（以下ノードクラスタリング法：NCMと略す）を基に，最適な縮約を行う数理モデルを構築することである．H30年度中には，本研究課題を解決するために必要な次の課題，(1)グラフ構造の複雑度を表すパラメータの開発，(2)グラフ自体が与える情報量の導出，(3)有向グラフの縮約率，(4)独立ノード，中継ノードの吸収法，を提案した．指標(1),(2),(3)はグラフ全体の数理構造を数値として表現できるいわばグラフの基データとなる．H31年度ではこれらのグラフの基データを適用し，NCMに関わる次の新たな3つの指標（グラフ縮約率，情報吸収率，情報損失率）を提案することができた．グラフ縮約率は，グラフがどの程度簡素化されたかを表す指標であり，情報吸収率は，与えられたノード間同士の関係がどの程度クラスタリングされたかを示す指標である．理想的なNCMとは，単にグラフが簡素化されれば良いという訳ではない．確かにグラフ縮約率が高ければむろんグラフが簡素化され，グラフの骨格を導きだすという利点がある．ただこの場合，もし情報吸収率も高ければ，与えられたノードの関係は入出力の状況も含め密接に絡んだ状態となり，情報が一塊になった密集状況（大域化）になっている可能性がある．そうなると例えばグラフ中に潜んでいるレア情報を抽出することが難しくなり，本来の理想的な縮約を遂行するNCMとならない．そこでこの問題を解決するため，クラスタリングされたノード間同士（グループ）における関係の依存度を測る新たな指標を開発した．この指標を多角的に適用することにより，NCMにより生成されたノード間のクラスタリングの妥当性を評価することが可能となり，NCMを理想的な縮約を与える数理モデルとして構築することができた．

本研究の目的は平成22年度～24年度の科研費採択期間中に開発した有向グラフを縮約する手法（以下ノードクラスタリング法：NCMと略す）を基に，最適な縮約を行う数理モデルを構築することである．H30年度中には，本研究課題を解決するために必要な次の課題，(1)グラフ構造の複雑度を表すパラメータの開発，(2)グラフ自体が与える情報量の導出，(3)有向グラフの縮約率，(4)独立ノード，中継ノードの吸収法，を提案した．指標(1),(2),(3)はグラフ全体の数理構造を数値として表現できるいわばグラフの基データとなる．H31年度ではこれらのグラフの基データを適用し，NCMに関わる次の新たな3つの指標（グラフ縮約率，情報吸収率，情報損失率）を提案することができた．グラフ縮約率は，グラフがどの程度簡素化されたかを表す指標であり，情報吸収率は，与えられたノード間同士の関係がどの程度クラスタリングされたかを示す指標である．理想的なNCMとは，単にグラフが簡素化されれば良いという訳ではない．確かにグラフ縮約率が高ければむろんグラフが簡素化され，グラフの骨格を導きだすという利点がある．ただこの場合，もし情報吸収率も高ければ，与えられたノードの関係は入出力の状況も含め密接に絡んだ状態となり，情報が一塊になった密集状況（大域化）になっている可能性がある．そうなると例えばグラフ中に潜んでいるレア情報を抽出することが難しくなり，本来の理想的な縮約を遂行するNCMとならない．そこでこの問題を解決するため，クラスタリングされたノード間同士（グループ）における関係の依存度を測る新たな指標を開発した．この指標を多角的に適用することにより，NCMにより生成されたノード間のクラスタリングの妥当性を評価することが可能となり，NCMを理想的な縮約を与える数理モデルとして構築することができた．