python - 如何从未连接的图中随机选择两个节点（节点对），Python，networkx

Question

我想从图中提取两个节点，但问题是它们不应该连接，即它们之间不存在直接边。我知道我可以使用“random.choice(g.edges())”获得随机边，但这会给我连接的随机节点。我想要一对未连接的节点（一对未连接的边）。帮帮我...谢谢

Answer 1

Simple! :)

Grab a random node - then pick a random node from the list of nodes excluding neighbours and itself. Code to illustrate is below. :)

import networkx as nx
from random import choice

# Consider this graph
#
#     3
#     |
# 2 - 1 - 5 - 6
#     | 
#     4

g = nx.Graph()
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(1,4)
g.add_edge(1,5)
g.add_edge(5,6)

first_node = choice(g.nodes())                  # pick a random node
possible_nodes = set(g.nodes())
neighbours = g.neighbors(first_node) + [first_node]
possible_nodes.difference_update(neighbours)    # remove the first node and all its neighbours from the candidates
second_node = choice(list(possible_nodes))      # pick second node      

print first_node, second_node

Answer 2

到目前为止，这里提出的解决方案都不会对非边缘 (v1,v2) 进行均匀采样。考虑具有 4 个节点和 2 条边的示例图：

1 —— 2
|
3    4

有 4 个非边可供选择：(1,4),(2,3),(2,4),(3,4)。使用 Maria 或 Philip 的方法，从所有 4 个顶点中随机选择第一个顶点，然后从受限顶点集中选择第二个顶点，以免创建任何边（或自环），将为每个非-要选择的边缘：

p(1,4) = 1/4 * 1 + 1/4 * 1/3 = 8/24

p(2,3) = 1/4 * 1/2 + 1/4 * 1/2 = 6/24

p(3,4) = p(2,4) = 1/4 * 1/2 + 1/4 * 1/3 = 5/24

所以程序不统一。

这意味着如果您想要均匀采样的非边，则必须选择不受限制的两个顶点并在它们形成现有边（或相等）时拒绝样本（两个顶点）。在 NetworkX 中：

v1 = np.random.choice(G.nodes())
v2 = np.random.choice(G.nodes())

while G.has(edge(v1,v2)) or v1==v2:
  v1 = np.random.choice(G.nodes())
  v2 = np.random.choice(G.nodes())

Answer 3

我不知道那个图书馆，但我猜你可以做以下事情：

  n1 = random.choice(g.nodes())
  n2 = random.choice(g.nodes()) 
  while (n1 == n2 or any of the edges of n1 lead to n2):
    n2 = random.choice(g.nodes())
  enjoy(yourNodes)

干杯

Answer 4

If the graph is small, you can collect nx.non_edges() into an np.array and random.choice from it:

non_edges = np.array(nx.non_edges(graph))

sample_num = 10000
sample = non_edges[np.random.choice(len(non_edges), sample_num, replace=False)]

Beware that non_edges() itself returns you the generator, not the actual list. But if you turn it into an np.array you acutally collects all the items in the generator. If your graph is large and sparse, this may raise a memory error, but for small graphs it would the most straightforward way to do it.