Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.42 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Ben Edwards (bedwards@cs.unm.edu)
10
#          Aric Hagberg (hagberg@lanl.gov)
11
"""Functions for computing rich-club coefficients."""
12
from __future__ import division
13

    
14
import networkx as nx
15
from networkx.utils import accumulate
16
from networkx.utils import not_implemented_for
17

    
18
__all__ = ['rich_club_coefficient']
19

    
20

    
21
@not_implemented_for('directed')
22
@not_implemented_for('multigraph')
23
def rich_club_coefficient(G, normalized=True, Q=100, seed=None):
24
    r"""Returns the rich-club coefficient of the graph `G`.
25

26
    For each degree *k*, the *rich-club coefficient* is the ratio of the
27
    number of actual to the number of potential edges for nodes with
28
    degree greater than *k*:
29

30
    .. math::
31

32
        \phi(k) = \frac{2 E_k}{N_k (N_k - 1)}
33

34
    where `N_k` is the number of nodes with degree larger than *k*, and
35
    `E_k` is the number of edges among those nodes.
36

37
    Parameters
38
    ----------
39
    G : NetworkX graph
40
        Undirected graph with neither parallel edges nor self-loops.
41
    normalized : bool (optional)
42
        Normalize using randomized network as in [1]_
43
    Q : float (optional, default=100)
44
        If `normalized` is True, perform `Q * m` double-edge
45
        swaps, where `m` is the number of edges in `G`, to use as a
46
        null-model for normalization.
47
    seed : integer, random_state, or None (default)
48
        Indicator of random number generation state.
49
        See :ref:`Randomness<randomness>`.
50

51
    Returns
52
    -------
53
    rc : dictionary
54
       A dictionary, keyed by degree, with rich-club coefficient values.
55

56
    Examples
57
    --------
58
    >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)])
59
    >>> rc = nx.rich_club_coefficient(G, normalized=False)
60
    >>> rc[0] # doctest: +SKIP
61
    0.4
62

63
    Notes
64
    -----
65
    The rich club definition and algorithm are found in [1]_.  This
66
    algorithm ignores any edge weights and is not defined for directed
67
    graphs or graphs with parallel edges or self loops.
68

69
    Estimates for appropriate values of `Q` are found in [2]_.
70

71
    References
72
    ----------
73
    .. [1] Julian J. McAuley, Luciano da Fontoura Costa,
74
       and Tibério S. Caetano,
75
       "The rich-club phenomenon across complex network hierarchies",
76
       Applied Physics Letters Vol 91 Issue 8, August 2007.
77
       https://arxiv.org/abs/physics/0701290
78
    .. [2] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon,
79
       "Uniform generation of random graphs with arbitrary degree
80
       sequences", 2006. https://arxiv.org/abs/cond-mat/0312028
81
    """
82
    if nx.number_of_selfloops(G) > 0:
83
        raise Exception('rich_club_coefficient is not implemented for '
84
                        'graphs with self loops.')
85
    rc = _compute_rc(G)
86
    if normalized:
87
        # make R a copy of G, randomize with Q*|E| double edge swaps
88
        # and use rich_club coefficient of R to normalize
89
        R = G.copy()
90
        E = R.number_of_edges()
91
        nx.double_edge_swap(R, Q * E, max_tries=Q * E * 10, seed=seed)
92
        rcran = _compute_rc(R)
93
        rc = {k: v / rcran[k] for k, v in rc.items()}
94
    return rc
95

    
96

    
97
def _compute_rc(G):
98
    """Returns the rich-club coefficient for each degree in the graph
99
    `G`.
100

101
    `G` is an undirected graph without multiedges.
102

103
    Returns a dictionary mapping degree to rich-club coefficient for
104
    that degree.
105

106
    """
107
    deghist = nx.degree_histogram(G)
108
    total = sum(deghist)
109
    # Compute the number of nodes with degree greater than `k`, for each
110
    # degree `k` (omitting the last entry, which is zero).
111
    nks = (total - cs for cs in accumulate(deghist) if total - cs > 1)
112
    # Create a sorted list of pairs of edge endpoint degrees.
113
    #
114
    # The list is sorted in reverse order so that we can pop from the
115
    # right side of the list later, instead of popping from the left
116
    # side of the list, which would have a linear time cost.
117
    edge_degrees = sorted((sorted(map(G.degree, e)) for e in G.edges()),
118
                          reverse=True)
119
    ek = G.number_of_edges()
120
    k1, k2 = edge_degrees.pop()
121
    rc = {}
122
    for d, nk in enumerate(nks):
123
        while k1 <= d:
124
            if len(edge_degrees) == 0:
125
                ek = 0
126
                break
127
            k1, k2 = edge_degrees.pop()
128
            ek -= 1
129
        rc[d] = 2 * ek / (nk * (nk - 1))
130
    return rc