Research On Minimizing The Seed-Set And Diffusion Time In Social Networks

Nowadays,many large-scale social network sites,such as Facebook,Twitter,We Chat,and Google+,have been popular platforms for spreading information,knowledge and influence.Comparing to traditional diffusion ways,information can spread faster and reach a much larger influence of people on social networks through users' forwarding and comment behaviors.The influence propagation problem is naturally inspired by research in marketing strategies.The research on the influence propagation problem is of practical value in many areas including viral marketing,brand promotion and public early warning.There are three orthogonal dimensions,which are the size of the seed-set,the expected number of activated nodes at the end of the propagation,and the time taken for the propagation,for the spreading of influence in a social network.We can constrain two of these dimensions and try to optimize the third.Kempe et.al systematically studied the influence maximization problem,that is how to target a given number of nodes from a network to maximize the influence spread without limitation of time.In this paper,we study the other two optimization problems.In the first problem,termed influence diffusion time minimization problem,a budget is given,which is sufficient enough to target k nodes,and the goal is to minimize the diffusion time in which a predefined influence spread is achieved.In the second problem,termed seed-set minimization with probabilistic coverage guarantee,the task is to select the minimal seed-set to reach the threshold of influence spread with guaranteed probability.In this paper,the main work is as follows:1.A diffusion time minimization algorithm based on Maximum Influence Arborescence(MIA)model is proposed.We restrict the graph to a tree representation in a local influence region for each node.We define the expected activation time of the node and prove its monotonicity.We design the Precise Two Stage Algorithm(PTSA)for influence diffusion time minimization problem.Our results from simulations on several real networks demonstrate the effectiveness of PTSA to commonly adopted benchmark algorithms.2.A seed-set minimization algorithm based on IC model is proposed.In IC model,the probability that a node will be activated is independent.Based on this property,we proposed an effective method for computing the largest marginal increase in expected influence spread to the seed-set.By using the conventional Minimized Seed-set Algorithm(MSA)scheme,we proposed the Fast Minimized Seed-set Algorithm(FMSA).The experimental results show that the speed of FMSA is thousands of times higher than MSA.3.Considering that community structures are quite common in social networks.Nodes are densely connected internally in community.We can find seed nodes within community rather than the entire network.Inspired by this,we design a dynamic programming algorithm for seed-set minimization problem with probabilistic coverage guarantee.Our results from simulations on several real networks and synthetic networks demonstrate the efficiency of our proposed algorithm.