Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (8.61 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
# Author: Aric Hagberg (hagberg@lanl.gov)
9
"""Betweenness centrality measures for subsets of nodes."""
10
import networkx as nx
11

    
12
from networkx.algorithms.centrality.betweenness import\
13
    _single_source_dijkstra_path_basic as dijkstra
14
from networkx.algorithms.centrality.betweenness import\
15
    _single_source_shortest_path_basic as shortest_path
16

    
17
__all__ = ['betweenness_centrality_subset', 'betweenness_centrality_source',
18
           'edge_betweenness_centrality_subset']
19

    
20

    
21
def betweenness_centrality_subset(G, sources, targets, normalized=False,
22
                                  weight=None):
23
    r"""Compute betweenness centrality for a subset of nodes.
24

25
    .. math::
26

27
       c_B(v) =\sum_{s\in S, t \in T} \frac{\sigma(s, t|v)}{\sigma(s, t)}
28

29
    where $S$ is the set of sources, $T$ is the set of targets,
30
    $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
31
    and $\sigma(s, t|v)$ is the number of those paths
32
    passing through some  node $v$ other than $s, t$.
33
    If $s = t$, $\sigma(s, t) = 1$,
34
    and if $v \in {s, t}$, $\sigma(s, t|v) = 0$ [2]_.
35

36

37
    Parameters
38
    ----------
39
    G : graph
40
      A NetworkX graph.
41

42
    sources: list of nodes
43
      Nodes to use as sources for shortest paths in betweenness
44

45
    targets: list of nodes
46
      Nodes to use as targets for shortest paths in betweenness
47

48
    normalized : bool, optional
49
      If True the betweenness values are normalized by $2/((n-1)(n-2))$
50
      for graphs, and $1/((n-1)(n-2))$ for directed graphs where $n$
51
      is the number of nodes in G.
52

53
    weight : None or string, optional (default=None)
54
      If None, all edge weights are considered equal.
55
      Otherwise holds the name of the edge attribute used as weight.
56

57
    Returns
58
    -------
59
    nodes : dictionary
60
       Dictionary of nodes with betweenness centrality as the value.
61

62
    See Also
63
    --------
64
    edge_betweenness_centrality
65
    load_centrality
66

67
    Notes
68
    -----
69
    The basic algorithm is from [1]_.
70

71
    For weighted graphs the edge weights must be greater than zero.
72
    Zero edge weights can produce an infinite number of equal length
73
    paths between pairs of nodes.
74

75
    The normalization might seem a little strange but it is the same
76
    as in betweenness_centrality() and is designed to make
77
    betweenness_centrality(G) be the same as
78
    betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
79

80

81
    References
82
    ----------
83
    .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
84
       Journal of Mathematical Sociology 25(2):163-177, 2001.
85
       http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
86
    .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
87
       Centrality and their Generic Computation.
88
       Social Networks 30(2):136-145, 2008.
89
       http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
90
    """
91
    b = dict.fromkeys(G, 0.0)  # b[v]=0 for v in G
92
    for s in sources:
93
        # single source shortest paths
94
        if weight is None:  # use BFS
95
            S, P, sigma = shortest_path(G, s)
96
        else:  # use Dijkstra's algorithm
97
            S, P, sigma = dijkstra(G, s, weight)
98
        b = _accumulate_subset(b, S, P, sigma, s, targets)
99
    b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed())
100
    return b
101

    
102

    
103
def edge_betweenness_centrality_subset(G, sources, targets, normalized=False,
104
                                       weight=None):
