Research On Influence Maximization Over Dynamic Graphs

With the prevalence of social media,such as Facebook,Weibo,how to maximize the influence of individuals in new media is of practical significance.Many studies on Influence Maximization(IM)aimed to select a subset of nodes in static graphs once.However,in the real world,graphs are evolving.Therefore,influential individuals are also changing.In these scenarios,people tend to select influential individuals multiple times instead of once.Namely,selections are raised sequentially,forming a sequence(query sequence).It raises several new challenges due to changing influential individuals.On the one hand,it is hard to quantify the influence of query sequence on the current query.On the other hand,how to efficiently generate the answer whenever a query is raised in dynamic graphs still remains challenging.In order to solve these issues,the relationship of different queries is first quantified as influence spread increment,then based on this concept the problem of Influence Maximization over Dynamic Graph(DGIM)is formulated.To solve DGIM problem,a compact solution,which eliminates redundant computation,is proposed for storing and indexing dynamic graphs and influential nodes.The solution includes Influence-IncrementIndex along with two sketch-centralized indices called Influence-Index and ReverseInfluence-Index.Computing influence set of nodes will incur a large number of redundant computations(intra-query and inter-query).So,these indices are designed to keep track of the nodes’ influence in sketches.Additionally,sliding window model is adopted to control the range of influence among different queries.Finally,with the indexing scheme,the algorithm to answer DGIM queries is devised.Extensive experiments on several real-world datasets demonstrate that compared with other methods extended from static scenarios,this method is competitive in terms of both efficiency and effectiveness owing to the design of index.Additionally,experiments show that the pruning technique plays a certain role in decreasing the number of visits,and the compression strategy is effective in reducing the memory cost.