グラフ・ネットワークマイニングとは？基本概念と主な応用分野を解説

グラフは、集合、系列、格子、木構造といった従来のデータ構造よりも汎用的なクラスを定義するものです。インターネットやソーシャルネットワーク、データネットワーク、生物学的ウェブ、バイオインフォマティクス、ケミカルインフォマティクス、コンピュータビジョン、マルチメディアおよびコンテンツ検索など、幅広い分野でグラフが活用されています。

ここでは、グラフ・ネットワークマイニングの代表的な応用について詳しく見ていきましょう。

グラフパターンマイニング

グラフパターンマイニングとは、単一のグラフまたは複数のグラフの集合から、頻出するサブグラフ（部分グラフ）を発見する手法です。マイニングのアプローチは大きく分けて、Aprioriベースの手法とパターングロース（成長）ベースの手法の2つに分類されます。

また、「閉じたグラフ（クローズドグラフ）」の集合をマイニングすることも可能です。グラフgが閉じているとは、gと同じサポート数を持つ適切な超グラフg'が存在しないことを意味します。さらに、近似頻出グラフ、凝集グラフ、密なグラフなど、さまざまな変種のグラフパターンも研究されています。ユーザー定義の制約条件をマイニング処理の段階に組み込むことで、マイニング効率を大幅に向上させることもできます。

ネットワークの統計モデリング

ネットワークは、オブジェクトに対応するノードの集合と、それらのノード間の関係を表すエッジ（リンク）の集合から構成されます。

ノードとリンクがすべて同じ種類で構成される場合、そのネットワークは「同質（ホモジニアス）」と呼ばれます。例として、友人ネットワーク、共著者ネットワーク、Webページネットワークなどが挙げられます。一方、ノードや接続が異なる種類で構成される場合は「異質（ヘテロジニアス）」と呼ばれます。たとえば、著者・会議・論文・テキストをつなぐ出版ネットワークや、医師・看護師・患者・疾患・治療をつなぐ医療ネットワークなどがこれに該当します。

情報ネットワーク分析によるデータクリーニング・統合・検証

巨大なネットワーク内で相互に接続された複数のデータ要素の間には、情報の冗長性が存在することがあります。こうした冗長性をネットワーク分析によって解析することで、高品質なデータクリーニング、データ統合、データ検証、そして信頼性の高い検索を実現できます。

グラフおよび同質ネットワークのクラスタリングと分類

大規模ネットワーク向けのクラスタ分析手法が数多く開発されており、ネットワークのトポロジー的構造とそれに関連する属性に基づいて、ネットワークの構造を解明し、隠れたコミュニティ、ハブ、外れ値を発見することができます。ネットワーククラスタリング手法にはさまざまな種類があり、分割型、階層型、密度ベースのアルゴリズムに分類できます。

異質ネットワークのクラスタリング、ランキング、分類

異質ネットワークは、複数の種類のノードと接続が相互に連携して構成されるネットワークです。このような相互接続構造は豊富な情報を含んでおり、ノードとリンクを相互に強化したり、あるタイプから別のタイプへと観察結果を伝播させたりするために活用できます。

異質ネットワークにおけるクラスタリングとランキングは、密接に関連付けて実装することが可能です。具体的には、クラスタ内で高ランクに位置するノードは、クラスタの凝集度を計算する際に、低ランクの対応ノードよりも大きな寄与をもたらします。