MetaFac: Community discovery via relational hypergraph factorization

Yu Ru Lin, Jimeng Sun, Paul Castro, Ravi Konuru, Hari Sundaram, Aisling Kelliher

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

Abstract

This paper aims at discovering community structure in rich media social networks, through analysis of time-varying, multi-relational data. Community structure represents the latent social context of user actions. It has important applications in information tasks such as search and recommendation. Social media has several unique challenges. (a) In social media, the context of user actions is constantly changing and co-evolving; hence the social context contains time-evolving multi-dimensional relations. (b) The social context is determined by the available system features and is unique in each social media website. In this paper we propose MetaFac (MetaGraph Factorization), a framework that extracts community structures from various social contexts and interactions. Our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multi-relational and multi-dimensional social data; (2) an efficient factorization method for community extraction on a given metagraph; (3) an on-line method to handle time-varying relations through incremental metagraph factorization. Extensive experiments on real-world social data collected from the Digg social media website suggest that our technique is scalable and is able to extract meaningful communities based on the social media contexts. We illustrate the usefulness of our framework through prediction tasks. We outperform baseline methods (including aspect model and tensor analysis) by an order of magnitude.

Original languageEnglish (US)
Title of host publicationKDD '09
Subtitle of host publicationProceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Pages527-535
Number of pages9
DOIs
StatePublished - Nov 16 2009
Event15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09 - Paris, France
Duration: Jun 28 2009Jul 1 2009

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09
CountryFrance
CityParis
Period6/28/097/1/09

Keywords

  • Dynamic social network analysis
  • MetaFac
  • Metagraph factorization
  • Non-negative tensor factorization, community discovery
  • Relational hypergraph

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'MetaFac: Community discovery via relational hypergraph factorization'. Together they form a unique fingerprint.

Cite this