Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/richclub.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for computing rich-club coefficients.""" | |
2 | |
3 import networkx as nx | |
4 from itertools import accumulate | |
5 from networkx.utils import not_implemented_for | |
6 | |
7 __all__ = ["rich_club_coefficient"] | |
8 | |
9 | |
10 @not_implemented_for("directed") | |
11 @not_implemented_for("multigraph") | |
12 def rich_club_coefficient(G, normalized=True, Q=100, seed=None): | |
13 r"""Returns the rich-club coefficient of the graph `G`. | |
14 | |
15 For each degree *k*, the *rich-club coefficient* is the ratio of the | |
16 number of actual to the number of potential edges for nodes with | |
17 degree greater than *k*: | |
18 | |
19 .. math:: | |
20 | |
21 \phi(k) = \frac{2 E_k}{N_k (N_k - 1)} | |
22 | |
23 where `N_k` is the number of nodes with degree larger than *k*, and | |
24 `E_k` is the number of edges among those nodes. | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX graph | |
29 Undirected graph with neither parallel edges nor self-loops. | |
30 normalized : bool (optional) | |
31 Normalize using randomized network as in [1]_ | |
32 Q : float (optional, default=100) | |
33 If `normalized` is True, perform `Q * m` double-edge | |
34 swaps, where `m` is the number of edges in `G`, to use as a | |
35 null-model for normalization. | |
36 seed : integer, random_state, or None (default) | |
37 Indicator of random number generation state. | |
38 See :ref:`Randomness<randomness>`. | |
39 | |
40 Returns | |
41 ------- | |
42 rc : dictionary | |
43 A dictionary, keyed by degree, with rich-club coefficient values. | |
44 | |
45 Examples | |
46 -------- | |
47 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)]) | |
48 >>> rc = nx.rich_club_coefficient(G, normalized=False, seed=42) | |
49 >>> rc[0] | |
50 0.4 | |
51 | |
52 Notes | |
53 ----- | |
54 The rich club definition and algorithm are found in [1]_. This | |
55 algorithm ignores any edge weights and is not defined for directed | |
56 graphs or graphs with parallel edges or self loops. | |
57 | |
58 Estimates for appropriate values of `Q` are found in [2]_. | |
59 | |
60 References | |
61 ---------- | |
62 .. [1] Julian J. McAuley, Luciano da Fontoura Costa, | |
63 and Tibério S. Caetano, | |
64 "The rich-club phenomenon across complex network hierarchies", | |
65 Applied Physics Letters Vol 91 Issue 8, August 2007. | |
66 https://arxiv.org/abs/physics/0701290 | |
67 .. [2] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon, | |
68 "Uniform generation of random graphs with arbitrary degree | |
69 sequences", 2006. https://arxiv.org/abs/cond-mat/0312028 | |
70 """ | |
71 if nx.number_of_selfloops(G) > 0: | |
72 raise Exception( | |
73 "rich_club_coefficient is not implemented for " "graphs with self loops." | |
74 ) | |
75 rc = _compute_rc(G) | |
76 if normalized: | |
77 # make R a copy of G, randomize with Q*|E| double edge swaps | |
78 # and use rich_club coefficient of R to normalize | |
79 R = G.copy() | |
80 E = R.number_of_edges() | |
81 nx.double_edge_swap(R, Q * E, max_tries=Q * E * 10, seed=seed) | |
82 rcran = _compute_rc(R) | |
83 rc = {k: v / rcran[k] for k, v in rc.items()} | |
84 return rc | |
85 | |
86 | |
87 def _compute_rc(G): | |
88 """Returns the rich-club coefficient for each degree in the graph | |
89 `G`. | |
90 | |
91 `G` is an undirected graph without multiedges. | |
92 | |
93 Returns a dictionary mapping degree to rich-club coefficient for | |
94 that degree. | |
95 | |
96 """ | |
97 deghist = nx.degree_histogram(G) | |
98 total = sum(deghist) | |
99 # Compute the number of nodes with degree greater than `k`, for each | |
100 # degree `k` (omitting the last entry, which is zero). | |
101 nks = (total - cs for cs in accumulate(deghist) if total - cs > 1) | |
102 # Create a sorted list of pairs of edge endpoint degrees. | |
103 # | |
104 # The list is sorted in reverse order so that we can pop from the | |
105 # right side of the list later, instead of popping from the left | |
106 # side of the list, which would have a linear time cost. | |
107 edge_degrees = sorted((sorted(map(G.degree, e)) for e in G.edges()), reverse=True) | |
108 ek = G.number_of_edges() | |
109 k1, k2 = edge_degrees.pop() | |
110 rc = {} | |
111 for d, nk in enumerate(nks): | |
112 while k1 <= d: | |
113 if len(edge_degrees) == 0: | |
114 ek = 0 | |
115 break | |
116 k1, k2 = edge_degrees.pop() | |
117 ek -= 1 | |
118 rc[d] = 2 * ek / (nk * (nk - 1)) | |
119 return rc |