Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/core.py: 20%

1"""

2Find the k-cores of a graph.

4The k-core is found by recursively pruning nodes with degrees less than k.

6See the following references for details:

8An O(m) Algorithm for Cores Decomposition of Networks

9Vladimir Batagelj and Matjaz Zaversnik, 2003.

10https://arxiv.org/abs/cs.DS/0310049

12Generalized Cores

13Vladimir Batagelj and Matjaz Zaversnik, 2002.

14https://arxiv.org/pdf/cs/0202039

16For directed graphs a more general notion is that of D-cores which

17looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core

18is the k-core.

20D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy

21Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011.

22http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf

24Multi-scale structure and topological anomaly detection via a new network \

25statistic: The onion decomposition

26L. Hébert-Dufresne, J. A. Grochow, and A. Allard

27Scientific Reports 6, 31708 (2016)

28http://doi.org/10.1038/srep31708

30"""

31import networkx as nx

32from networkx.exception import NetworkXError

33from networkx.utils import not_implemented_for

35__all__ = [

36 "core_number",

37 "k_core",

38 "k_shell",

39 "k_crust",

40 "k_corona",

41 "k_truss",

42 "onion_layers",

43]

46@not_implemented_for("multigraph")

47@nx._dispatch

48def core_number(G):

49 """Returns the core number for each vertex.

51 A k-core is a maximal subgraph that contains nodes of degree k or more.

53 The core number of a node is the largest value k of a k-core containing

54 that node.

56 Parameters

57 ----------

58 G : NetworkX graph

59 A graph or directed graph

61 Returns

62 -------

63 core_number : dictionary

64 A dictionary keyed by node to the core number.

66 Raises

67 ------

68 NetworkXError

69 The k-core is not implemented for graphs with self loops

70 or parallel edges.

72 Notes

73 -----

74 Not implemented for graphs with parallel edges or self loops.

76 For directed graphs the node degree is defined to be the

77 in-degree + out-degree.

79 References

80 ----------

81 .. [1] An O(m) Algorithm for Cores Decomposition of Networks

82 Vladimir Batagelj and Matjaz Zaversnik, 2003.

83 https://arxiv.org/abs/cs.DS/0310049

84 """

85 if nx.number_of_selfloops(G) > 0:

86 msg = (

87 "Input graph has self loops which is not permitted; "

88 "Consider using G.remove_edges_from(nx.selfloop_edges(G))."

89 )

90 raise NetworkXError(msg)

91 degrees = dict(G.degree())

92 # Sort nodes by degree.

93 nodes = sorted(degrees, key=degrees.get)

94 bin_boundaries = [0]

95 curr_degree = 0

96 for i, v in enumerate(nodes):

97 if degrees[v] > curr_degree:

98 bin_boundaries.extend([i] * (degrees[v] - curr_degree))

99 curr_degree = degrees[v]

100 node_pos = {v: pos for pos, v in enumerate(nodes)}

101 # The initial guess for the core number of a node is its degree.

102 core = degrees

103 nbrs = {v: list(nx.all_neighbors(G, v)) for v in G}

104 for v in nodes:

105 for u in nbrs[v]:

106 if core[u] > core[v]:

107 nbrs[u].remove(v)

108 pos = node_pos[u]

109 bin_start = bin_boundaries[core[u]]

110 node_pos[u] = bin_start

111 node_pos[nodes[bin_start]] = pos

112 nodes[bin_start], nodes[pos] = nodes[pos], nodes[bin_start]

113 bin_boundaries[core[u]] += 1

114 core[u] -= 1

115 return core

116

117

118def _core_subgraph(G, k_filter, k=None, core=None):

119 """Returns the subgraph induced by nodes passing filter `k_filter`.

120

121 Parameters

122 ----------

123 G : NetworkX graph

124 The graph or directed graph to process

125 k_filter : filter function

126 This function filters the nodes chosen. It takes three inputs:

127 A node of G, the filter's cutoff, and the core dict of the graph.

128 The function should return a Boolean value.

129 k : int, optional

130 The order of the core. If not specified use the max core number.

131 This value is used as the cutoff for the filter.

132 core : dict, optional

133 Precomputed core numbers keyed by node for the graph `G`.

134 If not specified, the core numbers will be computed from `G`.

135

136 """

