如何找到捕获最大总成本的多个潜在独立的无向图中顶点的最小集合

我有一大组表示一组图形的顶点/节点。请注意，这个完整集合中可能有许多独立的图。目标是在所有这些图上找到最小数量的顶点，这些顶点对应于这些选定顶点捕获的所有边上的最大权重总和。我在熊猫中有邻接矩阵，我正在使用networkx。如何找到捕获最大总成本的多个潜在独立的无向图中顶点的最小集合

以下是三个列的示例数据框，其中Number_Of_Trips是权重。为了将两个度量合并在一起，我可以提供node = 10 *行程的权重。即旅行的最大化＃ - 10个* NumberOfNodes

Number_Of_Trips dropoff_gh7 pickup_gh7 
0 304 9tbqhsx 9tbqj4g 
1 271 9tbqj4f 9tbqhsx 
2 263 9tbqt4s 9tbqhsx 
3 258 9tbqdye 9tbqdsr 
4 256 9tbqhgh 9tbqjfv 
5 236 9tbqhsw 9tbqj4g 
6 233 9tbqt4g 9tbqv03 
7 229 9tbqhsx 9tbqj4c 
8 218 9tbqy3f 9tbqt4s 
9 213 9tbq5v4 9tbqh41 
10 210 9tbqhgh 9tbqhsw 
11 192 9tbqhgh 9tbqje4 
12 186 9tbqy3f 9tbqt4g 
13 184 9tbqhgh 9tbqj4z 
14 183 9tbqe3d 9tbqe9e 
15 170 9tbq3xn 9tbq39w 
16 167 9tbq5bw 9tbqht6 
17 163 9tbqhsx 9tbqh0x 
18 162 9tbqdk1 9tbq7p2 
19 160 9tbqsch 9tbqt4s 

x = nx.from_pandas_dataframe(df,"dropoff_gh7","pickup_gh7","Number_Of_Trips") 
graphs = list(nx.connected_component_subgraphs(x))

来源

2017-10-18 SriK

您引用了相互矛盾的评估标准;我们需要你来定义这个问题。我们还需要您描述您的研究，以及可用算法如何不能满足您的需求。如果您的成本函数表现得很好，我会认为Dijkstra的算法可以随时适应您的事业。 – Prune

请包括一个样本数据集以及您迄今为止所尝试的数据，然后我们可能会提供帮助。阅读关于如何创建[最小，完整和可验证的示例]的帮助（https://stackoverflow.com/help/mcve）。 –

@JoelOstblom - 我补充说明。此外，为了回答Prune的问题，我似乎找不到任何算法，因为它具有最大总权重但节点数最少的子图。 Djikstra需要一个特定的源和目的地，并且生成树实施一条通过所有节点的路径。这些不符合我的需要。因此我的问题。 – SriK

请注意，问题的一个警告是，您可以在图中有多个独立的子图，这可能是解决方案。该解决方案的关键直觉是子图的最可能的候选者是彼此共享许多边的顶点。事实证明，这正是在图中查看Cliques时所评估的内容。因此，该解决方案只是简单地提取所有派系，然后按照派系中顶点表示的权重总数排序它们 - 顶点的数量*顶点的成本。这可以使用NetworkX快速建立原型。

G = nx.from_pandas_dataframe(df, "dropoff_gh7", "pickup_gh7", ['num_of_trips']) 
# Find all the cliques in the graph (not only maximal but all sub cliques as well. Note that clique finding is NP complete so this may take a long time if your graph is > 100k of edges or more. For <100k edges, this took within 5 mins on a 16GB macbook pro 3GHz machine. 
cliques = nx.find_cliques(G) 
clique_trips = [np.array([c,G.subgraph(c).size(weight="num_of_trips")]) for c in cliques] 
df_cliques = pd.DataFrame(clique_trips,columns=["vertices","num_of_trips"]) 
df_cliques["num_vertices"] = df_cliques.apply(lambda x:len(x[0]), axis=1) 
df_cliques["weighted_trips"] = df_cliques.apply(lambda row: 
    row["num_of_trips"] - row["num_vertices"]*COST_PER_NODE, axis=1) 
df_cliques = df_cliques.sort_values("weighted_trips")[::-1] 
df_cliques.head() 
# The top N cliques can then be aggregated into a set to identify the precise vertices that are most valuable.

来源

2017-10-31 17:28:42 SriK

这里的逻辑的轮廓。

创建一个集群结构。 A 集群具有成员节点，内部值（总内部行程）和到其他集群的边。

从单个群集中的每个节点开始。将所有这些集群放入“未完成”列表中。你现在要遍历这个列表，合并你发现优势的集群。选择列表中的第一个群集。

迭代：对于该群集的每个边缘，检查合并该边缘另一端的群集的净值：内部行程+边缘行程 - 10 *群集总数（节点数量）。

合并：连接两个群集的成员节点列表。添加它们的内部值和它们之间的边缘值。调整节点人口（如果您还没有在其他地方进行会计核算）。将边缘列表合并到其他集群。从“未完成”列表中删除合并的集群。

继续使用“Kleene Closure”过程，直到您没有更多的节点增加收益。将此结果集群移至“完成”列表。选择“未完成”列表中的下一个节点，并重复迭代&合并循环，直到“完成”列表为空。

现在，将整个“完成”列表移回“未完成”列表并重复该过程，直到完成与的通过，否进一步合并。

这是足够详细的代码进程吗？

来源

2017-10-20 21:13:24 Prune

我确定你的方法可能会工作，虽然我没有能够将它转换为代码，因为我没有遵循它的全部。尽管如此，我发布了一个不是最优的解决方案，但是提供了基于派系分析的相当不错的结果。尽管感谢您的输入。感谢指导！如果你有想法的任何代码，看到它也会很棒。 – SriK

如何找到捕获最大总成本的多个潜在独立的无向图中顶点的最小集合

回答

相关问题