中国物理B ›› 2025, Vol. 34 ›› Issue (3): 30204-030204.doi: 10.1088/1674-1056/adb67c

所属专题： SPECIAL TOPIC — Computational programs in complex systems

• • 上一篇    下一篇

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

Chang Su(苏畅)1, Xu Na(那旭)1, Fang Zhou(周方)2, and Linyuan Lü(吕琳媛)3,†   

  1. 1 Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China;
    2 Hangzhou Innovation Institute of Beihang University, Hangzhou 310000, China;
    3 School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230026, China
  • 收稿日期:2024-11-27 修回日期:2025-02-10 接受日期:2025-02-15 发布日期:2025-03-15
  • 通讯作者: Linyuan Lü E-mail:linyuan.lv@ustc.edu.cn
  • 基金资助:
    The author acknowledges support from the National Natural Science Foundation of China (Grant No. T2293771), the STI 2030-Major Projects (Grant No. 2022ZD0211400), and the Sichuan Province Outstanding Young Scientists Foundation (Grant No. 2023NSFSC1919).

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

Chang Su(苏畅)1, Xu Na(那旭)1, Fang Zhou(周方)2, and Linyuan Lü(吕琳媛)3,†   

  1. 1 Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China;
    2 Hangzhou Innovation Institute of Beihang University, Hangzhou 310000, China;
    3 School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230026, China
  • Received:2024-11-27 Revised:2025-02-10 Accepted:2025-02-15 Published:2025-03-15
  • Contact: Linyuan Lü E-mail:linyuan.lv@ustc.edu.cn
  • Supported by:
    The author acknowledges support from the National Natural Science Foundation of China (Grant No. T2293771), the STI 2030-Major Projects (Grant No. 2022ZD0211400), and the Sichuan Province Outstanding Young Scientists Foundation (Grant No. 2023NSFSC1919).

RichHTML

0

PDF (PC)

261

赞

补充材料

1

摘要： 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 introduces 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.

关键词: complex networks, information spreading, independent cascade model, parallel computing, GPU

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 introduces 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.

Key words: complex networks, information spreading, independent cascade model, parallel computing, GPU

中图分类号:  (Computational techniques; simulations)

  • 02.70.-c
64.60.aq (Networks) 89.20.Ff (Computer science and technology)