在网络图中获取断开连接的节点对？

Question

这是我的数据集：

4095    546
3213    2059 
4897    2661 
...
3586    2583
3437    3317
3364    1216

每条线都是一对节点，它们之间有一条边。整个数据集构建一个图形。但我想获得许多彼此断开连接的节点对。如何从数据集中获得 1000（或更多）个这样的节点对？如：

2761    2788
4777    3365
3631    3553
...
3717    4074
3013    2225

每条线都是一对没有边的节点。

Answer 1

只需进行 BFS 或 DFS 即可在 O(|E|) 时间内获得每个连通分量的大小。然后，一旦有了组件大小，就可以轻松获得断开连接的节点数：它是每对大小的乘积之和。

例如。如果您的图形有 3 个连通分量，大小为：50、20、100。那么断开连接的节点对数为：50*20 + 50*100 + 20*100 = 8000.

如果你想实际输出断开连接的对而不是仅仅计算它们，你可能应该使用 union-find 然后遍历所有节点对并在它们不在同一组件中时输出它们。

Answer 2

请参阅编辑下的部分！

我认为其他选项更通用，从编程的角度来看可能更好。我只是快速想到如何使用 numpy 以非常简单的方式获取列表。

首先创建邻接矩阵，您的节点列表是一个数组：

    import numpy as np
    node_list= np.random.randint(10 , size=(10, 2))
    A = np.zeros((np.max(node_list) + 1, np.max(node_list) + 1)) # + 1 to account for zero indexing
    A[node_list[:, 0],  node_list[:, 1]] = 1 # set connected nodes to 1
    x, y = np.where(A == 0) # Find disconnected nodes
    disconnected_list = np.vstack([x, y]).T # The final list of disconnected nodes

虽然我不知道这将如何与真正的大型网络一起工作。

编辑：上面的解决方案是我想得太快了。到目前为止，上面的解决方案提供了节点之间缺失的边，而不是断开连接的节点（在有向图的情况下）。此外，disconnected_list 包含每个节点两次。这是第二个棘手的解决方案：

    import numpy as np
    node_list= np.random.randint(10 , size=(10, 2))
    A = np.zeros((np.max(node_list) + 1, np.max(node_list) + 1)) # + 1 to account for zero indexing
    A[node_list[:, 0], node_list[:, 1]] = 1 # set connected nodes to 1 
    A[node_list[:, 1], node_list[:, 0]] = 1 # Make the graph symmetric
    A = A + np.triu(np.ones(A.shape)) # Add ones to the upper triangular
    # matrix, so they are not considered in np.where (set k if you want to consider the diagonal)
    x, y = np.where(A == 0) # Find disconnected nodes
    disconnected_list = np.vstack([x, y]).T # The final list of disconnected nodes

在网络图中获取断开连接的节点对？

Get disconnected pairs of nodes in the network graph?

matlab

graph

social-networking

igraph

python-3.x