Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/richclub.py @ 1:56ad4e20f292 draft

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