HCDF: A Hybrid Community Discovery Framework

Google Tech Talk March 11, 2010 ABSTRACT Presented by Tina Eliassi-Rad. We introduce a novel Bayesian framework for hybrid community discovery in graphs. Our framework, HCDF (short for Hybrid Community Discovery Framework ), can effectively incorporate hints from a number of other community detection algorithms and produce results that outperform the constituent parts. We describe two HCDF-based approaches which are: (1) effective, in terms of link prediction performance and robustness to small perturbations in network structure; (2) consistent, in terms of effectiveness across various application domains; (3) scalable to very large graphs; and (4) nonparametric. Our extensive evaluation on a collection of diverse and large real-world graphs, with millions of links, show that our HCDF-based approaches (a) achieve up to 0.22 improvement in link prediction performance as measured by area under ROC curve (AUC), (b) never have an AUC that drops below 0.91 in the worst case, and (c) find communities that are robust to small perturbations of the network structure as defined by Variation of Information (an entropy-based distance metric). Dr. Tina Eliassi-Rad, Lawrence Livermore National Laboratory http://people.llnl.gov/eliassirad1 Tina Eliassi-Rad (http://eliassi.org) is a computer scientist and principal investigator at the Center for Applied Scientific Computing at Lawrence Livermore National Laboratory. She will join the faculty at the Department of Computer Science at Rutgers University in Fall 2010. Tina earned her Ph.D. in Computer Sciences (with a minor in Mathematical Statistics) at the University of Wisconsin-Madison. Her research interests include data mining, machine learning, and artificial intelligence. Her work has been applied to the World-Wide Web, text corpora, large-scale scientific simulation data, and complex networks. She serves as an action editor for the Data Mining and Knowledge Discovery Journal.