获取网络中所有断开连接的节点对

Question

我已经使用igraph（无向）编码了一个网络，并且我想获得网络中未连接的节点对的列表。

翻阅igraph的文档（Python），我还没有找到这样做的方法。我必须手动执行此操作吗？

一个相关的问题：给定网络中的任何节点对，如何使用igraph找到这两个节点的公共邻居列表？再次看来，igraph似乎没有这种方法。

Answer 1

重新对第一个问题（上市断开连接的节点对）：是的，你必须手动做到这一点，但它是相当容易：

from itertools import product 

all_nodes = set(range(g.vcount()) 
disconnected_pairs = [list(product(cluster, all_nodes.difference(cluster))) \ 
         for cluster in g.clusters()] 

但要注意，这可能是一个相当大的列表，如果你的图形很大，由很多不连通的组件组成。

再第二个问题（上市常见的邻居）：同样，你必须手动做到这一点，但只需要在Python一个交集操作：

set(g.neighbors(v1)).intersection(set(g.neighbors(v2))) 

如果你发现你需要做到这一点对于许多节点对，你应该创建邻居首先设置：

neighbor_sets = [set(neis) for neis in g.get_adjlist()] 

然后，你可以简单地写neighbor_sets[i]而不是set(g.neighbors(i))。