python - 随机加权子图

Question

我正在使用跨语言语义图，例如看到的 here对于嘴。

我希望能够绘制该图并提取n个加权随机子图，其中权重由链接权重确定。也就是说，对于随机子图，将优先选择权重较高的连接节点。我在谷歌上进行了徒劳的搜索，主要是获取有关创建具有特定子图属性的完全随机图的软件和论文。

盯着 networkx 的文档并没有给我带来任何可能的帮助，但不幸的是，我是这个领域的涉足者，可能由于术语上的无知而遗漏了一些东西。

我正在寻找有关正确术语的建议来找到这个(如果我遗漏了一些明显的东西)，或者指向可以完成此任务的工具(甚至是另一种编程语言)。

Answer 1

这是算法的粗略草图。

1. 将图表转换为距离矩阵。
2. 使用普通 Python random 函数随机选择一个单元格 (v_0)。
3. 假设该图是无向的，请抓取包含 v_0 的列或行(它是对称的，因此它们是相同的)。
4. 使用 weighted choice function捕获一个可能远离该行初始顶点的顶点。由于权重是顶点之间的距离，这意味着将行从链接的代码段输入到 weighted_pick 中，其中 picks = 1。令该顶点为 v_1。
5. 将包含 v_0 的行归零，这样它就不会再被选中。
6. 重复 m/n 次，以 v_1 作为新的起始顶点开始下一次迭代。将您刚刚选择的顶点保存在子图中。
7. 重复整个过程 n 次以获取子图的完整列表。

这并不完全符合您的要求 - 因为它选择长路径而不是粗边缘 - 但这很容易修复。如果 v_1 和 v_2 之间没有任何边，您可以调整距离矩阵，使 d(v_1, v_2) = 0。然后你只会得到连接的子图，这似乎就是你想要的。

这应该在 O(|V|) * t 时间内运行，其中 t 是加权选择函数的时间复杂度。不幸的是，numpy没有说明searchsorted的时间复杂度是多少，但我猜它会是O(log n) ，因为它正在插入已排序的列表。这将为您提供 O(|V| log |V|) 时间来完成整个过程，这非常好。我猜想，如果您的数据一开始就采用良好的格式，您可以用大约 100 行 Python 来完成它。