graph - 如何使用 Girvan-Newman 算法在有向图中找到 k 个分量？

Question

我知道Girvan - Newman算法 - 这是算法：

1. 首先计算网络中所有现有边的介数。
2. 具有最高介数的边被移除。
3. 重新计算受移除影响的所有边缘的介数。
4. 重复步骤 2 和 3，直到没有边缘。

但我想用这个算法在有向图中找到 k 个分量，其中 k 是给定的整数。
我怎样才能做到这一点？可能吗？
谢谢。

Answer 1

如果图是有向的，则只需要处理有向版本的edgebetweenness，即计算通过一条边的有向最短路径。

关于您的参数 k，您必须删除最中心的链接，直到您获得 k 个分离的组件。换句话说，在没有边缘之前，您不需要应用第 4 步：当您达到所需的 k 时，您可以在之前停止。结果组件中包含的节点对应于初始图中的社区。