text: # -*- 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.accumulate(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
  
  