68
Chapter 5. Modelling asymmetric relationships
By counting the common connections we can get a symmetric matrix; W =
WW , W = W W or W = WW +W W . However, these methods only work well when
it is true that the number of the nodes connected in common is a meaningful value of
local similarity. If this assumption holds true, the degree-discounted symmetrization
method [79] is suitable when the degree of nodes in a network varies.
Chung [20] was the first to present a formal model and proof for use of the
Laplacian approach for directed graphs. This algorithm is based on random walk
strategy in which a transition probability matrix P and its associated stationary distribution Π are used to reconstruct the symmetric matrix.
The weighted cut algorithm is a generalized version of the Laplacian approach
for directed graphs and was developed by Meila and Pentney [57]. Instead of using
the stationary distribution Π as the weight (importance) of each node, the weighted
cut offers a more flexible way to define the node’s weight used to symmetrize the
adjacency matrix of a directed graph. It is always a problem to decide what node
weights should be used to normalize and transform the adjacent matrix to a symmetric Laplacian matrix.
There are some modularity based community structure detection techniques
for directed networks [13, 14, 49]. There is also an earlier version of a non-symmetric
matrix decomposition spectral approach [110]. An overview of approaches for directed networks can be found in Malliaros and Vazirgiannis [56].
However, in the embedding of the above approaches, the directionality between nodes is lost. Thus in the embedding we know the distance between two
nodes A and B, but cannot tell the direction of the original edge that joined them.
This limits the analysis possible within the embedding.
The material in this chapter was first presented in Zheng and Skillicorn [111]
and [114].
Chapter 5. Modelling asymmetric relationships
By counting the common connections we can get a symmetric matrix; W =
WW , W = W W or W = WW +W W . However, these methods only work well when
it is true that the number of the nodes connected in common is a meaningful value of
local similarity. If this assumption holds true, the degree-discounted symmetrization
method [79] is suitable when the degree of nodes in a network varies.
Chung [20] was the first to present a formal model and proof for use of the
Laplacian approach for directed graphs. This algorithm is based on random walk
strategy in which a transition probability matrix P and its associated stationary distribution Π are used to reconstruct the symmetric matrix.
The weighted cut algorithm is a generalized version of the Laplacian approach
for directed graphs and was developed by Meila and Pentney [57]. Instead of using
the stationary distribution Π as the weight (importance) of each node, the weighted
cut offers a more flexible way to define the node’s weight used to symmetrize the
adjacency matrix of a directed graph. It is always a problem to decide what node
weights should be used to normalize and transform the adjacent matrix to a symmetric Laplacian matrix.
There are some modularity based community structure detection techniques
for directed networks [13, 14, 49]. There is also an earlier version of a non-symmetric
matrix decomposition spectral approach [110]. An overview of approaches for directed networks can be found in Malliaros and Vazirgiannis [56].
However, in the embedding of the above approaches, the directionality between nodes is lost. Thus in the embedding we know the distance between two
nodes A and B, but cannot tell the direction of the original edge that joined them.
This limits the analysis possible within the embedding.
The material in this chapter was first presented in Zheng and Skillicorn [111]
and [114].