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 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
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.
Fund: 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).
Chang Su(苏畅), Xu Na(那旭), Fang Zhou(周方), and Linyuan Lü(吕琳媛) GPIC: A GPU-based parallel independent cascade algorithm in complex networks 2025 Chin. Phys. B 34 030204
[1] Barabási A L 2013 Phil. Trans. R. Soc. A 371 20120375 [2] Newman M 2018 Networks (New York: Oxford University Press) [3] Luding S 2005 Nature 435 159 [4] Goldenberg J, Libai B and Muller E 2001 Market. Lett. 12 211 [5] Goldenberg J, Libai B and Muller E 2001 Acad. Market. Sci. Rev. 9 1 [6] Chen D, Lü L, Shang M S, Zhang Y C and Zhou T 2012 Physica A 391 1777 [7] Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C and Zhou T 2016 Phys. Rep. 650 1 [8] Malliaros F D, RossiME G and Vazirgiannis M 2016 Sci. Rep. 6 19307 [9] Granovetter M S 1973 Am. J. Sociol. 78 1360 [10] Granovetter M 1983 Sociol. Theor. 1 201 [11] Lü L and Zhou T 2011 Physica A 390 1150 [12] Wiki 2024 GPU Wikipedia [13] Krizhevsky A, Sutskever I and Hinton G E 2017 Communications of the ACM 60 84 [14] Huang Y P, Xia Y, Yang L, Wei J, Yang Y I and Gao Y Q 2022 Chin. J. Chem. 40 160 [15] Wang B,Wald I, Morrical N, UsherW, Mu L, Thompson K and Hughes R 2022 Comput. Phys. Commun. 271 108221 [16] Zhang Y H, Zhu H Z, Dong Y J, Zeng J, Han X P, Bratchenko I A, Zhang F R, Xu S Y and Wang S 2023 Chin. Phys. B 32 118702 [17] Zhang B D, Tang Y H, Wu J J and Li X 2011 Chin. Phys. B 20 098901 [18] Du Nguyen H A, Al-Ars Z, Smaragdos G and Strydis C 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE) (Grenoble, France) p. 974 [19] Gao M, Li Z, Li R, Cui C, Chen X, Ye B, Li Y, Gu W, Gong Q, Wang X and Chen Y 2023 Patterns 4 100839 [20] Zheng Z, Shi X and Jin H 2023 IEEE Transactions on Big Data 9 677 [21] Liu X, Li M, Li S, Peng S, Liao X and Lu X 2014 IEEE Transactions on Parallel and Distributed Systems 25 136 [22] Zou P, Lü Y s,Wu L d, Chen L l and Yao Y p 2013 Simulation 89 1154 [23] Barabási A L and Albert R 1999 Science 286 509 [24] Erdős P and Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17 [25] Eggemann N and Noble S D 2011 Discrete Appl. Math. 159 953 [26] Watts D J and Strogatz S H 1998 Nature 393 440 [27] Liu J G, Lin J H, Guo Q and Zhou T 2016 Sci. Rep. 6 21380 [28] Kempe D, Kleinberg J and Tardos É 2003 Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Washington, D.C, USA) p. 137 [29] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E and Makse H A 2010 Nat. Phys. 6 888 [30] Iannelli F, Mariani M S and Sokolov I M 2018 Phys. Rev. E 98 062302 [31] Awerbuch B, Goldberg A V, LubyMand Plotkin S A 1989 30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, NC, USA) p. 364 [32] Ren X L, Gleinig N, Helbing D and Antulov-Fantulin N 2019 Proc. Natl. Acad. Sci. USA 116 6554 [33] Jajodia S, Noel S and O’berry B 2005 Topological analysis of network attack vulnerability (Boston, MA: Springer) [34] Katz E and Lazarsfeld P F 1955 Personal influence: The part played by people in the flow of mass communications (New York: Routledge) [35] Watts D J and Dodds P S 2007 J. Consum. Res. 34 441 [36] Leskovec J, Kleinberg J and Faloutsos C 2007 ACM Trans. Knowl. Discov. Data 1 2 [37] Leskovec J, Lang K J, Dasgupta A and Mahoney M W 2009 Internet Mathematics 6 29 [38] Yang J and Leskovec J 2012 IEEE 12th International Conference on Data Mining (Brussels, Belgium) p. 745 [39] Yang P L, Zhao L J, Dong C, Xu G Q and Zhou L X 2023 Chin. Phys. B 32 058901 [40] Keeling M J and Rohani P 2008 Modeling Infectious Diseases in Humans and Animals (Princeton: Princeton University Press) [41] Liu S, Perra N, Karsai M and Vespignani A 2014 Phys. Rev. Lett. 112 118702 [42] Pastor-Satorras R, Castellano C, Van Mieghem P and Vespignani A 2015 Rev. Mod. Phys. 87 925
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
