ioftools / networkxMiCe / networkxmaster / networkx / algorithms / richclub.py @ 5cef0f13
History  View  Annotate  Download (4.42 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 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 richclub 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 richclub coefficient of the graph `G`.

25 

26 
For each degree *k*, the *richclub 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 selfloops.

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` doubleedge

45 
swaps, where `m` is the number of edges in `G`, to use as a

46 
nullmodel 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 richclub 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 richclub 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/condmat/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 richclub 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 richclub 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
