如何估计 StructuralHoles 的执行时间

Question

我有一个 UndirectedSparseGraph g，有 5000 个节点和 200000 个链接。我正在尝试在我的 4GB macbook air 上使用 运行 StructuralHoles()。有没有办法估计完成任务需要多长时间？

Answer 1

首先，我要提到 StructuralHoles class 有几种不同的 public 方法，因此您需要指定要计算的度量：http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/metrics/StructuralHoles.html

一旦你弄清楚了这一点，有几种方法可以进行这种估算。

(1) 查看源代码（或参考论文），了解算法的时间复杂度。这将为您了解所需时间如何随图形大小而变化提供基础。

(2) 提取子图（例如，节点大小为 50、100 和 500）并测量算法对每个子图花费的时间。然后进行推断，最好使用 (1) 中的分析（并考虑每个子图中的边数）。

(3) 在现有代码中添加一些日志记录，以便您可以确定处理一批 N 个节点（或 M 条边）需要多长时间，然后 运行 它。