Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (8.47 KB)

1
#-*- coding: utf-8 -*-
2
#    Copyright (C) 2011 by
3
#    Jordi Torrents <jtorrents@milnou.net>
4
#    Aric Hagberg <hagberg@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
import networkx as nx
8
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
9
                            'Aric Hagberg (hagberg@lanl.gov)'])
10
__all__ = ['degree_centrality',
11
           'betweenness_centrality',
12
           'closeness_centrality']
13

    
14

    
15
def degree_centrality(G, nodes):
16
    r"""Compute the degree centrality for nodes in a bipartite network.
17

18
    The degree centrality for a node `v` is the fraction of nodes
19
    connected to it.
20

21
    Parameters
22
    ----------
23
    G : graph
24
       A bipartite network
25

26
    nodes : list or container
27
      Container with all nodes in one bipartite node set.
28

29
    Returns
30
    -------
31
    centrality : dictionary
32
       Dictionary keyed by node with bipartite degree centrality as the value.
33

34
    See Also
35
    --------
36
    betweenness_centrality,
37
    closeness_centrality,
38
    sets,
39
    is_bipartite
40

41
    Notes
42
    -----
43
    The nodes input parameter must contain all nodes in one bipartite node set,
44
    but the dictionary returned contains all nodes from both bipartite node
45
    sets. See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
46
    for further details on how bipartite graphs are handled in NetworkX.
47

48
    For unipartite networks, the degree centrality values are
49
    normalized by dividing by the maximum possible degree (which is
50
    `n-1` where `n` is the number of nodes in G).
51

52
    In the bipartite case, the maximum possible degree of a node in a
53
    bipartite node set is the number of nodes in the opposite node set
54
    [1]_.  The degree centrality for a node `v` in the bipartite
55
    sets `U` with `n` nodes and `V` with `m` nodes is
56

57
    .. math::
58

59
        d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
60

61
        d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
62

63

64
    where `deg(v)` is the degree of node `v`.
65

66
    References
67
    ----------
68
    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
69
        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
70
        of Social Network Analysis. Sage Publications.
71
        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
72
    """
73
    top = set(nodes)
74
    bottom = set(G) - top
75
    s = 1.0 / len(bottom)
76
    centrality = dict((n, d * s) for n, d in G.degree(top))
77
    s = 1.0 / len(top)
78
    centrality.update(dict((n, d * s) for n, d in G.degree(bottom)))
79
    return centrality
80

    
81

    
82
def betweenness_centrality(G, nodes):
83
    r"""Compute betweenness centrality for nodes in a bipartite network.
84

85
    Betweenness centrality of a node `v` is the sum of the
86
    fraction of all-pairs shortest paths that pass through `v`.
87

88
    Values of betweenness are normalized by the maximum possible
89
    value which for bipartite graphs is limited by the relative size
90
    of the two node sets [1]_.
91

92
    Let `n` be the number of nodes in the node set `U` and
93
    `m` be the number of nodes in the node set `V`, then
94
    nodes in `U` are normalized by dividing by
95

96
    .. math::
97

98
       \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] ,
99

100
    where
101

102
    .. math::
103

104
        s = (n - 1) \div m , t = (n - 1) \mod m ,
105

106
    and nodes in `V` are normalized by dividing by
107

108
    .. math::
109

110
        \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] ,
111

112
    where,
113

114
    .. math::
115

116
        p = (m - 1) \div n , r = (m - 1) \mod n .
117

118
    Parameters
119
    ----------
120
    G : graph
121
        A bipartite graph
122

123
    nodes : list or container
124
        Container with all nodes in one bipartite node set.
125

126
    Returns
127
    -------
128
    betweenness : dictionary
129
        Dictionary keyed by node with bipartite betweenness centrality
130
        as the value.
131

132
    See Also
133
    --------
134
    degree_centrality,
135
    closeness_centrality,
136
    sets,
137
    is_bipartite
138

139
    Notes
140
    -----
141
    The nodes input parameter must contain all nodes in one bipartite node set,
142
    but the dictionary returned contains all nodes from both node sets.
143
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
144
    for further details on how bipartite graphs are handled in NetworkX.
145

146

147
    References
148
    ----------
149
    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
150
        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
151
        of Social Network Analysis. Sage Publications.
152
        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
153
    """
