Scalable Community Discovery from Multi-Faceted Graphs
Venue
2015 IEEE International Conference on Big Data, IEEE, 445 Hoes Lane Piscataway, NJ 08854-4141 USA (to appear)
Publication Year
2015
Authors
Ahmed Metwally, Jia-Yu Pan, Minh Doan, Christos Faloutsos
BibTeX
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.
