Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/spectral_graph_forge.py: 18%

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

2 

3 

4import networkx as nx 

5from networkx.utils import np_random_state 

6 

7__all__ = ["spectral_graph_forge"] 

8 

9 

10@np_random_state(3) 

11@nx._dispatch 

12def spectral_graph_forge(G, alpha, transformation="identity", seed=None): 

13 """Returns a random simple graph with spectrum resembling that of `G` 

14 

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

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

17 builds a random graph with a similar eigenstructure. 

18 SGF has been proved to be particularly useful for synthesizing 

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

20 graph sensitive data. 

21 

22 Parameters 

23 ---------- 

24 G : Graph 

25 alpha : float 

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

27 values in [0,1]. 

28 transformation : string, optional 

29 Represents the intended matrix linear transformation, possible values 

30 are 'identity' and 'modularity' 

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

32 Indicator of numpy random number generation state. 

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

34 

35 Returns 

36 ------- 

37 H : Graph 

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

39 

40 Raises 

41 ------ 

42 NetworkXError 

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

44 

45 Notes 

46 ----- 

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

48 global properties of the given one. 

49 It leverages the low-rank approximation of the associated adjacency matrix 

50 driven by the *alpha* precision parameter. 

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

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

53 and attributes can be directly mapped. 

54 

55 It considers the graph adjacency matrices which can optionally be 

56 transformed to other symmetric real matrices (currently transformation 

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

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

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

60 

61 SGF applies a low-rank approximation whose fixed rank is computed from the 

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

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

64 pass filtering common in telecommunications. 

65 

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

67 sampling for constructing a random adjacency matrix. 

68 

69 References 

70 ---------- 

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

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

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

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

75 2010 

76 

77 Examples 

78 -------- 

79 >>> G = nx.karate_club_graph() 

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

81 >>> 

82 """ 

83 import numpy as np 

84 import scipy as sp 

85 

86 available_transformations = ["identity", "modularity"] 

87 alpha = np.clip(alpha, 0, 1) 

88 A = nx.to_numpy_array(G) 

89 n = A.shape[1] 

90 level = round(n * alpha) 

91 

92 if transformation not in available_transformations: 

93 msg = f"{transformation!r} is not a valid transformation. " 

94 msg += f"Transformations: {available_transformations}" 

95 raise nx.NetworkXError(msg) 

96 

97 K = np.ones((1, n)) @ A 

98 

99 B = A 

100 if transformation == "modularity": 

101 B -= K.T @ K / K.sum() 

102 

103 # Compute low-rank approximation of B 

104 evals, evecs = np.linalg.eigh(B) 

105 k = np.argsort(np.abs(evals))[::-1] # indices of evals in descending order 

106 evecs[:, k[np.arange(level, n)]] = 0 # set smallest eigenvectors to 0 

107 B = evecs @ np.diag(evals) @ evecs.T 

108 

109 if transformation == "modularity": 

110 B += K.T @ K / K.sum() 

111 

112 B = np.clip(B, 0, 1) 

113 np.fill_diagonal(B, 0) 

114 

115 for i in range(n - 1): 

116 B[i, i + 1 :] = sp.stats.bernoulli.rvs(B[i, i + 1 :], random_state=seed) 

117 B[i + 1 :, i] = np.transpose(B[i, i + 1 :]) 

118 

119 H = nx.from_numpy_array(B) 

120 

121 return H