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,786 | The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches | 2020 | SIGMOD | 6.0890538e-05 |
| 7,315 | Analysis of Influence Contribution in Social Advertising | 2022 | VLDB | 5.6470323e-05 |
| 11,458 | Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem | 2023 | VLDB | 5.093636e-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 |
|---|---|---|---|---|
| 194 | Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency | 2014 | SIGMOD | 0.000259047 |
| 315 | Influence Maximization in Near-Linear Time: A Martingale Approach | 2015 | SIGMOD | 0.00021436156 |
| 389 | One Trillion Edges: Graph Processing at Facebook-Scale | 2015 | VLDB | 0.00019386526 |
| 453 | Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks | 2016 | SIGMOD | 0.00018145895 |
| 1,163 | Local Graph Sparsification for Scalable Clustering | 2011 | SIGMOD | 0.00011865557 |
| 1,339 | Computing Personalized PageRank Quickly by Exploiting Graph Structures | 2014 | VLDB | 0.00011112799 |
| 3,021 | SCARAB: Scaling Reachability Computation on Large Graphs | 2012 | SIGMOD | 7.8401031e-05 |
| 7,446 | Dynamic Influence Analysis in Evolving Networks | 2016 | VLDB | 5.6149944e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,216 | Influence Maximization via Vertex Countering | 2024 | VLDB |
| 2 | 2,752 | Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks | 2020 | VLDB |
| 3 | 11,409 | Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach | 2023 | SIGMOD |
| 4 | 296 | A Data-Based Approach to Social Influence Maximization | 2012 | VLDB |
| 5 | 9,396 | Hindering Influence Diffusion of Community | 2022 | SIGMOD |
| 6 | 6,415 | Influence Maximization in Real-World Closed Social Networks | 2023 | VLDB |
| 7 | 11,286 | Fast and Space-Efficient Parallel Algorithms for Influence Maximization | 2024 | VLDB |
| 8 | 315 | Influence Maximization in Near-Linear Time: A Martingale Approach | 2015 | SIGMOD |
| 9 | 7,446 | Dynamic Influence Analysis in Evolving Networks | 2016 | VLDB |
| 10 | 194 | Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency | 2014 | SIGMOD |