{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:24:46Z","timestamp":1750307086006,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>Data mining techniques for understanding how graphs evolve over time have become increasingly important. Evolving graphs arise naturally in diverse applications such as computer network topologies, multiplayer games and medical imaging. A natural and interesting problem in evolving graph analysis is the discovery of compact subgraphs that change in a similar manner. Such subgraphs are known as regions of correlated change and they can both summarise change patterns in graphs and help identify the underlying events causing these changes. However, previous techniques for discovering regions of correlated change suffer from limited scalability, making them unsuitable for analysing the evolution of very large graphs. In this paper, we introduce a new algorithm called ciForager, that addresses this scalability challenge and offers considerable improvements. The efficiency of ciForager is based on the use of new incremental techniques for detecting change, as well as the use of Voronoi representations for efficiently determining distance. We experimentally show that ciForager can achieve speedups of up to 1000 times over previous approaches. As a result, it becomes feasible for the first time to discover regions of correlated change in extremely large graphs, such as the entire BGP routing topology of the Internet.<\/jats:p>","DOI":"10.1145\/2362383.2362385","type":"journal-article","created":{"date-parts":[[2012,10,26]],"date-time":"2012-10-26T18:34:02Z","timestamp":1351276442000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["ciForager"],"prefix":"10.1145","volume":"6","author":[{"given":"Jeffrey","family":"Chan","sequence":"first","affiliation":[{"name":"University of Melbourne, Australia"}]},{"given":"James","family":"Bailey","sequence":"additional","affiliation":[{"name":"University of Melbourne, Australia"}]},{"given":"Christopher","family":"Leckie","sequence":"additional","affiliation":[{"name":"University of Melbourne, Australia"}]},{"given":"Michael","family":"Houle","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2012,10,29]]},"reference":[{"volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases. 81--92","author":"Aggarwal C. C.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 17th International Conference on Scientific and Statistical Database Management. 163--172","author":"Ali M. H.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"Arlitt M. and Jin T. 1999. Workload characterization of the 1998 World Cup website. Tech. rep. HPL-99-35R1 Hewlett-Packard Labs.  Arlitt M. and Jin T. 1999. Workload characterization of the 1998 World Cup website. Tech. rep. HPL-99-35R1 Hewlett-Packard Labs."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-009-0164-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.101"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.124"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.112"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150467"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0117-z"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1662565.1662571"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281212"},{"key":"e_1_2_1_12_1","unstructured":"Clare S. 1997. Functional MRI: Methods and applications. Ph.D. thesis University of Nottingham.  Clare S. 1997. Functional MRI: Methods and applications. Ph.D. thesis University of Nottingham."},{"key":"e_1_2_1_13_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"volume":"6321","volume-title":"Machine Learning and Knowledge Discovery in Databases. Lecture Notes in Computer Science Series","author":"Du N.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4401044"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases. 721--732","author":"Gibson D.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012801612483"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVD.2009.26"},{"key":"e_1_2_1_21_1","unstructured":"Jain A. K. and Dubes R. C. 1998. Algorithms for Clustering Data. Prentice-Hall Inc.   Jain A. K. and Dubes R. C. 1998. Algorithms for Clustering Data. Prentice-Hall Inc."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775233"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-009-0253-8"},{"volume-title":"Workshop on Link Analysis, Couterterrorism and Security.","author":"Lauw H. W.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_27_1","unstructured":"Luenberger D. 2003. Linear and Nonlinear Programming. Kluwer Academic Publishers.  Luenberger D. 2003. Linear and Nonlinear Programming. Kluwer Academic Publishers."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_14"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265902000562"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2004.01.010"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150445"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121525.3121559"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081962"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225662.3225976"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102481"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362383.2362385","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2362383.2362385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:22Z","timestamp":1750239262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362383.2362385"}},"subtitle":["Incrementally discovering regions of correlated change in evolving graphs"],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2362383.2362385"],"URL":"https:\/\/doi.org\/10.1145\/2362383.2362385","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}