Source-linked AI summary
Inferring Networks of Diffusion and Influence
Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause
TL;DR
The paper addresses how to infer unobserved diffusion networks from infection or adoption times. It develops NETINF, a scalable near-optimal approximation algorithm, and finds core-periphery structure in online news propagation.
Problem
Transmission paths and the underlying networks of information diffusion and virus propagation are often unobserved despite observable infection or adoption times.
Method
NETINF models contagion cascades probabilistically and uses a scalable approximation algorithm to infer sparse directed networks from observed cascades.
Results
The inferred online news network has a core-periphery structure, with mass media influencing much of the blogosphere and sites interconnecting topic clusters.
Takeaways & Limitations
NETINF enables analysis of large real-world diffusion networks, including information flow among news websites and blogs.
Takeaways & Limitations
The method uses time differences to infer edges and assumes propagation networks are static, although real influence networks are dynamic.
Abstract
from arXiv · showhide
Information diffusion and virus propagation are fundamental processes taking place in networks. While it is often possible to directly observe when nodes become infected with a virus or adopt the information, observing individual transmissions (i.e., who infects whom, or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and finds provably near-optimal networks. We demonstrate the effectiveness of our approach by tracing information diffusion in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news for the top 1,000 media sites and blogs tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.
1. INTRODUCTION
The paper addresses diffusion and influence inference when transmissions and the underlying propagation network are unobserved. It introduces NETINF, a scalable approach that uses infection times across cascades to recover near-optimal directed networks and applies it to large-scale online news diffusion.
- Motivation: Diffusion processes are widespread, but observations often reveal when nodes become infected rather than who infected them or the network carrying the contagion.The challenge applies to information, viruses, diseases, and other contagions.
- Problem formulation: Observing many contagions enables inference because nodes repeatedly infected soon after one another suggest an underlying propagation edge.The premise uses correlations in infection times across cascades to estimate connectivity.
- Method: NETINF models contagions as directed trees on a hypothetical network and efficiently approximates the otherwise intractable network-likelihood optimization.The method considers many propagation trees consistent with observed infection times and exploits a diminishing-returns property to obtain near-optimal networks.
- Evaluation: Validation on synthetic and real datasets shows NETINF outperforms a baseline heuristic by an order of magnitude and correctly discovers more than 90% of edges.The paper reports reliable recovery regardless of overall network structure.
- Web application: Applied to 170 million blogs and news articles over one year, the inferred network has a core-periphery structure with core sites diffusing information to the rest of the Web.General news media sites act as connectors between stable circles of influence.
- Significance: Inferring propagation structure helps characterize node positions and roles in diffusion and assess their range of influence.The paper frames network modeling as a way to study information and virus propagation.
2. DIFFUSION NETWORK INFERENCE PROBLEM
The paper formulates inference of an unknown static directed propagation network from infection times without observing transmission sources. It models cascades as time-aware directed trees and seeks a network maximizing the likelihood of the observed cascades.
- Problem statement: The goal is to recover an unknown directed network from multiple contagions when only node infection or adoption times are observed.The transmission paths, node neighborhoods, and infecting sources are unobserved.
- Problem statement: Each cascade is represented by observed node–hit-time pairs, with uninfected nodes assigned hit time ∞.The complete propagation trace would instead record which node infected each other node.
- Estimating the network: The likelihood of a cascade in a candidate network sums the likelihoods of all propagation trees consistent with its observed hit times.A particular tree assigns successful propagation to its edges and cascade stopping to edges where propagation did not occur.
- Cascade Transmission Model: Under the Independent Cascade Model, each infected node independently attempts to infect neighbors, so each cascade forms a directed tree contained in the network.Only the first successful infection of a node matters; later infections have no impact.
- Cascade Transmission Model: Transmission probability Pc(u, v) is zero when u is infected after v, while otherwise it can depend on contagion, node, edge, and timing properties.For simplicity, the paper later models transmission using the hit-time difference and exponential or power-law incubation distributions.
- Estimating the network: Evaluating the exact likelihood remains impractical because quadratic evaluation is costly on large graphs and optimizing over all candidate graphs is super-exponential.The paper identifies efficient maximization of the full likelihood as an open problem at this stage.
3. ALTERNATIVE FORMULATION AND THE NETINF ALGORITHM
The paper replaces an intractable diffusion-network inference problem with a tractable approximation and optimizes it using NETINF. The method models external influence with ε-edges, selects likely propagation trees, and uses submodularity to obtain scalable near-optimal networks.
- 3.1 An alternative formulation: The approximation evaluates each cascade using only its most likely propagation tree instead of summing over all possible trees.The authors report that exhaustive-search experiments on small networks produced results indistinguishable from the original formulation.
- 3.1 An alternative formulation: ε-edges represent contagion transmissions caused by external influence rather than the inferred network.The graph is treated as fully connected, partitioned into network edges E and ε-edges Eε.
- 3.1 An alternative formulation: Propagation trees combine network and ε-edges, distinguishing edges that transmitted the contagion from those that failed to transmit it.The likelihood combines edge-type contributions with incubation-time products; Fig. 4 illustrates the four edge categories.
- 3.1 An alternative formulation: Each participating edge receives a non-negative weight equal to its improvement in log-likelihood under the most likely propagation tree.Under the approximation, nonparticipating-edge contributions are constant for a cascade and can be ignored when selecting the tree.
- 3.2 The NETINF algorithm for efficient maximization of FC(G): The resulting objective is monotonic and submodular, so greedy maximization provides a provably near-optimal solution to the NP-hard network-selection problem.Submodularity supplies the diminishing-returns property needed for efficient optimization.
- 3.2 The NETINF algorithm for efficient maximization of FC(G): 63% is the greedy algorithm’s worst-case guarantee relative to the optimum achievable with k edges.The bound is (1 − 1/e) ≈ 63% for monotonic submodular objectives.
- 3.2 The NETINF algorithm for efficient maximization of FC(G): Theorem 4 provides an online, data-dependent bound on how far a candidate network is from the unknown optimum.It uses the marginal gains of edges not already included in the candidate graph.
- 3.2 The NETINF algorithm for efficient maximization of FC(G): Localized updates and lazy evaluation reduce runtime by several orders of magnitude without loss in solution quality, enabling NETINF to scale.The paper notes that formal complexity analysis is out of scope because it depends heavily on network structure, so runtime is evaluated empirically.
4. EXPERIMENTAL EVALUATION
Synthetic and real-data experiments show that NETINF reliably recovers diffusion networks, achieves near-optimal objective values, remains robust across network and cascade structures, and scales to large datasets. On Web data, it improves over a heuristic baseline while accommodating noise and missing observations.
- Synthetic data: Two errors recovered a 20-node, 23-edge ground-truth network from 24 cascades using NETINF, whereas the baseline performed poorly.The experiment used an exponential incubation model with β = 0.2.
- Synthetic data: 97% of the optimal graph score was achieved at 2,000 inferred edges, with sparse solutions capturing most objective value.The objective flattened after about 1,000 edges, indicating diminishing returns from adding edges.
- Synthetic data: 0.99 break-even precision-recall was achieved across three Kronecker graphs, compared with 0.4–0.5 for the baseline under exponential incubation.NETINF remained strong across random, hierarchical-community, and core-periphery structures.
- Synthetic data: NETINF remained in the high 90s under power-law incubation while the baseline fell below 0.1, where heavier-tailed timing made inference harder.Performance on Forest Fire networks was somewhat lower, but NETINF remained stable across network structures and incubation models.
- Synthetic data: 2 propagation events per edge were typically sufficient for reliable network recovery, although larger cascades made parent identification harder.Performance increased with more cascade data, while smaller cascades required less data in the reported β comparison.
- Scalability: 45× localized updates and 6× lazy evaluation produced a 280× overall speedup without loss in solution quality, enabling 10,000-node inference within hours.These measurements were reported for a Kronecker network with an exponential incubation model, α = 1 and β = 0.5.
- Robustness: Noise and missing cascade nodes reduced performance, although ε-edges could mitigate the effect of missing observations.The experiments varied Gaussian timing noise and the percentage of missing nodes.
- Real data: On real Web data, NETINF improved blog-hyperlink break-even performance from 0.34 to 0.44 and Memetracker performance from 0.17 to 0.28.The Memetracker experiment inferred hyperlink structure from observed phrase-mention times, while the exponential incubation model was acknowledged as simplistic for real data.
5. FURTHER RELATED WORK
The paper situates its directed diffusion-network inference approach among probabilistic network inference and graphical-model structure learning, emphasizing general directed graphs and submodular optimization.
- CONNIE and NETRATE use generative probabilistic models and convex programming to infer latent social networks from diffusion cascades.
- Unlike Bayesian-network methods, this work learns directed networks without restricting them to acyclic graphs.The approach allows cycles and reciprocal edges.
- The method differs from undirected graphical-model structure learning by inferring directed rather than undirected networks.
- Bayesian-network structure inference methods are generally heuristic approaches without approximation guarantees.
- The paper identifies submodular function maximization for network structure learning as a novel application.
6. CONCLUSIONS
The paper presents NETINF as a scalable near-optimal method for inferring diffusion networks, validates its recovery performance, and applies it to large-scale online news propagation. The inferred networks reveal core-periphery organization and topic-based clusters, while the method remains limited by static-network assumptions and time-only edge inference.
- NETINF exploits submodularity, localized updates, and lazy evaluation to infer a near-optimal set of directed diffusion-network edges at scale.Selecting the best k edges by likelihood is NP-hard.
- Synthetic experiments show that NETINF accurately recovers underlying networks from relatively few cascade samples and outperforms a naive maximum-weight baseline.
- Real-data analysis finds a core-periphery network in which mass media influence most of the blogosphere.The analysis uses memes propagating across news websites and blogs.
- Topic-related site clusters emerge, while a few socially prominent sites interconnect clusters and may support cross-cluster information diffusion.
- The method uses time differences to infer edges and assumes static propagation networks, although real influence networks are dynamic.Future work proposes using textual content and relaxing the static-network assumption.
- The authors frame the results as a step toward understanding complex network processes from partial observations.