Coarsening Massive Influence Networks for Scalable Diffusion Analysis
Summary: Coarsens large influence graphs into vertex-weighted summaries preserving diffusion properties. Two implementations—linear-time speed-focused and scalable near-linear with sublinear space—enable frameworks that accelerate influence maximization and estimation on billion-edge networks, shrinking graphs to ~4% and delivering ~4x/3.5x speedups. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Naoto Ohsaka (Exploratory Research for Advanced Technology; Japan Science and Technology Agency; Kawarabayashi Large Graph Project; University of Tokyo)
- 2. Tomohiro Sonobe (Exploratory Research for Advanced Technology; Japan Science and Technology Agency; Kawarabayashi Large Graph Project; National Institute of Informatics)
- 3. Sumio Fujita (Yahoo)
- 4. Ken-ichi Kawarabayashi (Exploratory Research for Advanced Technology; Japan Science and Technology Agency; Kawarabayashi Large Graph Project; National Institute of Informatics)
BibTeX Citation
@inproceedings{ohsaka_sigmod17,
title = {{Coarsening Massive Influence Networks for Scalable Diffusion Analysis}},
author = {Ohsaka, Naoto and Sonobe, Tomohiro and Fujita, Sumio and Kawarabayashi, Ken-ichi},
series = {{SIGMOD} '17},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3035918.3064045},
url = {https://dl.acm.org/doi/10.1145/3035918.3064045},
year = {2017}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,872 | The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches | 2020 | SIGMOD | 5.9639045e-05 |
| 7,445 | Analysis of Influence Contribution in Social Advertising | 2022 | VLDB | 5.5247739e-05 |
| 11,770 | Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem | 2023 | VLDB | 4.9793485e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 199 | Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency | 2014 | SIGMOD | 0.00025522558 |
| 320 | Influence Maximization in Near-Linear Time: A Martingale Approach | 2015 | SIGMOD | 0.00021143147 |
| 394 | One Trillion Edges: Graph Processing at Facebook-Scale | 2015 | VLDB | 0.00019191286 |
| 455 | Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks | 2016 | SIGMOD | 0.0001796092 |
| 1,187 | Local Graph Sparsification for Scalable Clustering | 2011 | SIGMOD | 0.00011606901 |
| 1,368 | Computing Personalized PageRank Quickly by Exploiting Graph Structures | 2014 | VLDB | 0.0001090624 |
| 2,563 | SCARAB: Scaling Reachability Computation on Large Graphs | 2012 | SIGMOD | 8.2934229e-05 |
| 7,586 | Dynamic Influence Analysis in Evolving Networks | 2016 | VLDB | 5.4896843e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,554 | Influence Maximization via Vertex Countering | 2024 | VLDB |
| 2 | 2,697 | Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks | 2020 | VLDB |
| 3 | 11,723 | Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach | 2023 | SIGMOD |
| 4 | 299 | A Data-Based Approach to Social Influence Maximization | 2012 | VLDB |
| 5 | 9,542 | Hindering Influence Diffusion of Community | 2022 | SIGMOD |
| 6 | 6,506 | Influence Maximization in Real-World Closed Social Networks | 2023 | VLDB |
| 7 | 9,963 | Fast and Space-Efficient Parallel Algorithms for Influence Maximization | 2024 | VLDB |
| 8 | 320 | Influence Maximization in Near-Linear Time: A Martingale Approach | 2015 | SIGMOD |
| 9 | 7,586 | Dynamic Influence Analysis in Evolving Networks | 2016 | VLDB |
| 10 | 199 | Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency | 2014 | SIGMOD |