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

Question

我正在与经历许多破坏性事件的网络合作。因此，许多节点由于给定事件而失败。因此，从左边的图像到右边的图像之间存在过渡:

我的问题:如何找到断开连接的子图，即使它们只包含 1 个节点？我的目的是计数它们并呈现失败，因为在我的研究中这就是适用于它们的内容。我所说的半隔离节点是指隔离节点组，但彼此相连。

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

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

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

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

然后您可以找到最大的组件，并获得“孤立”节点的计数:

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()