Mutual or unrequited love: Identifying stable clusters in social networks with uni- and bi-directional links

Yanhua Li, Zhi-Li Zhang, Jie Bao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Models for the Web Graph - 9th International Workshop, WAW 2012, Proceedings
Pages113-125
Number of pages13
DOIs
StatePublished - Jul 30 2012
Event9th Workshop on Algorithms and Models for the Web Graph, WAW 2012 - Halifax, NS, Canada
Duration: Jun 22 2012Jun 23 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7323 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th Workshop on Algorithms and Models for the Web Graph, WAW 2012
CountryCanada
CityHalifax, NS
Period6/22/126/23/12

Fingerprint Dive into the research topics of 'Mutual or unrequited love: Identifying stable clusters in social networks with uni- and bi-directional links'. Together they form a unique fingerprint.

Cite this