Tracking Switched Dynamic Network Topologies From Information Cascades

Brian Baingana, Georgios B. GiannakisIEEE TSP 2016 · DOI · arXiv · OpenReview

Abstract

Contagions, such as the spread of popular news stories, or infectious diseases, propagate in cascades over dynamic networks with unobservable topologies. However, “social signals,” such as product purchase time, or blog entry timestamps are measurable, and implicitly depend on the underlying topology, making it possible to track it over time. Interestingly, network topologies often “jump” between discrete states that may account for sudden changes in the observed signals. The present paper advocates a switched dynamic structural equation model to capture the topology dependent cascade evolution, as well as the discrete states driving the underlying topologies. Conditions under which the proposed switched model is identifiable are established. Leveraging the edge sparsity inherent to social networks, a recursive $\ell_1$-norm regularized least-squares estimator is put forth to jointly track the states and network topologies. An efficient first-order proximal-gradient algorithm is developed to solve the resulting optimization problem. Numerical experiments on both synthetic data and real cascades measured over the span of one year are conducted, and test results corroborate the efficacy of the advocated approach.

Introduction: The Challenge of Hidden, Shifting Networks

In the digital age, information flows in cascades—from viral memes on social media to the spread of infectious diseases. While we can often observe the timing of these events (e.g., when a blog post is published or a patient is diagnosed), the underlying network structure that facilitates this spread is frequently unobservable. Furthermore, these networks are rarely static. They can "jump" suddenly between discrete states, such as an email network shifting from professional links during business hours to social links on the weekend.

Information cascades spreading through a network over time.

Standard network inference models often assume slow, continuous changes. However, real-world systems exhibit "bursty" behavior where sudden reconfigurations occur due to major external events. Tracking these "switched" topologies requires a model that can handle both the unobservable nature of the links and the discrete jumps in network states.

The Switched Dynamic Structural Equation Model

To address these challenges, the authors propose a Switched Dynamic Structural Equation Model (SEM). In this framework, the infection time of a node is modeled as a linear combination of the infection times of its neighbors, influenced by the current state of the network.

The structural equation model (SEM) representing the influence of neighboring nodes and external inputs on a target node.

As shown in the figure above, the state of node $y_{11}^t$ at time $t$ depends on its neighbors ($y_{21}^t, y_{31}^t, y_{41}^t$) through weights $a_{ij}^{\sigma(t)}$, where $\sigma(t)$ represents the active network state at time $t$. The model also accounts for external influences $x_{11}$ with weights $b_{11}^{\sigma(t)}$.

Key Technical Components

  • Switched Linear System: The network is assumed to exist in one of $S$ discrete states at any given time.
  • Identifiability: The authors prove that hidden matrices can be uniquely recovered from timing data by leveraging edge sparsity—the observation that most nodes in a large network are not directly connected.
  • Recursive Estimation: A recursive $\ell_1$-regularized least-squares estimator is used to handle large-scale networks, enforcing sparsity to maintain physical realism.
  • Proximal-Gradient Algorithm: An adapted Iterative Shrinkage-Thresholding Algorithm (ISTA) jointly tracks the network state and connection weights in real-time.

Experimental Validation

The model was tested on both synthetic and real-world datasets:

  1. Synthetic Kronecker Graphs: Networks with 64 nodes and 4 switching states were used to verify the algorithm's ability to recover ground-truth topologies.
  2. InfoPath Dataset: A year-long dataset of 3.3 million websites was analyzed, focusing on 625 "memes" spreading across 1,131 core websites.

Key Insights

  • Robustness to Jumps: Unlike "slow-varying" models that average out distinct states during a jump, the switched model accurately tracks sudden transitions, maintaining significantly lower relative error (approx. 0.4 vs. 0.6-0.9 for standard trackers).
  • Small-World Heuristic: By tuning the sparsity parameter $\lambda$ to match realistic "small-world" path lengths (6–10 hops), the model's accuracy is enhanced.
  • Media Influence: In real-world news cascades, the model identified three primary network states and highlighted the dominance of major outlets like nytimes.com and cnn.com as central hubs of influence.

Conclusion and Future Directions

The proposed switched dynamic SEM provides a powerful framework for tracking hidden network topologies that undergo abrupt changes. While the current approach requires a predefined number of states $S$, future work may focus on automated state detection. Additionally, scaling these proximal-gradient methods to millions of nodes for real-time applications remains a key engineering challenge. Despite these hurdles, the ability to infer shifting influence patterns from simple timestamps offers profound insights into the dynamics of information spread.

Summary updated

Abstract

Contagions, such as the spread of popular news stories, or infectious diseases, propagate in cascades over dynamic networks with unobservable topologies. However, “social signals,” such as product purchase time, or blog entry timestamps are measurable, and implicitly depend on the underlying topology, making it possible to track it over time. Interestingly, network topologies often “jump” between discrete states that may account for sudden changes in the observed signals. The present paper advocates a switched dynamic structural equation model to capture the topology dependent cascade evolution, as well as the discrete states driving the underlying topologies. Conditions under which the proposed switched model is identifiable are established. Leveraging the edge sparsity inherent to social networks, a recursive ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -norm regularized least-squares estimator is put forth to jointly track the states and network topologies. An efficient first-order proximal-gradient algorithm is developed to solve the resulting optimization problem. Numerical experiments on both synthetic data and real cascades measured over the span of one year are conducted, and test results corroborate the efficacy of the advocated approach.
BibTeX
@article{baingana2016tracking,
  author = {Brian Baingana and Georgios B. Giannakis},
  title = {{Tracking Switched Dynamic Network Topologies From Information Cascades}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2016},
  doi = {10.1109/tsp.2016.2628354},
}
Figure