graph - 需要图分区技术

Question

我有一个图 G = (V,E)，V 是节点集，E 是边集。我有两种类型的节点：源节点和消费者节点（源节点的数量远低于消费者节点）。节点具有地理位置。

我想将图划分为子图的集合，这些子图是：

a- 连通子图，

b- 适当大小（分区大小必须平衡；但不一定相等。例如在 2000-3000 个节点之间），

c- 分区最好直接连接到源。因此，如果分区中没有 Source，则分区到 Source 节点的路径不应包含其他分区中的任何节点。（最重要的约束）

d- 分区中的节点应该彼此靠近（地理上）

最小割集是可取的。源节点可以与其他分区隔离（可以在一个分区中；仅它们自己）。

我可以使用任何现有的分区技术吗？任何形式的帮助都将不胜感激。

Answer 1

有一些工作基于社区检测中使用的模块化度量。例如，在陈等人。2012 年，他们将模块化扩展到空间、加权、有向网络。空间距离用于调制链接权重。

这将符合您的观点 a) 和 d)。但是，（常规）模块化并非旨在寻找类似规模的社区，因此它无法满足您的观点 b）。也许您最好使用经典的最小切割方法，通过以类似于 Chen等人的方式修改诸如电导之类的度量。

对于你的观点 c)，我必须说我以前从未遇到过这种类型的约束，我觉得它很有趣。我想您可以尝试执行一些双标准优化，尝试最小化电导（或模块化）和标准，例如到最近源的平均距离。但这并不能保证对 c) 点的尊重。您还可以强制检测到社区的数量，使其小于来源的数量。