1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
"""
Current-flow closeness centrality measures.
"""
# Copyright (C) 2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__all__ = ['current_flow_closeness_centrality']
import networkx as nx
import numpy as np
def current_flow_closeness_centrality(G,normalized=True):
"""Compute current-flow closeness centrality for nodes.
A variant of closeness centrality based on effective
resistance between nodes in a network. This metric
is also known as information centrality.
Parameters
----------
G : graph
A networkx graph
normalized : bool, optional
If True the values are normalized by 1/(n-1) where n is the
number of nodes in G.
Returns
-------
nodes : dictionary
Dictionary of nodes with current flow closeness centrality as the value.
See Also
--------
closeness_centrality
Notes
-----
The algorithm is from Brandes [1]_.
If the edges have a 'weight' attribute they will be used as
weights in this algorithm. Unspecified weights are set to 1.
See also [2]_ for the original definition of information centrality.
References
----------
.. [1] Ulrik Brandes and Daniel Fleischer,
Centrality Measures Based on Current Flow.
Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf
.. [2] Stephenson, K. and Zelen, M.
Rethinking centrality: Methods and examples.
Social Networks. Volume 11, Issue 1, March 1989, pp. 1-37
http://dx.doi.org/10.1016/0378-8733(89)90016-6
"""
try:
import numpy as np
except ImportError:
raise ImportError, \
"flow_closeness_centrality() requires NumPy: http://scipy.org/ "
from itertools import izip
if G.is_directed():
raise nx.NetworkXError(\
"current_flow_closeness_centrality() not defined for digraphs.")
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected.")
betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G
n=len(G)
mapping=dict(zip(G,range(n))) # map nodes to integers
C=_compute_C(G)
for v in G:
vi=mapping[v]
Cv=C[:,vi]
for w in G:
wi=mapping[w]
betweenness[v]+=C[vi,vi]-2*C[wi,vi]
betweenness[w]+=C[vi,vi]
if normalized:
nb=len(betweenness)-1.0
else:
nb=1.0
for v in G:
betweenness[v]=nb/(betweenness[v])
return betweenness
def _compute_C(G):
"""Compute inverse of Laplacian."""
L=nx.laplacian(G) # use ordering of G.nodes()
# remove first row and column
LR=L[1:,1:]
LRinv=np.linalg.inv(LR)
C=np.zeros(L.shape)
C[1:,1:]=LRinv
return C
|
