2012/03/25 by Yanhua Li, Li, Yanhua, Zhili Zhang +3
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1203.5474
openalex publication_date 2012/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.