Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.61 KB)

1
#    Copyright (C) 2010-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
# Author: Aric Hagberg (hagberg@lanl.gov)
9
"""Current-flow closeness centrality measures."""
10
import networkx as nx
11

    
12
from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering
13
from networkx.algorithms.centrality.flow_matrix import *
14

    
15
__all__ = ['current_flow_closeness_centrality', 'information_centrality']
16

    
17

    
18
@not_implemented_for('directed')
19
def current_flow_closeness_centrality(G, weight=None,
20
                                      dtype=float, solver='lu'):
21
    """Compute current-flow closeness centrality for nodes.
22

23
    Current-flow closeness centrality is variant of closeness
24
    centrality based on effective resistance between nodes in
25
    a network. This metric is also known as information centrality.
26

27
    Parameters
28
    ----------
29
    G : graph
30
      A NetworkX graph.
31

32
    weight : None or string, optional (default=None)
33
      If None, all edge weights are considered equal.
34
      Otherwise holds the name of the edge attribute used as weight.
35

36
    dtype: data type (default=float)
37
      Default data type for internal matrices.
38
      Set to np.float32 for lower memory consumption.
39

40
    solver: string (default='lu')
41
       Type of linear solver to use for computing the flow matrix.
42
       Options are "full" (uses most memory), "lu" (recommended), and
43
       "cg" (uses least memory).
44

45
    Returns
46
    -------
47
    nodes : dictionary
48
       Dictionary of nodes with current flow closeness centrality as the value.
49

50
    See Also
51
    --------
52
    closeness_centrality
53

54
    Notes
55
    -----
56
    The algorithm is from Brandes [1]_.
57

58
    See also [2]_ for the original definition of information centrality.
59

60
    References
61
    ----------
62
    .. [1] Ulrik Brandes and Daniel Fleischer,
63
       Centrality Measures Based on Current Flow.
64
       Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
65
       LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
66
       http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf
67

68
    .. [2] Karen Stephenson and Marvin Zelen:
69
       Rethinking centrality: Methods and examples.
70
       Social Networks 11(1):1-37, 1989.
71
       https://doi.org/10.1016/0378-8733(89)90016-6
72
    """
73
    import numpy as np
74
    import scipy
75
    if not nx.is_connected(G):
76
        raise nx.NetworkXError("Graph not connected.")
77
    solvername = {"full": FullInverseLaplacian,
78
                  "lu": SuperLUInverseLaplacian,
79
                  "cg": CGInverseLaplacian}
80
    n = G.number_of_nodes()
81
    ordering = list(reverse_cuthill_mckee_ordering(G))
82
    # make a copy with integer labels according to rcm ordering
83
    # this could be done without a copy if we really wanted to
84
    H = nx.relabel_nodes(G, dict(zip(ordering, range(n))))
85
    betweenness = dict.fromkeys(H, 0.0)  # b[v]=0 for v in H
86
    n = H.number_of_nodes()
87
    L = laplacian_sparse_matrix(H, nodelist=range(n), weight=weight,
88
                                dtype=dtype, format='csc')
89
    C2 = solvername[solver](L, width=1, dtype=dtype)  # initialize solver
90
    for v in H:
91
        col = C2.get_row(v)
92
        for w in H:
93
            betweenness[v] += col[v] - 2 * col[w]
94
            betweenness[w] += col[v]
95
    for v in H:
96
        betweenness[v] = 1.0 / (betweenness[v])
97
    return dict((ordering[k], float(v)) for k, v in betweenness.items())
98

    
99

    
100
information_centrality = current_flow_closeness_centrality
101

    
102

    
103
# fixture for nose tests
104
def setup_module(module):
105
    from nose import SkipTest
106
    try:
107
        import numpy
108
    except:
109
        raise SkipTest("NumPy not available")