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.展开更多
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.展开更多
基金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.
基金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.
