一連の数千のノードがあるとします。ノードのペアごとに、距離メトリックがあります。この距離メトリックは、物理的な距離 (たとえば、すべてのノードの x、y 座標) またはノードを類似させるその他のものである可能性があります。
各ノードは、最大 N 個の他のノードに接続できます。ここで、N は小さく、たとえば 6 です。
すべてのグラフノード間の合計距離を最小限に抑えながら、完全に接続されたグラフを作成するにはどうすればよいですか (たとえば、グラフエッジに続く任意の 2 つのノード間を移動できます)。
つまり、トラバーサルの合計距離が最小化されるグラフは必要ありませんが、任意のノードについて、そのノードからのすべてのリンクの合計距離が最小化されるグラフは必要ありません。
絶対最小値は必要ありません-NP完全である可能性が高いと思います-しかし、真の絶対最小値に近いグラフを取得する比較的効率的な方法です。
すべての頂点が 6 つの隣接点を持つまでエッジを選択する貪欲なヒューリスティックをお勧めします。たとえば、最小スパニング ツリーから始めます。次に、頂点のいくつかのランダムなペアについて、選択されていないエッジの最大 1 つを使用するそれらの間の最短パスを見つけます (選択されたエッジを持つグラフの 2 つのコピーに対してダイクストラのアルゴリズムを使用し、選択されていないエッジによって接続されます)。次に、合計で最大の距離減少をもたらしたエッジを選択します。
カーネルを使用して、特定のカットオフ距離の下にあるノードに対してのみエッジを作成できます。
重み付けされていないエッジが必要な場合は、単純に基本的なカットオフを使用して開始できます。d(v1,v2) < R の場合、2 点間にエッジを追加します。
カットオフ R を微調整して、ノード間の適切な平均エッジ数を取得できます。
重み付きグラフが必要な場合、優先されるカーネルは多くの場合、ガウス カーネルです。
K(x,y) = e^(-d(x,y)^2/d_0)
値が低すぎるノードを遠ざけるためのカットオフがあります。d_0 は、最適な重みを得るために微調整するパラメーターです。
参考文献を探しているときに、私が知らなかったこのブログ投稿を見つけましたが、それは非常に説明的で、より多くの詳細が記載されているようです: http://charlesmartin14.wordpress.com/2012/10/09/spectral-clustering/
この方法は、グラフベースの半教師付き機械学習タスクで使用されます。たとえば、画像認識では、オブジェクトの小さな部分にタグを付け、オブジェクト全体を識別するための効率的なラベル伝達が行われます。
Google で検索できます:グラフによる半教師あり学習