Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/spectral_graph_forge.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 """Generates graphs with a given eigenvector structure""" | |
2 | |
3 | |
4 import networkx as nx | |
5 from networkx.utils import np_random_state | |
6 | |
7 __all__ = ["spectral_graph_forge"] | |
8 | |
9 | |
10 def _mat_spect_approx(A, level, sorteigs=True, reverse=False, absolute=True): | |
11 """ Returns the low-rank approximation of the given matrix A | |
12 | |
13 Parameters | |
14 ---------- | |
15 A : 2D numpy array | |
16 level : integer | |
17 It represents the fixed rank for the output approximation matrix | |
18 sorteigs : boolean | |
19 Whether eigenvectors should be sorted according to their associated | |
20 eigenvalues before removing the firsts of them | |
21 reverse : boolean | |
22 Whether eigenvectors list should be reversed before removing the firsts | |
23 of them | |
24 absolute : boolean | |
25 Whether eigenvectors should be sorted considering the absolute values | |
26 of the corresponding eigenvalues | |
27 | |
28 Returns | |
29 ------- | |
30 B : 2D numpy array | |
31 low-rank approximation of A | |
32 | |
33 Notes | |
34 ----- | |
35 Low-rank matrix approximation is about finding a fixed rank matrix close | |
36 enough to the input one with respect to a given norm (distance). | |
37 In the case of real symmetric input matrix and euclidean distance, the best | |
38 low-rank approximation is given by the sum of first eigenvector matrices. | |
39 | |
40 References | |
41 ---------- | |
42 .. [1] G. Eckart and G. Young, The approximation of one matrix by another | |
43 of lower rank | |
44 .. [2] L. Mirsky, Symmetric gauge functions and unitarily invariant norms | |
45 | |
46 """ | |
47 | |
48 import numpy as np | |
49 | |
50 d, V = np.linalg.eigh(A) | |
51 d = np.ravel(d) | |
52 n = len(d) | |
53 if sorteigs: | |
54 if absolute: | |
55 k = np.argsort(np.abs(d)) | |
56 else: | |
57 k = np.argsort(d) | |
58 # ordered from the lowest to the highest | |
59 else: | |
60 k = range(n) | |
61 if not reverse: | |
62 k = np.flipud(k) | |
63 | |
64 z = np.zeros(n) | |
65 for i in range(level, n): | |
66 V[:, k[i]] = z | |
67 | |
68 B = V @ np.diag(d) @ V.T | |
69 return B | |
70 | |
71 | |
72 @np_random_state(3) | |
73 def spectral_graph_forge(G, alpha, transformation="identity", seed=None): | |
74 """Returns a random simple graph with spectrum resembling that of `G` | |
75 | |
76 This algorithm, called Spectral Graph Forge (SGF), computes the | |
77 eigenvectors of a given graph adjacency matrix, filters them and | |
78 builds a random graph with a similar eigenstructure. | |
79 SGF has been proved to be particularly useful for synthesizing | |
80 realistic social networks and it can also be used to anonymize | |
81 graph sensitive data. | |
82 | |
83 Parameters | |
84 ---------- | |
85 G : Graph | |
86 alpha : float | |
87 Ratio representing the percentage of eigenvectors of G to consider, | |
88 values in [0,1]. | |
89 transformation : string, optional | |
90 Represents the intended matrix linear transformation, possible values | |
91 are 'identity' and 'modularity' | |
92 seed : integer, random_state, or None (default) | |
93 Indicator of numpy random number generation state. | |
94 See :ref:`Randomness<randomness>`. | |
95 | |
96 Returns | |
97 ------- | |
98 H : Graph | |
99 A graph with a similar eigenvector structure of the input one. | |
100 | |
101 Raises | |
102 ------ | |
103 NetworkXError | |
104 If transformation has a value different from 'identity' or 'modularity' | |
105 | |
106 Notes | |
107 ----- | |
108 Spectral Graph Forge (SGF) generates a random simple graph resembling the | |
109 global properties of the given one. | |
110 It leverages the low-rank approximation of the associated adjacency matrix | |
111 driven by the *alpha* precision parameter. | |
112 SGF preserves the number of nodes of the input graph and their ordering. | |
113 This way, nodes of output graphs resemble the properties of the input one | |
114 and attributes can be directly mapped. | |
115 | |
116 It considers the graph adjacency matrices which can optionally be | |
117 transformed to other symmetric real matrices (currently transformation | |
118 options include *identity* and *modularity*). | |
119 The *modularity* transformation, in the sense of Newman's modularity matrix | |
120 allows the focusing on community structure related properties of the graph. | |
121 | |
122 SGF applies a low-rank approximation whose fixed rank is computed from the | |
123 ratio *alpha* of the input graph adjacency matrix dimension. | |
124 This step performs a filtering on the input eigenvectors similar to the low | |
125 pass filtering common in telecommunications. | |
126 | |
127 The filtered values (after truncation) are used as input to a Bernoulli | |
128 sampling for constructing a random adjacency matrix. | |
129 | |
130 References | |
131 ---------- | |
132 .. [1] L. Baldesi, C. T. Butts, A. Markopoulou, "Spectral Graph Forge: | |
133 Graph Generation Targeting Modularity", IEEE Infocom, '18. | |
134 https://arxiv.org/abs/1801.01715 | |
135 .. [2] M. Newman, "Networks: an introduction", Oxford university press, | |
136 2010 | |
137 | |
138 Examples | |
139 -------- | |
140 >>> G = nx.karate_club_graph() | |
141 >>> H = nx.spectral_graph_forge(G, 0.3) | |
142 >>> | |
143 """ | |
144 | |
145 import numpy as np | |
146 import scipy.stats as stats | |
147 | |
148 available_transformations = ["identity", "modularity"] | |
149 alpha = np.clip(alpha, 0, 1) | |
150 A = nx.to_numpy_array(G) | |
151 n = A.shape[1] | |
152 level = int(round(n * alpha)) | |
153 | |
154 if transformation not in available_transformations: | |
155 msg = f"'{transformation}' is not a valid transformation. " | |
156 msg += f"Transformations: {available_transformations}" | |
157 raise nx.NetworkXError(msg) | |
158 | |
159 K = np.ones((1, n)) @ A | |
160 | |
161 B = A | |
162 if transformation == "modularity": | |
163 B -= K.T @ K / K.sum() | |
164 | |
165 B = _mat_spect_approx(B, level, sorteigs=True, absolute=True) | |
166 | |
167 if transformation == "modularity": | |
168 B += K.T @ K / K.sum() | |
169 | |
170 B = np.clip(B, 0, 1) | |
171 np.fill_diagonal(B, 0) | |
172 | |
173 for i in range(n - 1): | |
174 B[i, i + 1 :] = stats.bernoulli.rvs(B[i, i + 1 :], random_state=seed) | |
175 B[i + 1 :, i] = np.transpose(B[i, i + 1 :]) | |
176 | |
177 H = nx.from_numpy_array(B) | |
178 | |
179 return H |