Research On Time-sensitive Social Network Influence Spread Algorithms

With the rapid development of mobile Internet,online social networks have be-come more and more popular,and have become the most effective operation platform for marketing activities,which has led to the promotion of "viral marketing".In the"viral marketing",the biggest challenge is how to select K users from the entire set of users to form a "seed set",using the seed set to spread the influence,so that the final ex-pectation number of affected users can be maximized.The above problem is the classic problem of Influence Maximization.Based on the above background,this paper first introduces new considerations for the influence spread problem in social networks.One is to differentiate the user's cost and benefit,and the other is to include the time delay of propagation and time deadline constraints.Under the time-sensitive spread model,we build a Time-sensitive Feedback Benefits Calculation(TFBC)problem.The purpose of this problem is to quickly and efficiently calculate the final spread impact of all active nodes under the time-sensitive spread model for any given node set S.This paper proves that the problem is#P-hard under both influence spread models,and designs a new sampling strategy to quickly and efficiently estimate the final feedback gain.The equivalence and approximation of the sampling strategy are theoretically analyzed,which proves the excellent properties of the sampling strategy.Secondly,this paper formally construct a Time-sensitive Feedback Benefits Max-imization(TFBM)problem.The goal of the problem is to find the most cost-effective set of users to maximize the impact on the target user under the time constraint T and the budget constraint B,so that the feedback benefits of all the affected users are max-imized.This paper proves that the problem is NP-hard under both influence spread models,and the approximation algorithm based on sampling strategy is designed to solve the problem.The approximate guarantee of the algorithm is obtained through theoretical proof.To the best of our knowledge,this algorithm is the first algorithm to provide an approximate guarantee for this problem.Finally,in view of the emerging social event organizer selection problem,based on the above-mentioned time-sensitive influence spread model,this paper constructs a Time-sensitive Influence Spread Event Organizer(TISEO)mining problem.The prob-lem is expected to find the most cost-effective seed set as the event organizer under budget and time constraints,so that the users in the seed set can not only cover the re-quired attributes required by social events,but also enable the social events to spread in social networks to maximize the feedback benefits of all the affected users for so-cial events.This paper also proves that the problem is NP-hard under both influence spread models,and the two efficient heuristic algorithms which names Naive-Greedy and Two-Directions are designed to solve this problem.In this paper,a lot of experimental experiments are carried out on the algorithm us-ing real social network datasets.The experimental results demonstrate the effectiveness and efficiency of the proposed algorithms.