{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:46:55Z","timestamp":1773272815893,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1443054, IIS-1633028"],"award-info":[{"award-number":["ACI-1443054, IIS-1633028"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011030","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC52-07NA27344"],"award-info":[{"award-number":["DE-AC52-07NA27344"]}],"id":[{"id":"10.13039\/100011030","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000774","name":"Defense Threat Reduction Agency","doi-asserted-by":"publisher","award":["HDTRA1-11-D-0016-0010"],"award-info":[{"award-number":["HDTRA1-11-D-0016-0010"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>One fundamental task in network analysis is detecting \u201chotspots\u201d or \u201canomalies\u201d in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the \u201ceffective solution size,\u201d while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1--2 orders of magnitude larger than all prior applications.<\/jats:p>","DOI":"10.1145\/3309712","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T17:12:14Z","timestamp":1556557934000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6161-7480","authenticated-orcid":false,"given":"Jose","family":"Cadena","sequence":"first","affiliation":[{"name":"Dept. of Computer Science and Biocomplexity Institute, Virginia Tech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Chen","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, University of Albany - SUNY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Vullikanti","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Biocomplexity Institute, Virginia Tech"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150410"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_40"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0091225"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"E. Awini P. Mattah O. Sankoh and M. Gyapong. 2010. Spatial variations in childhood mortalities at the Dodowa Health and Demographic Surveillance System site of the INDEPTH network in Ghana. Tropical Medicine 8 International Health 15 5 (2010) 520--528.  E. Awini P. Mattah O. Sankoh and M. Gyapong. 2010. Spatial variations in childhood mortalities at the Dodowa Health and Demographic Surveillance System site of the INDEPTH network in Ghana. Tropical Medicine 8 International Health 15 5 (2010) 520--528.","DOI":"10.1111\/j.1365-3156.2010.02492.x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1979.10481035"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00533250"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.101"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4081\/gh.2016.304"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2813311"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5210\/ojphi.v6i1.5137"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623619"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1089\/big.2014.0072"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869869"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000265"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-STS506"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X112396"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1558607.1558658"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/00223980.1972.9924813"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176344559"},{"key":"e_1_2_1_23_1","unstructured":"R. A. Fisher. 1925. Statistical Methods for Research Workers. Edinburgh Oliver 8 Boyd.  R. A. Fisher. 1925. Statistical Methods for Research Workers. Edinburgh Oliver 8 Boyd."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/0009053607000000244"},{"key":"e_1_2_1_27_1","volume-title":"Rare and weak effects in large-scale inference: Methods and phase diagrams. Statistica Sinica","author":"Jin Jiashun","year":"2016"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Johnson D."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/sim.3951"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078850"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610929708831995"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9473(02)00160-3"},{"key":"e_1_2_1_33_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_34_1","volume-title":"A community-based assessment of learning disabilities using environmental and contextual risk factors. Social Science 8 Medicine 56, 5","author":"Margai Florence","year":"2003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567713"},{"key":"e_1_2_1_36_1","volume-title":"Singh","author":"Mongiovi Misael","year":"2013"},{"key":"e_1_2_1_37_1","first-page":"48","article-title":"Fast and flexible outbreak detection by linear-time subset scanning","volume":"5","author":"Neill Daniel B.","year":"2008","journal-title":"Advances in Disease Surveillance"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1186\/1476-072X-8-20"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2011.01014.x"},{"key":"e_1_2_1_40_1","first-page":"106","article-title":"A nonparametric scan statistic for multivariate disease surveillance","volume":"4","author":"Neill Daniel B.","year":"2007","journal-title":"Advances in Disease Surveillance"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(556)"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 17th International Conference on Artificial Intelligence and Statistics.","author":"Qian Jing","year":"2014"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 26th International Conference on Neural Information Processing Systems.","author":"Sharpnack James","year":"2013"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the Artificial Intelligence and Statistics.","author":"Sharpnack James","year":"2012"},{"key":"e_1_2_1_46_1","unstructured":"James Sharpnack Aarti Singh and Alessandro Rinaldo. 2013b. Changepoint detection over graphs with the spectral scan statistic. In Procedings of the Artificial Intelligence and Statistics.  James Sharpnack Aarti Singh and Alessandro Rinaldo. 2013b. Changepoint detection over graphs with the spectral scan statistic. In Procedings of the Artificial Intelligence and Statistics."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2014.960926"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 13th International Conference on Data Mining. IEEE, 697--706","author":"Speakman Skyler"},{"key":"e_1_2_1_49_1","volume-title":"Williams","author":"Stouffer Samuel A.","year":"1949"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/1476-072X-7-14"},{"key":"e_1_2_1_51_1","volume-title":"Jacobson","author":"Vaneckova Pavla","year":"2010"},{"key":"e_1_2_1_52_1","volume-title":"Kolmogorov--Smirnov test. Encyclopedia of Biostatistics","author":"Wilcox R."},{"key":"e_1_2_1_53_1","volume-title":"Homicide as infectious disease: Using public health methods to investigate the diffusion of homicide. Justice quarterly 31, 3","author":"Zeoli April M.","year":"2014"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309712","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309712","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:35Z","timestamp":1750204415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3309712"],"URL":"https:\/\/doi.org\/10.1145\/3309712","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}