← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/centrality/current_flow_closeness.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/centrality/current_flow_closeness.py
8
8
#    Pieter Swart <swart@lanl.gov>
9
9
#    All rights reserved.
10
10
#    BSD license.
11
 
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
 
11
__author__ = """Aric Hagberg <aric.hagberg@gmail.com>"""
12
12
 
13
13
__all__ = ['current_flow_closeness_centrality','information_centrality']
14
14
 
15
15
import networkx as nx
 
16
from networkx.algorithms.centrality.flow_matrix import *
 
17
    
16
18
 
17
 
def current_flow_closeness_centrality(G,normalized=True):
 
19
def current_flow_closeness_centrality(G, normalized=True, weight='weight', 
 
20
                                      dtype=float, solver='lu'):
18
21
    """Compute current-flow closeness centrality for nodes.
19
22
 
20
23
    A variant of closeness centrality based on effective
24
27
    Parameters
25
28
    ----------
26
29
    G : graph
27
 
      A networkx graph 
 
30
      A NetworkX graph 
28
31
 
29
32
    normalized : bool, optional
30
33
      If True the values are normalized by 1/(n-1) where n is the 
31
34
      number of nodes in G.
32
 
       
 
35
 
 
36
    dtype: data type (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
 
33
45
    Returns
34
46
    -------
35
47
    nodes : dictionary
43
55
    -----
44
56
    The algorithm is from Brandes [1]_.
45
57
 
46
 
    If the edges have a 'weight' attribute they will be used as 
47
 
    weights in this algorithm.  Unspecified weights are set to 1.
48
 
 
49
58
    See also [2]_ for the original definition of information centrality.
50
59
 
51
60
    References
61
70
       Social Networks. Volume 11, Issue 1, March 1989, pp. 1-37
62
71
       http://dx.doi.org/10.1016/0378-8733(89)90016-6
63
72
    """
 
73
    from networkx.utils import reverse_cuthill_mckee_ordering 
64
74
    try:
65
75
        import numpy as np
66
76
    except ImportError:
67
 
        raise ImportError("flow_closeness_centrality() requires NumPy: http://scipy.org/ ")
68
 
    
69
 
 
 
77
        raise ImportError('current_flow_closeness_centrality requires NumPy ',
 
78
                          'http://scipy.org/')
 
79
    try:
 
80
        import scipy 
 
81
    except ImportError:
 
82
        raise ImportError('current_flow_closeness_centrality requires SciPy ',
 
83
                          'http://scipy.org/')
 
84
    if G.is_directed():
 
85
        raise nx.NetworkXError('current_flow_closeness_centrality ',
 
86
                               'not defined for digraphs.')
70
87
    if G.is_directed():
71
88
        raise nx.NetworkXError(\
72
89
            "current_flow_closeness_centrality() not defined for digraphs.")
73
 
 
74
90
    if not nx.is_connected(G):
75
91
        raise nx.NetworkXError("Graph not connected.")
 
92
    solvername={"full" :FullInverseLaplacian,
 
93
                "lu": SuperLUInverseLaplacian,
 
94
                "cg": CGInverseLaplacian}
 
95
    n = G.number_of_nodes()
 
96
    ordering = list(reverse_cuthill_mckee_ordering(G))
 
97
    # make a copy with integer labels according to rcm ordering
 
98
    # this could be done without a copy if we really wanted to
 
99
    H = nx.relabel_nodes(G,dict(zip(ordering,range(n))))
 
100
    betweenness = dict.fromkeys(H,0.0) # b[v]=0 for v in H
 
101
    n = G.number_of_nodes()
 
102
    L = laplacian_sparse_matrix(H, nodelist=range(n), weight=weight, 
 
103
                                dtype=dtype, format='csc')
 
104
    C2 = solvername[solver](L, width=1, dtype=dtype) # initialize solver
 
105
    for v in H:
 
106
        col=C2.get_row(v)
 
107
        for w in H:
 
108
            betweenness[v]+=col[v]-2*col[w]
 
109
            betweenness[w]+=col[v]
76
110
 
77
 
    betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G
78
 
    n=len(G)
79
 
    mapping=dict(zip(G,list(range(n))))  # map nodes to integers
80
 
    C=_compute_C(G)
81
 
    for v in G:
82
 
        vi=mapping[v]
83
 
        Cv=C[:,vi]
84
 
        for w in G:
85
 
            wi=mapping[w]
86
 
            betweenness[v]+=C[vi,vi]-2*C[wi,vi]
87
 
            betweenness[w]+=C[vi,vi]
88
 
                
89
111
    if normalized:
90
112
        nb=len(betweenness)-1.0
91
113
    else:
92
114
        nb=1.0
93
 
    for v in G:
 
115
    for v in H:
94
116
        betweenness[v]=nb/(betweenness[v])
95
 
    return betweenness            
96
 
 
97
 
 
98
 
def _compute_C(G):
99
 
    """Compute inverse of Laplacian."""
100
 
    try:
101
 
        import numpy as np
102
 
    except ImportError:
103
 
        raise ImportError("flow_closeness_centrality() requires NumPy: http://scipy.org/ ")
104
 
    L=nx.laplacian(G) # use ordering of G.nodes()
105
 
    # remove first row and column
106
 
    LR=L[1:,1:]
107
 
    LRinv=np.linalg.inv(LR)
108
 
    C=np.zeros(L.shape)
109
 
    C[1:,1:]=LRinv
110
 
    return C
 
117
    return dict((ordering[k],float(v)) for k,v in betweenness.items())
111
118
 
112
119
information_centrality=current_flow_closeness_centrality
113
120
 
118
125
        import numpy
119
126
    except:
120
127
        raise SkipTest("NumPy not available")
121