Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Generates graphs with a given eigenvector structure"""
3import networkx as nx
4from networkx.utils import np_random_state
6__all__ = ["spectral_graph_forge"]
9@np_random_state(3)
10@nx._dispatchable(preserve_edge_attrs={"G": {"weight": 1}}, returns_graph=True)
11def spectral_graph_forge(G, alpha, transformation="identity", seed=None):
12 """Returns a random simple graph with spectrum resembling that of `G`
14 This algorithm, called Spectral Graph Forge (SGF), computes the
15 eigenvectors of a given graph adjacency matrix, filters them and
16 builds a random graph with a similar eigenstructure.
17 SGF has been proved to be particularly useful for synthesizing
18 realistic social networks and it can also be used to anonymize
19 graph sensitive data.
21 Parameters
22 ----------
23 G : Graph
24 alpha : float
25 Ratio representing the percentage of eigenvectors of G to consider,
26 values in [0,1].
27 transformation : string, optional
28 Represents the intended matrix linear transformation, possible values
29 are 'identity' and 'modularity'
30 seed : integer, random_state, or None (default)
31 Indicator of numpy random number generation state.
32 See :ref:`Randomness<randomness>`.
34 Returns
35 -------
36 H : Graph
37 A graph with a similar eigenvector structure of the input one.
39 Raises
40 ------
41 NetworkXError
42 If transformation has a value different from 'identity' or 'modularity'
44 Notes
45 -----
46 Spectral Graph Forge (SGF) generates a random simple graph resembling the
47 global properties of the given one.
48 It leverages the low-rank approximation of the associated adjacency matrix
49 driven by the *alpha* precision parameter.
50 SGF preserves the number of nodes of the input graph and their ordering.
51 This way, nodes of output graphs resemble the properties of the input one
52 and attributes can be directly mapped.
54 It considers the graph adjacency matrices which can optionally be
55 transformed to other symmetric real matrices (currently transformation
56 options include *identity* and *modularity*).
57 The *modularity* transformation, in the sense of Newman's modularity matrix
58 allows the focusing on community structure related properties of the graph.
60 SGF applies a low-rank approximation whose fixed rank is computed from the
61 ratio *alpha* of the input graph adjacency matrix dimension.
62 This step performs a filtering on the input eigenvectors similar to the low
63 pass filtering common in telecommunications.
65 The filtered values (after truncation) are used as input to a Bernoulli
66 sampling for constructing a random adjacency matrix.
68 References
69 ----------
70 .. [1] L. Baldesi, C. T. Butts, A. Markopoulou, "Spectral Graph Forge:
71 Graph Generation Targeting Modularity", IEEE Infocom, '18.
72 https://arxiv.org/abs/1801.01715
73 .. [2] M. Newman, "Networks: an introduction", Oxford university press,
74 2010
76 Examples
77 --------
78 >>> G = nx.karate_club_graph()
79 >>> H = nx.spectral_graph_forge(G, 0.3)
80 >>>
81 """
82 import numpy as np
83 import scipy as sp
85 available_transformations = ["identity", "modularity"]
86 alpha = np.clip(alpha, 0, 1)
87 A = nx.to_numpy_array(G)
88 n = A.shape[1]
89 level = round(n * alpha)
91 if transformation not in available_transformations:
92 msg = f"{transformation!r} is not a valid transformation. "
93 msg += f"Transformations: {available_transformations}"
94 raise nx.NetworkXError(msg)
96 K = np.ones((1, n)) @ A
98 B = A
99 if transformation == "modularity":
100 B -= K.T @ K / K.sum()
102 # Compute low-rank approximation of B
103 evals, evecs = np.linalg.eigh(B)
104 k = np.argsort(np.abs(evals))[::-1] # indices of evals in descending order
105 evecs[:, k[np.arange(level, n)]] = 0 # set smallest eigenvectors to 0
106 B = evecs @ np.diag(evals) @ evecs.T
108 if transformation == "modularity":
109 B += K.T @ K / K.sum()
111 B = np.clip(B, 0, 1)
112 np.fill_diagonal(B, 0)
114 for i in range(n - 1):
115 B[i, i + 1 :] = sp.stats.bernoulli.rvs(B[i, i + 1 :], random_state=seed)
116 B[i + 1 :, i] = np.transpose(B[i, i + 1 :])
118 H = nx.from_numpy_array(B)
120 return H