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.

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

谢谢。

编辑：我刚刚意识到我需要为第三个参数指定最小数量的 edges/probability。

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

感谢您的帮助！

Answer 1

考虑到您有一个只有 10 条边的 {5, 6} 二分图，您的图很可能会断开连接（它非常稀疏，甚至很可能有孤立的节点）。

import networkx as nx
import random

random.seed(0)

B = nx.bipartite.gnmk_random_graph(5,6,10)
isolated_nodes = set(B.nodes())
for (u, v) in B.edges():
  isolated_nodes -= {u}
  isolated_nodes -= {v}
print(isolated_nodes)

将向您显示 id=1 的节点是孤立的。你可以做的是让你的图连接起来，只保留它最大的连接组件：

import networkx as nx
import random

random.seed(0)

B = nx.bipartite.gnmk_random_graph(5,6,11)
components = sorted(nx.connected_components(B), key=len, reverse=True)
largest_component = components[0]
C = B.subgraph(largest_component)

这里只会删除节点 1（一个孤立的节点）。

现在唯一的问题是"how random this new graph is"。换句话说，它是否以相等的概率选择具有 5-6 个节点和 10 个边的随机连接的二分图集合中的任何图。现在我不确定，但我认为它看起来不错。

当然你的建议（选择一个图直到它连接起来）是可以的，但它可能很昂贵（当然取决于 3 个参数）。

编辑我很笨，这不行，因为新图表没有正确的 nodes/edges 数量。但是应该有一个更好的解决方案，而不是仅仅重试直到你得到一个好的图表。嗯，这很有趣......

第二次编辑也许这个answer可以帮助找到解决这个问题的好方法。

第三次编辑和一个建议

正如您在我链接的问题中注意到的那样，接受的答案并不是真正正确的，因为生成的图不是 select 在预期图集中随机均匀地编辑。我们可以在这里做一些类似的事情以获得第一个像样的解决方案。这个想法是首先通过迭代选择孤立节点并将它们连接到二分图的另一侧来创建具有最少边数的连接二分图。为此，我们将创建两个集合 N 和 M，创建从 N 到 M 的第一条边。然后我们将选择一个随机的孤立节点（来自 N 或 M）并将其连接到另一侧的随机非孤立节点。一旦我们没有更多的孤立节点，我们将恰好有 n+m-1 条边，因此我们需要向图中添加 k-(n+m-1) 条额外的边以匹配原始约束。

这是该算法对应的代码

import networkx as nx
import random

random.seed(0)

def biased_random_connected_bipartite(n, m, k):
  G = nx.Graph()

  # These will be the two components of the bipartite graph
  N = set(range(n)) 
  M = set(range(n, n+m))
  G.add_nodes_from(N)
  G.add_nodes_from(M)

  # Create a first random edge 
  u = random.choice(tuple(N))
  v = random.choice(tuple(M))
  G.add_edge(u, v)

  isolated_N = set(N-{u})
  isolated_M = set(M-{v})
  while isolated_N and isolated_M:
    # Pick any isolated node:
    isolated_nodes = isolated_N|isolated_M
    u = random.choice(tuple(isolated_nodes))

    # And connected it to the existing connected graph:
    if u in isolated_N:
      v = random.choice(tuple(M-isolated_M))
      G.add_edge(u, v)
      isolated_N.remove(u)
    else:
      v = random.choice(tuple(N-isolated_N))
      G.add_edge(u, v)
      isolated_M.remove(u)

  # Add missing edges
  for i in range(k-len(G.edges())):
    u = random.choice(tuple(N))
    v = random.choice(tuple(M))
    G.add_edge(u, v)

  return G

B = biased_random_connected_bipartite(5, 6, 11)

但我再说一遍，这个图在所有可能的二分图的集合中并不是select均匀随机的（我们在 n、m 和k).正如我在另一个 post 中所说的那样，该图将倾向于具有比其他节点更高度的一些节点。这是因为我们将孤立的节点一个一个地连接到连接的组件上，因此在此过程中较早添加的节点将倾向于吸引更多的节点（优先连接）。我问 question on cstheory 看看有没有什么好主意。

edit 我添加了另一种解决方案而不是此处介绍的解决方案，它好一点但仍然不是一个好方案。

Answer 2

简答

你想做

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 也是一个完全合法的分区。 return应该选哪一个？这是模棱两可的。该算法明确拒绝做出选择。相反，它会给你一个错误。

怎么办？如果断开连接，您可以丢弃 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]

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

NetworkX - generating a random connected bipartite graph

python

bipartite