ioftools / networkxMiCe / networkxmaster / networkx / generators / spectral_graph_forge.py @ 5cef0f13
History  View  Annotate  Download (6.33 KB)
1 
# Copyright (C) 20172019 by


2 
# Luca Baldesi

3 
# BSD license.

4 
#

5 
# Author: Luca Baldesi (luca.baldesi@unitn.it)

6 
"""Generates graphs with a given eigenvector structure"""

7  
8  
9 
import networkx as nx 
10 
from networkx.utils import np_random_state 
11  
12 
__all__ = ['spectral_graph_forge']

13  
14  
15 
def _truncate(x): 
16 
""" Returns the truncated value of x in the interval [0,1]

17 
"""

18  
19 
if x < 0: 
20 
return 0 
21 
if x > 1: 
22 
return 1 
23 
return x

24  
25  
26 
def _mat_spect_approx(A, level, sorteigs=True, reverse=False, absolute=True): 
27 
""" Returns the lowrank approximation of the given matrix A

28 

29 
Parameters

30 


31 
A : numpy matrix

32 
level : integer

33 
It represents the fixed rank for the output approximation matrix

34 
sorteigs : boolean

35 
Whether eigenvectors should be sorted according to their associated

36 
eigenvalues before removing the firsts of them

37 
reverse : boolean

38 
Whether eigenvectors list should be reversed before removing the firsts

39 
of them

40 
absolute : boolean

41 
Whether eigenvectors should be sorted considering the absolute values

42 
of the corresponding eigenvalues

43 

44 
Returns

45 


46 
B : numpy matrix

47 
lowrank approximation of A

48 

49 
Notes

50 


51 
Lowrank matrix approximation is about finding a fixed rank matrix close

52 
enough to the input one with respect to a given norm (distance).

53 
In the case of real symmetric input matrix and euclidean distance, the best

54 
lowrank approximation is given by the sum of first eigenvector matrices.

55 

56 
References

57 


58 
.. [1] G. Eckart and G. Young, The approximation of one matrix by another

59 
of lower rank

60 
.. [2] L. Mirsky, Symmetric gauge functions and unitarily invariant norms

61 

62 
"""

63  
64 
import numpy as np 
65  
66 
d, V = np.linalg.eigh(A) 
67 
d = np.ravel(d) 
68 
n = len(d)

69 
if sorteigs:

70 
if absolute:

71 
k = np.argsort(np.abs(d)) 
72 
else:

73 
k = np.argsort(d) 
74 
# ordered from the lowest to the highest

75 
else:

76 
k = range(n)

77 
if not reverse: 
78 
k = np.flipud(k) 
79  
80 
z = np.zeros((n, 1))

81 
for i in range(level, n): 
82 
V[:, k[i]] = z 
83  
84 
B = V*np.diag(d)*np.transpose(V) 
85 
return B

86  
87  
88 
@np_random_state(3) 
89 
def spectral_graph_forge(G, alpha, transformation='identity', seed=None): 
90 
"""Returns a random simple graph with spectrum resembling that of `G`

91 

92 
This algorithm, called Spectral Graph Forge (SGF), computes the

93 
eigenvectors of a given graph adjacency matrix, filters them and

94 
builds a random graph with a similar eigenstructure.

95 
SGF has been proved to be particularly useful for synthesizing

96 
realistic social networks and it can also be used to anonymize

97 
graph sensitive data.

98 

99 
Parameters

100 


101 
G : Graph

102 
alpha : float

103 
Ratio representing the percentage of eigenvectors of G to consider,

104 
values in [0,1].

105 
transformation : string, optional

106 
Represents the intended matrix linear transformation, possible values

107 
are 'identity' and 'modularity'

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

109 
Indicator of numpy random number generation state.

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

111 

112 
Returns

113 


114 
H : Graph

115 
A graph with a similar eigenvector structure of the input one.

116 

117 
Raises

118 


119 
NetworkXError

120 
If transformation has a value different from 'identity' or 'modularity'

121 

122 
Notes

123 


124 
Spectral Graph Forge (SGF) generates a random simple graph resembling the

125 
global properties of the given one.

126 
It leverages the lowrank approximation of the associated adjacency matrix

127 
driven by the *alpha* precision parameter.

128 
SGF preserves the number of nodes of the input graph and their ordering.

129 
This way, nodes of output graphs resemble the properties of the input one

130 
and attributes can be directly mapped.

131 

132 
It considers the graph adjacency matrices which can optionally be

133 
transformed to other symmetric real matrices (currently transformation

134 
options include *identity* and *modularity*).

135 
The *modularity* transformation, in the sense of Newman's modularity matrix

136 
allows the focusing on community structure related properties of the graph.

137 

138 
SGF applies a lowrank approximation whose fixed rank is computed from the

139 
ratio *alpha* of the input graph adjacency matrix dimension.

140 
This step performs a filtering on the input eigenvectors similar to the low

141 
pass filtering common in telecommunications.

142 

143 
The filtered values (after truncation) are used as input to a Bernoulli

144 
sampling for constructing a random adjacency matrix.

145 

146 
References

147 


148 
.. [1] L. Baldesi, C. T. Butts, A. Markopoulou, "Spectral Graph Forge:

149 
Graph Generation Targeting Modularity", IEEE Infocom, '18.

150 
https://arxiv.org/abs/1801.01715

151 
.. [2] M. Newman, "Networks: an introduction", Oxford university press,

152 
2010

153 

154 
Examples

155 


156 
>>> import networkx as nx

157 
>>> G = nx.karate_club_graph()

158 
>>> H = nx.spectral_graph_forge(G, 0.3)

159 
>>>

160 
"""

161  
162 
import numpy as np 
163 
import scipy.stats as stats 
164  
165 
available_transformations = ['identity', 'modularity'] 
166 
alpha = _truncate(alpha) 
167 
A = nx.to_numpy_matrix(G) 
168 
n = A.shape[1]

169 
level = int(round(n*alpha)) 
170  
171 
if transformation not in available_transformations: 
172 
msg = '\'{0}\' is not a valid transformation. '.format(transformation)

173 
msg += 'Transformations: {0}'.format(available_transformations)

174 
raise nx.NetworkXError(msg)

175  
176 
K = np.ones((1, n)) * A

177  
178 
B = A 
179 
if (transformation == 'modularity'): 
180 
B = np.transpose(K) * K / float(sum(np.ravel(K))) 
181  
182 
B = _mat_spect_approx(B, level, sorteigs=True, absolute=True) 
183  
184 
if (transformation == 'modularity'): 
185 
B += np.transpose(K) * K / float(sum(np.ravel(K))) 
186  
187 
B = np.vectorize(_truncate, otypes=[np.float])(B) 
188 
np.fill_diagonal(B, np.zeros((1, n)))

189  
190 
for i in range(n1): 
191 
B[i, i+1:] = stats.bernoulli.rvs(B[i, i+1:], random_state=seed) 
192 
B[i+1:, i] = np.transpose(B[i, i+1:]) 
193  
194 
H = nx.from_numpy_matrix(B) 
195  
196 
return H

197  
198  
199 
# fixture for nose tests

200 
def setup_module(module): 
201 
from nose import SkipTest 
202 
try:

203 
import numpy 
204 
except:

205 
raise SkipTest("NumPy not available") 
206 
try:

207 
import scipy 
208 
except:

209 
raise SkipTest("SciPy not available") 