Tracking the Invisible: Inferring Dynamic Social Topologies via Proximal Gradients
13597_Proximal-Gradient Algorithms for Tracking Cascades Over Social Networks.
This paper introduces a dynamic Structural Equation Model (SEM) to track the time-varying and sparse topologies of social networks using infection or adoption timestamps. The authors develop a suite of algorithms based on Proximal Gradient descent (ISTA), its accelerated variant (FISTA), and Stochastic Gradient Descent (SGD) to estimate directed network edges while accounting for external (exogenous) influences.
TL;DR
Information cascades—the way news, viruses, or trends spread—often mask the underlying network structure. This paper proposes a Dynamic Structural Equation Model (SEM) combined with Proximal Gradient algorithms to unmask these hidden, time-varying, and sparse networks using only the timestamps of when nodes "adopt" a trend.
Background: Why Inferring Networks is Hard
In a world of "viral" content, we usually see when someone tweets but rarely why or who specifically influenced them. Previous methods faced a trifecta of challenges:
- Stationarity Assumption: They assumed the network never changed.
- Directionality: They struggled to distinguish between "A influenced B" and "B influenced A."
- External Bias: They failed to account for "exogenous" factors (e.g., reading a mainstream news site vs. being influenced by a friend).
Methodology: The Dynamic SEM Framework
The authors model the infection time of node for contagion at time as:
eq i} a_{ij}^t y_{jc}^t + b_{ii}^t x_{ic} + e_{ic}^t$$ - **$a_{ij}^t$**: The directed edge weight (endogenous influence). - **$b_{ii}^t x_{ic}$**: The external influence (exogenous susceptibility). - **$e_{ic}^t$**: Unmodeled noise. ### The Optimization Solver To track this in real-time, the paper uses an **Exponentially-Weighted Least-Squares (EWLS)** criterion with an $L_1$ penalty to enforce sparsity.  *Above: Example of an 8-node network where edges evolve over three time intervals.* The researchers developed three flavors of solvers: - **ISTA (Iterative Shrinkage-Thresholding)**: Basic proximal gradient. - **FISTA (Fast ISTA)**: Uses Nesterov acceleration to speed up convergence. - **SGD (Stochastic Gradient Descent)**: For ultra-large-scale, "on-the-fly" processing. ## Performance and Real-World Validation The algorithms were tested against synthetic datasets (Kronecker graphs) and real-world media traces. ### Synthetic Efficiency FISTA showed a significant advantage in convergence speed over standard ISTA, while the SGD version proved capable of tracking even non-smooth, abrupt changes in edge weights.  *Fig 4. MSE versus time for different edge evolution patterns, demonstrating the robustness of Algorithm 1.* ### Case Study: "Kim Jong-un" and "LinkedIn IPO" By analyzing meme propagation in 2011, the model successfully mapped the "media frenzy." For the keyword "Kim Jong-un," the inferred network showed a massive spike in edges (connectivity) exactly during his appointment and the death of Kim Jong-il. Similarly, the network for "Reid Hoffman" spiked during the LinkedIn IPO.  *Evidence of connectivity spikes matching major geopolitical events.* ## Critical Insight: The "Warm-Restart" Advantage A key takeaway for practitioners is the use of **Warm-Restarts**. In dynamic environments, the network at time $t$ is usually very similar to time $t-1$. By initializing the algorithm with the previous solution, the authors reduced the number of iterations needed for convergence to as few as 5–10 per window, making it viable for near-streaming applications. ## Conclusion This paper elevates network inference from a static statistical exercise to a dynamic tracking problem. By blending structural equations with modern proximal optimization, it provides the tools to map the invisible hand of social influence as it shifts in real-time. ### Future Directions - **Scalability**: Moving towards MapReduce/Hadoop for million-node graphs. - **Causality**: Formalizing the links between these inferred edges and true causal influence.