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

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, and there is a good Python wrapper 优化的 C 实现（您必须单独 build/install）。它采用 networkx 图或简单的邻接表作为输入。

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

下面是一些示例代码，使用 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 可视化分区：

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

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

Which algorithm can be used to partition graph to make each partitioned group(or component)'s value equal or balance?

algorithm

optimization

partitioning

mathematical-optimization

graph-algorithm