what-when-how
In Depth Tutorials and Information
methods is two-folded. First, spectral clustering methods aim to minimize the cut
between communities, while our randomness framework is based on maximizing
the densities of communities. Second, in traditional spectral clustering methods,
communities are represented by dense clusters in the spectral space of Laplacian or
normal matrix, whereas communities in our framework are represented by quasi-
orthogonal lines in the spectral space of the adjacency matrix. Our proposed frame-
work can quantify randomness at all edge, node, and overall graph levels using the
spectra of the adjacency matrix. It is interesting to explore whether similar frame-
works can also be derived using the spectra of the Laplacian or normal matrix. We
will study this issue in our future work.
4.4 SpectralAnalysisofGraphPerturbation
Two natural edge-based graph perturbation strategies are often applied to protect
link privacy in privacy-preserving social-network analysis.
◾
RandAdd/Del
: We randomly add one edge followed by deleting another edge
and repeat this process
k
times. his strategy preserves the total number of
edges in the original graph.
◾
RandSwitch
: We randomly switch a pair of existing edges (
t
,
w
) and (
u
,
v
)
(satisfying that edge (
t
,
v
) and (
u
,
w
) does not exist in
G
) to (
t
,
v
) and
(
u
,
w
) and repeat it
k
times. his strategy preserves the degree of each
vertex.
Edge randomization may significantly affect the utility of the released random-
ized graph. To preserve utility, we expect certain aggregate characteristics of the
original graph to remain basically unchanged or, at least, for them to be able to be
reconstructed from the randomized graph. Since there are so many graph charac-
teristics, we focus on how randomization affects the spectrum of a graph and give
bounds of the spectrum change. We first empirically show how the spectrum of a
graph and some real-space characteristics are affected by the random perturbation
strategies and then give the bounds of the spectrum changes. Lastly, we present our
advanced spectrum-preserving randomization strategies that can better preserve
structural properties.
4.4.1 Graph Characteristics versus Perturbation:
An Illustrating Example
In this section we empirically show how the graph characteristics (including two
spectral [
λ
1
,
μ
2
] and four real [harmonic mean of the geodesic path, modularity,
transitivity, and subgraph centrality]) vary when
RandAdd/Del
and
RandSwitch
