8.5. Summary
119
relationships tend to be transitive in a natural way (the friend of my friend might
well become my friend), but negative relationships are more complex. The enemy
of my enemy could form an alliance with me against out mutual enemy but, on the
other hand, I might dislike them even more than my immediate enemy. We have
developed a way to balance the similarity implicit in positive relationships with the
dissimilarity implicit in negative relationships. Using it as the basis of embeddings
produces plausible results, looked at from several different perspectives.
Notes
The spectral method for signed graphs proposed by Kunegis et al. [48] can be used
to embed signed networks and do further analysis, such as clustering. However,
their signed graph embedding has an obvious weakness, and is also problematic to
extend from 2-way signed ratio cut and 2-way normalized cut to the k-way clustering
problem [17].
A weighted kernel k-means clustering objective is mathematically equivalent
to a general spectral clustering objective [24] and can outperform spectral methods
in terms of quality, speed, and memory usage. Chiang et al. [17] modified weighted
kernel k-means clustering to apply it to signed graphs. Their signed kernel is similar
to one of our methods, but is a different way to solve this problem. Furthermore, an
embedding map is more meaningful than a simple index of partitions. For example,
the embedding allows us to visualize a graph, and tells us the global quantifiable
similarity between unconnected nodes which a simple clustering cannot do.
There are also other signed graph clustering methods. For example, Yang et
al. [108] proposed an agent-based approach to partition signed networks; Traag and
Bruggeman [98] presented a graph clustering method based on modularity using the
Potts model representation; Anchuri and Magdon-Ismail [1] extended an existing
modularity-based graph-partitioning technique [70] to signed networks. However,
an embedding map is more meaningful than a simple index of partitions.
The approach described in this chapter was first presented in Zheng and Skillicorn [112].
119
relationships tend to be transitive in a natural way (the friend of my friend might
well become my friend), but negative relationships are more complex. The enemy
of my enemy could form an alliance with me against out mutual enemy but, on the
other hand, I might dislike them even more than my immediate enemy. We have
developed a way to balance the similarity implicit in positive relationships with the
dissimilarity implicit in negative relationships. Using it as the basis of embeddings
produces plausible results, looked at from several different perspectives.
Notes
The spectral method for signed graphs proposed by Kunegis et al. [48] can be used
to embed signed networks and do further analysis, such as clustering. However,
their signed graph embedding has an obvious weakness, and is also problematic to
extend from 2-way signed ratio cut and 2-way normalized cut to the k-way clustering
problem [17].
A weighted kernel k-means clustering objective is mathematically equivalent
to a general spectral clustering objective [24] and can outperform spectral methods
in terms of quality, speed, and memory usage. Chiang et al. [17] modified weighted
kernel k-means clustering to apply it to signed graphs. Their signed kernel is similar
to one of our methods, but is a different way to solve this problem. Furthermore, an
embedding map is more meaningful than a simple index of partitions. For example,
the embedding allows us to visualize a graph, and tells us the global quantifiable
similarity between unconnected nodes which a simple clustering cannot do.
There are also other signed graph clustering methods. For example, Yang et
al. [108] proposed an agent-based approach to partition signed networks; Traag and
Bruggeman [98] presented a graph clustering method based on modularity using the
Potts model representation; Anchuri and Magdon-Ismail [1] extended an existing
modularity-based graph-partitioning technique [70] to signed networks. However,
an embedding map is more meaningful than a simple index of partitions.
The approach described in this chapter was first presented in Zheng and Skillicorn [112].