Home

Paper abstract

Hierarchical, Parameter-Free Community Discovery

Spiros Papadimitriou - IBM Research, USA
Jimeng Sun - IBM Research, USA
Philip S. Yu - University of Illinois, Chicago, USA
Christos Faloutsos - Carnegie Mellon University, USA

Session: Social Networks
Springer Link: http://dx.doi.org/10.1007/978-3-540-87481-2_12

Given a large bipartite graph (like document-term, or user-product graph), how can we find meaningful communities, quickly, and automatically? We propose to look for community hierarchies, with communities-within-communities. Our proposed method, the Context-specific Cluster Tree (CCT) finds such communities at multiple levels, with no user intervention, based on information theoretic principles (MDL). More specifically, it partitions the graph into progressively more refined subgraphs, allowing users to quickly navigate from the global, coarse structure of a graph to more focused and local patterns. As a fringe benefit, and also as an additional indication of its quality, it also achieves better compression than typical, non-hierarchical methods. We demonstrate its scalability and effectiveness on real, large graphs.