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

1"""Group centrality measures."""

2from copy import deepcopy

4import networkx as nx

5from networkx.algorithms.centrality.betweenness import (

6 _accumulate_endpoints,

7 _single_source_dijkstra_path_basic,

8 _single_source_shortest_path_basic,

10from networkx.utils.decorators import not_implemented_for

12__all__ = [

13 "group_betweenness_centrality",

14 "group_closeness_centrality",

15 "group_degree_centrality",

16 "group_in_degree_centrality",

17 "group_out_degree_centrality",

18 "prominent_group",

19]

22@nx._dispatch(edge_attrs="weight")

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

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

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

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

29 .. math::

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

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

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

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

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

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

39 Parameters

40 ----------

41 G : graph

42 A NetworkX graph.

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

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

46 centrality is to be calculated.

48 normalized : bool, optional (default=True)

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

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

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

53 If None, all edge weights are considered equal.

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

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

57 endpoints : bool, optional (default=False)

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

60 Raises

61 ------

62 NodeNotFound

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

65 Returns

66 -------

67 betweenness : list of floats or float

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

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

71 See Also

72 --------

73 betweenness_centrality

75 Notes

76 -----

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

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

79 an improved algorithm presented in [4]_.

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

82 is the total number of nodes in the graph.

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

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

86 paths between pairs of nodes.

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

89 differently for directed and undirected graphs. Directed paths

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

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

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

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

96 References

97 ----------

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

99 The Centrality of Groups and Classes.

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

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

102 .. [2] Ulrik Brandes:

103 On Variants of Shortest-Path Betweenness

104 Centrality and their Generic Computation.

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

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

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

108 Group Centrality Maximization via Network Design.

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

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

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

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

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

114

115 """

116 GBC = [] # initialize betweenness

117 list_of_groups = True

118 # check weather C contains one or many groups

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

120 C = [C]

121 list_of_groups = False

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

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

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

125

126 # pre-processing

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

128

129 # the algorithm for each group

130 for group in C:

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

132 # initialize the matrices of the sigma and the PB

133 GBC_group = 0

134 sigma_m = deepcopy(sigma)

135 PB_m = deepcopy(PB)

136 sigma_m_v = deepcopy(sigma_m)

137 PB_m_v = deepcopy(PB_m)

138 for v in group:

139 GBC_group += PB_m[v][v]

140 for x in group:

141 for y in group:

142 dxvy = 0

143 dxyv = 0

144 dvxy = 0

145 if not (

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

147 ):

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

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

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

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

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

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

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

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

156 if y != v:

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

158 if x != v:

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

160 sigma_m, sigma_m_v = sigma_m_v, sigma_m

161 PB_m, PB_m_v = PB_m_v, PB_m

162

163 # endpoints

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

165 if not endpoints:

166 scale = 0

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

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

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

170 if nx.is_directed(G):

171 if nx.is_strongly_connected(G):

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

173 elif nx.is_connected(G):

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

175 if scale == 0:

176 for group_node1 in group:

177 for node in D[group_node1]:

178 if node != group_node1:

179 if node in group:

180 scale += 1

181 else:

182 scale += 2

183 GBC_group -= scale

184

185 # normalized

186 if normalized:

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

188 GBC_group *= scale

189

190 # If undirected than count only the undirected edges

191 elif not G.is_directed():

192 GBC_group /= 2

193

194 GBC.append(GBC_group)

195 if list_of_groups:

196 return GBC

197 return GBC[0]

198

199

200def _group_preprocessing(G, set_v, weight):

201 sigma = {}

202 delta = {}

203 D = {}

204 betweenness = dict.fromkeys(G, 0)

205 for s in G:

206 if weight is None: # use BFS

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

208 else: # use Dijkstra's algorithm

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

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

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

212 if s != i:

213 delta[s][i] += 1

214 if weight is not None:

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

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

217 PB = dict.fromkeys(G)

218 for group_node1 in set_v:

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

220 for group_node2 in set_v:

221 if group_node2 not in D[group_node1]:

222 continue

223 for node in G:

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

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

226 if (

227 D[node][group_node2]

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

229 ):

230 PB[group_node1][group_node2] += (

231 delta[node][group_node2]

232 * sigma[node][group_node1]

233 * sigma[group_node1][group_node2]

234 / sigma[node][group_node2]

235 )

236 return PB, sigma, D

237

238

239@nx._dispatch(edge_attrs="weight")

240def prominent_group(

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

242):

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

244 group is evaluated by the group betweenness centrality.

245

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

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

248

249 .. math::

250

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

252

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

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

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

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

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

258

259 Parameters

260 ----------

261 G : graph

262 A NetworkX graph.

263

264 k : int

265 The number of nodes in the group.

266

267 normalized : bool, optional (default=True)

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

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

270 nodes in C.

271

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

273 If None, all edge weights are considered equal.

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

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

276

277 endpoints : bool, optional (default=False)

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

279

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

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

282

283 greedy : bool, optional (default=False)

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

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

286 results.

287

288 Raises

289 ------

290 NodeNotFound

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

292

293 Returns

294 -------

295 max_GBC : float

296 The group betweenness centrality of the prominent group.

297

298 max_group : list

299 The list of nodes in the prominent group.

300

301 See Also

302 --------

303 betweenness_centrality, group_betweenness_centrality

304

305 Notes

306 -----

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

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

309

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

311 is the total number of nodes in the graph.

312

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

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

315 paths between pairs of nodes.

316

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

318 differently for directed and undirected graphs. Directed paths

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

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

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

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

323

324 References

325 ----------

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

327 The Centrality of Groups and Classes.

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

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

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

331 "Finding the Most Prominent Group in Complex Networks"

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

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

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

335 Group Centrality Maximization via Network Design.

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

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

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

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

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

341 """

342 import numpy as np

343 import pandas as pd

344

345 if C is not None:

346 C = set(C)

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

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

349 nodes = list(G.nodes - C)

350 else:

351 nodes = list(G.nodes)

352 DF_tree = nx.Graph()

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

354 betweenness = pd.DataFrame.from_dict(PB)

355 if C is not None:

356 for node in C:

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

358 betweenness.drop(index=node, inplace=True)

359 betweenness.drop(columns=node, inplace=True)

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

361 max_GBC = 0

362 max_group = []

363 DF_tree.add_node(

364 1,

365 CL=CL,

366 betweenness=betweenness,

367 GBC=0,

368 GM=[],

369 sigma=sigma,

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

371 )

372

373 # the algorithm

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

375 for i in range(k):

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

377 max_GBC, DF_tree, max_group = _dfbnb(

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

379 )

380

381 v = len(G)

382 if not endpoints:

383 scale = 0

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

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

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

387 if nx.is_directed(G):

388 if nx.is_strongly_connected(G):

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

390 elif nx.is_connected(G):

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

392 if scale == 0:

393 for group_node1 in max_group:

394 for node in D[group_node1]:

395 if node != group_node1:

396 if node in max_group:

397 scale += 1

398 else:

399 scale += 2

400 max_GBC -= scale

401

402 # normalized

403 if normalized:

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

405 max_GBC *= scale

406

407 # If undirected then count only the undirected edges

408 elif not G.is_directed():

409 max_GBC /= 2

410 max_GBC = float("%.2f" % max_GBC)

411 return max_GBC, max_group

412

413

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

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

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

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

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

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

420 # maximal GBC found then prune

421 if (

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

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

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

425 ):

426 return max_GBC, DF_tree, max_group

427

428 # finding the heuristic of both children

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

430

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

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

433 if greedy:

434 max_GBC, DF_tree, max_group = _dfbnb(

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

436 )

437

438 elif (

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

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

441 ):

442 max_GBC, DF_tree, max_group = _dfbnb(

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

444 )

445 max_GBC, DF_tree, max_group = _dfbnb(

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

447 )

448 else:

449 max_GBC, DF_tree, max_group = _dfbnb(

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

451 )

452 max_GBC, DF_tree, max_group = _dfbnb(

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

454 )

455 return max_GBC, DF_tree, max_group

456

457

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

459 import numpy as np

460

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

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

463 node_p = DF_tree.number_of_nodes() + 1

464 node_m = DF_tree.number_of_nodes() + 2

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

466

467 # adding the plus node

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

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

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

471 root_node = DF_tree.nodes[root]

472 for x in nodes:

473 for y in nodes:

474 dxvy = 0

475 dxyv = 0

476 dvxy = 0

477 if not (

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

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

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

481 ):

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

483 dxyv = (

484 root_node["sigma"][x][y]

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

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

487 )

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

489 dxvy = (

490 root_node["sigma"][x][added_node]

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

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

493 )

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

495 dvxy = (

496 root_node["sigma"][added_node][x]

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

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

499 )

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

501 DF_tree.nodes[node_p]["betweenness"][x][y] = (

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

503 )

504 if y != added_node:

505 DF_tree.nodes[node_p]["betweenness"][x][y] -= (

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

507 )

508 if x != added_node:

509 DF_tree.nodes[node_p]["betweenness"][x][y] -= (

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

511 )

512

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

514 node

515 for _, node in sorted(

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

517 )

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

519 ]

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

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

