## File: richclub.py

package info (click to toggle)
python-networkx 1.7~rc1-3
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 # -*- coding: utf-8 -*- import networkx as nx __author__ = """\n""".join(['Ben Edwards', 'Aric Hagberg ']) __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 _) 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 # doctest: +SKIP 0.4 Notes ------ The rich club definition and algorithm are found in _. 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 _. References ---------- ..  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 ..  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