incremental_closeness_centrality#

incremental_closeness_centrality(G, edge, prev_cc=None, insertion=True, wf_improved=True)[source]#

Incremental closeness centrality for nodes.

Compute closeness centrality for nodes using level-based work filtering as described in Incremental Algorithms for Closeness Centrality by Sariyuce et al.

Level-based work filtering detects unnecessary updates to the closeness centrality and filters them out.

— From “Incremental Algorithms for Closeness Centrality”:

Theorem 1: Let \(G = (V, E)\) be a graph and u and v be two vertices in V such that there is no edge (u, v) in E. Let \(G' = (V, E \cup uv)\) Then \(cc[s] = cc'[s]\) if and only if \(\left|dG(s, u) - dG(s, v)\right| \leq 1\).

Where \(dG(u, v)\) denotes the length of the shortest path between two vertices u, v in a graph G, cc[s] is the closeness centrality for a vertex s in V, and cc’[s] is the closeness centrality for a vertex s in V, with the (u, v) edge added. —

We use Theorem 1 to filter out updates when adding or removing an edge. When adding an edge (u, v), we compute the shortest path lengths from all other nodes to u and to v before the node is added. When removing an edge, we compute the shortest path lengths after the edge is removed. Then we apply Theorem 1 to use previously computed closeness centrality for nodes where \(\left|dG(s, u) - dG(s, v)\right| \leq 1\). This works only for undirected, unweighted graphs; the distance argument is not supported.

Closeness centrality [1] of a node u is the reciprocal of the sum of the shortest path distances from u to all n-1 other nodes. Since the sum of distances depends on the number of nodes in the graph, closeness is normalized by the sum of minimum possible distances n-1.

\[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]

where d(v, u) is the shortest-path distance between v and u, and n is the number of nodes in the graph.

Notice that higher values of closeness indicate higher centrality.

Parameters:

Ggraph: A NetworkX graph
edgetuple: The modified edge (u, v) in the graph.
prev_ccdictionary: The previous closeness centrality for all nodes in the graph.
insertionbool, optional: If True (default) the edge was inserted, otherwise it was deleted from the graph.
wf_improvedbool, optional (default=True): If True, scale by the fraction of nodes reachable. This gives the Wasserman and Faust improved formula. For single component graphs it is the same as the original formula.

Returns:

nodesdictionary: Dictionary of nodes with closeness centrality as the value.