Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/second_order.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 """Copyright (c) 2015 – Thomson Licensing, SAS | |
2 | |
3 Redistribution and use in source and binary forms, with or without | |
4 modification, are permitted (subject to the limitations in the | |
5 disclaimer below) provided that the following conditions are met: | |
6 | |
7 * Redistributions of source code must retain the above copyright | |
8 notice, this list of conditions and the following disclaimer. | |
9 | |
10 * Redistributions in binary form must reproduce the above copyright | |
11 notice, this list of conditions and the following disclaimer in the | |
12 documentation and/or other materials provided with the distribution. | |
13 | |
14 * Neither the name of Thomson Licensing, or Technicolor, nor the names | |
15 of its contributors may be used to endorse or promote products derived | |
16 from this software without specific prior written permission. | |
17 | |
18 NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE | |
19 GRANTED BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT | |
20 HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED | |
21 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | |
22 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
23 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE | |
24 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
25 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
26 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR | |
27 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | |
28 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE | |
29 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN | |
30 IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
31 """ | |
32 | |
33 import networkx as nx | |
34 from networkx.utils import not_implemented_for | |
35 | |
36 # Authors: Erwan Le Merrer (erwan.lemerrer@technicolor.com) | |
37 """ Second order centrality measure.""" | |
38 | |
39 __all__ = ["second_order_centrality"] | |
40 | |
41 | |
42 @not_implemented_for("directed") | |
43 def second_order_centrality(G): | |
44 """Compute the second order centrality for nodes of G. | |
45 | |
46 The second order centrality of a given node is the standard deviation of | |
47 the return times to that node of a perpetual random walk on G: | |
48 | |
49 Parameters | |
50 ---------- | |
51 G : graph | |
52 A NetworkX connected and undirected graph. | |
53 | |
54 Returns | |
55 ------- | |
56 nodes : dictionary | |
57 Dictionary keyed by node with second order centrality as the value. | |
58 | |
59 Examples | |
60 -------- | |
61 >>> G = nx.star_graph(10) | |
62 >>> soc = nx.second_order_centrality(G) | |
63 >>> print(sorted(soc.items(), key=lambda x: x[1])[0][0]) # pick first id | |
64 0 | |
65 | |
66 Raises | |
67 ------ | |
68 NetworkXException | |
69 If the graph G is empty, non connected or has negative weights. | |
70 | |
71 See Also | |
72 -------- | |
73 betweenness_centrality | |
74 | |
75 Notes | |
76 ----- | |
77 Lower values of second order centrality indicate higher centrality. | |
78 | |
79 The algorithm is from Kermarrec, Le Merrer, Sericola and Trédan [1]_. | |
80 | |
81 This code implements the analytical version of the algorithm, i.e., | |
82 there is no simulation of a random walk process involved. The random walk | |
83 is here unbiased (corresponding to eq 6 of the paper [1]_), thus the | |
84 centrality values are the standard deviations for random walk return times | |
85 on the transformed input graph G (equal in-degree at each nodes by adding | |
86 self-loops). | |
87 | |
88 Complexity of this implementation, made to run locally on a single machine, | |
89 is O(n^3), with n the size of G, which makes it viable only for small | |
90 graphs. | |
91 | |
92 References | |
93 ---------- | |
94 .. [1] Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan | |
95 "Second order centrality: Distributed assessment of nodes criticity in | |
96 complex networks", Elsevier Computer Communications 34(5):619-628, 2011. | |
97 """ | |
98 | |
99 try: | |
100 import numpy as np | |
101 except ImportError as e: | |
102 raise ImportError("Requires NumPy: http://numpy.org/") from e | |
103 | |
104 n = len(G) | |
105 | |
106 if n == 0: | |
107 raise nx.NetworkXException("Empty graph.") | |
108 if not nx.is_connected(G): | |
109 raise nx.NetworkXException("Non connected graph.") | |
110 if any(d.get("weight", 0) < 0 for u, v, d in G.edges(data=True)): | |
111 raise nx.NetworkXException("Graph has negative edge weights.") | |
112 | |
113 # balancing G for Metropolis-Hastings random walks | |
114 G = nx.DiGraph(G) | |
115 in_deg = dict(G.in_degree(weight="weight")) | |
116 d_max = max(in_deg.values()) | |
117 for i, deg in in_deg.items(): | |
118 if deg < d_max: | |
119 G.add_edge(i, i, weight=d_max - deg) | |
120 | |
121 P = nx.to_numpy_array(G) | |
122 P /= P.sum(axis=1)[:, np.newaxis] # to transition probability matrix | |
123 | |
124 def _Qj(P, j): | |
125 P = P.copy() | |
126 P[:, j] = 0 | |
127 return P | |
128 | |
129 M = np.empty([n, n]) | |
130 | |
131 for i in range(n): | |
132 M[:, i] = np.linalg.solve( | |
133 np.identity(n) - _Qj(P, i), np.ones([n, 1])[:, 0] | |
134 ) # eq 3 | |
135 | |
136 return dict( | |
137 zip(G.nodes, [np.sqrt(2 * np.sum(M[:, i]) - n * (n + 1)) for i in range(n)]) | |
138 ) # eq 6 |