Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / spectral_graph_forge.py @ 5cef0f13

History | View | Annotate | Download (6.33 KB)

1
#    Copyright (C) 2017-2019 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 low-rank 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
        low-rank approximation of A
48

49
    Notes
50
    -----
51
    Low-rank 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
    low-rank 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 low-rank 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 low-rank 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(n-1):
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")