python - NetworkX - 生成随机连接的二分图

Question

我正在使用 NetworkX 使用 nx.bipartite.random_graph 或 nx.bipartite.gnmk_random_graph 生成二分图，如下所示:

B = bipartite.gnmk_random_graph(5,6,10)
bottom_nodes, top_nodes = bipartite.sets(B)

但是，我得到一个错误:

networkx.exception.AmbiguousSolution: Disconnected graph: Ambiguous solution for bipartite sets.

它只是一行，所以我不确定我怎么会做错以及为什么他们的包会返回(我假设是)无效的二分图。

谢谢。

编辑:我刚刚意识到我需要为第三个参数指定最小边数/概率。

例如bipartite.random_graph(5,6,0.6) 并使 p>0.5 消除错误。同样，bipartite.gnmk_random_graph(5,6,11) 其中 k>n+m。我没有意识到是这种情况，因为我假设如果边的数量少于连接每个顶点所需的数量，那么只会有一些 float 顶点。

感谢您的帮助!

Answer 1

简短回答

你想做什么

B = bipartite.gnmk_random_graph(5,6,10)
top = [node for node in B.nodes() if B.node[node]['bipartite']==0]
bottom = [node for node in B.nodes() if B.node[node]['bipartite']==1]

---

解释

所以当你生成这个二分图的时候，它很可能是断线的。假设它有 2 个独立的组件 X 和 Y。这两个组件都是双向的。

bipartite.sets(B) 应该确定哪些集合是 B 的两个分区。但它会遇到麻烦。

为什么？

X 可以分成两个分区 X_1 和 X_2 而 Y 可以分成 Y_1 和 Y_2。 B 呢？让 top = X_1 + Y_1 和 bottom = X_2 + Y_2。这是一个完全合法的分区。但是 top = X_1+Y_2 和 bottom = X_2+Y_1 也是一个完全合法的分区。它应该返回哪一个？这是模棱两可的。该算法明确拒绝做出选择。相反，它会给你一个错误。

要做什么？如果断开连接，您可以丢弃 B 并重试。但是您正在使用 B 做一些对的事情吗？只关注连通图是否合理？也许，也许不是。这是你需要弄清楚的事情。但是，如果因为断开连接的图形不方便，那么将您的注意力仅限于连接图形是不合理的。你似乎经常遇到这个错误，所以很大一部分图表是断开的——你扔掉了很大一部分案例。看起来这可能会使您所做的任何事情的最终结果产生偏差。 (类似地，如果你采取措施连接你的网络，你将不再从原始分布中获得随机图，因为你已经确保它们没有断开连接，现在更糟的是 - 你可能不会从连接图)。

那么什么是更好的选择呢？查看源代码后，我发现此方法没有按应有的方式记录。事实证明，对于

B = bipartite.gnmk_random_graph(5,6,10)

节点 0 到 4(前五个)在顶部，节点 5 到 10(接下来的 6 个)在底部。

或者，您可以直接从图 B 中编码的数据中获取它(文档中未提及)。尝试

B = bipartite.gnmk_random_graph(5,6,10)
B.nodes(data=True)
> NodeDataView({0: {'bipartite': 0}, 1: {'bipartite': 0}, 2: {'bipartite': 0}, 3: {'bipartite': 0}, 4: {'bipartite': 0}, 5: {'bipartite': 1}, 6: {'bipartite': 1}, 7: {'bipartite': 1}, 8: {'bipartite': 1}, 9: {'bipartite': 1}, 10: {'bipartite': 1}})

所以它实际上是在存储哪个节点在哪个部分。让我们使用它(和列表理解)

top = [node for node in B.nodes() if B.node[node]['bipartite']==0]
bottom = [node for node in B.nodes() if B.node[node]['bipartite']==1]