  Many social networks, e.g., Slashdot and Twitter, can be represented as
directed graphs (digraphs) with two types of links between entities: mutual
(bi-directional) and one-way (uni-directional) connections. Social science
theories reveal that mutual connections are more stable than one-way
connections, and one-way connections exhibit various tendencies to become
mutual connections. It is therefore important to take such tendencies into
account when performing clustering of social networks with both mutual and
one-way connections.
  In this paper, we utilize the dyadic methods to analyze social networks, and
develop a generalized mutuality tendency theory to capture the tendencies of
those node pairs which tend to establish mutual connections more frequently
than those occur by chance. Using these results, we develop a
mutuality-tendency-aware spectral clustering algorithm to identify more stable
clusters by maximizing the within-cluster mutuality tendency and minimizing the
cross-cluster mutuality tendency. Extensive simulation results on synthetic
datasets as well as real online social network datasets such as Slashdot,
demonstrate that our proposed mutuality-tendency-aware spectral clustering
algorithm extracts more stable social community structures than traditional
spectral clustering methods.
