Research On Models And Applications Of Social Influence Propagation

With more and more people using social networking services,recent years have wit-nessed a boom of information spread through social networks.This motivates the research works about influence spread model and its corresponding applications.One of the most hot application topic is viral marketing that is based on the word-of-mouth theory.It can be modeled by a discrete optimization problem,i.e.,influence maximization.By selecting a group of influential users(seed nodes)to post specific tweets such as online comments,product reviews,etc.,a large chain of product adoption might be triggered.During the past two decades,there are much literature on the influence spread model and the influence max-imization problem.So far,the independent cascade model and the linear threshold model(proposed in 2003)are still the most widely used influence spread model.The currently best theoretical guarantees of approximation ratio and time complexity for solving the influence maximization are proved to be near optimal,which seems cannot be improved anymore.Therefore,much research attention start to focus on considering specific real world scenar-ios to introduce practical constraints and study variants of influence maximization problem.In this paper,we follow this line of research and focus on three typical real application sce-narios as follows.1.Location driven influence maximization: Existing works on influence maximization(IM)aim at finding influential online users as seed nodes.Originated from these seed nodes,large online influence spread can be triggered.However,such user-driven perspective limits the IM problem within the purely online environment.Due to the increasing interactions between the cyber world and the physical world,of-fline events in real world are showing more impact on online information spread.Most IM methods are totally unaware of the cyber–physical interactions and thus their effectiveness is limited when offline events are taken into account.To address this issue,in this paper we consider influence maximization from an online–offline interactive setting and propose the location-driven influence maximization(LDIM)problem.The LDIM problem aims to find the optimal offline deployment of loca-tions and durations to hold events,so as to maximize the online influence spread.2.Holistic Budgeted Influence Maximization: Existing works mainly focus on select-ing the optimal seed nodes to maximize the influence spread,with an underlying assumption that costs for involving different users are equal.In fact,this assump-tion seldom holds and it is usually more expensive to involve influential users in a promotion event than ordinary users.Inspired by these observations,in this paper,we consider the Holistic Budgeted Influence Maximization(HBIM)problem,which maximizes the influence spread by deploying the budget to select seed nodes(for posting)and boost nodes(for reposting).By involving both seed nodes and boost nodes in influence spread,HBIM offers more flexibility in budget-based influence maximization.3.Spread of negative influence(N-Inf)in a networked system seems to be inevitable.The widespread of N-Inf might cause severe damage and hence the Influence Block-ing(IB)problem is attracting ample research interest.The IB problem aims at mini-mizing the N-Inf spread by immunization,i.e.selecting k(budget size)immunization nodes(Imm-nodes)to prevent the N-Inf from spreading.However,existing works for IB problem are all formulated as a one-shot task: selecting all the k Imm-nodes at the very beginning of N-Inf spread.In real world,unforeseen events might occur and one-shot policies will lack reserved measures to handle these situations.A more reasonable policy is to adaptively invest the budget based on the observation of N-Inf spread along as the time goes by.Motivated by the above considerations,we propose a novel Adaptive Influence Blocking(AIB)problem.For all the above three works,we elaborately present the hardness analyses and de-sign approximation algorithms with provable theoretical approximation guarantees.By constructing reasonable data structure,we design scalable implementation algorithms for all the proposed methods.We conduct extensive simulation experiments on real world datasets.The experimental results demonstrate the effectiveness and scalability of all the proposed algorithms.In this paper,we mainly focus on combining the influence spread re-search works with three real world application scenarios,so as to study three corresponding variants.We expect the works in this paper can offer reasonable solutions for real applica-tions and open abundant future directions for further investigations.