The influence maximization(IM)problem aims to find a set of seed nodes that maximizes the spread of their influence in a social network.The positive influence maximization(PIM)problem is an extension of the IM problem...The influence maximization(IM)problem aims to find a set of seed nodes that maximizes the spread of their influence in a social network.The positive influence maximization(PIM)problem is an extension of the IM problem,which consider the polar relation of nodes in signed social networks so that the positive influence of seeds can be the most widely spread.To solve the PIM problem,this paper proposes the polar and decay related independent cascade(IC-PD)model to simulate the influence propagation of nodes and the decay of information during the influence propagation in signed social networks.To overcome the low efficiency of the greedy based algorithm,this paper defines the polar reverse reachable(PRR)set and devises a signed reverse influence sampling(SRIS)algorithm.The algorithm utilizes the ICPD model as well as the PRR set to select seeds.There are two phases in SRIS.One is the sampling phase,which utilizes the IC-PD model to generate the PRR set and a binary search algorithm to calculate the number of needed PRR sets.The other is the node selection phase,which uses a greedy coverage algorithm to select optimal seeds.Finally,Experiments on three real-world polar social network datasets demonstrate that SRIS outperforms the baseline algorithms in effectiveness.Especially on the Slashdot dataset,SRIS achieves 24.7% higher performance than the best-performing compared algorithm under the weighted cascade model when the seed set size is 25.展开更多
The reversible spreading processes with repeated infection widely exist in nature and human society,such as gonorrhea propagation and meme spreading.Identifying influential spreaders is an important issue in the rever...The reversible spreading processes with repeated infection widely exist in nature and human society,such as gonorrhea propagation and meme spreading.Identifying influential spreaders is an important issue in the reversible spreading dynamics on complex networks,which has been given much attention.Except for structural centrality,the nodes’dynamical states play a significant role in their spreading influence in the reversible spreading processes.By integrating the number of outgoing edges and infection risks of node’s neighbors into structural centrality,a new measure for identifying influential spreaders is articulated which considers the relative importance of structure and dynamics on node influence.The number of outgoing edges and infection risks of neighbors represent the positive effect of the local structural characteristic and the negative effect of the dynamical states of nodes in identifying influential spreaders,respectively.We find that an appropriate combination of these two characteristics can greatly improve the accuracy of the proposed measure in identifying the most influential spreaders.Notably,compared with the positive effect of the local structural characteristic,slightly weakening the negative effect of dynamical states of nodes can make the proposed measure play the best performance.Quantitatively understanding the relative importance of structure and dynamics on node influence provides a significant insight into identifying influential nodes in the reversible spreading processes.展开更多
基金supported by theYouth Science and Technology Innovation Personnel Training Project of Heilongjiang(No.UNPYSCT-2020072)the FundamentalResearch Funds for the Universities of Heilongjiang(Nos.145109217,135509234)+1 种基金the Education Science Fourteenth Five-Year Plan 2021 Project of Heilongjiang(No.GJB1421344)the Innovative Research Projects for Postgraduates of Qiqihar University(No.YJSCX2022048).
文摘The influence maximization(IM)problem aims to find a set of seed nodes that maximizes the spread of their influence in a social network.The positive influence maximization(PIM)problem is an extension of the IM problem,which consider the polar relation of nodes in signed social networks so that the positive influence of seeds can be the most widely spread.To solve the PIM problem,this paper proposes the polar and decay related independent cascade(IC-PD)model to simulate the influence propagation of nodes and the decay of information during the influence propagation in signed social networks.To overcome the low efficiency of the greedy based algorithm,this paper defines the polar reverse reachable(PRR)set and devises a signed reverse influence sampling(SRIS)algorithm.The algorithm utilizes the ICPD model as well as the PRR set to select seeds.There are two phases in SRIS.One is the sampling phase,which utilizes the IC-PD model to generate the PRR set and a binary search algorithm to calculate the number of needed PRR sets.The other is the node selection phase,which uses a greedy coverage algorithm to select optimal seeds.Finally,Experiments on three real-world polar social network datasets demonstrate that SRIS outperforms the baseline algorithms in effectiveness.Especially on the Slashdot dataset,SRIS achieves 24.7% higher performance than the best-performing compared algorithm under the weighted cascade model when the seed set size is 25.
基金This work was supported by the National Natural Science Foundation of China(Grant Nos.11875132,11975099,82161148012,11835003,and 61802321)the Natural Science Foundation of Shanghai(Grant No.18ZR1411800)the Science and Technology Commission of Shanghai Municipality(Grant No.14DZ2260800).
文摘The reversible spreading processes with repeated infection widely exist in nature and human society,such as gonorrhea propagation and meme spreading.Identifying influential spreaders is an important issue in the reversible spreading dynamics on complex networks,which has been given much attention.Except for structural centrality,the nodes’dynamical states play a significant role in their spreading influence in the reversible spreading processes.By integrating the number of outgoing edges and infection risks of node’s neighbors into structural centrality,a new measure for identifying influential spreaders is articulated which considers the relative importance of structure and dynamics on node influence.The number of outgoing edges and infection risks of neighbors represent the positive effect of the local structural characteristic and the negative effect of the dynamical states of nodes in identifying influential spreaders,respectively.We find that an appropriate combination of these two characteristics can greatly improve the accuracy of the proposed measure in identifying the most influential spreaders.Notably,compared with the positive effect of the local structural characteristic,slightly weakening the negative effect of dynamical states of nodes can make the proposed measure play the best performance.Quantitatively understanding the relative importance of structure and dynamics on node influence provides a significant insight into identifying influential nodes in the reversible spreading processes.
