如何用Girvan算法在有向图中寻找k分量？

Question

我知道吉文-纽曼算法-以下是算法：

1. 首先计算网络中所有现有边的中间性。
2. 最中间的边缘被移除。
3. 重新计算了受移除影响的所有边缘之间的关系。
4. 步骤2和步骤3被重复，直到没有保留边缘。

但是我想用这个算法在有向图中找到k个分量，其中k是一个给定的整数。

我该怎么做？有可能吗？

谢谢。

Answer 1

如果图是有向的，您只需要处理有向边之间的有向版本，即计算通过边的有向最短路径。

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