Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links

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.