137 if core is None:

138 core = core_number(G)

139 if k is None:

140 k = max(core.values())

141 nodes = (v for v in core if k_filter(v, k, core))

142 return G.subgraph(nodes).copy()

143

144

145@nx._dispatch(preserve_all_attrs=True)

146def k_core(G, k=None, core_number=None):

147 """Returns the k-core of G.

148

149 A k-core is a maximal subgraph that contains nodes of degree k or more.

150

151 Parameters

152 ----------

153 G : NetworkX graph

154 A graph or directed graph

155 k : int, optional

156 The order of the core. If not specified return the main core.

157 core_number : dictionary, optional

158 Precomputed core numbers for the graph G.

159

160 Returns

161 -------

162 G : NetworkX graph

163 The k-core subgraph

164

165 Raises

166 ------

167 NetworkXError

168 The k-core is not defined for graphs with self loops or parallel edges.

169

170 Notes

171 -----

172 The main core is the core with the largest degree.

173

174 Not implemented for graphs with parallel edges or self loops.

175

176 For directed graphs the node degree is defined to be the

177 in-degree + out-degree.

178

179 Graph, node, and edge attributes are copied to the subgraph.

180

181 See Also

182 --------

183 core_number

184

185 References

186 ----------

187 .. [1] An O(m) Algorithm for Cores Decomposition of Networks

188 Vladimir Batagelj and Matjaz Zaversnik, 2003.

189 https://arxiv.org/abs/cs.DS/0310049

190 """

191

192 def k_filter(v, k, c):

193 return c[v] >= k

194

195 return _core_subgraph(G, k_filter, k, core_number)

196

197

198@nx._dispatch(preserve_all_attrs=True)

199def k_shell(G, k=None, core_number=None):

200 """Returns the k-shell of G.

201

202 The k-shell is the subgraph induced by nodes with core number k.

203 That is, nodes in the k-core that are not in the (k+1)-core.

204

205 Parameters

206 ----------

207 G : NetworkX graph

208 A graph or directed graph.

209 k : int, optional

210 The order of the shell. If not specified return the outer shell.

211 core_number : dictionary, optional

212 Precomputed core numbers for the graph G.

213

214

215 Returns

216 -------

217 G : NetworkX graph

218 The k-shell subgraph

219

220 Raises

221 ------

222 NetworkXError

223 The k-shell is not implemented for graphs with self loops

224 or parallel edges.

225

226 Notes

227 -----

228 This is similar to k_corona but in that case only neighbors in the

229 k-core are considered.

230

231 Not implemented for graphs with parallel edges or self loops.

232

233 For directed graphs the node degree is defined to be the

234 in-degree + out-degree.

235

236 Graph, node, and edge attributes are copied to the subgraph.

237

238 See Also

239 --------

240 core_number

241 k_corona

242

243

244 References

245 ----------

246 .. [1] A model of Internet topology using k-shell decomposition

247 Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,

248 and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154

249 http://www.pnas.org/content/104/27/11150.full

250 """

251

252 def k_filter(v, k, c):

253 return c[v] == k

254

255 return _core_subgraph(G, k_filter, k, core_number)

256

257

258@nx._dispatch(preserve_all_attrs=True)

259def k_crust(G, k=None, core_number=None):

260 """Returns the k-crust of G.

261

262 The k-crust is the graph G with the edges of the k-core removed

263 and isolated nodes found after the removal of edges are also removed.

264

265 Parameters

266 ----------

267 G : NetworkX graph

268 A graph or directed graph.

269 k : int, optional

270 The order of the shell. If not specified return the main crust.

271 core_number : dictionary, optional

272 Precomputed core numbers for the graph G.

273

274 Returns

275 -------

276 G : NetworkX graph

277 The k-crust subgraph

278

279 Raises

280 ------

281 NetworkXError

282 The k-crust is not implemented for graphs with self loops

283 or parallel edges.

284

285 Notes

286 -----

287 This definition of k-crust is different than the definition in [1]_.

288 The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm.

289

290 Not implemented for graphs with parallel edges or self loops.

291

292 For directed graphs the node degree is defined to be the

293 in-degree + out-degree.

294

295 Graph, node, and edge attributes are copied to the subgraph.

296

297 See Also

298 --------

299 core_number

300

301 References

302 ----------

303 .. [1] A model of Internet topology using k-shell decomposition

304 Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,

305 and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154

306 http://www.pnas.org/content/104/27/11150.full

307 """

