为什么 LightGraphs.betweenness_centrality() 运行 这么长
Why does LightGraphs.betweenness_centrality() run so long
当我尝试使用 julia 的 LightGraphs 包计算我的 SimpleWeightedGraph 的 betweenness_centrality() 时，它会无限期地运行。它不断增加它的 RAM 使用，直到在某个时候它崩溃而没有错误消息。我的图表有问题吗？或者找到此问题原因的最佳方法是什么？
我的图表不是由 LightGraphs 生成的，而是由另一个库 FlashWeave 生成的。我不知道这是否重要...
未加权的 SimpleGraph 或我在 LightGraphs 中创建的加权图不会出现此问题...
using BenchmarkTools
using FlashWeave
using ParserCombinator
using GraphIO.GML
using LightGraphs
using SimpleWeightedGraphs
data_path = /path/to/my/data
netw_results = FlashWeave.learn_network(data_path,
sensitive = true,
heterogeneous = false)
dummy_weighted_graph = SimpleWeightedGraph(smallgraph(:house))
# {5, 6} undirected simple Int64 graph with Float64 weights
my_weighted_graph = graph(netw_results_no_meta)
# {6558, 8484} undirected simple Int64 graph with Float64 weights
# load_graph() only loads unweighted graphs
save_network(gml_no_meta_path, netw_results_no_meta)
my_unweighted_graph = loadgraph(gml_no_meta_path, GMLFormat())
# {6558, 8484} undirected simple Int64 graph
@time betweenness_centrality(my_unweighted_graph)
# 12.467820 seconds (45.30 M allocations: 7.531 GiB, 2.73% gc time)
@time betweenness_centrality(dummy_weighted_graph)
# 0.271050 seconds (282.41 k allocations: 13.838 MiB)
@time betweenness_centrality(my_weighted_graph)
# steadily increasing RAM usage until RAM is full and julia crashes.
您检查过您的图表是否包含负权重吗？ LightGraphs.betweenness_centrality() 使用 Dijkstra 的最短路径计算介数中心性，因此期望非负权重。
LightGraphs.betweenness_centrality() 不检查 illegal/nonsensical 图表。这就是它没有抛出错误的原因。该问题已报告 here，但现在，如果您不确定它们是否合法，请检查您自己的图表。
A = Float64[
0 4 2
4 0 1
2 1 0
]
B = Float64[
0 4 2
4 0 -1
2 -1 0
]
graph_a = SimpleWeightedGraph(A)
# {3, 3} undirected simple Int64 graph with Float64 weights
graph_b = SimpleWeightedGraph(B)
# {3, 3} undirected simple Int64 graph with Float64 weights
minimum(graph_a.weights)
# 0.00
minimum(graph_b.weights)
# -1.00
@time betweenness_centrality(graph_a)
# 0.321796 seconds (726.13 k allocations: 36.906 MiB, 3.53% gc time)
# Vector{Float64} with 3 elements
# 0.00
# 0.00
# 1.00
@time betweenness_centrality(graph_b)
# reproduces your problem.
在此问题发布之前，https://github.com/JuliaGraphs/LightGraphs.jl/issues/1531 已经回答了这个问题。正如决议中提到的，您在图表中有负权重。 Dijkstra 不处理负权重的图，LightGraphs betweenness centrality 使用 Dijkstra。
当我尝试使用 julia 的 LightGraphs 包计算我的 SimpleWeightedGraph 的 betweenness_centrality() 时，它会无限期地运行。它不断增加它的 RAM 使用，直到在某个时候它崩溃而没有错误消息。我的图表有问题吗？或者找到此问题原因的最佳方法是什么？
我的图表不是由 LightGraphs 生成的，而是由另一个库 FlashWeave 生成的。我不知道这是否重要...
未加权的 SimpleGraph 或我在 LightGraphs 中创建的加权图不会出现此问题...
using BenchmarkTools
using FlashWeave
using ParserCombinator
using GraphIO.GML
using LightGraphs
using SimpleWeightedGraphs
data_path = /path/to/my/data
netw_results = FlashWeave.learn_network(data_path,
sensitive = true,
heterogeneous = false)
dummy_weighted_graph = SimpleWeightedGraph(smallgraph(:house))
# {5, 6} undirected simple Int64 graph with Float64 weights
my_weighted_graph = graph(netw_results_no_meta)
# {6558, 8484} undirected simple Int64 graph with Float64 weights
# load_graph() only loads unweighted graphs
save_network(gml_no_meta_path, netw_results_no_meta)
my_unweighted_graph = loadgraph(gml_no_meta_path, GMLFormat())
# {6558, 8484} undirected simple Int64 graph
@time betweenness_centrality(my_unweighted_graph)
# 12.467820 seconds (45.30 M allocations: 7.531 GiB, 2.73% gc time)
@time betweenness_centrality(dummy_weighted_graph)
# 0.271050 seconds (282.41 k allocations: 13.838 MiB)
@time betweenness_centrality(my_weighted_graph)
# steadily increasing RAM usage until RAM is full and julia crashes.
您检查过您的图表是否包含负权重吗？ LightGraphs.betweenness_centrality() 使用 Dijkstra 的最短路径计算介数中心性，因此期望非负权重。
LightGraphs.betweenness_centrality() 不检查 illegal/nonsensical 图表。这就是它没有抛出错误的原因。该问题已报告 here，但现在，如果您不确定它们是否合法，请检查您自己的图表。
A = Float64[
0 4 2
4 0 1
2 1 0
]
B = Float64[
0 4 2
4 0 -1
2 -1 0
]
graph_a = SimpleWeightedGraph(A)
# {3, 3} undirected simple Int64 graph with Float64 weights
graph_b = SimpleWeightedGraph(B)
# {3, 3} undirected simple Int64 graph with Float64 weights
minimum(graph_a.weights)
# 0.00
minimum(graph_b.weights)
# -1.00
@time betweenness_centrality(graph_a)
# 0.321796 seconds (726.13 k allocations: 36.906 MiB, 3.53% gc time)
# Vector{Float64} with 3 elements
# 0.00
# 0.00
# 1.00
@time betweenness_centrality(graph_b)
# reproduces your problem.
在此问题发布之前，https://github.com/JuliaGraphs/LightGraphs.jl/issues/1531 已经回答了这个问题。正如决议中提到的，您在图表中有负权重。 Dijkstra 不处理负权重的图，LightGraphs betweenness centrality 使用 Dijkstra。