需要图分区技术

Question

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

欲图形划分成子图是其的集合：

A-连接子图，

适当大小的B-（分区的大小必须是平衡的;然而不一定相等，例如在2000-3000个节点之间），

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

D-在一个分区中的节点应该是彼此接近（地理）

的最小割集是优选的。源节点可以与其他分区隔离（可以在一个分区中;只有它们自己）。

我可以使用任何现有的分区技术吗？任何形式的帮助都会被完全赞赏。

Answer 1

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

这将符合你的观点a）和d）。然而，（规则）模块化并不是为了寻找相似大小的社区而设计的，因此它不能满足你的要求。也许你最好使用经典的最小切割方法，通过类似于陈等的方式修改诸如conductance等度量。

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