105
    r"""Compute betweenness centrality for edges for a subset of nodes.
106

107
    .. math::
108

109
       c_B(v) =\sum_{s\in S,t \in T} \frac{\sigma(s, t|e)}{\sigma(s, t)}
110

111
    where $S$ is the set of sources, $T$ is the set of targets,
112
    $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
113
    and $\sigma(s, t|e)$ is the number of those paths
114
    passing through edge $e$ [2]_.
115

116
    Parameters
117
    ----------
118
    G : graph
119
      A networkx graph.
120

121
    sources: list of nodes
122
      Nodes to use as sources for shortest paths in betweenness
123

124
    targets: list of nodes
125
      Nodes to use as targets for shortest paths in betweenness
126

127
    normalized : bool, optional
128
      If True the betweenness values are normalized by `2/(n(n-1))`
129
      for graphs, and `1/(n(n-1))` for directed graphs where `n`
130
      is the number of nodes in G.
131

132
    weight : None or string, optional (default=None)
133
      If None, all edge weights are considered equal.
134
      Otherwise holds the name of the edge attribute used as weight.
135

136
    Returns
137
    -------
138
    edges : dictionary
139
       Dictionary of edges with Betweenness centrality as the value.
140

141
    See Also
142
    --------
143
    betweenness_centrality
144
    edge_load
145

146
    Notes
147
    -----
148
    The basic algorithm is from [1]_.
149

150
    For weighted graphs the edge weights must be greater than zero.
151
    Zero edge weights can produce an infinite number of equal length
152
    paths between pairs of nodes.
153

154
    The normalization might seem a little strange but it is the same
155
    as in edge_betweenness_centrality() and is designed to make
156
    edge_betweenness_centrality(G) be the same as
157
    edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
158

159
    References
160
    ----------
161
    .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
162
       Journal of Mathematical Sociology 25(2):163-177, 2001.
163
       http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
164
    .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
165
       Centrality and their Generic Computation.
166
       Social Networks 30(2):136-145, 2008.
167
       http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
168
    """
169
    b = dict.fromkeys(G, 0.0)  # b[v]=0 for v in G
170
    b.update(dict.fromkeys(G.edges(), 0.0))  # b[e] for e in G.edges()
171
    for s in sources:
172
        # single source shortest paths
173
        if weight is None:  # use BFS
174
            S, P, sigma = shortest_path(G, s)
175
        else:  # use Dijkstra's algorithm
176
            S, P, sigma = dijkstra(G, s, weight)
177
        b = _accumulate_edges_subset(b, S, P, sigma, s, targets)
178
    for n in G:  # remove nodes to only return edges
179
        del b[n]
180
    b = _rescale_e(b, len(G), normalized=normalized, directed=G.is_directed())
181
    return b
182

    
183

    
184
# obsolete name
185
def betweenness_centrality_source(G, normalized=True, weight=None,
186
                                  sources=None):
187
    if sources is None:
188
        sources = G.nodes()
189
    targets = list(G)
190
    return betweenness_centrality_subset(G, sources, targets, normalized,
191
                                         weight)
192

    
193

    
194
def _accumulate_subset(betweenness, S, P, sigma, s, targets):
195
    delta = dict.fromkeys(S, 0.0)
196
    target_set = set(targets) - {s}
197
    while S:
198
        w = S.pop()
199
        if w in target_set:
200
            coeff = (delta[w] + 1.0)/ sigma[w]
201
        else:
202
            coeff = delta[w] / sigma[w]
203
        for v in P[w]:
204
            delta[v] += sigma[v] * coeff
205
        if w != s:
206
            betweenness[w] += delta[w]
207
    return betweenness
208

    
209

    
210
def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets):
211
    """edge_betweenness_centrality_subset helper."""
212
    delta = dict.fromkeys(S, 0)
213
    target_set = set(targets)
214
    while S:
215
        w = S.pop()
216
        for v in P[w]:
217
            if w in target_set:
218
                c = (sigma[v] / sigma[w]) * (1.0 + delta[w])
219
            else:
220
                c = delta[w] / len(P[w])
221
            if (v, w) not in betweenness:
222
                betweenness[(w, v)] += c
223
            else:
224
                betweenness[(v, w)] += c
225
            delta[v] += c
226
        if w != s:
227
            betweenness[w] += delta[w]
228
    return betweenness
229

    
230

    
231
def _rescale(betweenness, n, normalized, directed=False):
232
    """betweenness_centrality_subset helper."""
233
    if normalized:
234
        if n <= 2:
235
            scale = None  # no normalization b=0 for all nodes
236
        else:
237
            scale = 1.0 / ((n - 1) * (n - 2))
238
    else:  # rescale by 2 for undirected graphs
239
        if not directed:
240
            scale = 0.5
241
        else:
242
            scale = None
243
    if scale is not None:
244
        for v in betweenness:
245
            betweenness[v] *= scale
246
    return betweenness
247

    
248

    
249
def _rescale_e(betweenness, n, normalized, directed=False):
250
    """edge_betweenness_centrality_subset helper."""
251
    if normalized:
252
        if n <= 1:
253
            scale = None  # no normalization b=0 for all nodes
254
        else:
255
            scale = 1.0 / (n * (n - 1))
256
    else:  # rescale by 2 for undirected graphs
257
        if not directed:
258
            scale = 0.5
259
        else:
260
            scale = None
261
    if scale is not None:
262
        for v in betweenness:
263
            betweenness[v] *= scale
264
    return betweenness