308 # Default for k is one less than in _core_subgraph, so just inline.

309 # Filter is c[v] <= k

310 if core_number is None:

311 core_number = nx.core_number(G)

312 if k is None:

313 k = max(core_number.values()) - 1

314 nodes = (v for v in core_number if core_number[v] <= k)

315 return G.subgraph(nodes).copy()

316

317

318@nx._dispatch(preserve_all_attrs=True)

319def k_corona(G, k, core_number=None):

320 """Returns the k-corona of G.

321

322 The k-corona is the subgraph of nodes in the k-core which have

323 exactly k neighbours in the k-core.

324

325 Parameters

326 ----------

327 G : NetworkX graph

328 A graph or directed graph

329 k : int

330 The order of the corona.

331 core_number : dictionary, optional

332 Precomputed core numbers for the graph G.

333

334 Returns

335 -------

336 G : NetworkX graph

337 The k-corona subgraph

338

339 Raises

340 ------

341 NetworkXError

342 The k-corona is not defined for graphs with self loops or

343 parallel edges.

344

345 Notes

346 -----

347 Not implemented for graphs with parallel edges or self loops.

348

349 For directed graphs the node degree is defined to be the

350 in-degree + out-degree.

351

352 Graph, node, and edge attributes are copied to the subgraph.

353

354 See Also

355 --------

356 core_number

357

358 References

359 ----------

360 .. [1] k -core (bootstrap) percolation on complex networks:

361 Critical phenomena and nonlocal effects,

362 A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes,

363 Phys. Rev. E 73, 056101 (2006)

364 http://link.aps.org/doi/10.1103/PhysRevE.73.056101

365 """

366

367 def func(v, k, c):

368 return c[v] == k and k == sum(1 for w in G[v] if c[w] >= k)

369

370 return _core_subgraph(G, func, k, core_number)

371

372

373@not_implemented_for("directed")

374@not_implemented_for("multigraph")

375@nx._dispatch(preserve_all_attrs=True)

376def k_truss(G, k):

377 """Returns the k-truss of `G`.

378

379 The k-truss is the maximal induced subgraph of `G` which contains at least

380 three vertices where every edge is incident to at least `k-2` triangles.

381

382 Parameters

383 ----------

384 G : NetworkX graph

385 An undirected graph

386 k : int

387 The order of the truss

388

389 Returns

390 -------

391 H : NetworkX graph

392 The k-truss subgraph

393

394 Raises

395 ------

396 NetworkXError

397

398 The k-truss is not defined for graphs with self loops, directed graphs

399 and multigraphs.

400

401 Notes

402 -----

403 A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core.

404

405 Not implemented for digraphs or graphs with parallel edges or self loops.

406

407 Graph, node, and edge attributes are copied to the subgraph.

408

409 K-trusses were originally defined in [2] which states that the k-truss

410 is the maximal induced subgraph where each edge belongs to at least

411 `k-2` triangles. A more recent paper, [1], uses a slightly different

412 definition requiring that each edge belong to at least `k` triangles.

413 This implementation uses the original definition of `k-2` triangles.

414

415 References

416 ----------

417 .. [1] Bounds and Algorithms for k-truss. Paul Burkhardt, Vance Faber,

418 David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2

419 .. [2] Trusses: Cohesive Subgraphs for Social Network Analysis. Jonathan

420 Cohen, 2005.

421 """

422 if nx.number_of_selfloops(G) > 0:

423 msg = (

424 "Input graph has self loops which is not permitted; "

425 "Consider using G.remove_edges_from(nx.selfloop_edges(G))."

426 )

