graph - Girvan-Newmanアルゴリズムを使用して有向グラフでkコンポーネントを見つける方法は?

Question

私はGirvan - Newmanアルゴリズムを知っています - ここにアルゴリズムがあります:

1. ネットワーク内の既存のすべてのエッジの中間性が最初に計算されます。
2. 中間性が最も高いエッジが削除されます。
3. 削除によって影響を受けるすべてのエッジの中間性が再計算されます。
4. ステップ 2 と 3 は、エッジがなくなるまで繰り返されます。

しかし、このアルゴリズムを使用して、有向グラフ内の k 個のコンポーネントを見つけたいと考えています。ここで、k は指定された整数です。
これどうやってするの？出来ますか？
ありがとう。

Answer 1

グラフが有向である場合は、edge betweenness の有向バージョンを処理するだけで済みます。つまり、エッジを通過する有向最短パスをカウントします。

パラメータ k に関しては、k 個の分離されたコンポーネントが得られるまで、最も中心的なリンクを削除する必要があります。つまり、エッジがなくなるまでステップ 4 を適用する必要はありません。必要な k に到達する前に停止できます。結果のコンポーネントに含まれるノードは、最初のグラフのコミュニティに対応します。