Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/centrality/group.py: 10%

1"""Group centrality measures."""

3from copy import deepcopy

5import networkx as nx

6from networkx.algorithms.centrality.betweenness import (

7 _accumulate_endpoints,

8 _single_source_dijkstra_path_basic,

9 _single_source_shortest_path_basic,

10)

11from networkx.utils.decorators import not_implemented_for

13__all__ = [

14 "group_betweenness_centrality",

15 "group_closeness_centrality",

16 "group_degree_centrality",

17 "group_in_degree_centrality",

18 "group_out_degree_centrality",

19 "prominent_group",

20]

23@nx._dispatchable(edge_attrs="weight")

24def group_betweenness_centrality(G, C, normalized=True, weight=None, endpoints=False):

25 r"""Compute the group betweenness centrality for a group of nodes.

27 Group betweenness centrality of a group of nodes $C$ is the sum of the

28 fraction of all-pairs shortest paths that pass through any vertex in $C$

30 .. math::

32 c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}

34 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of

35 shortest $(s, t)$-paths, and $\sigma(s, t|C)$ is the number of

36 those paths passing through some node in group $C$. Note that

37 $(s, t)$ are not members of the group ($V-C$ is the set of nodes

38 in $V$ that are not in $C$).

40 Parameters

41 ----------

42 G : graph

43 A NetworkX graph.

45 C : list or set or list of lists or list of sets

46 A group or a list of groups containing nodes which belong to G, for which group betweenness

47 centrality is to be calculated.

49 normalized : bool, optional (default=True)

50 If True, group betweenness is normalized by `1/((|V|-|C|)(|V|-|C|-1))`

51 where `|V|` is the number of nodes in G and `|C|` is the number of nodes in C.

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 The weight of an edge is treated as the length or distance between the two sides.

58 endpoints : bool, optional (default=False)

59 If True include the endpoints in the shortest path counts.

61 Raises

62 ------

63 NodeNotFound

64 If node(s) in C are not present in G.

66 Returns

67 -------

68 betweenness : list of floats or float

69 If C is a single group then return a float. If C is a list with

70 several groups then return a list of group betweenness centralities.

72 See Also

73 --------

74 betweenness_centrality

76 Notes

77 -----

78 Group betweenness centrality is described in [1]_ and its importance discussed in [3]_.

79 The initial implementation of the algorithm is mentioned in [2]_. This function uses

80 an improved algorithm presented in [4]_.

82 The number of nodes in the group must be a maximum of n - 2 where `n`

83 is the total number of nodes in the graph.

85 For weighted graphs the edge weights must be greater than zero.

86 Zero edge weights can produce an infinite number of equal length

87 paths between pairs of nodes.

89 The total number of paths between source and target is counted

90 differently for directed and undirected graphs. Directed paths

91 between "u" and "v" are counted as two possible paths (one each

92 direction) while undirected paths between "u" and "v" are counted

93 as one path. Said another way, the sum in the expression above is

94 over all ``s != t`` for directed graphs and for ``s < t`` for undirected graphs.

97 References

98 ----------

99 .. [1] M G Everett and S P Borgatti:

100 The Centrality of Groups and Classes.

101 Journal of Mathematical Sociology. 23(3): 181-201. 1999.

102 http://www.analytictech.com/borgatti/group_centrality.htm

103 .. [2] Ulrik Brandes:

104 On Variants of Shortest-Path Betweenness

105 Centrality and their Generic Computation.

106 Social Networks 30(2):136-145, 2008.

107 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.9610&rep=rep1&type=pdf

108 .. [3] Sourav Medya et. al.:

109 Group Centrality Maximization via Network Design.

110 SIAM International Conference on Data Mining, SDM 2018, 126–134.

111 https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf

112 .. [4] Rami Puzis, Yuval Elovici, and Shlomi Dolev.

113 "Fast algorithm for successive computation of group betweenness centrality."

114 https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709

115

116 """

117 GBC = [] # initialize betweenness

118 list_of_groups = True

119 # check weather C contains one or many groups

120 if any(el in G for el in C):

121 C = [C]

