如何将无向图的节点划分为k个集合 [英] how to partition the nodes of an undirected graph into k sets

问题描述

我有一个无向图G =（V，E），其中每个顶点表示一个大型网络中的一台路由器。每个边代表从一个路由器到另一个路由器的网络跳跃，因此所有边都具有相同的权重。我希望将这个路由器网络划分为3个或k个不同的集合，这些集合通过Hop计数聚集在一起。

动机：
这个想法是以复制这三组中的每一组中包含的路由器中的一些数据。这样，每当网络图中的节点（或客户端或其他）请求某个数据项时，我就可以在3个集中搜索它并从每个集合中获得一个负责任的节点（一个缓存了特定数据的节点） 。然后，我会选择距离请求节点最小跳数的节点，并继续进行算法和测试。

缓存分配和请求响应不在此问题的范围内。我只需要一种方法将网络划分为3组，以便我可以对其执行上述操作。

在这种情况下可以使用哪种聚类算法。我在图中有近9000个节点，我希望每个节点有3组〜3000个节点。

在图表情况下，可以使用基于最小生成树的聚类方法。

常规算法如下：

1. 查找图的最小生成树。
   
2. 删除生成树中的 k - 1 最长边，其中 k 是所需的簇数。

然而，只有当边缘长度（或重量）不同时。在长度相等的情况下，每个生成树都是最小的，所以这样做效果不好。然而，稍微思考一下，我发现使用BFS的另一种算法。

算法：

  1。对于i = 1..k do //对于每个群集
 2.选择群集i中的节点数量n 
 3.选择任意节点n 
 4.运行广度优先搜索（BFS），直到N 
 5.将由BFS点击的前N个节点（包括n）分配给第i个集群
 6.将这些节点（和入射边）从graph 
 7. done 
  

这个算法（结果）很大程度上取决于步骤3，即选择群集的根节点。为了简单起见，我选择了一个任意节点，但它可能更复杂。最好的节点是那些在图的结尾的节点。您可以找到图形的中心（一个节点的路径长度与所有其他节点的总和最小），然后使用该中心的节点。

真正的问题是你的边缘是平等的（如果我理解你的问题陈述的好处），而你没有关于节点的信息（即它们的坐标 - 那么你可以使用例如k-means）。

I have an undirected graph G=(V,E) where each vertex represents a router in a large network. Each edge represents a network hop from one router to the other therefore, all edges have the same weight. I wish to partition this network of routers into 3 or k different sets clustered by Hop count.

Motivation: The idea is to replicate some data in routers contained in each of these 3 sets. This is so that whenever a node( or client or whatever) in the network graph requests for a certain data item, I can search for it in the 3 sets and get a responsible node(one that has cached that particular data) from each set. Then I'd select the node which is at the minimum hop count away from the requesting node and continue with my algorithms and tests.

The cache distribution and request response are not in the scope of this question. I just need a way to partition the network into 3 sets so that I can perform the above operations on it.

Which clustering algorithm could be used in such a scenario. I have almost 9000 nodes in the graph and I wish to get 3 sets of ~3000 nodes each

解决方案

In the graph case, a clustering method based on minimum spanning trees can be used.

The regular algorithm is the following:

1. Find the minimum spanning tree of the graph.
2. Remove the k - 1 longest edges in the spanning tree, where k is the desired number of clusters.

However, this works only if the edges differ in length (or weight). In the case of edges of equal length, every spanning tree is a minimum one so this would not work well. However, putting a little thinking into it, a different algorithm came to my mind which uses BFS.

The algorithm:

1. for i = 1..k do // for each cluster
2.     choose the number of nodes N in cluster i
3.     choose an arbitrary node n
4.     run breadth-first search (BFS) from n until N
5.     assign the first N nodes (incl. n) tapped by the BFS to the i-th cluster
6.     remove these nodes (and the incident edges) from the graph
7. done

This algorithm (the results) hugely depends on how step 3, i.e. choosing the "root" node of a cluster, is implemented. For the sake of simplicity I choose an arbitrary node, but it could be more sophisticated. The best nodes are those that are the at the "end" of the graph. You could find a center of the graph (a node that has the lowest sum of lengths of paths to all other nodes) and then use the nodes that are the furthes from this center.

The real issue is that your edges are equal (if I understood your problem statement well) and you have no information about the nodes (i.e. their coordinates - then you could use e.g. k-means).

这篇关于如何将无向图的节点划分为k个集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！