Research On Influence Maximization For Large-scale Social Networks

Influence Maximization(IM)is a hot topic in the social networking.It has been widely integrated into product marketing,disease control and personalized recommendation.Given a social network,IM mainly aims to find a seed set to achieve the best influence diffusion under a special information diffusion model.Existing algorithms are difficult to be applied to large-scale social networks because of high time complexity and limited influence spread.To address above problems,this paper proposes efficient IM algorithms based on Reverse Influence Sampling(RIS).The specific research contents are as follows:Firstly,considering the problem that RIS is difficult to determine the sampling times,this paper proposes a strategy based on boundary constraints.The interval range of the approximate optimal value is calculated in advance,and the lower bound of the influence and the upper bound of the expected influence under the current seed set are estimated.The algorithm terminates as soon as the ratio of the lower bound to the upper bound meets the approximate ratio.By using tightened and accurate boundary constraints,the approximate optimal sampling time can be estimated and the time to determine the sampling time is reduced,so as to greatly improve the operation efficiency.Secondly,two optimization strategies are proposed to further improve the seed set quality and speed up the processing speed.A preprocessing strategy based on node degree is proposed to filter an effective node set with great potential influence.Sampling from the effective node set in Sampling phase can’t only narrow the sampling range,but also can improve the coverage of the seed set to Reverse Reachable Sets(RR sets)and the quality of the seed set.Another pruning strategy based on influence increment is proposed to avoid invalid repeated sorting when the relative ranking remains unchanged after the update of node influence,which reduces unnecessary time consumption.Finally,the experiments based on several real social networks and two mainstream propagation models are carried out.The results show that compared with efficient algorithms in this field,the proposed algorithms can obtain(1-1/-)-approximate solution,greatly expand the expected influence and significantly enhance the efficiency.