522 )

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

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

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

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

527 ]

528

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

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

531 if not greedy:

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

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

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

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

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

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

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

539 ]

540 else:

541 node_m = None

542

543 return node_p, node_m, DF_tree

544

545

546@nx._dispatch(edge_attrs="weight")

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

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

549

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

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

552

553 .. math::

554

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

556

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

558

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

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

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

562

563 Parameters

564 ----------

565 G : graph

566 A NetworkX graph.

567

568 S : list or set

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

570 centrality is to be calculated.

571

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

573 If None, all edge weights are considered equal.

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

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

576

577 Raises

578 ------

579 NodeNotFound

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

581

582 Returns

583 -------

584 closeness : float

585 Group closeness centrality of the group S.

586

587 See Also

588 --------

589 closeness_centrality

590

591 Notes

592 -----

593 The measure was introduced in [1]_.

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

595

596 Higher values of closeness indicate greater centrality.

597

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

599 or when a shortest path length is 0).

600

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

602 is the total number of nodes in the graph.

603

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

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

606

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

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

609 paths between pairs of nodes.

610

611 References

612 ----------

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

614 The Centrality of Groups and Classes.

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

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

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

618 Measuring and Maximizing Group Closeness Centrality over

619 Disk Resident Graphs.

620 WWWConference Proceedings, 2014. 689-694.

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

