Mining network hotspots with holes: A summary of results

Emre Eftelioglu, Yan Li, Xun Tang, Shashi Shekhar, James M. Kang, Christopher Farah

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

5 Scopus citations


Given a spatial network and a collection of activities (e.g. crime locations), the problem of Mining Network Hotspots with Holes (MNHH) finds network hotspots with doughnut shaped spatial footprint, where the concentration of activities is unusually high (e.g. statistically significant). MNHH is important for societal applications such as criminology, where it may focus the efforts of officials to identify a crime source. MNHH is challenging because of the large number of candidates and the high computational cost of statistical significance test. Previous work focused either on geometry based hotspots (e.g. circular, ring-shaped) on Euclidean space or connected subgraphs (e.g. shortest path), limiting the ability to detect statistically significant hotspots with holes on a spatial network. This paper proposes a novel Network Hotspot with Hole Generator (NHHG) algorithm to detect network hotspots with holes. The proposed algorithm features refinements that improve the performance of a naïve approach. Case studies on real crime datasets confirm the superiority of NHHG over previous approaches. Experimental results on real data show that the proposed approach yields substantial computational savings without reducing result quality.

Original languageEnglish (US)
Title of host publicationGeographic Information Science - 9th International Conference, GIScience 2016, Proceedings
EditorsDavid O’Sullivan, Nancy Wiegand, Jennifer A. Miller
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783319457376
StatePublished - 2016
Event9th International Conference on Geographic Information Science, GIScience 2016 - Montreal, Canada
Duration: Sep 27 2016Sep 30 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9927 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Geographic Information Science, GIScience 2016

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grants No. 1029711, IIS-1320580, 0940818 and IIS-1218168, the USDOD under Grants No. HM1582-08-1-0017. We would like to thank Kim Koffolt and University of Minnesota Spatial Computing Research Group for their comments.

Publisher Copyright:
© Springer International Publishing Switzerland 2016.


  • Crime hotspots
  • Hotspot detection
  • Spatial scan statistics


Dive into the research topics of 'Mining network hotspots with holes: A summary of results'. Together they form a unique fingerprint.

Cite this