GraphScope
Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou et al. · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 2007
How can we find communities in dynamic networks of socialinteractions, such as who calls whom, who emails whom, or who sells to whom? How can we spot discontinuity time-points in such streams of graphs, in an on-line, any-time fashion? We propose GraphScope, that addresses both problems, using information theoretic principles. Contrary to the majority of earlier methods, it needs no user-defined parameters. Moreover, it is designed to operate on large graphs, in a streaming fashion. We demonstrate the efficiency and effectiveness of our GraphScope on real datasets from several diverse domains. In all cases it produces meaningful time-evolving patterns that agree with human intuition.
Cited by 532 works. doi:10.1145/1281192.1281266
Authors
References
- Elements of Information Theory
- On power-law relationships of the Internet topology
- On Spectral Clustering: Analysis and an algorithm
- A Universal Prior for Integers and Estimation by Minimum Description Length
- Group formation in large social networks
- Graphs over time
- Multilevelk-way Partitioning Scheme for Irregular Graphs
- Extracting Large-Scale Knowledge Bases from the Web
- Information-theoretic co-clustering
- Towards parameter-free data mining