what-when-how
In Depth Tutorials and Information
29 is based on the
L
1
-constrained eigenvectors of the adjacency matrix; various
community/cluster partition algorithms [30] have been developed based on the
spectrum of Laplacian or normal matrix.
4.3 Spectrum-BasedGraphRandomnessAnalysis
In this section we analyze graph randomness at all granularity levels, from edge
node to the whole graph. We show that all our nonrandomness measures can be
determined by spectral coordinates of nodes in the first
k
-dimensional spectral
space, where
k
corresponds to the number of communities in the graph. We then
present a framework that provides a series of nonrandomness measures at different
levels. Nonrandomness specified at the edge level can help users quantify how dif-
ferent a given interaction is from random interactions. Similarly, nonrandomness
specified at the node level can help users quantify how different a given individual
is from random nodes (those individuals actually not belonging to this social net-
work). In our framework, we first examine how much nonrandomness a given edge
(social interaction) has, then measure a node's nonrandomness by examining the
nonrandomness values of edges connecting to this node. Finally, we derive the
nonrandomness measure of the whole graph by incorporating the nonrandomness
values of all edges within the whole graph.
hroughout this section, we use the politics book network [23] as an example to
illustrate how we deine and calculate graph nonrandomness at various levels. he
politics book network contains 105 nodes and 441 edges as shown in Figure 4.1. In
this network, nodes represent books about U.S. politics sold by the online bookseller
Amazon.com, while edges represent frequent copurchasing of books by the same
buyers on Amazon. Each node is labeled “liberal” (blue), “neutral” (white), or “con-
servative” (red). hese alignments were assigned separately by Mark Newman based
on a reading of the descriptions and reviews of the books posted on Amazon.
4.3.1 Graph Spectral Geometry
Let
xi
be the unit eigenvector of
λ
i
, and let
x
ij
denote the
j
-th entry of
x
i
.
x
x
x
x
1
i
k
n
↓
⎛
x
x
x
x
⎞
11
i
1
k
1
n
1
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎟
⎟
⎟
⎟
⎟
(4.1)
α
→
x
x
x
x
u
⎟
⎟
⎟
⎟
⎟
1
u
iu
ku
nu
x
x
x
x
⎝
1
n
in
kn
nn
⎠
