Document Open Access Logo

Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks

Authors Jessica Enright, Kitty Meeks, George B. Mertzios, Viktor Zamaraev

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.57.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Jessica Enright
  • Global Academy of Agriculture and Food Security, University of Edinburgh, UK
Kitty Meeks
  • School of Computing Science, University of Glasgow, UK
George B. Mertzios
  • Department of Computer Science, Durham University, UK
Viktor Zamaraev
  • Department of Computer Science, Durham University, UK

Funding

  • Meeks, Kitty: supported by a Royal Society of Edinburgh Personal Research Fellowship, funded by the Scottish Government.
  • Mertzios, George B.: partially supported by the EPSRC Grants EP/P020372/1.
  • Zamaraev, Viktor: supported by the EPSRC Grant EP/P020372/1.

Acknowledgements

The authors wish to thank Bruno Courcelle and Barnaby Martin for useful discussions and hints on monadic second order logic.

Cite AsGet BibTex

Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.57

Abstract

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of goods over logistical infrastructure. Often, the networks over which these processes spread are dynamic in nature, and can be modeled with graphs whose structure is subject to discrete changes over time, i.e. with temporal graphs. Here, we consider temporal graphs in which edges are available at specified timesteps, and study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path (i.e. a path, along which the times of the edge availabilities increase). We introduce a natural deletion problem for temporal graphs and we provide positive and negative results on its computational complexity, both in the traditional and the parameterised sense (subject to various natural parameters), as well as addressing the approximability of this problem.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Temporal networks
  • spreading processes
  • graph modification
  • parameterised complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Aaron, Danny Krizanc, and Elliot Meyerson. DMVP: foremost waypoint coverage of time-varying graphs. In Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 29-41, 2014. Google Scholar
  2. E. Akrida, G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, P.G. Spirakis, and V. Zamaraev. How fast can we reach a target vertex in stochastic temporal graphs?, 2019. Technical Report available at URL: https://arxiv.org/abs/1903.03636.
  3. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87:109-120, 2016. Google Scholar
  4. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3):907-944, 2017. Google Scholar
  5. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), 2018. To appear. Technical Report available at URL: https://arxiv.org/abs/1802.07103.
  6. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277 - -284, 1987. Google Scholar
  7. Alain Barrat, Marc Barthlemy, and Alessandro Vespignani. Dynamical Processes on Complex Networks. Cambridge University Press, New York, NY, USA, 1st edition, 2008. Google Scholar
  8. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 226-234, 1993. Google Scholar
  9. Alfredo Braunstein and Alessandro Ingrosso. Inference of causality in epidemics on temporal contact networks. Scientific Reports, 6:27538, 2016. URL: https://doi.org/10.1038/srep27538.
  10. Dirk Brockmann and Dirk Helbing. The Hidden Geometry of Complex, Network-Driven Contagion Phenomena. Science, 342(6164):1337-1342, 2013. URL: https://doi.org/10.1126/science.1245200.
  11. Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks. International Journal of Foundations of Computer Science, 14(2):267-285, 2003. Google Scholar
  12. Arnaud Casteigts and Paola Flocchini. Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics. Technical report, Defence R&D Canada, April 2013. URL: https://hal.archives-ouvertes.fr/hal-00865762.
  13. Arnaud Casteigts and Paola Flocchini. Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools. Technical report, Defence R&D Canada, April 2013. URL: https://hal.archives-ouvertes.fr/hal-00865764.
  14. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems (IJPEDS), 27(5):387-408, 2012. Google Scholar
  15. Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Flooding Time of Edge-Markovian Evolving Graphs. SIAM Journal on Discrete Mathematics (SIDMA), 24(4):1694-1712, 2010. Google Scholar
  16. Vittoria Colizza, Alain Barrat, Marc Barthélemy, and Alessandro Vespignani. The role of the airline transportation network in the prediction and predictability of global epidemics. Proceedings of the National Academy of Sciences, 103(7):2015-2020, 2006. URL: https://doi.org/10.1073/pnas.0510525103.
  17. Bruno Courcelle, 2018. Personal communication. Google Scholar
  18. Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach. Cambridge University Press, 2012. Google Scholar
  19. Jessica Enright and Kitty Meeks. Changing times to optimise reachability in temporal graphs. Technical Report available at URL: https://arxiv.org/abs/1802.05905.
  20. Jessica Enright and Kitty Meeks. Deleting edges to restrict the size of an epidemic: a new application for treewidth. Algorithmica, 80(6):1857-1889, 2018. Google Scholar
  21. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On Temporal Graph Exploration. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 444-455, 2015. Google Scholar
  22. Afonso Ferreira. Building a Reference Combinatorial Model for MANETs. IEEE Network, 18(5):24-29, 2004. Google Scholar
  23. Stephen Finbow and Gary MacGillivray. The Firefighter Problem: a survey of results, directions and questions. Australasian J. Combinatorics, 43:57-78, 2009. URL: http://ajc.maths.uq.edu.au/pdf/43/ajc_v43_p057.pdf.
  24. Paola Flocchini, Bernard Mans, and Nicola Santoro. Exploration of Periodically Varying Graphs. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 534-543, 2009. Google Scholar
  25. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  26. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. In 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2018. To appear. Technical Report available at URL: https://arxiv.org/abs/1803.00882.
  27. George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. Randomized Rumor Spreading in Dynamic Graphs. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 495-507, 2014. Google Scholar
  28. Daniel T. Haydon, Rowland R. Kao, and Paul R. Kitching. The UK foot-and-mouth disease outbreak - the aftermath. Nature Reviews Microbiology, 2(8):675, 2004. Google Scholar
  29. Itai Himelboim, Marc A. Smith, Lee Rainie, Ben Shneiderman, and Camila Espina. Classifying Twitter Topic-Networks Using Social Network Analysis. Social Media + Society, 3(1):2056305117691545, 2017. URL: https://doi.org/10.1177/2056305117691545.
  30. Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining, 7(1):35:1-35:16, 2017. Google Scholar
  31. Petter Holme and Jari Saramäki, editors. Temporal Networks. Springer, 2013. Google Scholar
  32. David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. In Proceedings of the 32nd annual ACM symposium on Theory of computing (STOC), pages 504-513, 2000. Google Scholar
  33. Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data, 1(1), 2007. Google Scholar
  34. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
  35. G.B. Mertzios, O. Michail, I. Chatzigiannakis, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, pages 1416-1449, 2019. Google Scholar
  36. George B Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring. In Proceedings of the 33st AAAI Conference on Artificial Intelligence (AAAI), (to appear). Google Scholar
  37. Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. Google Scholar
  38. Othon Michail and Paul G. Spirakis. Elements of the Theory of Dynamic Networks. Communications of the ACM, 61(2):72-72, 2018. Google Scholar
  39. A. Mitchell, D. Bourn, J. Mawdsley, W. Wint, R. Clifton-Hadley, and M. Gilbert. Characteristics of cattle movements in Britain - an analysis of records from the Cattle Tracing System. Animal Science, 80(3):265?273, 2005. URL: https://doi.org/10.1079/ASC50020265.
  40. Andrew Mitchell, David Bourn, J. Mawdsley, William Wint, Richard Clifton-Hadley, and Marius Gilbert. Characteristics of cattle movements in Britain - an analysis of records from the Cattle Tracing System. Animal Science, 80(3):265-273, 2005. Google Scholar
  41. Maria Noremark and Stefan Widgren. EpiContactTrace: an R-package for contact tracing during livestock disease outbreaks and for risk-based surveillance. BMC Veterinary Research, 10(1), 2014. URL: https://doi.org/10.1186/1746-6148-10-71.
  42. Piotr Sapiezynski, Arkadiusz Stopczynski, Radu Gatej, and Sune Lehmann. Tracking human mobility using wifi signals. PloS One, 10(7):e0130824, 2015. Google Scholar
  43. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag Berlin Heidelberg, 2003. Google Scholar
  44. John Kit Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. Characterising temporal distance and reachability in mobile and online social networks. ACM Computer Communication Review, 40(1):118-124, 2010. Google Scholar
  45. Dimitrios M. Thilikos, Maria Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. Journal of Algorithms, 56(1):1-24, 2005. URL: https://doi.org/10.1016/j.jalgor.2004.12.001.
  46. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
  47. Eugenio Valdano, Luca Ferreri, Chiara Poletto, and Vittoria Colizza. Analytical Computation of the Epidemic Threshold on Temporal Networks. Phys. Rev. X, 5:021005, April 2015. URL: https://doi.org/10.1103/PhysRevX.5.021005.
  48. Eugenio Valdano, Chiara Poletto, Armando Giovannini, Diana Palma, Lara Savini, and Vittoria Colizza. Predicting Epidemic Risk from Past Temporal Contact Data. PLoS Computational Biology, 11(3):e1004152, March 2015. URL: https://doi.org/10.1371/journal.pcbi.1004152.
  49. Jordan Viard, Matthieu Latapy, and Clémence Magnien. Revealing contact patterns among high-school students using maximal cliques in link streams. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 1517-1522, 2015. Google Scholar
  50. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
  51. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. On efficiently finding small separators in temporal graphs. Technical Report available at URL: https://arxiv.org/abs/1803.00882.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact