GraphX には、グラフの連結要素を見つけるためのアルゴリズムが付属しています。
それらの実装の複雑さについての声明は見つかりませんでした。
一般に、連結要素の検索は、幅優先検索や深さ優先検索などによって、線形時間で実行できます (ウィキペディアの記事を参照)。ただし、これはグラフをメモリに保持できることを前提としています。GraphX は分散型のアウト オブ コア アルゴリズムを実装しているため、比較することはできないと思います。
彼らのアルゴリズムがどのように機能し、どのような複雑さがあるか知っていますか?
グラフと非グラフのソリューションの主な目的は、問題を解決するために必要な一連のステップの数を減らすことだと思います。これは複雑さとは異なります。実際、Graph ソリューションは、実行するのにより多くの合計 CPU 命令を必要とする場合がありますが、連続するステップの数を削減する場合でも、適切なソリューションになります。
連結成分を見つけるという点では、幅優先アプローチと深さ優先アプローチの両方で、連続するステップの数は同じです。つまり、グラフの頂点数の倍数です。同じロジックを各頂点に順番に適用する必要があります。それが全体の解決策です。
グラフにほぼ同じサイズのクラスターが 2 つある場合でも、作業を 2 つのワーカーに分割し、一方の端から開始して中央で合流することはできません。終わりがどこにあるのかわからない。真ん中がどこかわからない。
出てくることを知っていれば、連続するステップの合計数を半分に減らすことができます。それが役立つ場合は、これを一連のステップに関して実行できる理論上の最善の方法と考えることができます。そして、それはグラフの形状に完全に依存しています。
接続されていない目立たないクラスターが多数あり、10 人を超えるクラスターがない場合、理論的には 10 の連続したステップが最適です。並列処理能力がどれだけ高くても、できることは 10 個の連続したステップです。
グラフ アルゴリズムは、理論上の最小値に近づけるだけではありません。クラスターの形状によっては、実際にそれを上回ります。
では、Spark アルゴリズムはどのように機能するのでしょうか? これはかなり単純です。各ノードは自分のノードを近隣ノードにブロードキャストするだけでVertexId、近隣ノードも同じことを行います。VertexId自身のブロードキャストよりも低い値を受信したノードは、次のラウンドをブロードキャストします。そうでない場合、頂点は沈黙します。
各頂点が他のすべての頂点に接続されているクラスターがある場合、1 ラウンドのメッセージの後、それぞれが最も低い VertexID が誰であるかを認識し、次のラウンドではすべてサイレントになります。一連の 1 つのステップ、クラスター全体。
一方、クラスター内の各頂点が最大 2 つの他の頂点にしか接続されていない場合、すべての頂点が最小値を認識するまでに N 連続ステップが必要になる可能性がVertexIDあります。
明らかに、一連のステップは、グラフ アルゴリズムでは異なる性質を持ち、グラフごとに異なります。適切に接続されたグラフは、多くのメッセージを生成し、それらのマージなどにより多くの時間を費やします。ただし、接続が不十分なグラフほど多くの連続したステップは必要ありません。
簡単に言うと、グラフ ソリューションのパフォーマンスはグラフの形状に完全に依存しますが、幅優先または深さ優先のソリューションよりもはるかに優れた並列処理を行う必要があります。