Wang et al ICDM 2010
Citation
Xufei Wang, Lei Tang, Huiji Gao, and Huan Liu. Discovering Overlapping Groups in Social Media. In Proceedings of The 10th IEEE International Conference on Data Mining (ICDM'10), 2010.
Online version
Available on Lei Tang's Website
Summary
This paper focuses on clustering with the purpose of discovering communities or groups in social media. The authors observe that many communities in social networks are overlapping -- users may belong to many communities at once. Previous methods give solutions that partition the network, and are not flexible enough to instead provide a set of overlapping subsets. Their method, however, relies on using other meta-information about the users. This work gives an alternate solution to the problem addressed by co-clustering. The authors introduce a general framework, and give specific applications that employ Cosine similarity, Latent semantic indexing, and Spectral Clustering.
General Framework
The authors propose the following general strategy. Suppose that there are a collection of users and tags available in a social network. Tags are features that are now common in social networks, and can often be associated with users easily. Thus, we can construct a graph in which users and tags are nodes, and edges are only allowed between one tag node and one user node. The authors then propose to create overlapping communities by clustering the edges, rather than the nodes themselves.
Formally, we seek to create a clustering which satisfies:
