查找并计算网络中隔离和半隔离节点的数量

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

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

我的理论尝试

它看起来像这个问题被寻址的洪水填充算法，这说明这里。但是，我想知道如何可以简单地计算巨型组件中的节点数，然后从在第 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 随机图，将孤立的节点着色为蓝色：

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