Research Of Influence Maximization Under Independent Cascade Model In Social Networks

With the rapid development of the Internet technology,online social networks(OSNs)such as forums,blog systems,micro-blogs and WeChat,show up and thrive.Nowadays,Social networks are not only the important channels for message delivery between people,but also great platforms where people share their ideas and maintain social relationships with their friends.As one of important topics of social network research,influence maximization is very meaningful for real-life situations and attracts great interests of researchers.Influence maximization(IM)is the problem of finding a small subset of nodes in a social network so that the number of nodes influenced by this subset can be maximized.To tackle this problem,researchers firstly build diffusion models for how social users diffuse and propagate their influence to others in social networks.Many diffusion models have been proposed already.Among them,the independent cascade model(IC)and linear threshold model(LT)are the classic ones.It's been proved that under both IC model and LT model influence maximization is a NP-hard problem.So it is very challenging to solve the IM problem.As far as we know,the approaches to solve the influence maximization problem can be roughly classified into three categories: heuristic methods,greedy approaches and hybrid approaches.Generally speaking,heuristics are simple and efficient but they work with low accuracy,which means the solutions they captured are usually not optimal.The second category is greedy approaches.Greedy approaches can achieve solutions with very good accuracy but they have great limitations–high computation cost and low efficiency,especially when they are applied in large networks.Hybrid approaches incorporate the ideas of heuristics and greedy approaches.Generally,hybrid methods consist of two phases: heuristic phase and greedy phase.Firstly,they detect and seek the “promising” nodes by measuring all the nodes with estimationtechniques of heuristic methods.After that,they search within the neighboring space of these “promising” nodes to gain a better solution search for better ones repeatedly.On one hand,estimation techniques with computation costs are utilized during the heuristic phase,so it speeds up the whole searching process.On the other hand,estimation techniques of the hybrid approaches reduce the accuracy of solutions.Thus we can say that hybrid approaches perform a trade-off between accuracy and efficiency.According to the analysis above,we can see that existent approaches perform badly in terms of accuracy and/or efficiency.Therefore,this paper tries to solve the influence maximization problem by handling these two issues.Firstly,we analyze the reason why traditional degree centrality method performs badly and suggest approaches for improvements.Then we propose two novel flexible degree based heuristics,i.e.Degree-Descending Search(DDS)and Degree Centrality with Distance Control(DCDC)for influence maximization.Experiments with real-world data sets prove that DDS and DCDC have better performances in term of accuracy than the traditional degree centrality method.What's notable is that DDS works at the same speed level as the traditional degree centrality method.To improve the accuracy of the proposed DDS further,we devised a novel evolutionary algorithm called DDSE.We design DDSE by transforming the idea of DDS into a solution-search strategy and integrate it in the evolution process.DDSE utilizes swarm intelligence methodology and greedy strategy and make the population evolve in an efficient way.As a result,DDSE is able to acquire a solution with very good accuracy.Experiments on real-world social networks demonstrate that DDSE is able to overcome the accuracy and efficiency issues and it is a desirable algorithm for solving influence maximization problem under independent cascade model with high efficiency and accuracy.