セミ クラスタリング アルゴリズムは、Google Pregel の論文で言及されています。セミクラスターのスコアは、以下の式を使用して計算されます
どこ
Ic はすべての内部エッジ
の重みの合計です Bc はすべての境界エッジの重みの合計です
Vc はセミ クラスター内の頂点の数であり、
fb は境界エッジ スコア係数です (ユーザーが 0 ～ 1 の間で定義)。
アルゴリズムは非常に簡単でしたが、上記の式がどのように得られたのか理解できませんでした。分母は Vc 個の頂点間で可能なエッジの数であることに注意してください。
誰か説明してくれませんか？
獲得する量を考えると、スコアは理にかなっています。
ここで取り上げる問題は、グラフの頂点をセミクラスター(単純に、各頂点が複数のセミクラスターに存在する可能性のある頂点のグループ) に配置する最良の方法を見つけ出すことです。セミクラスター。したがって、「最良の」方法を見つける方法の 1 つは、潜在的なセミクラスター (つまり、頂点の任意のグループ) にスコアを割り当てることです。次に、問題は合計スコアを最大化することになります。
したがって、セミクラスターは、グラフでクリークをキャプチャすることを目的としています。たとえば、ソーシャル グラフでは、セミクラスターは高校のバスケットボール チームのメンバーである可能性があります。
したがって、内側のエッジが多いほど、「より良い」セミクラスターに相当します。これはI_c、分子の を説明しています。同様に、境界エッジが多数ある場合は、調べているものを含むより良い準グループが存在する可能性が高いため、境界エッジは非常に少なくする必要があります。これにより-f_b * B_c、分子の が得られます。f_b境界エッジに割り当てるペナルティの量を調整できるようにするための単純なスケーリング係数です。
分母も一種の倍率です。これは、小さなクラスターが大きなクラスターによって完全に支配されないように、セミクラスター スコアを正規化するために使用されます。これの極端な例は、世界中の全員の半グループを考えた場合です。明らかに境界エッジがなく、内部エッジがたくさんありますが、高校のバスケットボール チームよりも有用性の低い半グループであることは間違いありません。
クリークに関連しています。
V_c *（V_c --1）は、サイズV_cのクリーク内のエッジの数です。
したがって、グループI_cのすべてのエッジの合計をとる場合、これは算術平均を取得するための適切な正規化です。
つまり、I_c /（V_c *（V_c --1））は、クリーク内の平均重量です。
ここで、-f_B * B_c項は、出力エッジのペナルティです。私見では、V_cで割るだけですが、これは個人的な好みです。予想される出力エッジは、この2乗ではなく、クリークメンバーの数に比例すると想定しているためです。