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.我没有意识到这种情况,因为我假设如果边缘的数量低于连接每个顶点所需的边数,那么就会有一些浮动顶点.

谢谢你的帮助!

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（一个孤立的节点）。

现在唯一的问题是“这个新图的随机性如何”。换句话说，它是否以相等的概率选择具有 5-6 个节点和 10 个边的随机连接二分图集合中的任何图。目前我还不确定，但我认为看起来还不错。

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

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

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

第三次编辑和建议

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

这是该算法对应的代码

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)

但我再说一遍，这个图并不是在所有可能的二分图集合中均匀随机选择的（带有我们在 n、m 和 k 上定义的约束）。正如我在另一篇文章中所说，该图往往会包含一些比其他节点具有更高度数的节点。这是因为我们将孤立的节点一一连接到连接的组件，因此在此过程中较早添加的节点往往会吸引更多的节点（优先连接）。我问了关于 cstheory 的问题，看看是否有什么好主意。

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