### comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/centrality.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 import networkx as nx
2
3 __all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"]
4
5
6 def degree_centrality(G, nodes):
7 r"""Compute the degree centrality for nodes in a bipartite network.
8
9 The degree centrality for a node v is the fraction of nodes
10 connected to it.
11
12 Parameters
13 ----------
14 G : graph
15 A bipartite network
16
17 nodes : list or container
18 Container with all nodes in one bipartite node set.
19
20 Returns
21 -------
22 centrality : dictionary
23 Dictionary keyed by node with bipartite degree centrality as the value.
24
26 --------
27 betweenness_centrality,
28 closeness_centrality,
29 sets,
30 is_bipartite
31
32 Notes
33 -----
34 The nodes input parameter must contain all nodes in one bipartite node set,
35 but the dictionary returned contains all nodes from both bipartite node
36 sets. See :mod:bipartite documentation <networkx.algorithms.bipartite>
37 for further details on how bipartite graphs are handled in NetworkX.
38
39 For unipartite networks, the degree centrality values are
40 normalized by dividing by the maximum possible degree (which is
41 n-1 where n is the number of nodes in G).
42
43 In the bipartite case, the maximum possible degree of a node in a
44 bipartite node set is the number of nodes in the opposite node set
45 [1]_. The degree centrality for a node v in the bipartite
46 sets U with n nodes and V with m nodes is
47
48 .. math::
49
50 d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
51
52 d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
53
54
55 where deg(v) is the degree of node v.
56
57 References
58 ----------
59 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
60 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
61 of Social Network Analysis. Sage Publications.
62 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
63 """
64 top = set(nodes)
65 bottom = set(G) - top
66 s = 1.0 / len(bottom)
67 centrality = {n: d * s for n, d in G.degree(top)}
68 s = 1.0 / len(top)
69 centrality.update({n: d * s for n, d in G.degree(bottom)})
70 return centrality
71
72
73 def betweenness_centrality(G, nodes):
74 r"""Compute betweenness centrality for nodes in a bipartite network.
75
76 Betweenness centrality of a node v is the sum of the
77 fraction of all-pairs shortest paths that pass through v.
78
79 Values of betweenness are normalized by the maximum possible
80 value which for bipartite graphs is limited by the relative size
81 of the two node sets [1]_.
82
83 Let n be the number of nodes in the node set U and
84 m be the number of nodes in the node set V, then
85 nodes in U are normalized by dividing by
86
87 .. math::
88
89 \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] ,
90
91 where
92
93 .. math::
94
95 s = (n - 1) \div m , t = (n - 1) \mod m ,
96
97 and nodes in V are normalized by dividing by
98
99 .. math::
100
101 \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] ,
102
103 where,
104
105 .. math::
106
107 p = (m - 1) \div n , r = (m - 1) \mod n .
108
109 Parameters
110 ----------
111 G : graph
112 A bipartite graph
113
114 nodes : list or container
115 Container with all nodes in one bipartite node set.
116
117 Returns
118 -------
119 betweenness : dictionary
120 Dictionary keyed by node with bipartite betweenness centrality
121 as the value.
122
124 --------
125 degree_centrality,
126 closeness_centrality,
127 sets,
128 is_bipartite
129
130 Notes
131 -----
132 The nodes input parameter must contain all nodes in one bipartite node set,
133 but the dictionary returned contains all nodes from both node sets.
134 See :mod:bipartite documentation <networkx.algorithms.bipartite>
135 for further details on how bipartite graphs are handled in NetworkX.
136
137
138 References
139 ----------
140 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
141 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
142 of Social Network Analysis. Sage Publications.
143 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
144 """
145 top = set(nodes)
146 bottom = set(G) - top
147 n = float(len(top))
148 m = float(len(bottom))
149 s = (n - 1) // m
150 t = (n - 1) % m
151 bet_max_top = (
152 ((m ** 2) * ((s + 1) ** 2))
153 + (m * (s + 1) * (2 * t - s - 1))
154 - (t * ((2 * s) - t + 3))
155 ) / 2.0
156 p = (m - 1) // n
157 r = (m - 1) % n
158 bet_max_bot = (
159 ((n ** 2) * ((p + 1) ** 2))
160 + (n * (p + 1) * (2 * r - p - 1))
161 - (r * ((2 * p) - r + 3))
162 ) / 2.0
163 betweenness = nx.betweenness_centrality(G, normalized=False, weight=None)
164 for node in top:
165 betweenness[node] /= bet_max_top
166 for node in bottom:
167 betweenness[node] /= bet_max_bot
168 return betweenness
169
170
171 def closeness_centrality(G, nodes, normalized=True):
172 r"""Compute the closeness centrality for nodes in a bipartite network.
173
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.
177
178 Parameters
179 ----------
180 G : graph
181 A bipartite network
182
183 nodes : list or container
184 Container with all nodes in one bipartite node set.
185
186 normalized : bool, optional
187 If True (default) normalize by connected component size.
188
189 Returns
190 -------
191 closeness : dictionary
192 Dictionary keyed by node with bipartite closeness centrality
193 as the value.
194
196 --------
197 betweenness_centrality,
198 degree_centrality
199 sets,
200 is_bipartite
201
202 Notes
203 -----
204 The nodes input parameter must contain all nodes in one bipartite node set,
205 but the dictionary returned contains all nodes from both node sets.
206 See :mod:bipartite documentation <networkx.algorithms.bipartite>
207 for further details on how bipartite graphs are handled in NetworkX.
208
209
210 Closeness centrality is normalized by the minimum distance possible.
211 In the bipartite case the minimum distance for a node in one bipartite
212 node set is 1 from all nodes in the other node set and 2 from all
213 other nodes in its own set [1]_. Thus the closeness centrality
214 for node v in the two bipartite sets U with
215 n nodes and V with m nodes is
216
217 .. math::
218
219 c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U,
220
221 c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V,
222
223 where d is the sum of the distances from v to all
224 other nodes.
225
226 Higher values of closeness indicate higher centrality.
227
228 As in the unipartite case, setting normalized=True causes the
229 values to normalized further to n-1 / size(G)-1 where n is the
230 number of nodes in the connected part of graph containing the
231 node. If the graph is not completely connected, this algorithm
232 computes the closeness centrality for each connected part
233 separately.
234
235 References
236 ----------
237 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
238 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
239 of Social Network Analysis. Sage Publications.
240 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
241 """
242 closeness = {}
243 path_length = nx.single_source_shortest_path_length
244 top = set(nodes)
245 bottom = set(G) - top
246 n = float(len(top))
247 m = float(len(bottom))
248 for node in top:
249 sp = dict(path_length(G, node))
250 totsp = sum(sp.values())
251 if totsp > 0.0 and len(G) > 1:
252 closeness[node] = (m + 2 * (n - 1)) / totsp
253 if normalized:
254 s = (len(sp) - 1.0) / (len(G) - 1)
255 closeness[node] *= s
256 else:
257 closeness[n] = 0.0
258 for node in bottom:
259 sp = dict(path_length(G, node))
260 totsp = sum(sp.values())
261 if totsp > 0.0 and len(G) > 1:
262 closeness[node] = (n + 2 * (m - 1)) / totsp
263 if normalized:
264 s = (len(sp) - 1.0) / (len(G) - 1)
265 closeness[node] *= s
266 else:
267 closeness[n] = 0.0
268 return closeness