122 list_of_groups = False

123 set_v = {node for group in C for node in group}

124 if set_v - G.nodes: # element(s) of C not in G

125 raise nx.NodeNotFound(f"The node(s) {set_v - G.nodes} are in C but not in G.")

126

127 # pre-processing

128 PB, sigma, D = _group_preprocessing(G, set_v, weight)

129

130 # the algorithm for each group

131 for group in C:

132 group = set(group) # set of nodes in group

133 # initialize the matrices of the sigma and the PB

134 GBC_group = 0

135 sigma_m = deepcopy(sigma)

136 PB_m = deepcopy(PB)

137 sigma_m_v = deepcopy(sigma_m)

138 PB_m_v = deepcopy(PB_m)

139 for v in group:

140 GBC_group += PB_m[v][v]

141 for x in group:

142 for y in group:

143 dxvy = 0

144 dxyv = 0

145 dvxy = 0

146 if not (

147 sigma_m[x][y] == 0 or sigma_m[x][v] == 0 or sigma_m[v][y] == 0

148 ):

149 if D[x][v] == D[x][y] + D[y][v]:

150 dxyv = sigma_m[x][y] * sigma_m[y][v] / sigma_m[x][v]

151 if D[x][y] == D[x][v] + D[v][y]:

152 dxvy = sigma_m[x][v] * sigma_m[v][y] / sigma_m[x][y]

153 if D[v][y] == D[v][x] + D[x][y]:

154 dvxy = sigma_m[v][x] * sigma[x][y] / sigma[v][y]

155 sigma_m_v[x][y] = sigma_m[x][y] * (1 - dxvy)

156 PB_m_v[x][y] = PB_m[x][y] - PB_m[x][y] * dxvy

157 if y != v:

158 PB_m_v[x][y] -= PB_m[x][v] * dxyv

159 if x != v:

160 PB_m_v[x][y] -= PB_m[v][y] * dvxy

161 sigma_m, sigma_m_v = sigma_m_v, sigma_m

162 PB_m, PB_m_v = PB_m_v, PB_m

163

164 # endpoints

165 v, c = len(G), len(group)

166 if not endpoints:

167 scale = 0

168 # if the graph is connected then subtract the endpoints from

169 # the count for all the nodes in the graph. else count how many

170 # nodes are connected to the group's nodes and subtract that.

171 if nx.is_directed(G):

172 if nx.is_strongly_connected(G):

173 scale = c * (2 * v - c - 1)

174 elif nx.is_connected(G):

175 scale = c * (2 * v - c - 1)

176 if scale == 0:

177 for group_node1 in group:

178 for node in D[group_node1]:

179 if node != group_node1:

180 if node in group:

181 scale += 1

182 else:

183 scale += 2

184 GBC_group -= scale

185

186 # normalized

187 if normalized:

188 scale = 1 / ((v - c) * (v - c - 1))

189 GBC_group *= scale

190

191 # If undirected than count only the undirected edges

192 elif not G.is_directed():

193 GBC_group /= 2

194

195 GBC.append(GBC_group)

196 if list_of_groups:

197 return GBC

198 return GBC[0]

199

200

201def _group_preprocessing(G, set_v, weight):

202 sigma = {}

203 delta = {}

204 D = {}

205 betweenness = dict.fromkeys(G, 0)

206 for s in G:

207 if weight is None: # use BFS

208 S, P, sigma[s], D[s] = _single_source_shortest_path_basic(G, s)

209 else: # use Dijkstra's algorithm

210 S, P, sigma[s], D[s] = _single_source_dijkstra_path_basic(G, s, weight)

211 betweenness, delta[s] = _accumulate_endpoints(betweenness, S, P, sigma[s], s)

212 for i in delta[s]: # add the paths from s to i and rescale sigma

213 if s != i:

214 delta[s][i] += 1

215 if weight is not None:

216 sigma[s][i] = sigma[s][i] / 2

217 # building the path betweenness matrix only for nodes that appear in the group

218 PB = dict.fromkeys(G)

219 for group_node1 in set_v:

220 PB[group_node1] = dict.fromkeys(G, 0.0)

