需要一种图分割技术

Question

3

我有一个图G =（V，E），其中V是节点集合，E是边集合。我有两种类型的节点：源节点和消费者节点（源节点数量远少于消费者节点）。这些节点具有地理位置。

我想将图划分为一组子图，它们应该是：

a- 连通的子图，

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

c- 划分应该直接连接到源。因此，如果在一个划分中没有源，则连接到源节点的路径不应包括其他划分中的任何节点。（最重要的约束条件）

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

最小割点集是首选。源节点可以与其他分区隔离（可以在单独的分区中；只有它们自己）。

是否有任何现有的分区技术可供使用？对任何帮助表示感激。

- Saeed Hajebi

这个问题似乎不属于讨论范围，因为它涉及到数学/理论计算机科学。 - user529758

你的图拓扑结构信息不足。源节点和消费节点是如何连接的？ - kuroi neko

这是一个水配送网络。因此，在网络中有一些源节点（例如3个）和一些消费者节点（例如14000个）。消费者通过连接（管道）与源相连，这些连接通过其他节点。因此，通常源和消费者之间的路径涉及其他消费者节点。 - Saeed Hajebi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vincent Labatut · Accepted Answer

有一些基于模块度量的工作用于社区检测。例如，在Chen et al. 2012中，他们将模块度扩展到空间、加权、有向网络中。空间距离用于调节链接权重。

这符合您的a）和d）点。然而，（常规）模块度不是设计用来找到大小相似的社区，因此它无法满足您的b）点。也许您最好使用经典的最小割方法，通过修改像Chen et al那样的度量方式，例如导电率。

对于您的c）点，我必须说我以前从未遇到过这种类型的约束条件，我觉得这非常有趣。我想您可以尝试执行一些双准则优化，尝试将导电率（或模块度）和最近源的平均距离这样的准则都最小化。但这并不能保证遵守c）点。您还可以强制检测到的社区数量少于源的数量。