GPIC: a GPU-based parallel independent cascade algorithm in complex networks

Abstract Independent cascade (IC) models, by simulating how one node can activate another, are important tools for studying the dynamics of information spreading in complex networks. However, traditional algorithms for the IC model implementation face significant efficiency bottlenecks when dealing with large-scale networks and multi-round simulations. To settle this problem, this study introduce a GPU-based parallel independent cascade (GPIC) algorithm, featuring an optimized representation of the network data structure and parallel task scheduling strategies. Specifically, for this GPIC algorithm, we propose a network data structure tailored for GPU processing, thereby enhancing the computational efficiency and the scalability of the IC model. In addition, we design a parallel framework that utilizes the full potential of GPU’s parallel processing capabilities, thereby augmenting the computational efficiency. The results from our simulation experiments demonstrate that GPIC not only preserves accuracy but also significantly boosts efficiency, achieving a speedup factor of 129 when compared to the baseline IC method. Our experiments also reveal that when using GPIC for the independent cascade simulation, 100-200 simulation rounds are sufficient for higher-cost studies, while high precision studies benefit from 500 rounds to ensure reliable results, providing empirical guidance for applying this new algorithm to practical research.