Unveiling the Hidden Pulse: Tracking Social Networks via Switched Dynamic SEMs
Switched dynamic structural equation models for tracking social network topologies
The paper introduces a Switched Dynamic Structural Equation Model (SEM) to track social network topologies that jump between discrete states. It utilizes infection timestamps from information cascades and exogenous influences to jointly infer the switching sequence and the sparse adjacency matrices of each network state.
TL;DR
Inferring the invisible architecture of social networks is a daunting task, especially when that architecture "jumps" between different states (e.g., a professional network during the week vs. a social one on weekends). This paper introduces a Switched Dynamic Structural Equation Model (SEM) that uses infection timestamps (cascades) to track these shifting topologies in real-time. By leveraging -sparsity regularization and an efficient Proximal-Gradient algorithm, the researchers can jointly identify which "state" the network is in and reconstruct its connection map.
Background & Motivation: Beyond Static Graphs
Most social signals—retweets, product purchases, or virus spreads—are measurable, but the underlying influence network is usually hidden. Previous State-of-the-Art (SOTA) methods often assumed that these networks evolve slowly.
However, the authors observe that human behavior is often hybrid: it has continuous dynamics (how a meme spreads) and discrete states (the context of the spread). A sports event or a political election can cause the network topology to "switch" instantly. The challenge is: how do we track these discrete state transitions and the specific sparse topology of each state simultaneously from streaming data?
Methodology: The Core Engine
The researchers model the infection time of node during interval as a linear combination of its graph neighbors' infection times and exogenous influences.
1. The Switched SEM Equation
The fundamental model is defined as:
eq i} a_{ij}^{\sigma(t)} y_{jc}^t + b_{ii}^{\sigma(t)} x_{ic} + e_{ic}^t$$ Here, $\sigma(t)$ is the "switch" that selects which topology $\mathbf{A}^s$ is active at time $t$. $\mathbf{X}$ represents external influences (like a news source), and $\mathbf{A}$ represents the internal nodal influence. ### 2. Sparsity and Optimization Since social networks are typically sparse (most people don't influence most others), the authors use an $\ell_1$-norm penalty. To avoid the NP-hard nature of switching systems, they split the problem into: * **State Estimation**: Choosing the most likely active state based on current model residuals. * **Topology Tracking**: Updating the parameters of that state using a **Proximal-Gradient (PG)** method.  *The matrix form of the dynamic SEM where Y is the infection timestamp matrix.* ## Parallelizable Tracking Algorithm The beauty of the proposed **Algorithm 1** lies in its recursivity. It doesn't need to store all past data. Instead, it maintains "moving averages" (Gram matrices) of the data. The updates for the adjacency matrix $\mathbf{A}$ and the exogenous matrix $\mathbf{B}$ are performed via **Soft-Thresholding**, which is computationally cheap and allows for parallel processing across different nodes.  *The Topology Tracking Algorithm (Algorithm 1) alternates between state selection and ISTA-based parameter updates.* ## Experiments & Results The authors tested their model on **Kronecker graphs**, which closely mimic real-world network properties. * **Topology Recovery**: As shown in the heatmaps (Fig. 1 in the paper), the algorithm successfully recovered the sparse structure of multiple different states from noisy infection data. * **Switching Accuracy**: The model was exceptionally robust in detecting exactly when the network switched from one topological state to another.  *Fig 2: The estimated switching sequence (b) meticulously tracks the actual ground truth (a).* ## Critical Insight & Conclusion This paper bridges the gap between **Control Theory** (switched linear systems) and **Social Network Analysis**. The use of Proximal-Gradient methods ensures that the solution remains scalable for the "Big Data" of the modern web. **Limitations**: The model currently requires the number of states ($S$) to be known a priori. In real-world scenarios, the number of potential network states might be unknown or infinite. **Future Work**: Incorporating Bayesian non-parametrics to automatically discover the number of states would be a significant next step for this research.