154
    top = set(nodes)
155
    bottom = set(G) - top
156
    n = float(len(top))
157
    m = float(len(bottom))
158
    s = (n - 1) // m
159
    t = (n - 1) % m
160
    bet_max_top = (((m**2) * ((s + 1)**2)) +
161
                   (m * (s + 1) * (2 * t - s - 1)) -
162
                   (t * ((2 * s) - t + 3))) / 2.0
163
    p = (m - 1) // n
164
    r = (m - 1) % n
165
    bet_max_bot = (((n**2) * ((p + 1)**2)) +
166
                   (n * (p + 1) * (2 * r - p - 1)) -
167
                   (r * ((2 * p) - r + 3))) / 2.0
168
    betweenness = nx.betweenness_centrality(G, normalized=False,
169
                                            weight=None)
170
    for node in top:
171
        betweenness[node] /= bet_max_top
172
    for node in bottom:
173
        betweenness[node] /= bet_max_bot
174
    return betweenness
175

    
176

    
177
def closeness_centrality(G, nodes, normalized=True):
178
    r"""Compute the closeness centrality for nodes in a bipartite network.
179

180
    The closeness of a node is the distance to all other nodes in the
181
    graph or in the case that the graph is not connected to all other nodes
182
    in the connected component containing that node.
183

184
    Parameters
185
    ----------
186
    G : graph
187
        A bipartite network
188

189
    nodes : list or container
190
        Container with all nodes in one bipartite node set.
191

192
    normalized : bool, optional
193
      If True (default) normalize by connected component size.
194

195
    Returns
196
    -------
197
    closeness : dictionary
198
        Dictionary keyed by node with bipartite closeness centrality
199
        as the value.
200

201
    See Also
202
    --------
203
    betweenness_centrality,
204
    degree_centrality
205
    sets,
206
    is_bipartite
207

208
    Notes
209
    -----
210
    The nodes input parameter must contain all nodes in one bipartite node set,
211
    but the dictionary returned contains all nodes from both node sets.
212
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
213
    for further details on how bipartite graphs are handled in NetworkX.
214

215

216
    Closeness centrality is normalized by the minimum distance possible.
217
    In the bipartite case the minimum distance for a node in one bipartite
218
    node set is 1 from all nodes in the other node set and 2 from all
219
    other nodes in its own set [1]_. Thus the closeness centrality
220
    for node `v`  in the two bipartite sets `U` with
221
    `n` nodes and `V` with `m` nodes is
222

223
    .. math::
224

225
        c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U,
226

227
        c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V,
228

229
    where `d` is the sum of the distances from `v` to all
230
    other nodes.
231

232
    Higher values of closeness  indicate higher centrality.
233

234
    As in the unipartite case, setting normalized=True causes the
235
    values to normalized further to n-1 / size(G)-1 where n is the
236
    number of nodes in the connected part of graph containing the
237
    node.  If the graph is not completely connected, this algorithm
238
    computes the closeness centrality for each connected part
239
    separately.
240

241
    References
242
    ----------
243
    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
244
        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
245
        of Social Network Analysis. Sage Publications.
246
        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
247
    """
248
    closeness = {}
249
    path_length = nx.single_source_shortest_path_length
250
    top = set(nodes)
251
    bottom = set(G) - top
252
    n = float(len(top))
253
    m = float(len(bottom))
254
    for node in top:
255
        sp = dict(path_length(G, node))
256
        totsp = sum(sp.values())
257
        if totsp > 0.0 and len(G) > 1:
258
            closeness[node] = (m + 2 * (n - 1)) / totsp
259
            if normalized:
260
                s = (len(sp) - 1.0) / (len(G) - 1)
261
                closeness[node] *= s
262
        else:
263
            closeness[n] = 0.0
264
    for node in bottom:
265
        sp = dict(path_length(G, node))
266
        totsp = sum(sp.values())
267
        if totsp > 0.0 and len(G) > 1:
268
            closeness[node] = (n + 2 * (m - 1)) / totsp
269
            if normalized:
270
                s = (len(sp) - 1.0) / (len(G) - 1)
271
                closeness[node] *= s
272
        else:
273
            closeness[n] = 0.0
274
    return closeness