46
Chapter 5. Modelling asymmetric relationships
5.2.1 Validation of the new directed embedding
The above example shows how our approach works. To justify this approach, we
demonstrate that the following two properties hold:
• The connection between the in and out versions of each node is strong enough
to keep them in the same cluster if the graph is partitioned or clustered.
• When applied to an undirected graph, the result is the same as for the conventional Laplacian embedding.
The proofs of these properties are as follows:
Property 1: Consistency in clustering
The proofs can be found in Appendices A and B.
Property 2: Consistency with the undirected Laplacian
For an undirected graph, if λ is an eigenvalue of L with eigenvector f , λ is an eigenvalue of L d with eigenvector
f
f
.
Since matrix W is symmetric for an undirected graph, W = W and din i =
dout i = d i . Thus, T =
3D 0
0 3D
, and
L d
f
f
=
T −
0
W + D in + D out
W + D in + D out
0
f
f
=
3D
−W − 2D
−W − 2D
3D
f
f
=
(3D −W − 2D) f
(−W − 2D + 3D) f
=
(D −W ) f
(D −W ) f
= λ
f
f
Furthermore, the eigenvalues of the other “half” of L d are β with eigenvectors
g
−g
if β is an eigenvalue of 5D+W with eigenvector g. Based on the graph cut point
of view, the eigenvector
g
−g
will separate the in and out copies into two different
groups. The corresponding cut value is so big that we would not consider it as a good
partition. It is the same with the eigenvalue β . Therefore, a good embedding of the
Laplacian matrix L d for an undirected graph is the same as the Laplacian matrix L.
For an undirected graph, if λ is an eigenvalue of L rw with eigenvector f , λ /3
is an eigenvalue of L drw with eigenvector
f
f
.