221 for group_node2 in set_v:

222 if group_node2 not in D[group_node1]:

223 continue

224 for node in G:

225 # if node is connected to the two group nodes than continue

226 if group_node2 in D[node] and group_node1 in D[node]:

227 if (

228 D[node][group_node2]

229 == D[node][group_node1] + D[group_node1][group_node2]

230 ):

231 PB[group_node1][group_node2] += (

232 delta[node][group_node2]

233 * sigma[node][group_node1]

234 * sigma[group_node1][group_node2]

235 / sigma[node][group_node2]

236 )

237 return PB, sigma, D

238

239

240@nx._dispatchable(edge_attrs="weight")

241def prominent_group(

242 G, k, weight=None, C=None, endpoints=False, normalized=True, greedy=False

243):

244 r"""Find the prominent group of size $k$ in graph $G$. The prominence of the

245 group is evaluated by the group betweenness centrality.

246

247 Group betweenness centrality of a group of nodes $C$ is the sum of the

248 fraction of all-pairs shortest paths that pass through any vertex in $C$

249

250 .. math::

251

252 c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}

253

254 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of

255 shortest $(s, t)$-paths, and $\sigma(s, t|C)$ is the number of

256 those paths passing through some node in group $C$. Note that

257 $(s, t)$ are not members of the group ($V-C$ is the set of nodes

258 in $V$ that are not in $C$).

259

260 Parameters

261 ----------

262 G : graph

263 A NetworkX graph.

264

265 k : int

266 The number of nodes in the group.

267

268 normalized : bool, optional (default=True)

269 If True, group betweenness is normalized by ``1/((|V|-|C|)(|V|-|C|-1))``

270 where ``|V|`` is the number of nodes in G and ``|C|`` is the number of

271 nodes in C.

272

273 weight : None or string, optional (default=None)

274 If None, all edge weights are considered equal.

275 Otherwise holds the name of the edge attribute used as weight.

276 The weight of an edge is treated as the length or distance between the two sides.

277

278 endpoints : bool, optional (default=False)

279 If True include the endpoints in the shortest path counts.

280

281 C : list or set, optional (default=None)

282 list of nodes which won't be candidates of the prominent group.

283

284 greedy : bool, optional (default=False)

285 Using a naive greedy algorithm in order to find non-optimal prominent

286 group. For scale free networks the results are negligibly below the optimal

287 results.

288

289 Raises

290 ------

291 NodeNotFound

292 If node(s) in C are not present in G.

293

294 Returns

295 -------

296 max_GBC : float

297 The group betweenness centrality of the prominent group.

298

299 max_group : list

300 The list of nodes in the prominent group.

301

302 See Also

303 --------

304 betweenness_centrality, group_betweenness_centrality

305

306 Notes

307 -----

308 Group betweenness centrality is described in [1]_ and its importance discussed in [3]_.

309 The algorithm is described in [2]_ and is based on techniques mentioned in [4]_.

310

311 The number of nodes in the group must be a maximum of ``n - 2`` where ``n``

312 is the total number of nodes in the graph.

313

314 For weighted graphs the edge weights must be greater than zero.

315 Zero edge weights can produce an infinite number of equal length

316 paths between pairs of nodes.

317

318 The total number of paths between source and target is counted

319 differently for directed and undirected graphs. Directed paths

320 between "u" and "v" are counted as two possible paths (one each

321 direction) while undirected paths between "u" and "v" are counted

322 as one path. Said another way, the sum in the expression above is

323 over all ``s != t`` for directed graphs and for ``s < t`` for undirected graphs.

324

325 References

326 ----------

327 .. [1] M G Everett and S P Borgatti:

328 The Centrality of Groups and Classes.

329 Journal of Mathematical Sociology. 23(3): 181-201. 1999.

330 http://www.analytictech.com/borgatti/group_centrality.htm

331 .. [2] Rami Puzis, Yuval Elovici, and Shlomi Dolev:

332 "Finding the Most Prominent Group in Complex Networks"

333 AI communications 20(4): 287-296, 2007.

334 https://www.researchgate.net/profile/Rami_Puzis2/publication/220308855

335 .. [3] Sourav Medya et. al.:

336 Group Centrality Maximization via Network Design.

337 SIAM International Conference on Data Mining, SDM 2018, 126–134.

338 https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf

339 .. [4] Rami Puzis, Yuval Elovici, and Shlomi Dolev.

340 "Fast algorithm for successive computation of group betweenness centrality."

341 https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709

342 """