427 raise NetworkXError(msg)

428

429 H = G.copy()

430

431 n_dropped = 1

432 while n_dropped > 0:

433 n_dropped = 0

434 to_drop = []

435 seen = set()

436 for u in H:

437 nbrs_u = set(H[u])

438 seen.add(u)

439 new_nbrs = [v for v in nbrs_u if v not in seen]

440 for v in new_nbrs:

441 if len(nbrs_u & set(H[v])) < (k - 2):

442 to_drop.append((u, v))

443 H.remove_edges_from(to_drop)

444 n_dropped = len(to_drop)

445 H.remove_nodes_from(list(nx.isolates(H)))

446

447 return H

448

449

450@not_implemented_for("multigraph")

451@not_implemented_for("directed")

452@nx._dispatch

453def onion_layers(G):

454 """Returns the layer of each vertex in an onion decomposition of the graph.

455

456 The onion decomposition refines the k-core decomposition by providing

457 information on the internal organization of each k-shell. It is usually

458 used alongside the `core numbers`.

459

460 Parameters

461 ----------

462 G : NetworkX graph

463 A simple graph without self loops or parallel edges

464

465 Returns

466 -------

467 od_layers : dictionary

468 A dictionary keyed by vertex to the onion layer. The layers are

469 contiguous integers starting at 1.

470

471 Raises

472 ------

473 NetworkXError

474 The onion decomposition is not implemented for graphs with self loops

475 or parallel edges or for directed graphs.

476

477 Notes

478 -----

479 Not implemented for graphs with parallel edges or self loops.

480

481 Not implemented for directed graphs.

482

483 See Also

484 --------

485 core_number

486

487 References

488 ----------

489 .. [1] Multi-scale structure and topological anomaly detection via a new

490 network statistic: The onion decomposition

491 L. Hébert-Dufresne, J. A. Grochow, and A. Allard

492 Scientific Reports 6, 31708 (2016)

493 http://doi.org/10.1038/srep31708

494 .. [2] Percolation and the effective structure of complex networks

495 A. Allard and L. Hébert-Dufresne

496 Physical Review X 9, 011023 (2019)

497 http://doi.org/10.1103/PhysRevX.9.011023

498 """

499 if nx.number_of_selfloops(G) > 0:

500 msg = (

501 "Input graph contains self loops which is not permitted; "

502 "Consider using G.remove_edges_from(nx.selfloop_edges(G))."

503 )

504 raise NetworkXError(msg)

505 # Dictionaries to register the k-core/onion decompositions.

506 od_layers = {}

507 # Adjacency list

508 neighbors = {v: list(nx.all_neighbors(G, v)) for v in G}

509 # Effective degree of nodes.

510 degrees = dict(G.degree())

511 # Performs the onion decomposition.

512 current_core = 1

513 current_layer = 1

514 # Sets vertices of degree 0 to layer 1, if any.

515 isolated_nodes = list(nx.isolates(G))

516 if len(isolated_nodes) > 0:

517 for v in isolated_nodes:

518 od_layers[v] = current_layer

519 degrees.pop(v)

520 current_layer = 2

521 # Finds the layer for the remaining nodes.

522 while len(degrees) > 0:

523 # Sets the order for looking at nodes.

524 nodes = sorted(degrees, key=degrees.get)

525 # Sets properly the current core.

526 min_degree = degrees[nodes[0]]

527 if min_degree > current_core:

528 current_core = min_degree

529 # Identifies vertices in the current layer.

530 this_layer = []

531 for n in nodes:

532 if degrees[n] > current_core:

533 break

534 this_layer.append(n)

535 # Identifies the core/layer of the vertices in the current layer.

536 for v in this_layer:

537 od_layers[v] = current_layer

538 for n in neighbors[v]:

539 neighbors[n].remove(v)

540 degrees[n] = degrees[n] - 1

541 degrees.pop(v)

542 # Updates the layer count.

543 current_layer = current_layer + 1

544 # Returns the dictionaries containing the onion layer of each vertices.

545 return od_layers