Temporal Cascade Model for Analyzing Spread in Evolving Networks

Aparajita Haldar, Shuang Wang, Gunduz Vehbi Demirci, Joe Oakley, Hakan Ferhatosmanoglu

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Current approaches for modeling propagation in networks (e.g., of diseases, computer viruses, rumors) cannot adequately capture temporal properties such as order/duration of evolving connections or dynamic likelihoods of propagation along connections. Temporal models on evolving networks are crucial in applications that need to analyze dynamic spread. For example, a disease spreading virus has varying transmissibility based on interactions between individuals occurring with different frequency, proximity, and venue population density. Similarly, propagation of information having a limited active period, such as rumors, depends on the temporal dynamics of social interactions. To capture such behaviors, we first develop the Temporal Independent Cascade (T-IC) model with a spread function that efficiently utilizes a hypergraph-based sampling strategy and dynamic propagation probabilities. We prove this function to be submodular, with guarantees of approximation quality. This enables scalable analysis on highly granular temporal networks where other models struggle, such as when the spread across connections exhibits arbitrary temporally evolving patterns. We then introduce the notion of “reverse spread” using the proposed T-IC processes, and develop novel solutions to identify both sentinel/detector nodes and highly susceptible nodes. Extensive analysis on real-world datasets shows that the proposed approach significantly outperforms the alternatives in modeling both if and how spread occurs, by considering evolving network topology alongside granular contact/interaction information. Our approach has numerous applications, such as virus/rumor/influence tracking. Utilizing T-IC, we explore vital challenges of monitoring the impact of various intervention strategies over real spatio-temporal contact networks where we show our approach to be highly effective.
Original languageEnglish
Article number12
Pages (from-to)1-30
JournalACM Transactions on Spatial Algorithms and Systems
Volume9
Issue number2
DOIs
Publication statusPublished - 12 Apr 2023

Keywords / Materials (for Non-textual outputs)

  • dynamic spread analysis
  • efficiency
  • Temporal cascade model
  • sentinel nodes
  • scalpability
  • spatio-temporal contact networks
  • reverse spread maximization
  • susceptible nodes

Fingerprint

Dive into the research topics of 'Temporal Cascade Model for Analyzing Spread in Evolving Networks'. Together they form a unique fingerprint.

Cite this