343 import numpy as np

344 import pandas as pd

345

346 if C is not None:

347 C = set(C)

348 if C - G.nodes: # element(s) of C not in G

349 raise nx.NodeNotFound(f"The node(s) {C - G.nodes} are in C but not in G.")

350 nodes = list(G.nodes - C)

351 else:

352 nodes = list(G.nodes)

353 DF_tree = nx.Graph()

354 DF_tree.__networkx_cache__ = None # Disable caching

355 PB, sigma, D = _group_preprocessing(G, nodes, weight)

356 betweenness = pd.DataFrame.from_dict(PB)

357 if C is not None:

358 for node in C:

359 # remove from the betweenness all the nodes not part of the group

360 betweenness = betweenness.drop(index=node)

361 betweenness = betweenness.drop(columns=node)

362 CL = [node for _, node in sorted(zip(np.diag(betweenness), nodes), reverse=True)]

363 max_GBC = 0

364 max_group = []

365 DF_tree.add_node(

366 1,

367 CL=CL,

368 betweenness=betweenness,

369 GBC=0,

370 GM=[],

371 sigma=sigma,

372 cont=dict(zip(nodes, np.diag(betweenness))),

373 )

374

375 # the algorithm

376 DF_tree.nodes[1]["heu"] = 0

377 for i in range(k):

378 DF_tree.nodes[1]["heu"] += DF_tree.nodes[1]["cont"][DF_tree.nodes[1]["CL"][i]]

379 max_GBC, DF_tree, max_group = _dfbnb(

380 G, k, DF_tree, max_GBC, 1, D, max_group, nodes, greedy

381 )

382

383 v = len(G)

384 if not endpoints:

385 scale = 0

386 # if the graph is connected then subtract the endpoints from

387 # the count for all the nodes in the graph. else count how many

388 # nodes are connected to the group's nodes and subtract that.

389 if nx.is_directed(G):

390 if nx.is_strongly_connected(G):

391 scale = k * (2 * v - k - 1)

392 elif nx.is_connected(G):

393 scale = k * (2 * v - k - 1)

394 if scale == 0:

395 for group_node1 in max_group:

396 for node in D[group_node1]:

397 if node != group_node1:

398 if node in max_group:

399 scale += 1

400 else:

401 scale += 2

402 max_GBC -= scale

403

404 # normalized

405 if normalized:

406 scale = 1 / ((v - k) * (v - k - 1))

407 max_GBC *= scale

408

409 # If undirected then count only the undirected edges

410 elif not G.is_directed():

411 max_GBC /= 2

412 max_GBC = float(f"{max_GBC:.2f}")

413 return max_GBC, max_group

414

415

416def _dfbnb(G, k, DF_tree, max_GBC, root, D, max_group, nodes, greedy):

417 # stopping condition - if we found a group of size k and with higher GBC then prune

418 if len(DF_tree.nodes[root]["GM"]) == k and DF_tree.nodes[root]["GBC"] > max_GBC:

419 return DF_tree.nodes[root]["GBC"], DF_tree, DF_tree.nodes[root]["GM"]

420 # stopping condition - if the size of group members equal to k or there are less than

421 # k - |GM| in the candidate list or the heuristic function plus the GBC is below the

422 # maximal GBC found then prune

423 if (

424 len(DF_tree.nodes[root]["GM"]) == k

425 or len(DF_tree.nodes[root]["CL"]) <= k - len(DF_tree.nodes[root]["GM"])

426 or DF_tree.nodes[root]["GBC"] + DF_tree.nodes[root]["heu"] <= max_GBC

427 ):

428 return max_GBC, DF_tree, max_group

429

430 # finding the heuristic of both children

