Hierarchical, Parameter-Free Community Discovery
Abstract
Given a large bipartite graph (like document-term, or userproduct 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.
Cite
Text
Papadimitriou et al. "Hierarchical, Parameter-Free Community Discovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2008. doi:10.1007/978-3-540-87481-2_12Markdown
[Papadimitriou et al. "Hierarchical, Parameter-Free Community Discovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2008.](https://mlanthology.org/ecmlpkdd/2008/papadimitriou2008ecmlpkdd-hierarchical/) doi:10.1007/978-3-540-87481-2_12BibTeX
@inproceedings{papadimitriou2008ecmlpkdd-hierarchical,
title = {{Hierarchical, Parameter-Free Community Discovery}},
author = {Papadimitriou, Spiros and Sun, Jimeng and Faloutsos, Christos and Yu, Philip S.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2008},
pages = {170-187},
doi = {10.1007/978-3-540-87481-2_12},
url = {https://mlanthology.org/ecmlpkdd/2008/papadimitriou2008ecmlpkdd-hierarchical/}
}