Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / closeness.py @ 5cef0f13

 1 ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Authors: Aric Hagberg ``` ```# Pieter Swart ``` ```# Sasha Gutfraind ``` ```# Dan Schult ``` ```""" ``` ```Closeness centrality measures. ``` ```""" ``` ```import functools ``` ```import networkx as nx ``` ```__all__ = ['closeness_centrality'] ``` ```def closeness_centrality(G, u=None, distance=None, wf_improved=True): ``` ``` r"""Compute closeness centrality for nodes. ``` ``` ``` ``` Closeness centrality _ of a node `u` is the reciprocal of the ``` ``` average shortest path distance to `u` over all `n-1` reachable nodes. ``` ``` ``` ``` .. math:: ``` ``` ``` ``` 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 that can reach `u`. Notice that the ``` ``` closeness distance function computes the incoming distance to `u` ``` ``` for directed graphs. To use outward distance, act on `G.reverse()`. ``` ``` ``` ``` Notice that higher values of closeness indicate higher centrality. ``` ``` ``` ``` Wasserman and Faust propose an improved formula for graphs with ``` ``` more than one connected component. The result is "a ratio of the ``` ``` fraction of actors in the group who are reachable, to the average ``` ``` distance" from the reachable actors _. You might think this ``` ``` scale factor is inverted but it is not. As is, nodes from small ``` ``` components receive a smaller closeness value. Letting `N` denote ``` ``` the number of nodes in the graph, ``` ``` ``` ``` .. math:: ``` ``` ``` ``` C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A NetworkX graph ``` ``` ``` ``` u : node, optional ``` ``` Return only the value for node u ``` ``` ``` ``` distance : edge attribute key, optional (default=None) ``` ``` Use the specified edge attribute as the edge distance in shortest ``` ``` path calculations ``` ``` ``` ``` wf_improved : bool, 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 ``` ``` ------- ``` ``` nodes : dictionary ``` ``` Dictionary of nodes with closeness centrality as the value. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` betweenness_centrality, load_centrality, eigenvector_centrality, ``` ``` degree_centrality ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The closeness centrality is normalized to `(n-1)/(|G|-1)` where ``` ``` `n` is the number of nodes in the connected part of graph ``` ``` containing the node. If the graph is not completely connected, ``` ``` this algorithm computes the closeness centrality for each ``` ``` connected part separately scaled by that parts size. ``` ``` ``` ``` If the 'distance' keyword is set to an edge attribute key then the ``` ``` shortest-path length will be computed using Dijkstra's algorithm with ``` ``` that edge attribute as the edge weight. ``` ``` ``` ``` In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the ``` ``` outward distance rather than the inward distance. If you use a 'distance' ``` ``` keyword and a DiGraph, your results will change between v2.2 and v2.3. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Linton C. Freeman: Centrality in networks: I. ``` ``` Conceptual clarification. Social Networks 1:215-239, 1979. ``` ``` http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf ``` ``` ..  pg. 201 of Wasserman, S. and Faust, K., ``` ``` Social Network Analysis: Methods and Applications, 1994, ``` ``` Cambridge University Press. ``` ``` """ ``` ``` if G.is_directed(): ``` ``` G = G.reverse() # create a reversed graph view ``` ``` if distance is not None: ``` ``` # use Dijkstra's algorithm with specified attribute as edge weight ``` ``` path_length = functools.partial(nx.single_source_dijkstra_path_length, ``` ``` weight=distance) ``` ``` else: ``` ``` path_length = nx.single_source_shortest_path_length ``` ``` if u is None: ``` ``` nodes = G.nodes ``` ``` else: ``` ``` nodes = [u] ``` ``` closeness_centrality = {} ``` ``` for n in nodes: ``` ``` sp = dict(path_length(G, n)) ``` ``` totsp = sum(sp.values()) ``` ``` if totsp > 0.0 and len(G) > 1: ``` ``` closeness_centrality[n] = (len(sp) - 1.0) / totsp ``` ``` # normalize to number of nodes-1 in connected part ``` ``` if wf_improved: ``` ``` s = (len(sp) - 1.0) / (len(G) - 1) ``` ``` closeness_centrality[n] *= s ``` ``` else: ``` ``` closeness_centrality[n] = 0.0 ``` ``` if u is not None: ``` ``` return closeness_centrality[u] ``` ``` else: ``` ``` return closeness_centrality ```