Research On Influence Maximization And Spread Evaluation In Social Network

With the development of network technology,the relationship between people becomes more and more complicated.The social relations between individuals have formed the complex social network.The large amount of information behind data deserves in-depth research.There are different application scenarios in the real life for the research on influence propagation in social networks,such as viral marketing and public opinion propagation,which makes it important to study social influence.Influence maximization problem is one of the most popular issue in influence propagation study,aim at finding seed nodes that maximizes influence spread.Most traditional influence maximization algorithms focus on the number of affected nodes when choosing nodes,while ignoring the distribution of seed nodes.In this paper,we take the distribution of influence spread into account and define influence layer as one of evaluation indicators.With an emphasis on influence layer,we further propose a Layer-Prioritized Influence Maximization(LPIM)algorithm,which divides the original social network into several sub-networks,then select only one influential node from each subgraph as Candidate nodes,finally use traditional influence maximization algorithm to choose seed nodes.The main purpose is to achieve more influence number and influence layer with proper distribution of seed nodes.On the other hand,Monte Carlo simulation is usually used to calculate the influence spread after giving seed nodes in influence maximization problem,and we hope to study the relationship between the influence spread and the seed nodes.For static propagation,based on the independent cascade model,we reasonably abstract the relationship between the size of the seed set and the influence spread in influence maximization problem as a logarithmic function.For dynamic propagation,we notice the diffusion of information between indivisuals and dissipation of the information over time,proposing a Dynamic Diffusion and Dissipation System(3DS)by analogy between heat-transfer and influence propagation.Furthermore,we give an efficient method to compute the influence spread function of time without much loss of accuracy.Finally,we practice several experiments on three real datasets.We compare our proposed Layer-Prioritized Influence Maximization with Random,PageRank and PMIA algorithms,the experimental results show that in the best case LPIM improved 16.2% and 18.1% on influence number and influence layer respectively.Meanwhile,we also provide experiments to show the rationality and the accuracy of the proposed logarithmic function relationship between the number of seed nodes and the influence spread.On NetHEPT,NetPHY and DBLP datasets,we choose three sample points respectively to calculate the functional relationship,and compare to the relatively accurate experimental results of Monte Carlo simulation.The average relative errors are 1.29%,1.58%,and 0.97%,which proves the validity and accuracy of proposed function.