假设我有一系列数千个节点。对于每对节点，我都有一个距离度量。这个距离度量可以是物理距离（比如每个节点的 x,y 坐标）或其他使节点相似的东西。
每个节点最多可以连接到 N 个其他节点，其中 N 很小——比如 6。
如何构建一个完全连接的图（例如，我可以在图边之后的任意两个节点之间移动），同时最小化所有图节点之间的总距离。
那就是我不想要一个图，其中任何遍历的总距离最小化，但对于任何节点，所有链接到该节点的总距离最小化。
我不需要绝对最小值——因为我认为这可能是 NP 完整的——而是一种相对有效的方法来获得接近真正绝对最小值的图形。
您可以使用内核仅为特定截止距离下的节点创建边。
如果您想要非加权边缘您可以简单地使用基本截止开始。如果 d(v1,v2) < R，则在 2 点之间添加一条边
您可以调整截止 R 以获得节点之间正确的平均边数。
如果你想要一个加权图，首选的内核通常是高斯内核，其中
K(x,y) = e^(-d(x,y)^2/d_0)
有一个截止以避开具有过低值的节点。d_0 是调整以获得最适合您的权重的参数。
在寻找参考资料时，我发现了这篇我没有提到的博客文章，但这似乎很容易解释，还有更多细节：http ://charlesmartin14.wordpress.com/2012/10/09/spectral-clustering/
此方法用于基于图形的半监督机器学习任务，例如在图像识别中，您可以标记对象的一小部分，并通过有效的标签传播来识别整个对象。
你可以在谷歌上搜索：半监督学习与图
我建议使用贪婪的启发式方法，在其中选择边，直到所有顶点都有 6 个邻居。例如，从最小生成树开始。然后，对于一些随机的顶点对，找到它们之间的最短路径，该路径最多使用一条未选择的边（在图的两个副本上使用 Dijkstra 算法，选择边，由未选择的边连接）。然后选择总距离减少最大的边。