SORB benchmark reveals graph reduction skews influence maximization on multilayer networks
New open-source framework shows sparsification preserves seed quality but flattening ruins rankings...
Real-world networks are messy — incomplete, noisy, and constantly changing. That makes influence maximization (IM), the task of finding key nodes to maximize information spread, computationally expensive. A new paper from Polish researchers introduces SORB (Spreading-Oriented Reduction Benchmark), an open-source framework that systematically measures how graph reduction techniques impact IM accuracy. Instead of analyzing IM algorithms in isolation, SORB quantifies how preprocessing steps like sparsification (removing edges) and coarsening (merging nodes) alter predictive performance across diverse network types.
Using SORB, the team tested several IM scenarios on both single-layer and multirelational (multilayer) networks. Key finding: sparsification preserves seed set quality (Gain@k) on single-layer networks, but flattening multilayer networks into a single layer causes systematic ranking degradation (AUC_cutoff) no matter which reduction strategy is used. This has major implications for social network analysis, epidemiology, and viral marketing — where practitioners often flatten heterogeneous networks without accounting for structural loss. SORB is available on GitHub and supports custom datasets, making it a valuable tool for researchers and engineers building scalable influence models.
- SORB is an open-source benchmark integrating sparsification and coarsening into influence maximization evaluation pipelines
- Sparsification retains seed quality on single-layer networks but flattening multilayer networks degrades rankings regardless of reduction method
- Framework tested on real-world single-layer and multilayer graphs with Gain@k and AUC_cutoff metrics
Why It Matters
For data scientists and network engineers: naive graph reduction can silently break influence models — use SORB to validate your preprocessing.