431 node_p, node_m, DF_tree = _heuristic(k, root, DF_tree, D, nodes, greedy)

432

433 # finding the child with the bigger heuristic + GBC and expand

434 # that node first if greedy then only expand the plus node

435 if greedy:

436 max_GBC, DF_tree, max_group = _dfbnb(

437 G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy

438 )

439

440 elif (

441 DF_tree.nodes[node_p]["GBC"] + DF_tree.nodes[node_p]["heu"]

442 > DF_tree.nodes[node_m]["GBC"] + DF_tree.nodes[node_m]["heu"]

443 ):

444 max_GBC, DF_tree, max_group = _dfbnb(

445 G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy

446 )

447 max_GBC, DF_tree, max_group = _dfbnb(

448 G, k, DF_tree, max_GBC, node_m, D, max_group, nodes, greedy

449 )

450 else:

451 max_GBC, DF_tree, max_group = _dfbnb(

452 G, k, DF_tree, max_GBC, node_m, D, max_group, nodes, greedy

453 )

454 max_GBC, DF_tree, max_group = _dfbnb(

455 G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy

456 )

457 return max_GBC, DF_tree, max_group

458

459

460def _heuristic(k, root, DF_tree, D, nodes, greedy):

461 import numpy as np

462

463 # This helper function add two nodes to DF_tree - one left son and the

464 # other right son, finds their heuristic, CL, GBC, and GM

465 node_p = DF_tree.number_of_nodes() + 1

466 node_m = DF_tree.number_of_nodes() + 2

467 added_node = DF_tree.nodes[root]["CL"][0]

468

469 # adding the plus node

470 DF_tree.add_nodes_from([(node_p, deepcopy(DF_tree.nodes[root]))])

471 DF_tree.nodes[node_p]["GM"].append(added_node)

472 DF_tree.nodes[node_p]["GBC"] += DF_tree.nodes[node_p]["cont"][added_node]

473 root_node = DF_tree.nodes[root]

474 for x in nodes:

475 for y in nodes:

476 dxvy = 0

477 dxyv = 0

478 dvxy = 0

479 if not (

480 root_node["sigma"][x][y] == 0

481 or root_node["sigma"][x][added_node] == 0

482 or root_node["sigma"][added_node][y] == 0

483 ):

484 if D[x][added_node] == D[x][y] + D[y][added_node]:

485 dxyv = (

486 root_node["sigma"][x][y]

487 * root_node["sigma"][y][added_node]

488 / root_node["sigma"][x][added_node]

489 )

490 if D[x][y] == D[x][added_node] + D[added_node][y]:

491 dxvy = (

492 root_node["sigma"][x][added_node]

493 * root_node["sigma"][added_node][y]

494 / root_node["sigma"][x][y]

495 )

496 if D[added_node][y] == D[added_node][x] + D[x][y]:

497 dvxy = (

498 root_node["sigma"][added_node][x]

499 * root_node["sigma"][x][y]

500 / root_node["sigma"][added_node][y]

501 )

502 DF_tree.nodes[node_p]["sigma"][x][y] = root_node["sigma"][x][y] * (1 - dxvy)

503 DF_tree.nodes[node_p]["betweenness"].loc[y, x] = (

504 root_node["betweenness"][x][y] - root_node["betweenness"][x][y] * dxvy

505 )

506 if y != added_node:

507 DF_tree.nodes[node_p]["betweenness"].loc[y, x] -= (

508 root_node["betweenness"][x][added_node] * dxyv

509 )

510 if x != added_node:

511 DF_tree.nodes[node_p]["betweenness"].loc[y, x] -= (

512 root_node["betweenness"][added_node][y] * dvxy

513 )

514

515 DF_tree.nodes[node_p]["CL"] = [

516 node

517 for _, node in sorted(

518 zip(np.diag(DF_tree.nodes[node_p]["betweenness"]), nodes), reverse=True

519 )

520 if node not in DF_tree.nodes[node_p]["GM"]

521 ]

522 DF_tree.nodes[node_p]["cont"] = dict(

523 zip(nodes, np.diag(DF_tree.nodes[node_p]["betweenness"]))

524 )

