2
# Copyright (C) 2011 by
3
# Jordi Torrents <jtorrents@milnou.net>
4
# Aric Hagberg <hagberg@lanl.gov>
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']
14
def degree_centrality(G, nodes):
15
r"""Compute the degree centrality for nodes in a bipartite network.
17
The degree centrality for a node `v` is the fraction of nodes
25
nodes : list or container
26
Container with all nodes in one bipartite node set.
30
centrality : dictionary
31
Dictionary keyed by node with bipartite degree centrality as the value.
35
betweenness_centrality,
42
The nodes input parameter must conatin all nodes in one bipartite node set,
43
but the dictionary returned contains all nodes from both bipartite node
46
For unipartite networks, the degree centrality values are
47
normalized by dividing by the maximum possible degree (which is
48
`n-1` where `n` is the number of nodes in G).
50
In the bipartite case, the maximum possible degree of a node in a
51
bipartite node set is the number of nodes in the opposite node set
52
[1]_. The degree centrality for a node `v` in the bipartite
53
sets `U` with `n` nodes and `V` with `m` nodes is
57
d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
59
d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
62
where `deg(v)` is the degree of node `v`.
66
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
67
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
68
of Social Network Analysis. Sage Publications.
69
http://www.steveborgatti.com/papers/bhaffiliations.pdf
74
centrality = dict((n,d*s) for n,d in G.degree_iter(top))
76
centrality.update(dict((n,d*s) for n,d in G.degree_iter(bottom)))
80
def betweenness_centrality(G, nodes):
81
r"""Compute betweenness centrality for nodes in a bipartite network.
83
Betweenness centrality of a node `v` is the sum of the
84
fraction of all-pairs shortest paths that pass through `v`.
86
Values of betweenness are normalized by the maximum possible
87
value which for bipartite graphs is limited by the relative size
88
of the two node sets [1]_.
90
Let `n` be the number of nodes in the node set `U` and
91
`m` be the number of nodes in the node set `V`, then
92
nodes in `U` are normalized by dividing by
96
\frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] ,
102
s = (n - 1) \div m , t = (n - 1) \mod m ,
104
and nodes in `V` are normalized by dividing by
108
\frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] ,
114
p = (m - 1) \div n , r = (m - 1) \mod n .
121
nodes : list or container
122
Container with all nodes in one bipartite node set.
126
betweenness : dictionary
127
Dictionary keyed by node with bipartite betweenness centrality
133
closeness_centrality,
139
The nodes input parameter must contain all nodes in one bipartite node set,
140
but the dictionary returned contains all nodes from both node sets.
144
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
145
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
146
of Social Network Analysis. Sage Publications.
147
http://www.steveborgatti.com/papers/bhaffiliations.pdf
150
bottom = set(G) - top
152
m = float(len(bottom))
155
bet_max_top = (((m**2)*((s+1)**2))+
160
bet_max_bot = (((n**2)*((p+1)**2))+
163
betweenness = nx.betweenness_centrality(G, normalized=False,
166
betweenness[node]/=bet_max_top
168
betweenness[node]/=bet_max_bot
171
def closeness_centrality(G, nodes, normalized=True):
172
r"""Compute the closeness centrality for nodes in a bipartite network.
174
The closeness of a node is the distance to all other nodes in the
175
graph or in the case that the graph is not connected to all other nodes
176
in the connected component containing that node.
183
nodes : list or container
184
Container with all nodes in one bipartite node set.
186
normalized : bool, optional
187
If True (default) normalize by connected component size.
191
closeness : dictionary
192
Dictionary keyed by node with bipartite closeness centrality
197
betweenness_centrality,
204
The nodes input parameter must conatin all nodes in one bipartite node set,
205
but the dictionary returned contains all nodes from both node sets.
207
Closeness centrality is normalized by the minimum distance possible.
208
In the bipartite case the minimum distance for a node in one bipartite
209
node set is 1 from all nodes in the other node set and 2 from all
210
other nodes in its own set [1]_. Thus the closeness centrality
211
for node `v` in the two bipartite sets `U` with
212
`n` nodes and `V` with `m` nodes is
216
c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U,
218
c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V,
220
where `d` is the sum of the distances from `v` to all
223
Higher values of closeness indicate higher centrality.
225
As in the unipartite case, setting normalized=True causes the
226
values to normalized further to n-1 / size(G)-1 where n is the
227
number of nodes in the connected part of graph containing the
228
node. If the graph is not completely connected, this algorithm
229
computes the closeness centrality for each connected part
234
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
235
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
236
of Social Network Analysis. Sage Publications.
237
http://www.steveborgatti.com/papers/bhaffiliations.pdf
240
path_length=nx.single_source_shortest_path_length
242
bottom = set(G) - top
244
m = float(len(bottom))
246
sp=path_length(G,node)
247
totsp=sum(sp.values())
248
if totsp > 0.0 and len(G) > 1:
249
closeness[node]= (m + 2*(n-1)) / totsp
251
s=(len(sp)-1.0) / ( len(G) - 1 )
256
sp=path_length(G,node)
257
totsp=sum(sp.values())
258
if totsp > 0.0 and len(G) > 1:
259
closeness[node]= (n + 2*(m-1)) / totsp
261
s=(len(sp)-1.0) / ( len(G) - 1 )
added
removed
networkx/algorithms/bipartite/centrality.py
