将加权图划分为等权群

Question

我有一个带加权边和加权顶点的双向图。我想找出N组不相交的连通顶点，以便：

每组的TargetWeight

• the权值之和接近，但不大于一定值的

1. 所选择的边的权重越小，这些组越低。这里的一个问题是:如果还选择了另一条边，那么边的重量就会减少(在边之间分担重量的一部分)。一个例子是: edge E1的重量为20，边缘E2的重量为30，他们的体重为5。只使用E1将导致体重20，同时考虑E1和E2的组合重量将导致45 (共享重量只考虑一次)。

N是事先已知的，但如果结果有很大改善，则允许N值更大。

TargetWeight是预先知道的，当多个成本较低的小组比高成本的大组更好时，就没有真正的度量。

在一个典型的例子中，这个图有大约50k个节点。图形没有存储在数据库中。

您可以将这个问题看作一个聚类算法，但是关于聚类的一般讨论可能与我所需要的有很多不同。我尝试过一个KMeans算法，但是我发现结果不够好。现在，我正在使用一个基于探索的启发式方法来检查一个特定的选择对未来群体的选择有多好。这种方法有效，但速度很慢。

Answer 1

我认为处理这类问题的最佳方法是：

• First:根据您的两个标准定义一个成本函数：

费用(图)=和(距离(子图权重，TargetWeight)+和(WeightEdges(子图))，其中距离(x，y)很大，如果(x，y)等于y-x，则将图随机分成N(或更多)不相交的subgraph

• third:组，通过图将一个顶点从一个组移动到另一个组，并检查总成本是否会减少

。