525 DF_tree.nodes[node_p]["heu"] = 0

526 for i in range(k - len(DF_tree.nodes[node_p]["GM"])):

527 DF_tree.nodes[node_p]["heu"] += DF_tree.nodes[node_p]["cont"][

528 DF_tree.nodes[node_p]["CL"][i]

529 ]

530

531 # adding the minus node - don't insert the first node in the CL to GM

532 # Insert minus node only if isn't greedy type algorithm

533 if not greedy:

534 DF_tree.add_nodes_from([(node_m, deepcopy(DF_tree.nodes[root]))])

535 DF_tree.nodes[node_m]["CL"].pop(0)

536 DF_tree.nodes[node_m]["cont"].pop(added_node)

537 DF_tree.nodes[node_m]["heu"] = 0

538 for i in range(k - len(DF_tree.nodes[node_m]["GM"])):

539 DF_tree.nodes[node_m]["heu"] += DF_tree.nodes[node_m]["cont"][

540 DF_tree.nodes[node_m]["CL"][i]

541 ]

542 else:

543 node_m = None

544

545 return node_p, node_m, DF_tree

546

547

548@nx._dispatchable(edge_attrs="weight")

549def group_closeness_centrality(G, S, weight=None):

550 r"""Compute the group closeness centrality for a group of nodes.

551

552 Group closeness centrality of a group of nodes $S$ is a measure

553 of how close the group is to the other nodes in the graph.

554

555 .. math::

556

557 c_{close}(S) = \frac{|V-S|}{\sum_{v \in V-S} d_{S, v}}

558

559 d_{S, v} = min_{u \in S} (d_{u, v})

560

561 where $V$ is the set of nodes, $d_{S, v}$ is the distance of

562 the group $S$ from $v$ defined as above. ($V-S$ is the set of nodes

563 in $V$ that are not in $S$).

564

565 Parameters

566 ----------

567 G : graph

568 A NetworkX graph.

569

570 S : list or set

571 S is a group of nodes which belong to G, for which group closeness

572 centrality is to be calculated.

573

574 weight : None or string, optional (default=None)

575 If None, all edge weights are considered equal.

576 Otherwise holds the name of the edge attribute used as weight.

577 The weight of an edge is treated as the length or distance between the two sides.

578

579 Raises

580 ------

581 NodeNotFound

582 If node(s) in S are not present in G.

583

584 Returns

585 -------

586 closeness : float

587 Group closeness centrality of the group S.

588

589 See Also

590 --------

591 closeness_centrality

592

593 Notes

594 -----

595 The measure was introduced in [1]_.

596 The formula implemented here is described in [2]_.

597

598 Higher values of closeness indicate greater centrality.

599

600 It is assumed that 1 / 0 is 0 (required in the case of directed graphs,

601 or when a shortest path length is 0).

602

603 The number of nodes in the group must be a maximum of n - 1 where `n`

604 is the total number of nodes in the graph.

605

606 For directed graphs, the incoming distance is utilized here. To use the

607 outward distance, act on `G.reverse()`.

608

609 For weighted graphs the edge weights must be greater than zero.

610 Zero edge weights can produce an infinite number of equal length

611 paths between pairs of nodes.

612

613 References

614 ----------

615 .. [1] M G Everett and S P Borgatti:

616 The Centrality of Groups and Classes.

617 Journal of Mathematical Sociology. 23(3): 181-201. 1999.

618 http://www.analytictech.com/borgatti/group_centrality.htm

619 .. [2] J. Zhao et. al.:

620 Measuring and Maximizing Group Closeness Centrality over

621 Disk Resident Graphs.

622 WWWConference Proceedings, 2014. 689-694.

623 https://doi.org/10.1145/2567948.2579356

624 """

625 if G.is_directed():

626 G = G.reverse() # reverse view

627 closeness = 0 # initialize to 0

628 V = set(G) # set of nodes in G

629 S = set(S) # set of nodes in group S

630 V_S = V - S # set of nodes in V but not S

631 shortest_path_lengths = nx.multi_source_dijkstra_path_length(G, S, weight=weight)