622 """

623 if G.is_directed():

624 G = G.reverse() # reverse view

625 closeness = 0 # initialize to 0

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

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

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

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

630 # accumulation

631 for v in V_S:

632 try:

633 closeness += shortest_path_lengths[v]

634 except KeyError: # no path exists

635 closeness += 0

636 try:

637 closeness = len(V_S) / closeness

638 except ZeroDivisionError: # 1 / 0 assumed as 0

639 closeness = 0

640 return closeness

641

642

643@nx._dispatch

644def group_degree_centrality(G, S):

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

646

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

648 of non-group members connected to group members.

649

650 Parameters

651 ----------

652 G : graph

653 A NetworkX graph.

654

655 S : list or set

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

657 centrality is to be calculated.

658

659 Raises

660 ------

661 NetworkXError

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

663

664 Returns

665 -------

666 centrality : float

667 Group degree centrality of the group S.

668

669 See Also

670 --------

671 degree_centrality

672 group_in_degree_centrality

673 group_out_degree_centrality

674

675 Notes

676 -----

677 The measure was introduced in [1]_.

678

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

680 is the total number of nodes in the graph.

681

682 References

683 ----------

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

685 The Centrality of Groups and Classes.

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

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

688 """

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

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

691 return centrality

692

693

694@not_implemented_for("undirected")

695@nx._dispatch

696def group_in_degree_centrality(G, S):

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

698

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

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

701

702 Parameters

703 ----------

704 G : graph

705 A NetworkX graph.

706

707 S : list or set

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

709 centrality is to be calculated.

710

711 Returns

712 -------

713 centrality : float

714 Group in-degree centrality of the group S.

715

716 Raises

717 ------

718 NetworkXNotImplemented

719 If G is undirected.

720

721 NodeNotFound

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

723

724 See Also

725 --------

726 degree_centrality

727 group_degree_centrality

728 group_out_degree_centrality

729

730 Notes

731 -----

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

733 is the total number of nodes in the graph.

734

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

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

737 """

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

739

740

741@not_implemented_for("undirected")

742@nx._dispatch

743def group_out_degree_centrality(G, S):

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

745

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

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

748

749 Parameters

750 ----------

751 G : graph

752 A NetworkX graph.

753

754 S : list or set

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

756 centrality is to be calculated.

757

758 Returns

759 -------

760 centrality : float

761 Group out-degree centrality of the group S.

762

763 Raises

764 ------

765 NetworkXNotImplemented

766 If G is undirected.

767

768 NodeNotFound

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

770

771 See Also

772 --------

773 degree_centrality

774 group_degree_centrality

775 group_in_degree_centrality

776

777 Notes

778 -----

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

780 is the total number of nodes in the graph.

781

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

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

784 """

785 return group_degree_centrality(G, S)