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 ...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.展开更多
In social network applications,individual opinion is often influenced by groups,and most decisions usually reflect the majority’s opinions.This imposes the group influence maximization(GIM) problem that selects k ini...In social network applications,individual opinion is often influenced by groups,and most decisions usually reflect the majority’s opinions.This imposes the group influence maximization(GIM) problem that selects k initial nodes,where each node belongs to multiple groups for a given social network and each group has a weight,to maximize the weight of the eventually activated groups.The GIM problem is apparently NP-hard,given the NP-hardness of the influence maximization(IM) problem that does not consider groups.Focusing on activating groups rather than individuals,this paper proposes the complementary maximum coverage(CMC) algorithm,which greedily and iteratively removes the node with the approximate least group influence until at most k nodes remain.Although the evaluation of the current group influence against each node is only approximate,it nevertheless ensures the success of activating an approximate maximum number of groups.Moreover,we also propose the improved reverse influence sampling(IRIS) algorithm through fine-tuning of the renowned reverse influence sampling algorithm for GIM.Finally,we carry out experiments to evaluate CMC and IRIS,demonstrating that they both outperform the baseline algorithms respective of their average number of activated groups under the independent cascade(IC)model.展开更多
基金support from the National Natural Science Foundation of China(Grant No.T2293771)the STI 2030-Major Projects(Grant No.2022ZD0211400)the Sichuan Province Outstanding Young Scientists Foundation(Grant No.2023NSFSC1919)。
文摘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.
基金supported by the Natural Science Foundation of Fujian Province (No. 2020J01845)the Educational Research Project for Young and MiddleAged Teachers of Fujian Provincial Department of Education (No. JAT190613)+1 种基金the National Natural Science Foundation of China (Nos. 61772005 and 92067108)the Outstanding Youth Innovation Team Project for Universities of Shandong Province (No. 2020KJN008)。
文摘In social network applications,individual opinion is often influenced by groups,and most decisions usually reflect the majority’s opinions.This imposes the group influence maximization(GIM) problem that selects k initial nodes,where each node belongs to multiple groups for a given social network and each group has a weight,to maximize the weight of the eventually activated groups.The GIM problem is apparently NP-hard,given the NP-hardness of the influence maximization(IM) problem that does not consider groups.Focusing on activating groups rather than individuals,this paper proposes the complementary maximum coverage(CMC) algorithm,which greedily and iteratively removes the node with the approximate least group influence until at most k nodes remain.Although the evaluation of the current group influence against each node is only approximate,it nevertheless ensures the success of activating an approximate maximum number of groups.Moreover,we also propose the improved reverse influence sampling(IRIS) algorithm through fine-tuning of the renowned reverse influence sampling algorithm for GIM.Finally,we carry out experiments to evaluate CMC and IRIS,demonstrating that they both outperform the baseline algorithms respective of their average number of activated groups under the independent cascade(IC)model.
