Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / core.py @ 5cef0f13

History | View | Annotate | Download (15.1 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    Antoine Allard <antoine.allard@phy.ulaval.ca>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Dan Schult (dschult@colgate.edu)
10
#          Jason Grout (jason-sage@creativetrax.com)
11
#          Aric Hagberg (hagberg@lanl.gov)
12
#          Antoine Allard (antoine.allard@phy.ulaval.ca)
13
"""
14
Find the k-cores of a graph.
15

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

18
See the following references for details:
19

20
An O(m) Algorithm for Cores Decomposition of Networks
21
Vladimir Batagelj and Matjaz Zaversnik, 2003.
22
https://arxiv.org/abs/cs.DS/0310049
23

24
Generalized Cores
25
Vladimir Batagelj and Matjaz Zaversnik, 2002.
26
https://arxiv.org/pdf/cs/0202039
27

28
For directed graphs a more general notion is that of D-cores which
29
looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core
30
is the k-core.
31

32
D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy
33
Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011.
34
http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf
35

36
Multi-scale structure and topological anomaly detection via a new network \
37
statistic: The onion decomposition
38
L. Hébert-Dufresne, J. A. Grochow, and A. Allard
39
Scientific Reports 6, 31708 (2016)
40
http://doi.org/10.1038/srep31708
41

42
"""
43
import networkx as nx
44
from networkx.exception import NetworkXError
45
from networkx.utils import not_implemented_for
46

    
47
__all__ = ['core_number', 'find_cores', 'k_core', 'k_shell',
48
           'k_crust', 'k_corona', 'k_truss', 'onion_layers']
49

    
50

    
51
@not_implemented_for('multigraph')
52
def core_number(G):
53
    """Returns the core number for each vertex.
54

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

57
    The core number of a node is the largest value k of a k-core containing
58
    that node.
59

60
    Parameters
61
    ----------
62
    G : NetworkX graph
63
       A graph or directed graph
64

65
    Returns
66
    -------
67
    core_number : dictionary
68
       A dictionary keyed by node to the core number.
69

70
    Raises
71
    ------
72
    NetworkXError
73
        The k-core is not implemented for graphs with self loops
74
        or parallel edges.
75

76
    Notes
77
    -----
78
    Not implemented for graphs with parallel edges or self loops.
79

80
    For directed graphs the node degree is defined to be the
81
    in-degree + out-degree.
82

83
    References
84
    ----------
85
    .. [1] An O(m) Algorithm for Cores Decomposition of Networks
86
       Vladimir Batagelj and Matjaz Zaversnik, 2003.
87
       https://arxiv.org/abs/cs.DS/0310049
88
    """
89
    if nx.number_of_selfloops(G) > 0:
90
        msg = ('Input graph has self loops which is not permitted; '
91
               'Consider using G.remove_edges_from(nx.selfloop_edges(G)).')
92
        raise NetworkXError(msg)
93
    degrees = dict(G.degree())
94
    # Sort nodes by degree.
95
    nodes = sorted(degrees, key=degrees.get)
96
    bin_boundaries = [0]
97
    curr_degree = 0
98
    for i, v in enumerate(nodes):
99
        if degrees[v] > curr_degree:
100
            bin_boundaries.extend([i] * (degrees[v] - curr_degree))
101
            curr_degree = degrees[v]
102
    node_pos = {v: pos for pos, v in enumerate(nodes)}
103
    # The initial guess for the core number of a node is its degree.
104
    core = degrees
105
    nbrs = {v: list(nx.all_neighbors(G, v)) for v in G}
106
    for v in nodes:
107
        for u in nbrs[v]:
108
            if core[u] > core[v]:
109
                nbrs[u].remove(v)
110
                pos = node_pos[u]
111
                bin_start = bin_boundaries[core[u]]
112
                node_pos[u] = bin_start
113
                node_pos[nodes[bin_start]] = pos
114
                nodes[bin_start], nodes[pos] = nodes[pos], nodes[bin_start]
115
                bin_boundaries[core[u]] += 1
116
                core[u] -= 1
117
    return core
118

    
119

    
120
find_cores = core_number
121

    
122

    
123
def _core_subgraph(G, k_filter, k=None, core=None):
124
    """Returns the subgraph induced by nodes passing filter `k_filter`.
125

126
    Parameters
127
    ----------
128
    G : NetworkX graph
129
       The graph or directed graph to process
130
    k_filter : filter function
131
       This function filters the nodes chosen. It takes three inputs:
132
       A node of G, the filter's cutoff, and the core dict of the graph.
133
       The function should return a Boolean value.
134
    k : int, optional
135
      The order of the core. If not specified use the max core number.
136
      This value is used as the cutoff for the filter.
137
    core : dict, optional
138
      Precomputed core numbers keyed by node for the graph `G`.
139
      If not specified, the core numbers will be computed from `G`.
140

141
    """
142
    if core is None:
143
        core = core_number(G)
144
    if k is None:
145
        k = max(core.values())
146
    nodes = (v for v in core if k_filter(v, k, core))
147
    return G.subgraph(nodes).copy()
148

    
149

    
150
def k_core(G, k=None, core_number=None):
151
    """Returns the k-core of G.
152

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

155
    Parameters
156
    ----------
157
    G : NetworkX graph
158
      A graph or directed graph
159
    k : int, optional
160
      The order of the core.  If not specified return the main core.
161
    core_number : dictionary, optional
162
      Precomputed core numbers for the graph G.
163

164
    Returns
165
    -------
166
    G : NetworkX graph
167
      The k-core subgraph
168

169
    Raises
170
    ------
171
    NetworkXError
172
      The k-core is not defined for graphs with self loops or parallel edges.
173

174
    Notes
175
    -----
176
    The main core is the core with the largest degree.
177

178
    Not implemented for graphs with parallel edges or self loops.
179

180
    For directed graphs the node degree is defined to be the
181
    in-degree + out-degree.
182

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

185
    See Also
186
    --------
187
    core_number
188

189
    References
190
    ----------
191
    .. [1] An O(m) Algorithm for Cores Decomposition of Networks
192
       Vladimir Batagelj and Matjaz Zaversnik,  2003.
193
       https://arxiv.org/abs/cs.DS/0310049
194
    """
195
    def k_filter(v, k, c):
196
        return c[v] >= k
197
    return _core_subgraph(G, k_filter, k, core_number)
198

    
199

    
200
def k_shell(G, k=None, core_number=None):
201
    """Returns the k-shell of G.
202

203
    The k-shell is the subgraph induced by nodes with core number k.
204
    That is, nodes in the k-core that are not in the (k+1)-core.
205

206
    Parameters
207
    ----------
208
    G : NetworkX graph
209
      A graph or directed graph.
210
    k : int, optional
211
      The order of the shell. If not specified return the outer shell.
212
    core_number : dictionary, optional
213
      Precomputed core numbers for the graph G.
214

215

216
    Returns
217
    -------
218
    G : NetworkX graph
219
       The k-shell subgraph
220

221
    Raises
222
    ------
223
    NetworkXError
224
        The k-shell is not implemented for graphs with self loops
225
        or parallel edges.
226

227
    Notes
228
    -----
229
    This is similar to k_corona but in that case only neighbors in the
230
    k-core are considered.
231

232
    Not implemented for graphs with parallel edges or self loops.
233

234
    For directed graphs the node degree is defined to be the
235
    in-degree + out-degree.
236

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

239
    See Also
240
    --------
241
    core_number
242
    k_corona
243

244

245
    References
246
    ----------
247
    .. [1] A model of Internet topology using k-shell decomposition
248
       Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,
249
       and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
250
       http://www.pnas.org/content/104/27/11150.full
251
    """
252
    def k_filter(v, k, c):
253
        return c[v] == k
254
    return _core_subgraph(G, k_filter, k, core_number)
255

    
256

    
257
def k_crust(G, k=None, core_number=None):
258
    """Returns the k-crust of G.
259

260
    The k-crust is the graph G with the k-core removed.
261

262
    Parameters
263
    ----------
264
    G : NetworkX graph
265
       A graph or directed graph.
266
    k : int, optional
267
      The order of the shell.  If not specified return the main crust.
268
    core_number : dictionary, optional
269
      Precomputed core numbers for the graph G.
270

271
    Returns
272
    -------
273
    G : NetworkX graph
274
       The k-crust subgraph
275

276
    Raises
277
    ------
278
    NetworkXError
279
        The k-crust is not implemented for graphs with self loops
280
        or parallel edges.
281

282
    Notes
283
    -----
284
    This definition of k-crust is different than the definition in [1]_.
285
    The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm.
286

287
    Not implemented for graphs with parallel edges or self loops.
288

289
    For directed graphs the node degree is defined to be the
290
    in-degree + out-degree.
291

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

294
    See Also
295
    --------
296
    core_number
297

298
    References
299
    ----------
300
    .. [1] A model of Internet topology using k-shell decomposition
301
       Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,
302
       and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
303
       http://www.pnas.org/content/104/27/11150.full
304
    """
305
    # Default for k is one less than in _core_subgraph, so just inline.
306
    #    Filter is c[v] <= k
307
    if core_number is None:
308
        core_number = find_cores(G)
309
    if k is None:
310
        k = max(core_number.values()) - 1
311
    nodes = (v for v in core_number if core_number[v] <= k)
312
    return G.subgraph(nodes).copy()
313

    
314

    
315
def k_corona(G, k, core_number=None):
316
    """Returns the k-corona of G.
317

318
    The k-corona is the subgraph of nodes in the k-core which have
319
    exactly k neighbours in the k-core.
320

321
    Parameters
322
    ----------
323
    G : NetworkX graph
324
       A graph or directed graph
325
    k : int
326
       The order of the corona.
327
    core_number : dictionary, optional
328
       Precomputed core numbers for the graph G.
329

330
    Returns
331
    -------
332
    G : NetworkX graph
333
       The k-corona subgraph
334

335
    Raises
336
    ------
337
    NetworkXError
338
        The k-cornoa is not defined for graphs with self loops or
339
        parallel edges.
340

341
    Notes
342
    -----
343
    Not implemented for graphs with parallel edges or self loops.
344

345
    For directed graphs the node degree is defined to be the
346
    in-degree + out-degree.
347

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

350
    See Also
351
    --------
352
    core_number
353

354
    References
355
    ----------
356
    .. [1]  k -core (bootstrap) percolation on complex networks:
357
       Critical phenomena and nonlocal effects,
358
       A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes,
359
       Phys. Rev. E 73, 056101 (2006)
360
       http://link.aps.org/doi/10.1103/PhysRevE.73.056101
361
    """
362
    def func(v, k, c):
363
        return c[v] == k and k == sum(1 for w in G[v] if c[w] >= k)
364
    return _core_subgraph(G, func, k, core_number)
365

    
366

    
367
@not_implemented_for('directed')
368
@not_implemented_for('multigraph')
369
def k_truss(G, k):
370
    """Returns the k-truss of `G`.
371

372
    The k-truss is the maximal subgraph of `G` which contains at least three
373
    vertices where every edge is incident to at least `k` triangles.
374

375
    Parameters
376
    ----------
377
    G : NetworkX graph
378
      An undirected graph
379
    k : int
380
      The order of the truss
381

382
    Returns
383
    -------
384
    H : NetworkX graph
385
      The k-truss subgraph
386

387
    Raises
388
    ------
389
    NetworkXError
390

391
      The k-truss is not defined for graphs with self loops or parallel edges
392
      or directed graphs.
393

394
    Notes
395
    -----
396
    A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core.
397

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

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

402
    References
403
    ----------
404
    .. [1] Bounds and Algorithms for k-truss. Paul Burkhardt, Vance Faber,
405
       David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2
406
    .. [2] Trusses: Cohesive Subgraphs for Social Network Analysis. Jonathan
407
       Cohen, 2005.
408
    """
409
    H = G.copy()
410

    
411
    n_dropped = 1
412
    while n_dropped > 0:
413
        n_dropped = 0
414
        to_drop = []
415
        seen = set()
416
        for u in H:
417
            nbrs_u = set(H[u])
418
            seen.add(u)
419
            new_nbrs = [v for v in nbrs_u if v not in seen]
420
            for v in new_nbrs:
421
                if len(nbrs_u & set(H[v])) < k:
422
                    to_drop.append((u, v))
423
        H.remove_edges_from(to_drop)
424
        n_dropped = len(to_drop)
425
        H.remove_nodes_from(list(nx.isolates(H)))
426

    
427
    return H
428

    
429

    
430
@not_implemented_for('multigraph')
431
@not_implemented_for('directed')
432
def onion_layers(G):
433
    """Returns the layer of each vertex in the onion decomposition of the graph.
434

435
    The onion decomposition refines the k-core decomposition by providing
436
    information on the internal organization of each k-shell. It is usually
437
    used alongside the `core numbers`.
438

439
    Parameters
440
    ----------
441
    G : NetworkX graph
442
        A simple graph without self loops or parallel edges
443

444
    Returns
445
    -------
446
    od_layers : dictionary
447
        A dictionary keyed by vertex to the onion layer. The layers are
448
        contiguous integers starting at 1.
449

450
    Raises
451
    ------
452
    NetworkXError
453
        The onion decomposition is not implemented for graphs with self loops
454
        or parallel edges or for directed graphs.
455

456
    Notes
457
    -----
458
    Not implemented for graphs with parallel edges or self loops.
459

460
    Not implemented for directed graphs.
461

462
    See Also
463
    --------
464
    core_number
465

466
    References
467
    ----------
468
    .. [1] Multi-scale structure and topological anomaly detection via a new
469
       network statistic: The onion decomposition
470
       L. Hébert-Dufresne, J. A. Grochow, and A. Allard
471
       Scientific Reports 6, 31708 (2016)
472
       http://doi.org/10.1038/srep31708
473
    .. [2] Percolation and the effective structure of complex networks
474
       A. Allard and L. Hébert-Dufresne
475
       Physical Review X 9, 011023 (2019)
476
       http://doi.org/10.1103/PhysRevX.9.011023
477
    """
478
    if nx.number_of_selfloops(G) > 0:
479
        msg = ('Input graph contains self loops which is not permitted; '
480
               'Consider using G.remove_edges_from(nx.selfloop_edges(G)).')
481
        raise NetworkXError(msg)
482
    # Dictionaries to register the k-core/onion decompositions.
483
    od_layers = {}
484
    # Adjacency list
485
    neighbors = {v: list(nx.all_neighbors(G, v)) for v in G}
486
    # Effective degree of nodes.
487
    degrees = dict(G.degree())
488
    # Performs the onion decomposition.
489
    current_core = 1
490
    current_layer = 1
491
    # Sets vertices of degree 0 to layer 1, if any.
492
    isolated_nodes = [v for v in nx.isolates(G)]
493
    if len(isolated_nodes) > 0:
494
        for v in isolated_nodes:
495
            od_layers[v] = current_layer
496
            degrees.pop(v)
497
        current_layer = 2
498
    # Finds the layer for the remaining nodes.
499
    while len(degrees) > 0:
500
        # Sets the order for looking at nodes.
501
        nodes = sorted(degrees, key=degrees.get)
502
        # Sets properly the current core.
503
        min_degree = degrees[nodes[0]]
504
        if min_degree > current_core:
505
            current_core = min_degree
506
        # Identifies vertices in the current layer.
507
        this_layer = []
508
        for n in nodes:
509
            if degrees[n] > current_core:
510
                break
511
            this_layer.append(n)
512
        # Identifies the core/layer of the vertices in the current layer.
513
        for v in this_layer:
514
            od_layers[v] = current_layer
515
            for n in neighbors[v]:
516
                neighbors[n].remove(v)
517
                degrees[n] = degrees[n] - 1
518
            degrees.pop(v)
519
        # Updates the layer count.
520
        current_layer = current_layer + 1
521
    # Returns the dictionaries containing the onion layer of each vertices.
522
    return od_layers