Abstract
Information diffusion is a fundamental process that takes place over networks. While it is rarely realistic to observe the individual transmissions of the information diffusion process, it is typically possible to observe when individuals first publish the information. We look specifically at previously published algorithm NETINF that probabilistically identifies the optimal network that best explains the observed infection times. We explore how the algorithm could perform on a range of intrinsically different social and information network topologies, from news blogs and websites to Twitter to Reddit.
Introduction
In modern social media environments, the underlying "who-follows-whom" network is frequently invisible or private. While we can observe the timing of posts (cascades), the specific paths of influence remain hidden. This study explores the challenge of network inference: reconstructing the most likely edges of a social network based solely on the arrival times of "contagions"—in this case, image submissions on Reddit.
Methodology
The researchers utilized the NETINF algorithm, which treats network reconstruction as a probabilistic inference problem. If node $v$ consistently posts shortly after node $u$ across multiple cascades, the algorithm assigns a high probability to a directed edge from $u$ to $v$. To maintain computational tractability, the algorithm leverages submodularity, allowing for a greedy optimization approach to identify a near-optimal set of edges.
Unlike traditional epidemiological models (SIR), the authors argue that Reddit diffusion follows an SI (Susceptible-Infected) model. In this framework, once a user is "infected" with content, they do not recover; instead, they may continue to share it across different subreddits over time, acting as a persistent carrier of the information.
Dataset and Scaling
The study employed two datasets:
- Synthetic Data: Kronecker networks (512 nodes, 1024 edges) to establish a ground-truth baseline.
- Reddit Dataset: 132,308 image submissions from 2009 to 2013, involving 16,736 unique images and their associated timestamps.
To handle the massive Reddit dataset, the pipeline was migrated to Azure D14 cloud servers. Through batching and parallelization, the estimated runtime was reduced from 150 hours to just 8 hours.
Key Results and Insights
Thresholding and Data Sparsity
The number of edges the algorithm can confidently identify is heavily dependent on the minimum cascade length chosen for the data subset. As the threshold for "popular" content increases, the available data for inference drops significantly.
Network Topology and "Hub" Posters
The inferred Reddit network revealed a highly fragmented structure. Rather than a dense, interconnected web, the network is dominated by unidirectional chains and a few central "Hub" posters. These hubs act as aggregators, consuming content from specific niches and dispersing it widely to maximize karma.
Analysis showed that Reddit is composed of many "small worlds" with minimal overlap—for instance, there is virtually no interaction between niche hobbyist communities. This fragmentation suggests that global network reconstruction is difficult, as local influences dominate the diffusion process.
Conclusion
The study demonstrates that real-world social data is more constrained and sparse than synthetic models suggest. While longer cascades provide more raw data, shorter cascades are often more effective for pinpointing specific local influences. Future work will focus on validating these inferred edges against public "retweet" data on Twitter and further optimizing the algorithm's concurrency for larger datasets.
Summary updated