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

简答

你想做

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]

Answer 2

考虑到您有一个只有 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。然后我们将选择一个随机的孤立节点（从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)

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

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