1import networkx as nx 2 3__all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"] 4 5 6def 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 25 See Also 26 -------- 27 betweenness_centrality 28 closeness_centrality 29 :func:`~networkx.algorithms.bipartite.basic.sets` 30 :func:`~networkx.algorithms.bipartite.basic.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 https://dx.doi.org/10.4135/9781446294413.n28 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 73def 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 123 See Also 124 -------- 125 degree_centrality 126 closeness_centrality 127 :func:`~networkx.algorithms.bipartite.basic.sets` 128 :func:`~networkx.algorithms.bipartite.basic.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 https://dx.doi.org/10.4135/9781446294413.n28 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 171def 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 195 See Also 196 -------- 197 betweenness_centrality 198 degree_centrality 199 :func:`~networkx.algorithms.bipartite.basic.sets` 200 :func:`~networkx.algorithms.bipartite.basic.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 https://dx.doi.org/10.4135/9781446294413.n28 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 269