what-when-how
In Depth Tutorials and Information
1.
heedgenonrandomnessR
(
u,v
)
isdeinedas
R u v
(
,
)
=
α α Σ
1
T
=
k
x x
.
u
v
i
=
iu iv
2.
henodenonrandomnessR
(
u
)
isdeinedasR
(
u
)
=
Σ
vÎ
Γ
(
u
)
R
(
u,v
)
,where
Γ
(
u
)
denotestheneighborsetofnodeu.
3.
hegraphnonrandomnessR
G
isdeinedasR
G
=
Σ
(
u,v
)
ÎER
(
u,v
).
4.3.2.1 Edge Nonrandomness:
R
(
u
,
v
)
he spectral coordinates of a node reflect its relative attachment to different com-
munities in
G
. When it comes to the measure of nonrandomness of an edge that
connects two nodes, intuitively, we need to incorporate the relationship of two
nodes' spectral vectors.
he edge nonrandomness measure
R
(
u
,
v
) in Definition 1 can be rewritten as
R u v
(
,
)
=
||
α
|| ||
2
α
|| cos(
α α
,
)
,
u
v
2
u
u
which is determined by the product of ||
α
u
||
2
||
α
v
||
2
and the cosine of the angle
between
α
u
and
α
u
. Generally,
R
(
u
,
v
) tends to be large when
u
and
v
clearly
belong to the same community (since cos(
α
u
,
α
u
) ≈ 1).
R
(
u
,
v
) tends to be small
when (1)
u
and
v
are from two different communities (since cos(
α
u
,
α
u
) ≈ 0); (2)
or either node is (or both nodes are) noisy (since ||
α
u
||
2
||
α
v
|| 2 ≈ 0). his intuitively
reflects the formation of real-world social networks: two individuals within the
same community have relatively higher probability to be connected than those in
different communities.
Figure 4.3(a) plots the distribution of edge nonrandomness values, where the
x
-axis is the cosine value between
α
u
and
α
v
,
while the
y
-axis denotes the product
of the two vector lengths. Figure 4.3(b) shows a snapshot of different types of 441
edges characterized by edge nonrandomness values of the politics book network.
We can observe that distributions of edge nonrandomness values characterized by
different regions reflect different types of edges in the original graph: edges with
large cosine value (plotted along the vertex line
x
= 1 and denoted by the blue
“+”) mostly connect two nodes within the same community; edges with small vec-
tor length product (green “+” and plotted along the line
y
= 0) mostly connect to
noncentral nodes; edges plotted in other areas form bridging edges between the two
communities. All this is consistent with our previous explanations.
4.3.2.2 Node Nonrandomness:
R
(
u
)
A node's nonrandomness is characterized by the nonrandomness of edges con-
nected to this node. his is well understood since edges in social networks often
exhibit patterns that indicate properties of the nodes such as the importance, rank,
or category of the corresponding individuals. Result 1 shows how to calculate node
nonrandomness using the spectral coordinates as well as the first
k
eigenvalues of
the adjacency matrix.
