Accession Number:

ADA555924

Title:

Community Detection in Multi-Dimensional Networks

Descriptive Note:

Corporate Author:

ARIZONA STATE UNIV TEMPE DEPT OF COMPUTER SCIENCE AND ENGINEERING

Personal Author(s):

Report Date:

2010-01-01

Pagination or Media Count:

31.0

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.

Subject Categories:

  • Computer Programming and Software
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE