Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/richclub.py: 26%

1"""Functions for computing rich-club coefficients.""" 

2 

3from itertools import accumulate 

4 

5import networkx as nx 

6from networkx.utils import not_implemented_for 

7 

8__all__ = ["rich_club_coefficient"] 

9 

10 

11@not_implemented_for("directed") 

12@not_implemented_for("multigraph") 

13@nx._dispatch 

14def rich_club_coefficient(G, normalized=True, Q=100, seed=None): 

15 r"""Returns the rich-club coefficient of the graph `G`. 

16 

17 For each degree *k*, the *rich-club coefficient* is the ratio of the 

18 number of actual to the number of potential edges for nodes with 

19 degree greater than *k*: 

20 

21 .. math:: 

22 

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

24 

25 where `N_k` is the number of nodes with degree larger than *k*, and 

26 `E_k` is the number of edges among those nodes. 

27 

28 Parameters 

29 ---------- 

30 G : NetworkX graph 

31 Undirected graph with neither parallel edges nor self-loops. 

32 normalized : bool (optional) 

33 Normalize using randomized network as in [1]_ 

34 Q : float (optional, default=100) 

35 If `normalized` is True, perform `Q * m` double-edge 

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

37 null-model for normalization. 

38 seed : integer, random_state, or None (default) 

39 Indicator of random number generation state. 

40 See :ref:`Randomness<randomness>`. 

41 

42 Returns 

43 ------- 

44 rc : dictionary 

45 A dictionary, keyed by degree, with rich-club coefficient values. 

46 

47 Examples 

48 -------- 

49 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)]) 

50 >>> rc = nx.rich_club_coefficient(G, normalized=False, seed=42) 

51 >>> rc[0] 

52 0.4 

53 

54 Notes 

55 ----- 

56 The rich club definition and algorithm are found in [1]_. This 

57 algorithm ignores any edge weights and is not defined for directed 

58 graphs or graphs with parallel edges or self loops. 

59 

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

61 

62 References 

63 ---------- 

64 .. [1] Julian J. McAuley, Luciano da Fontoura Costa, 

65 and Tibério S. Caetano, 

66 "The rich-club phenomenon across complex network hierarchies", 

67 Applied Physics Letters Vol 91 Issue 8, August 2007. 

68 https://arxiv.org/abs/physics/0701290 

69 .. [2] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon, 

70 "Uniform generation of random graphs with arbitrary degree 

71 sequences", 2006. https://arxiv.org/abs/cond-mat/0312028 

72 """ 

73 if nx.number_of_selfloops(G) > 0: 

74 raise Exception( 

75 "rich_club_coefficient is not implemented for " "graphs with self loops." 

76 ) 

77 rc = _compute_rc(G) 

78 if normalized: 

79 # make R a copy of G, randomize with Q*|E| double edge swaps 

80 # and use rich_club coefficient of R to normalize 

81 R = G.copy() 

82 E = R.number_of_edges() 

83 nx.double_edge_swap(R, Q * E, max_tries=Q * E * 10, seed=seed) 

84 rcran = _compute_rc(R) 

85 rc = {k: v / rcran[k] for k, v in rc.items()} 

86 return rc 

87 

88 

89def _compute_rc(G): 

90 """Returns the rich-club coefficient for each degree in the graph 

91 `G`. 

92 

93 `G` is an undirected graph without multiedges. 

94 

95 Returns a dictionary mapping degree to rich-club coefficient for 

96 that degree. 

97 

98 """ 

99 deghist = nx.degree_histogram(G) 

100 total = sum(deghist) 

101 # Compute the number of nodes with degree greater than `k`, for each 

102 # degree `k` (omitting the last entry, which is zero). 

103 nks = (total - cs for cs in accumulate(deghist) if total - cs > 1) 

104 # Create a sorted list of pairs of edge endpoint degrees. 

105 # 

106 # The list is sorted in reverse order so that we can pop from the 

107 # right side of the list later, instead of popping from the left 

108 # side of the list, which would have a linear time cost. 

109 edge_degrees = sorted((sorted(map(G.degree, e)) for e in G.edges()), reverse=True) 

110 ek = G.number_of_edges() 

111 k1, k2 = edge_degrees.pop() 

112 rc = {} 

113 for d, nk in enumerate(nks): 

114 while k1 <= d: 

115 if len(edge_degrees) == 0: 

116 ek = 0 

117 break 

118 k1, k2 = edge_degrees.pop() 

119 ek -= 1 

120 rc[d] = 2 * ek / (nk * (nk - 1)) 

121 return rc