Source-linked AI summary
Structure and Dynamics of Information Pathways in Online Media
Manuel Gomez Rodriguez, Jure Leskovec, Bernhard Schölkopf
TL;DR
The paper asks how to infer diffusion networks when both their structure and edge dynamics change over time. It develops the online INFOPATH algorithm and applies it to large-scale media cascades, finding that pathways are stable for recurrent topics but shift sharply during major events. These shifts include short-lived media clusters and increased blog information transfer during social movements and civil unrest.
Problem
The paper addresses how to infer unobserved dynamic networks and changing contagion pathways from observed diffusion or infection times.
Method
INFOPATH uses stochastic-gradient optimization with a diffusion model to estimate time-varying network edges and transmission rates online, emphasizing recent cascades.
Results
INFOPATH tracks dynamic network topology and transmission rates synthetically, while real data show stable recurrent-topic pathways and dramatic event-driven shifts.
Takeaways & Limitations
Information pathways and influential media structures can emerge, vanish, and reorganize over days, especially around major social movements and civil unrest.
Takeaways & Limitations
The authors identify rigorous convergence analysis for the stochastic-gradient method as future work and note that inferred network changes may reflect sudden external events.
Abstract
from arXiv · showhide
Diffusion of information, spread of rumors and infectious diseases are all instances of stochastic processes that occur over the edges of an underlying network. Many times networks over which contagions spread are unobserved, and such networks are often dynamic and change over time. In this paper, we investigate the problem of inferring dynamic networks based on information diffusion data. We assume there is an unobserved dynamic network that changes over time, while we observe the results of a dynamic process spreading over the edges of the network. The task then is to infer the edges and the dynamics of the underlying network. We develop an on-line algorithm that relies on stochastic convex optimization to efficiently solve the dynamic network inference problem. We apply our algorithm to information diffusion among 3.3 million mainstream media and blog sites and experiment with more than 179 million different pieces of information spreading over the network in a one year period. We study the evolution of information pathways in the online media space and find interesting insights. Information pathways for general recurrent topics are more stable across time than for on-going news events. Clusters of news media sites and blogs often emerge and vanish in matter of days for on-going news events. Major social movements and events involving civil population, such as the Libyan's civil war or Syria's uprise, lead to an increased amount of information pathways among blogs as well as in the overall increase in the network centrality of blogs and social media sites.
1. INTRODUCTION
The paper addresses inference of unobserved, time-varying diffusion networks from observed infection times and develops INFOPATH to estimate changing edges and transmission dynamics. Applied to large-scale online media data, it finds that information pathways vary with topic and event type, with social movements associated with increased blog information transfer.
- Problem: Observed infection times reveal diffusion traces, but the network edges carrying contagions often remain unobserved.This gap applies to information diffusion, behavior adoption, and disease transmission.
- Problem: Previous network-inference methods assumed static network structure and constant edge transmission dynamics.The paper motivates time-varying inference because contagion pathways can change with the propagating content.
- Evaluation: 179 million information cascades among 3.3 million blog and news media sites were analyzed over one year.The study period ran from March 2011 through February 2012.
- Findings: General recurrent topics have relatively stable information pathways, whereas unexpected events produce dramatic changes and short-lived clusters of news sites and blogs.Clusters can emerge and vanish within days during ongoing news events.
- Findings: News involving large-scale social movements and civil unrest produces greater increases in information transfer among blogs than among mainstream media.Examples include the Libyan civil war, Egypt’s revolution, Syria’s uprising, and Occupy Wall Street.
- Method: INFOPATH combines stochastic-gradient optimization with a diffusion model to estimate time-varying network edges and transmission rates online.The model uses observed temporal diffusion events and emphasizes recent cascades when estimating current structure.
2. PROBLEM FORMULATION
The paper formulates dynamic network inference from observed contagion infection times when the underlying diffusion pathways are hidden. It models heterogeneous transmission rates and estimates time-varying networks through weighted maximum likelihood.
- Observed data: Observed cascades record node infection times, while the edges that generated those infections remain unobserved.Each cascade is observed over a finite window, and nodes not infected during that window are represented by ∞.
- Diffusion model: Each contagion propagates independently, and a node is infected only once by the first parent that infects it.The infection likelihood sums over mutually disjoint events in which each possible parent is first.
- Transmission model: Pairwise transmission rates α_j,i quantify how frequently information spreads from node j to node i and may differ across edges.The model allows rates to change across cascades but not within a cascade, enabling time-varying diffusion networks.
- Transmission model: The continuous-time model uses survival and hazard functions to represent transmission likelihoods, including exponential, power-law, and Rayleigh edge models.Uninfected nodes contribute multiplicative survival terms to the cascade likelihood.
- Dynamic network inference: INFOPATH is specified as an on-line dynamic network inference algorithm for efficiently solving the time-varying optimization problem.The formulation uses iterative updates with step sizes and nonnegative projected transmission-rate estimates.
- Dynamic network inference: Dynamic inference maximizes a weighted log-likelihood over cascades observed by time t, assigning greater importance to recent cascades.The inferred edges are node pairs whose estimated transmission rates α_j,i(t) are positive.
3. THE INFOPATH ALGORITHM
INFOPATH formulates dynamic network inference as a convex optimization problem and solves it online with projected stochastic gradients. It uses recency-aware sampling and aging to track changing transmission rates while controlling computation.
- The network inference problem is convex under log-concave survival and concave hazard functions for the considered transmission models.
- Projected stochastic gradient updates use sampled cascades and nonnegative projection to estimate edge transmission rates over time.The gradients for all three edge transmission models are specified in Table 2.
- Recent cascades receive higher implicit importance because sampling probabilities decay with cascade age, improving scalability over explicitly weighting all historic data.The algorithm initializes each edge rate at its previous outputted estimate to further speed computation.
- Each iteration computes gradients only for edges whose source node was infected in the sampled cascade, making iteration cost and convergence rate independent of |C|.The paper leaves rigorous convergence analysis for future work because standard gradient conditions can be violated.
- Aging edges: Unused edges are multiplied by aging factor ρ so their transmission rates decay toward zero; experiments use ρ = 0.95.This addresses edges that remain positive when their source node is not infected in subsequent cascades.
- Cascade sampling: Shorter sampling windows track transmission-rate changes faster but produce less reliable estimates, creating a tradeoff that requires many cascades over time.
4. EXPERIMENTAL EVALUATION
The evaluation tests INFOPATH on synthetic dynamic networks and real hyperlink cascades, measuring edge recovery, transmission-rate tracking, speed, and evolving information pathways. INFOPATH remains stable across synthetic temporal changes, is substantially faster than NETRATE, and reveals rapidly changing structures and centrality patterns in online media.
- Real-data evaluation: 179 million information cascades from 3.3 million media sites were used to evaluate dynamic network inference over one year.The real-data evaluation covered March 2011 through February 2012.
- Synthetic evaluation: INFOPATH tracks evolving edge transmission rates and remains stable across time, with continuous evolution patterns easier to estimate than discontinuous ones.Synthetic experiments used multiple Kronecker topologies and five transmission-rate evolution patterns.
- Synthetic evaluation: 10 to 100 times faster than NETRATE, INFOPATH reaches the same accuracy while attaining lower MSE more quickly.INFOPATH is as fast as NETINF in the reported static-network comparison.
- Real-data evaluation: Online diffusion networks usually have core-periphery structure, but clusters can emerge and vanish within short periods because of geography, language, or shared events.The examples include sudden clustering around EU sanctions against Syria and geographically separated Fukushima discussions.
- Real-data evaluation: Unexpected news events produce sharp short-term increases in connectivity, whereas recurrent topics such as the NBA show more stable networks.Blogs sometimes lead mainstream media for population-wide events, although mainstream-media-to-mainstream-media links are usually most numerous.
- Real-data evaluation: Blogs comprise roughly 30% to 70% of the top 100 most central sites across most topics, with their centrality rising during events such as Occupy Wall Street.Mainstream media dominate some topics, while blogs dominate others for substantial periods.
- Real-data evaluation: Time-varying hyperlink networks show weekly periodicity and performance around 0.4 to 0.5 for Precision, Recall, and Accuracy.This result uses 11,461 nodes, 19,915 edges, and 495,655 hyperlink cascades.
5. CONCLUSION
INFOPATH infers time-varying diffusion edges and transmission rates, enabling information pathways to emerge and vanish over time. Synthetic and real-data experiments show accurate dynamic tracking and distinct stability patterns across topics and events.
- INFOPATH provides on-line estimates of network edges and dynamic edge transmission rates, unlike prior static network-inference algorithms.
- INFOPATH successfully tracks changing network topology, estimates time-varying transmission rates accurately, and remains robust across tested network conditions.
- General recurrent topics have relatively stable information pathways, whereas major real-world events produce dramatic pathway changes.
- Clusters of mainstream news sites and blogs can emerge and disappear within days.
- Early information transfer increases more among blogs than mainstream media for news involving social unrest and general-population events.
- The authors identify future work in convergence analysis, external-influence detection, unexpected-event detection, and signed-network inference for sentiment.