查找並計算網絡中隔離和半隔離節點的數量

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 

但你會如何修改這些行，以使他們找到孤立的節點組，以及像那些在右側畫面突出？

MY理論未遂

它看起來像這個問題是由顏色填充算法，這是解釋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()