| """ |
| Closeness centrality measures. |
| """ |
| # Copyright (C) 2004-2013 by |
| # Aric Hagberg <hagberg@lanl.gov> |
| # Dan Schult <dschult@colgate.edu> |
| # Pieter Swart <swart@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| import functools |
| import networkx as nx |
| __author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>', |
| 'Pieter Swart (swart@lanl.gov)', |
| 'Sasha Gutfraind (ag362@cornell.edu)']) |
| __all__ = ['closeness_centrality'] |
| |
| |
| def closeness_centrality(G, u=None, distance=None, normalized=True): |
| r"""Compute closeness centrality for nodes. |
| |
| 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`. |
| |
| .. math:: |
| |
| C(u) = \frac{n - 1}{\sum_{v=1}^{n} 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 |
| ---------- |
| 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 |
| normalized : bool, optional |
| If True (default) normalize by the number of nodes in the connected |
| part of the graph. |
| |
| 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. |
| |
| 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. |
| |
| References |
| ---------- |
| .. [1] Freeman, L.C., 1979. Centrality in networks: I. |
| Conceptual clarification. Social Networks 1, 215--239. |
| http://www.soc.ucsb.edu/faculty/friedkin/Syllabi/Soc146/Freeman78.PDF |
| """ |
| 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 = 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 normalized: |
| 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 |
