Computes local node connectivity for nodes s and t.
Local node connectivity for two non adjacent nodes s and t is the minimum number of nodes that must be removed (along with their incident edges) to disconnect them.
This is a flow based implementation of node connectivity. We compute the maximum flow on an auxiliary digraph build from the original input graph (see below for details). This is equal to the local node connectivity because the value of a maximum s-t-flow is equal to the capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [R201] .
Parameters : | G : NetworkX graph
s : node
t : node
aux_digraph : NetworkX DiGraph (default=None)
mapping : dict (default=None)
|
---|---|
Returns : | K : integer
|
See also
node_connectivity, all_pairs_node_connectivity_matrix, local_edge_connectivity, edge_connectivity, max_flow, ford_fulkerson
Notes
This is a flow based implementation of node connectivity. We compute the maximum flow using the Ford and Fulkerson algorithm on an auxiliary digraph build from the original input graph:
For an undirected graph G having n nodes and m edges we derive a directed graph D with 2n nodes and 2m+n arcs by replacing each original node v with two nodes v_A, v_B linked by an (internal) arc in D. Then for each edge (u, v) in G we add two arcs (u_B, v_A) and (v_B, u_A) in D. Finally we set the attribute capacity = 1 for each arc in D [R201] .
For a directed graph G having n nodes and m arcs we derive a directed graph D with 2n nodes and m+n arcs by replacing each original node v with two nodes v_A, v_B linked by an (internal) arc (v_A, v_B) in D. Then for each arc (u,v) in G we add one arc (u_B,v_A) in D. Finally we set the attribute capacity = 1 for each arc in D.
This is equal to the local node connectivity because the value of a maximum s-t-flow is equal to the capacity of a minimum s-t-cut (Ford and Fulkerson theorem).
References
[R201] | (1, 2, 3) Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and Erlebach, ‘Network Analysis: Methodological Foundations’, Lecture Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf |
Examples
>>> # Platonic icosahedral graph has node connectivity 5
>>> # for each non adjacent node pair
>>> G = nx.icosahedral_graph()
>>> nx.local_node_connectivity(G,0,6)
5