Networkxのグラフクラスタリング

Question

Networkxでは、どのようにノードの色に基づいてノードをクラスタリングできますか？たとえば、100個のノードがあり、そのうちのいくつかは黒に近く、他のノードは白に近いノードです。グラフのレイアウトでは、似たような色を持つノードをお互いに接近させ、非常に色の違うノードは互いに離れたままにしておきます。どうやってやるの？基本的に、エッジウェイトはspring_layoutのレイアウトにどのように影響しますか？ NetworkXがそれを行うことができない場合は、レイアウトを計算するのに役立つ他のツールはありますか？ i番目とj番目の隣接頂点の両方が同じ色のそれらの間の辺の重みであれば ：[OK]を

おかげ

Answer 1

は、簡単な手順に従って、私たちにそのグラフの隣接行列Wを構築することができますW_ {i、j}は大きな数字です（これは後で実験で調整されます）。そうでない場合は、同様に計算する小さな数字です。

行列のラプラシアンを L = D - Wと書くことができます。ここで、DはW i番目の行の合計に等しい要素d_ {i、i}を持つ対角行列です。

ここで、fがある任意のベクトルである fLf^Tの値は、巨大な調整重みを持つ頂点が近いf値を有する場合には、小さいことを容易に示すことができる。 iを使ってグラフの座標系を設定する方法については、頂点が1次元空間でf_i座標を持つように考えることができます。

ここで、いくつかのユークリッド空間の点集合としてグラフを表現するような、いくつかの数のこのようなベクトルf^kを選択しましょう。たとえば、k-meansが働きます：今、i番目の頂点f^1_i、f^2_i、...を有する初期グラフの同じ色の隣接するベクトルもこの新しい座標空間に接近する。

ベクトルfを選択する方法についての質問は単純です。行列Lの固有ベクトルのうちのいくつかをfとすると、小さいが非ゼロの固有値に対応します。

これは、スペクトルクラスタリングと呼ばれるよく知られた方法です。

続きを読む： データマイニング、推論、および予測の要素。著者ページから無料で入手可能ですトレバー・ハスティー、ロバート・ティブシャーアーニとジェローム・フリードマン

によってはhttp://www-stat.stanford.edu/~tibs/ElemStatLearn/