为什么LightGraphs.betweenness_centrality()运行这么长时间

Question

当我尝试计算 betweenness_centrality() 我的SimpleWeightedGraph和julia的LightGraphs包，它会无限期地运行。它不断增加它的RAM使用率，直到在某一时刻崩溃而没有出现错误消息。我的图表有问题吗？或者，找到这个问题原因的最好方法是什么？

我的图不是由LightGraphs生成的，而是由另一个库FlashWeave生成的。我不知道这是否重要..。

对于未加权的简单图或我在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.

Answer 1

你有没有检查你的图表是否包含负权重？

LightGraphs.betweenness_centrality() 使用Dijkstra的最短路径来计算中间中心性，因此期望非负权重。

LightGraphs.betweenness_centrality() 不检查非法/无意义的图形。这就是它没有抛出错误的原因。已报告该问题这里，但现在，如果您不确定它们是否合法，请检查您自己的图表。

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.

Answer 2

这个问题已经在

https://github.com/JuliaGraphs/LightGraphs.jl/issues/1531

，在这个问题张贴在这里之前。正如解决方案中所提到的，您在图形中具有负权重。Dijkstra不处理具有负权重的图，而LightGraphs居间中心性使用Dijkstra。