Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.56 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Authors:  Aric Hagberg <aric.hagberg@gmail.com>
9
#           Pieter Swart <swart@lanl.gov>
10
#           Sasha Gutfraind <ag362@cornell.edu>
11
#           Dan Schult <dschult@colgate.edu>
12
"""
13
Closeness centrality measures.
14
"""
15
import functools
16
import networkx as nx
17

    
18
__all__ = ['closeness_centrality']
19

    
20

    
21
def closeness_centrality(G, u=None, distance=None, wf_improved=True):
22
    r"""Compute closeness centrality for nodes.
23

24
    Closeness centrality [1]_ of a node `u` is the reciprocal of the
25
    average shortest path distance to `u` over all `n-1` reachable nodes.
26

27
    .. math::
28

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

31
    where `d(v, u)` is the shortest-path distance between `v` and `u`,
32
    and `n` is the number of nodes that can reach `u`. Notice that the
33
    closeness distance function computes the incoming distance to `u`
34
    for directed graphs. To use outward distance, act on `G.reverse()`.
35

36
    Notice that higher values of closeness indicate higher centrality.
37

38
    Wasserman and Faust propose an improved formula for graphs with
39
    more than one connected component. The result is "a ratio of the
40
    fraction of actors in the group who are reachable, to the average
41
    distance" from the reachable actors [2]_. You might think this
42
    scale factor is inverted but it is not. As is, nodes from small
43
    components receive a smaller closeness value. Letting `N` denote
44
    the number of nodes in the graph,
45

46
    .. math::
47

48
        C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
49

50
    Parameters
51
    ----------
52
    G : graph
53
      A NetworkX graph
54

55
    u : node, optional
56
      Return only the value for node u
57

58
    distance : edge attribute key, optional (default=None)
59
      Use the specified edge attribute as the edge distance in shortest
60
      path calculations
61

62
    wf_improved : bool, optional (default=True)
63
      If True, scale by the fraction of nodes reachable. This gives the
64
      Wasserman and Faust improved formula. For single component graphs
65
      it is the same as the original formula. 
66

67
    Returns
68
    -------
69
    nodes : dictionary
70
      Dictionary of nodes with closeness centrality as the value.
71

72
    See Also
73
    --------
74
    betweenness_centrality, load_centrality, eigenvector_centrality,
75
    degree_centrality
76

77
    Notes
78
    -----
79
    The closeness centrality is normalized to `(n-1)/(|G|-1)` where
80
    `n` is the number of nodes in the connected part of graph
81
    containing the node.  If the graph is not completely connected,
82
    this algorithm computes the closeness centrality for each
83
    connected part separately scaled by that parts size.
84

85
    If the 'distance' keyword is set to an edge attribute key then the
86
    shortest-path length will be computed using Dijkstra's algorithm with
87
    that edge attribute as the edge weight.
88

89
    In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the
90
    outward distance rather than the inward distance. If you use a 'distance'
91
    keyword and a DiGraph, your results will change between v2.2 and v2.3.
92

93
    References
94
    ----------
95
    .. [1] Linton C. Freeman: Centrality in networks: I.
96
       Conceptual clarification. Social Networks 1:215-239, 1979.
97
       http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf
98
    .. [2] pg. 201 of Wasserman, S. and Faust, K.,
99
       Social Network Analysis: Methods and Applications, 1994,
100
       Cambridge University Press.
101
    """
102
    if G.is_directed():
103
        G = G.reverse()  # create a reversed graph view
104

    
105
    if distance is not None:
106
        # use Dijkstra's algorithm with specified attribute as edge weight
107
        path_length = functools.partial(nx.single_source_dijkstra_path_length,
108
                                        weight=distance)
109
    else:
110
        path_length = nx.single_source_shortest_path_length
111

    
112
    if u is None:
113
        nodes = G.nodes
114
    else:
115
        nodes = [u]
116
    closeness_centrality = {}
117
    for n in nodes:
118
        sp = dict(path_length(G, n))
119
        totsp = sum(sp.values())
120
        if totsp > 0.0 and len(G) > 1:
121
            closeness_centrality[n] = (len(sp) - 1.0) / totsp
122
            # normalize to number of nodes-1 in connected part
123
            if wf_improved:
124
                s = (len(sp) - 1.0) / (len(G) - 1)
125
                closeness_centrality[n] *= s
126
        else:
127
            closeness_centrality[n] = 0.0
128
    if u is not None:
129
        return closeness_centrality[u]
130
    else:
131
        return closeness_centrality