Community Detection in Multi-Dimensional Networks
Abstract
The pervasiveness of Web 2.0 and social networking sites has enabled people to interact with each other easily through various social media. For instance, popular sites like Del.icio.us, Flickr, and YouTube allow users to comment on shared content (bookmarks, photos, videos), and users can tag their favorite content. Users can also connect with one another, and subscribe to or become a fan or a follower of others. These diverse activities result in a multi-dimensional network among actors, forming group structures with group members sharing similar interests or a liations. This work systematically addresses two challenges. First, it is challenging to e ectively integrate interactions over multiple dimensions to discover hidden community structures shared by heterogeneous interactions. We show that representative community detection methods for single-dimensional networks can be presented in a uni- ed view. Based on this uni ed view, we present and analyze four possible integration strategies to extend community detection from single-dimensional to multi-dimensional networks. In particular, we propose a novel integration scheme based on structural features. Another challenge is the evaluation of different methods without ground truth information about community membership. We employ a novel cross-dimension network validation procedure to compare the performance of di erent methods. We use synthetic data to deepen our understanding, and real-world data to compare integration strategies as well as baseline methods in a large scale. We study further the computational time of di erent methods, normalization e ect during integration, sensitivity to related parameters, and alternative community detection methods for integration.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2010
- Accession Number
- ADA555924
Entities
People
- Huan Liu
- Lei Tang
- Xufei Wang
Organizations
- Arizona State University