spectral_graph_forge(G, alpha, transformation='identity', seed=None)
This algorithm, called Spectral Graph Forge (SGF), computes the eigenvectors of a given graph adjacency matrix, filters them and builds a random graph with a similar eigenstructure. SGF has been proved to be particularly useful for synthesizing realistic social networks and it can also be used to anonymize graph sensitive data.
Spectral Graph Forge (SGF) generates a random simple graph resembling the global properties of the given one. It leverages the low-rank approximation of the associated adjacency matrix driven by the alpha precision parameter. SGF preserves the number of nodes of the input graph and their ordering. This way, nodes of output graphs resemble the properties of the input one and attributes can be directly mapped.
It considers the graph adjacency matrices which can optionally be transformed to other symmetric real matrices (currently transformation options include identity and modularity). The modularity transformation, in the sense of Newman's modularity matrix allows the focusing on community structure related properties of the graph.
SGF applies a low-rank approximation whose fixed rank is computed from the ratio alpha of the input graph adjacency matrix dimension. This step performs a filtering on the input eigenvectors similar to the low pass filtering common in telecommunications.
The filtered values (after truncation) are used as input to a Bernoulli sampling for constructing a random adjacency matrix.
Ratio representing the percentage of eigenvectors of G to consider, values in [0,1].
Represents the intended matrix linear transformation, possible values are 'identity' and 'modularity'
Indicator of numpy random number generation state. See Randomness<randomness>
.
If transformation has a value different from 'identity' or 'modularity'
A graph with a similar eigenvector structure of the input one.
Returns a random simple graph with spectrum resembling that of G
>>> G = nx.karate_club_graph()See :
... H = nx.spectral_graph_forge(G, 0.3) >>>
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.generators.spectral_graph_forge.spectral_graph_forge
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them