可以使用哪种算法对图进行分区以使每个分区组（或组件）的值相等或平衡？

Question

我们假设图由具有值和无向边的节点组成。
我想将图划分为几个组，我选择这些组来满足每个分区组具有与节点具有相似或相同的值总和的条件。

您能否推荐哪些算法可用于在满足我提到的条件的情况下对图进行分区？
如果您附上用 python 或 java 实现的算法，我将更加感激。


（为了方便您理解，我们附上了图片和数据类型。）

<Data information>
[node_id]: n_1, n_2, n_3 ,, etc
[node_value]: 10, 5, 20,, etc
[node_adjacency_data] : Please refer to the attached picture.
[node_latitude]: 37.25201, 37.25211, 37.25219,, etc
[node_longitude]: 127.10195, 127.11321, 127.11377,, etc 

Answer 1

首先，这个问题是NP-Hard问题，所以你将无法得到这个问题的完美解决方案。然而，实际上有大量的研究旨在以这种方式划分图。通过查找顶点加权图分区开始搜索。

以这种方式分区图的最著名的算法是METIS，并且有一个很好的用于优化 C 实现的 Python 包装器（您必须单独构建/安装）。它采用 networkx 图或简单的邻接列表作为输入。

METIS 采用带有加权顶点和边的图，并返回给定数量的分区，同时最小化被切割边的权重。您仍然需要选择要将图表分成多少部分。

下面是一些使用 Python METIS 库来解决您给出的示例问题的示例代码：

import networkx as nx
import metis

# Set up graph structure
G = nx.Graph()
G.add_edges_from([ (0,1), (0,2), (0,3), (1, 2), (3, 4) ])

# Add node weights to graph
for i, value in enumerate([1,3,2,4,3]):
    G.node[i]['node_value'] = value

# tell METIS which node attribute to use for 
G.graph['node_weight_attr'] = 'node_value' 

# Get at MOST two partitions from METIS
(cut, parts) = metis.part_graph(G, 2) 
# parts == [0, 0, 0, 1, 1]

# Assuming you have PyDot installed, produce a DOT description of the graph:
colors = ['red', 'blue']
for i, part in enumerate(parts):
    G.node[i]['color'] = colors[part]
nx.nx_pydot.write_dot(G, 'example.dot')

然后我们可以使用 GraphViz 来可视化分区：

这与您在问题中给出的分区相同。