632 # accumulation

633 for v in V_S:

634 try:

635 closeness += shortest_path_lengths[v]

636 except KeyError: # no path exists

637 closeness += 0

638 try:

639 closeness = len(V_S) / closeness

640 except ZeroDivisionError: # 1 / 0 assumed as 0

641 closeness = 0

642 return closeness

643

644

645@nx._dispatchable

646def group_degree_centrality(G, S):

647 """Compute the group degree centrality for a group of nodes.

648

649 Group degree centrality of a group of nodes $S$ is the fraction

650 of non-group members connected to group members.

651

652 Parameters

653 ----------

654 G : graph

655 A NetworkX graph.

656

657 S : list or set

658 S is a group of nodes which belong to G, for which group degree

659 centrality is to be calculated.

660

661 Raises

662 ------

663 NetworkXError

664 If node(s) in S are not in G.

665

666 Returns

667 -------

668 centrality : float

669 Group degree centrality of the group S.

670

671 See Also

672 --------

673 degree_centrality

674 group_in_degree_centrality

675 group_out_degree_centrality

676

677 Notes

678 -----

679 The measure was introduced in [1]_.

680

681 The number of nodes in the group must be a maximum of n - 1 where `n`

682 is the total number of nodes in the graph.

683

684 References

685 ----------

686 .. [1] M G Everett and S P Borgatti:

687 The Centrality of Groups and Classes.

688 Journal of Mathematical Sociology. 23(3): 181-201. 1999.

689 http://www.analytictech.com/borgatti/group_centrality.htm

690 """

691 centrality = len(set().union(*[set(G.neighbors(i)) for i in S]) - set(S))

692 centrality /= len(G.nodes()) - len(S)

693 return centrality

694

695

696@not_implemented_for("undirected")

697@nx._dispatchable

698def group_in_degree_centrality(G, S):

699 """Compute the group in-degree centrality for a group of nodes.

700

701 Group in-degree centrality of a group of nodes $S$ is the fraction

702 of non-group members connected to group members by incoming edges.

703

704 Parameters

705 ----------

706 G : graph

707 A NetworkX graph.

708

709 S : list or set

710 S is a group of nodes which belong to G, for which group in-degree

711 centrality is to be calculated.

712

713 Returns

714 -------

715 centrality : float

716 Group in-degree centrality of the group S.

717

718 Raises

719 ------

720 NetworkXNotImplemented

721 If G is undirected.

722

723 NodeNotFound

724 If node(s) in S are not in G.

725

726 See Also

727 --------

728 degree_centrality

729 group_degree_centrality

730 group_out_degree_centrality

731

732 Notes

733 -----

734 The number of nodes in the group must be a maximum of n - 1 where `n`

735 is the total number of nodes in the graph.

736

737 `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph,

738 so for group in-degree centrality, the reverse graph is used.

739 """

740 return group_degree_centrality(G.reverse(), S)

741

742

743@not_implemented_for("undirected")

744@nx._dispatchable

745def group_out_degree_centrality(G, S):

746 """Compute the group out-degree centrality for a group of nodes.

747

748 Group out-degree centrality of a group of nodes $S$ is the fraction

749 of non-group members connected to group members by outgoing edges.

750

751 Parameters

752 ----------

753 G : graph

754 A NetworkX graph.

755

756 S : list or set

757 S is a group of nodes which belong to G, for which group in-degree

758 centrality is to be calculated.

759

760 Returns

761 -------

762 centrality : float

763 Group out-degree centrality of the group S.

764

765 Raises

766 ------

767 NetworkXNotImplemented

768 If G is undirected.

769

770 NodeNotFound

771 If node(s) in S are not in G.

772

773 See Also

774 --------

775 degree_centrality

776 group_degree_centrality

777 group_in_degree_centrality

778

779 Notes

780 -----

781 The number of nodes in the group must be a maximum of n - 1 where `n`

782 is the total number of nodes in the graph.

783

784 `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph,

785 so for group out-degree centrality, the graph itself is used.

786 """

787 return group_degree_centrality(G, S)