Google Research

Scalable Community Discovery from Multi-Faceted Graphs

  • Ahmed Metwally
  • Jia-Yu Pan
  • Minh Doan
  • Christos Faloutsos
2015 IEEE International Conference on Big Data, IEEE, 445 Hoes Lane Piscataway, NJ 08854-4141 USA (to appear)

Abstract

A multi-faceted graph defines several facets on a set of nodes. Each facet is a set of edges that represent the relationships between the nodes in a specific context. Mining multi-faceted graphs have several applications, including finding fraudster rings that launch advertising traffic fraud attacks, tracking IP addresses of botnets over time, analyzing interactions on social networks and co-authorship of scientific papers. We propose NeSim, a distributed efficient clustering algorithm that does soft clustering on individual facets. We also propose optimizations to further improve the scalability, the efficiency and the clusters quality. We employ general purpose graph-clustering algorithms in a novel way to discover communities across facets. Due to the qualities of NeSim, we employ it as a backbone in the distributed MuFace algorithm, which discovers multi-faceted communities. We evaluate the proposed algorithms on several real and synthetic datasets, where NeSim is shown to be superior to MCL, JP and AP, the well-established clustering algorithms. We also report the success stories of MuFace in finding advertisement click rings.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work