{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T14:44:06Z","timestamp":1786545846369,"version":"3.56.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,30]],"date-time":"2019-12-30T00:00:00Z","timestamp":1577664000000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Smart cities and traffic applications can be modelled by dynamic graphs for which vertices or edges can be added, removed or change their properties. In the smart city or traffic <jats:italic>monitoring problem<\/jats:italic>, we wish to detect if a city dynamic graph maintains a certain local or global property. Monitoring city large dynamic graphs, is even more complicated. To treat the monitoring problem efficiently we divide a large city graph into sub-graphs. In the <jats:italic>distributed monitoring problem<\/jats:italic> we would like to define some local conditions for which the global city graph G maintains a certain property. Furthermore, we would like to detect if a local city change in a sub-graph affect a global graph property. Here we show that turning the graph into a non-trivial one by handling directed graphs, weighted graphs, graphs with nodes that contain different attributes or combinations of these aspects, can be integrated in known urban environment applications. These implementations are demonstrated here in two types of network applications: traffic network application and on-line social network smart city applications. We exemplify these two problems, show their experimental results and characterize efficient monitoring algorithms that can handle them.<\/jats:p>","DOI":"10.1007\/s41109-019-0224-2","type":"journal-article","created":{"date-parts":[[2019,12,30]],"date-time":"2019-12-30T16:02:51Z","timestamp":1577721771000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Managing large distributed dynamic graphs for smart city network applications"],"prefix":"10.1007","volume":"4","author":[{"given":"Nadav","family":"Voloch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noa","family":"Voloch - Bloch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yair","family":"Zadok","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,12,30]]},"reference":[{"key":"224_CR1","doi-asserted-by":"publisher","unstructured":"Babcock, B, Olston C (2003) Distributed top-k monitoring In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, 28\u201339. https:\/\/doi.org\/10.1145\/872757.872764.","DOI":"10.1145\/872757.872764"},{"key":"224_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-19662-6_3","volume-title":"Ad-hoc, Mobile, and Wireless Networks","author":"Evangelos Bampas","year":"2015","unstructured":"Bampas, E, Karousatou C, Pagourtzis A, Potika K (2015) Scheduling connections via path and edge multicoloring In: Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015, Athens, Greece, June 29 - July 1, 2015, Proceedings, 33\u201347. https:\/\/doi.org\/10.1007\/978-3-319-19662-6_3."},{"key":"224_CR3","doi-asserted-by":"publisher","first-page":"1499","DOI":"10.12988\/ces.2018.83126","volume":"11","author":"O Barzilai","year":"2018","unstructured":"Barzilai, O, Voloch N, Hasgall A, Lavi Steiner O, Ahituv N (2018) Traffic control in a smart intersection by an algorithm with social priorities. Contemp Eng Sci 11:1499\u20131511. https:\/\/doi.org\/10.12988\/ces.2018.83126.","journal-title":"Contemp Eng Sci"},{"issue":"1","key":"224_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271. https:\/\/doi.org\/10.1007\/BF01386390.","journal-title":"Numer Math"},{"issue":"6","key":"224_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, RW (1962) Algorithm 97: Shortest path. Commun ACM 5(6):345. http:\/\/doi.acm.org\/10.1145\/367766.368168.","journal-title":"Commun ACM"},{"key":"224_CR6","unstructured":"Fortunato, S (2009) Community detection in graphs. CoRR abs\/0906:0612. http:\/\/arxiv.org\/abs\/0906.0612."},{"key":"224_CR7","doi-asserted-by":"publisher","unstructured":"Gao, J, Zhou C, Zhou J, Yu JX (2014) Continuous pattern detection over billion-edge graph using distributed framework In: 2014 IEEE 30th International Conference on Data Engineering, 556\u2013567. https:\/\/doi.org\/10.1109\/icde.2014.6816681.","DOI":"10.1109\/icde.2014.6816681"},{"key":"224_CR8","first-page":"599","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), vol. 14","author":"JE Gonzalez","year":"2014","unstructured":"Gonzalez, JE, Xin RS, Dave A, Crankshaw D, Franklin MJ, Stoica I (2014) Graphx: Graph processing in a distributed dataflow framework In: 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), vol. 14, 599\u2013613.. Broomfield, Berkeley."},{"issue":"3","key":"224_CR9","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s10955-014-1024-9","volume":"158","author":"Dirk Helbing","year":"2014","unstructured":"Helbing, D, Brockmann D, Chadefaux T, Donnay K, Blanke U, Woolley Meza O, Moussa\u00efd M, Johansson A, Krause J, Schutte S, Perc M (2014) Saving human lives: What complexity science and information systems can contribute. J Stat Phys 158. https:\/\/doi.org\/10.1007\/s10955-014-1024-9.","journal-title":"Journal of Statistical Physics"},{"issue":"04","key":"224_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"Shlomo Hoory","year":"2006","unstructured":"Hoory, S, Linial N, Wigderson A (2006) Expander graphs and their applications. Bull Amer Math Soc:439\u2013561.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"224_CR11","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/comnet\/cnx019","volume":"5","author":"M Jalili","year":"2017","unstructured":"Jalili, M, Perc M (2017) Information cascades in complex networks. J Complex Netw 5:665\u2013693. https:\/\/doi.org\/10.1093\/comnet\/cnx019.","journal-title":"J Complex Netw"},{"key":"224_CR12","doi-asserted-by":"publisher","DOI":"10.2174\/97816080581811140101","volume-title":"Social Network Analysis: An Introduction with an Extensive Implementation to a Large-Scale Online Network Using Pajek","year":"2014","unstructured":"Kadry, S, Al-Taie MZ (2014) Social network analysis: An introduction with an extensive implementation to a large-scale online network using pajek. Bentham Science Publishers. https:\/\/doi.org\/10.2174\/97816080581811140101."},{"issue":"3","key":"224_CR13","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"L Kenneth","year":"1966","unstructured":"Kenneth, L, Cooke EH (1966) The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl 14(3):493\u2013498.","journal-title":"J Math Anal Appl"},{"key":"224_CR14","first-page":"219","volume":"22","author":"U Lauther","year":"2004","unstructured":"Lauther, U (2004) An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. Geoinformation und Mobilit\u00e4t-von der Forschung zur praktischen Anwendung 22:219\u2013230.","journal-title":"Geoinformation und Mobilit\u00e4t-von der Forschung zur praktischen Anwendung"},{"issue":"1","key":"224_CR15","first-page":"1","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L (1993) Random walks on graphs: A survey. Combinatorics, Paul erdos is eighty 2(1):1\u201346.","journal-title":"Combinatorics, Paul erdos is eighty"},{"key":"224_CR16","doi-asserted-by":"publisher","unstructured":"Mondal, J, Deshpande A (2012) Managing large dynamic graphs efficiently. https:\/\/doi.org\/10.1145\/2213836.2213854.","DOI":"10.1145\/2213836.2213854"},{"key":"224_CR17","doi-asserted-by":"publisher","first-page":"036,122","DOI":"10.1103\/PhysRevE.68.036122","volume":"68","author":"MEJ Newman","year":"2003","unstructured":"Newman, MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68:036,122.","journal-title":"Phys Rev E"},{"key":"224_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1800-9_176","volume-title":"Social Network Analysis, Graph Theoretical Approaches to","author":"W de Nooy","year":"2012","unstructured":"de Nooy, W (2012) Social Network Analysis, Graph Theoretical Approaches to. Springer New York, New York."},{"issue":"14","key":"224_CR19","first-page":"1870","volume":"6","author":"A Pavan","year":"2013","unstructured":"Pavan, A, Tangwongsan K, Tirthapura S, Wu K (2013) Counting and sampling triangles from a graph stream. PVLDB 6(14):1870\u20131881. http:\/\/www.vldb.org\/pvldb\/vol6\/p1870-aduri.pdf.","journal-title":"PVLDB"},{"key":"224_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2017.05.004","volume":"687","author":"M Perc","year":"2017","unstructured":"Perc, M, Jordan JJ, Rand DG, Wang Z, Boccaletti S, Szolnoki A (2017) Statistical physics of human cooperation. Phys Rep 687:1\u201351. https:\/\/doi.org\/10.1016\/j.physrep.2017.05.004. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0370157317301424.","journal-title":"Phys Rep"},{"issue":"1","key":"224_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S Pettie","year":"2004","unstructured":"Pettie, S (2004) A new approach to all-pairs shortest paths on real-weighted graphs. Theor Comput Sci 312(1):47\u201374.","journal-title":"Theor Comput Sci"},{"key":"224_CR22","doi-asserted-by":"publisher","unstructured":"Cormode, G, Keralapura R, Ramamirtham J (2006) Communication-efficient distributed monitoring of thresholded counts, Chicago. https:\/\/doi.org\/10.1145\/1142473.1142507.","DOI":"10.1145\/1142473.1142507"},{"issue":"3","key":"224_CR23","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R Seidel","year":"1995","unstructured":"Seidel, R (1995) On the all-pairs-shortest-path problem in unweighted undirected graphs. J Comput Syst Sci 51(3):400\u2013403. https:\/\/doi.org\/10.1006\/jcss.1995.1078.","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"224_CR24","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/080734315","volume":"53","author":"AL Traud","year":"2011","unstructured":"Traud, AL, Kelsic ED, Mucha PJ, Porter MA (2011) Comparing community structure to characteristics in online collegiate social networks. SIAM Rev 53(3):526\u2013543.","journal-title":"SIAM Rev"},{"key":"224_CR25","first-page":"4503","volume":"abs\/1111.4503","author":"J Ugander","year":"2011","unstructured":"Ugander, J, Karrer B, Backstrom L, Marlow C (2011) The anatomy of the facebook social graph. CoRR abs\/1111 abs\/1111.4503:4503.","journal-title":"CoRR abs\/1111"},{"key":"224_CR26","doi-asserted-by":"publisher","unstructured":"Wang, L, Xiao Y, Shao B, Wang H (2014) How to partition a billion-node graph In: IEEE 30th International Conference on Data Engineering, 568\u2013579, Chicago. https:\/\/doi.org\/10.1109\/icde.2014.6816682.","DOI":"10.1109\/icde.2014.6816682"},{"key":"224_CR27","doi-asserted-by":"publisher","unstructured":"Wang, W, Bai Y, Yu C, Gu Y, Feng P, Wang X, Wang R (2018) A network traffic flow prediction with deep learning approach for large-scale metropolitan area network In: NOMS 2018 - 2018 IEEE\/IFIP Network Operations and Management Symposium, 1\u20139. https:\/\/doi.org\/10.1109\/NOMS.2018.8406252.","DOI":"10.1109\/NOMS.2018.8406252"},{"key":"224_CR28","unstructured":"Williams, R (2013) Faster all-pairs shortest paths via circuit complexity. CoRR abs\/1312:6680. http:\/\/arxiv.org\/abs\/1312.6680."},{"key":"224_CR29","doi-asserted-by":"publisher","unstructured":"Yang, S, Yan X, Zong B, Khan A (2012) Towards effective partition management for large graphs In: Proceedings of the ACM SIGMOD International Conference on Management of Data, 517\u2013528, USA. https:\/\/doi.org\/10.1145\/2213836.2213895.","DOI":"10.1145\/2213836.2213895"},{"key":"224_CR30","doi-asserted-by":"publisher","unstructured":"Yehuda, G, Keren D, Akaria I (2017) Monitoring properties of large, distributed, dynamic graphs In: 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS USA, 2\u201311. https:\/\/doi.org\/10.1109\/ipdps.2017.123.","DOI":"10.1109\/ipdps.2017.123"},{"key":"224_CR31","first-page":"94","volume":"1408","author":"A Ziliaskopoulos","year":"1993","unstructured":"Ziliaskopoulos, A, Mahmassani H (1993) A time-dependent shortest path algorithm for real-time intelligent vehicle\/highway system. Transp Res Rec J Transp Res Board 1408:94\u2013100.","journal-title":"Transp Res Rec J Transp Res Board"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0224-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-019-0224-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0224-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T00:06:54Z","timestamp":1609200414000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-019-0224-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["224"],"URL":"https:\/\/doi.org\/10.1007\/s41109-019-0224-2","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"17 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"130"}}