AnalyzingSociotechnical Networks:ASpectrum Perspective - Socio-Technical Networks - page 88

perturbation strategies are applied. his experiment was conducted on the U.S.
politics book data.
We can observe from Figure 4.4 that the changes of spectral measures display
similar trends as those of real graph characteristics while applying the two pertur-
bation strategies. Especially, as shown in Figures 4.4(b-e), the μ 2 of the Laplacian
matrix displays a very similar pattern as the harmonic mean of the geodesic path,
modularity, and transitivity. Similarly, as shown in Figures 4.4(a)(f ), the λ 1 of the
adjacency matrix displays a similar pattern as the subgraph centrality measure for
both RandAdd/Del and RandSwitch strategies. Networks with community struc-
tures are not resilient to the random perturbation strategy. his is intuitively reason-
able, as shown in Figure 4.4(d). Average vertex-vertex distance may change sharply
when edges across communities are switched with edges within communities.
We can also observe that neither RandAdd/Del nor RandSwitch can well pre-
serve the graph characteristics when we increase k to more than 100. Since we
have 441 edges in this graph, even medium randomization ( k = 100) significantly
decreases the utility of the released graph. Generally, more perturbation can lead
to stronger privacy protection, but it also greatly changes many features of the
network, decreasing information utility. For example, network resilience and com-
munity structure are of particular importance in epidemiology where removal of
vertices or edges in a contact network may correspond to vaccination of individuals
against a disease. hen, the epidemiological solution developed from the randomly
perturbed graph may not be applicable to the real graph. In Section 4.4.3 we shall
investigate how to perturb graphs without changing much network structural fea-
tures such as resilience and community structure.

4.4.2 Theoretical Analysis of Spectral Perturbation

he graph perturbation theory is concerned primarily with changes in eigenvalues
that result from local modifications of a graph such as adding or deleting an edge.
In the following, we let A and A be the adjacency matrices of the original graph G
and the perturbed graph G ′ with spectra λ 1 ≥ λ 2 ≥ … ≥ λ n and λ

≥ λ ≥ … ≥ n , λ 1 2

respectively.
Lemma1: [8] Spectra λ

1

< λ

wheneverG ′ isobtainedfromGbydeletinganedge

1

1

orvertex.Similarly, λ < λ wheneverG ′ isobtainedfromGbyaddinganedgeora 1

nonisolatedvertex .
Lemma 1 shows that any proper subgraph of G has smaller index value λ 1 , and
any supgraph of G has larger index value λ 1 . his is also one reason why we only
focus on the perturbation strategies that keep the number of edges unchanged.
Otherwise, the index of the graph λ 1 may be significantly changed, which will
affect many real-space graph characteristics.
heorem 2 : Weyl's heorem [18]. Given two n × n symmetric matrices A and E,
assumethat λ 1 ≥ λ 2 ≥ … ≥ λ nand Σ 1 ≥ Σ 2 ≥ … ≥ Σ naretheireigenvalues,respectively.
Let A = A+Eand λ

≥ λ ≥ … ≥ n , beitseigenvalues.henWeyl'sinequalitiesare λ 1 2