Spatial scan statistics for graph clustering

Bei Wang, Jeff M. Phillips, Robert Schreiber, Dennis Wilkinson, Nina Mishra, Robert Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

In this paper, we present a measure associated with detection and inference of statistically anomalous clusters of a graph based on the likelihood test of observed and expected edges in a subgraph. This measure is adapted from spatial scan statistics for point sets and provides quantitative assessment for clusters. We discuss some important properties of this statistic and its relation to modularity and Bregman divergences. We apply a simple clustering algorithm to find clusters with large values of this measure in a variety of real-world data sets, and we illustrate its ability to identify statistically significant clusters of selected granularity.

Original languageEnglish (US)
Title of host publicationSociety for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130
PublisherSociety for Industrial and Applied Mathematics Publications
Pages727-738
Number of pages12
ISBN (Print)9781605603179
DOIs
StatePublished - 2008
Event8th SIAM International Conference on Data Mining 2008, Applied Mathematics 130 - Atlanta, GA, United States
Duration: Apr 24 2008Apr 26 2008

Publication series

NameSociety for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130
Volume2

Other

Other8th SIAM International Conference on Data Mining 2008, Applied Mathematics 130
CountryUnited States
CityAtlanta, GA
Period4/24/084/26/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Software
  • Signal Processing

Fingerprint Dive into the research topics of 'Spatial scan statistics for graph clustering'. Together they form a unique fingerprint.

  • Cite this

    Wang, B., Phillips, J. M., Schreiber, R., Wilkinson, D., Mishra, N., & Tarjan, R. (2008). Spatial scan statistics for graph clustering. In Society for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130 (pp. 727-738). (Society for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130; Vol. 2). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611972788.66