查找并计算网络中孤立和半孤立节点的数量

Question

我正在处理经历了一些中断事件 的网络。因此，许多节点由于给定事件而失败。因此从左边的图像到右边的图像之间有一个过渡：

我的问题：如何找到断开连接的子图，即使它们只包含 1 个节点？我的目的是 count 它们并将 渲染为失败 ，因为在我的研究中这就是适用于它们的。我所说的半隔离节点是指 组隔离节点，但相互连接。

我知道我可以找到这样的孤立节点：

def find_isolated_nodes(graph):
    """ returns a list of isolated nodes. """
    isolated = []
    for node in graph:
        if not graph[node]:
            isolated += node
    return isolated

但是您将如何修改这些行以使它们也能找到孤立的节点组，就像右侧图片中突出显示的那样？

我的理论尝试

Flood Fill 算法似乎解决了这个问题，here 对此进行了解释。但是，我想知道如何简单地计算巨型组件中的节点数，然后从在第 2 阶段仍处于活动状态的节点数中减去它。您将如何实现？

Answer 1

如果我理解正确，您正在寻找 "isolated" 个节点，这意味着节点不在图表的最大组成部分中。正如您所提到的，识别 "isolated" 节点的一种方法是查找所有不在最大组件中的节点。为此，您只需使用 networkx.connected_components 即可获取组件列表并按大小对它们进行排序：

components = list(nx.connected_components(G)) # list because it returns a generator
components.sort(key=len, reverse=True)

然后你可以找到最大的组件，并得到 "isolated" 个节点的计数：

largest = components.pop(0)
num_isolated = G.order() - len(largest)

我将所有这些放在一个例子中，我画了一个 Erdos-Renyi random graph，将孤立的节点着色为蓝色：

# Load modules and create a random graph
import networkx as nx, matplotlib.pyplot as plt
G = nx.gnp_random_graph(10, 0.15)

# Identify the largest component and the "isolated" nodes
components = list(nx.connected_components(G)) # list because it returns a generator
components.sort(key=len, reverse=True)
largest = components.pop(0)
isolated = set( g for cc in components for g in cc )

# Draw the graph
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos=pos, nodelist=largest, node_color='r')
nx.draw_networkx_nodes(G, pos=pos, nodelist=isolated, node_color='b')
nx.draw_networkx_edges(G, pos=pos)
plt.show()

查找并计算网络中孤立和半孤立节点的数量

Find and count the number of isolated and semi-isolated nodes in a network

python

count

components

networkx

connectivity