Source code for networkx.algorithms.richclub

# -*- coding: utf-8 -*-
import networkx as nx
__author__ = """\n""".join(['Ben Edwards',
                            'Aric Hagberg <hagberg@lanl.gov>'])

__all__ = ['rich_club_coefficient']

def rich_club_coefficient(G, normalized=True, Q=100):
    """Return the rich-club coefficient of the graph G.

    The rich-club coefficient is the ratio, for every degree k, of the
    number of actual to the number of potential edges for nodes 
    with degree greater than k: 

    .. math::

        \\phi(k) = \\frac{2 Ek}{Nk(Nk-1)}

    where Nk is the number of nodes with degree larger than k, and Ek
    be the number of edges among those nodes.

    Parameters
    ----------
    G : NetworkX graph 
    normalized : bool (optional)
       Normalize using randomized network (see [1]_)
    Q : float (optional, default=100)
       If normalized=True build a random network by performing 
       Q*M double-edge swaps, where M is the number of edges in G,
       to use as a null-model for normalization.

    Returns
    -------       
    rc : dictionary 
       A dictionary, keyed by degree, with rich club coefficient values.

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

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

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

    References
    ----------
    .. [1] Julian J. McAuley, Luciano da Fontoura Costa, and Tibério S. Caetano,
       "The rich-club phenomenon across complex network hierarchies",
       Applied Physics Letters Vol 91 Issue 8, August 2007.
       http://arxiv.org/abs/physics/0701290
    .. [2] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon,
       "Uniform generation of random graphs with arbitrary degree 
       sequences", 2006. http://arxiv.org/abs/cond-mat/0312028
    """
    if G.is_multigraph() or G.is_directed():
        raise Exception('rich_club_coefficient is not implemented for ',
                        'directed or multiedge graphs.')
    if len(G.selfloop_edges()) > 0:
        raise Exception('rich_club_coefficient is not implemented for ',
                        'graphs with self loops.')
    rc=_compute_rc(G)
    if normalized:
        # make R a copy of G, randomize with Q*|E| double edge swaps
        # and use rich_club coefficient of R to normalize
        R = G.copy()
        E = R.number_of_edges()
        nx.double_edge_swap(R,Q*E,max_tries=Q*E*10)
        rcran=_compute_rc(R)
        for d in rc:
#            if rcran[d] > 0:
            rc[d]/=rcran[d]
    return rc


def _compute_rc(G):
    # compute rich club coefficient for all k degrees in G
    deghist = nx.degree_histogram(G)
    total = sum(deghist)
    # number of nodes with degree > k (omit last entry which is zero)
    nks = [total-cs for cs in nx.utils.cumulative_sum(deghist) if total-cs > 1]
    deg=G.degree()
    edge_degrees=sorted(sorted((deg[u],deg[v])) for u,v in G.edges_iter()) 
    ek=G.number_of_edges()
    k1,k2=edge_degrees.pop(0)
    rc={}
    for d,nk in zip(range(len(nks)),nks):         
        while k1 <= d:
            if len(edge_degrees)==0:
                break
            k1,k2=edge_degrees.pop(0)
            ek-=1
        rc[d] = 2.0*ek/(nk*(nk-1))
    return rc