The spread of behavior over social networks depends on the contact structure among individuals, and seeding the most influential agents can substantially enhance the extent of the spread. While the choice of the best seed set, known as influence maximization, is a computationally hard problem, many computationally efficient algorithms have been proposed to approximate the optimal seed sets with provable guarantees. Most of the previous work on influence maximization assumes the knowledge of the entire network graph. However, in practice, obtaining full knowledge of the network structure is very costly. In this work, we consider the choice of @math initial seeds to maximize the expected number of adopters under the independent cascade model. We propose a ''probe-and-seed'' algorithm that provides almost tight approximation guarantees using @math edge queries in @math time, where @math is the network size and @math is the probability of spreading through an edge. To the best of our knowledge, this is the first result to provide approximation guarantees for influence maximization, using a sub-quadratic number of queries for polynomially small @math . We complement this result by showing that it is impossible to approximate the problem using @math edge queries for constant @math . In the end, we consider a more advanced query model, where one seeds a node and observes the resultant adopters after running the spreading process. We provide an algorithm that uses only @math such queries and provides almost tight approximation guarantees.
In fact, our results fall in the general category of work that addresses how lack of perfect knowledge about the spreading process affects the design and performance of seeding strategies @cite_0 . This question has been studied by researchers from many other angles, including algorithmic stability and robustness @cite_14 @cite_25 . Some other prior work has focused on uncertainty in spreading model parameters, for example, by bounding the worst-case performance when the true edge influence probabilities are constrained to an interval @cite_29 . Others have considered such uncertainties in dynamic settings @cite_4 or with changing network graph @cite_11 .
@cite_14 @cite_4 @cite_29 @cite_0 @cite_25 @cite_11
2962773920 2621117388 2272986348 2811355759 2889208719
Influence maximization is the problem of selecting top @math seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of influence ranking (IR) and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the influence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is much more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory. This paper focuses on new challenges in influence maximization inspired by non-profits' use of social networks to effect behavioral change in their target populations. Influence maximization is a multiagent problem where the challenge is to select the most influential agents from a population connected by a social network. Specifically, our work is motivated by the problem of spreading messages about HIV prevention among homeless youth using their social network. We show how to compute solutions which are provably close to optimal when the parameters of the influence process are unknown. We then extend our algorithm to a dynamic setting where information about the network is revealed at each stage. Simulation experiments using real world networks collected by the homeless shelter show the advantages of our approach. In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization. Identifying the optimal set of individuals to first receive information ('seeds') in a social network is a widely-studied question in many settings, such as the diffusion of information, microfinance programs, and new technologies. Numerous studies have proposed various network-centrality based heuristics to choose seeds in a way that is likely to boost diffusion. Here we show that, for some frequently studied diffusion processes, randomly seeding s plus x individuals can prompt a larger cascade than optimally targeting the best s individuals, for a small x. We prove our results for large classes of random networks, but also show that they hold in simulations over several real-world networks. This suggests that the returns to collecting and analyzing network information to identify the optimal seeds may not be economically significant. Given these findings, practitioners interested in communicating a message to a large number of people may wish to compare the cost of network-based targeting to that of slightly expanding initial outreach. In the well-studied Influence Maximization problem, the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. A large body of recent work has justified research on Influence Maximization models and algorithms with their potential to create societ al or economic value. However, in order to live up to this potential, the algorithms must be robust to large amounts of noise, for they require quantitative estimates of the influence, which individuals exert on each other; ground truth for such quantities is inaccessible, and even decent estimates are very difficult to obtain. We begin to address this concern formally. First, we exhibit simple inputs on which even very small estimation errors may mislead every algorithm into highly suboptimal solutions. Motivated by this observation, we propose the Perturbation Interval model as a framework to characterize the stability of Influence Maximization against noise in the inferred diffusion network. Analyzing the susceptibility of specific instances to estimation errors leads to a clean algorithmic question, which we term the Influence Difference Maximization problem. However, the objective function of Influence Difference Maximization is NP-hard to approximate within a factor of O(n1−e) for any e > 0. Given the infeasibility of diagnosing instability algorithmically, we focus on finding influential users robustly across multiple diffusion settings. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions. The algorithm’s goal is to identify a set of k nodes who are simultaneously influential for all influence functions, compared to the (function-specific) optimum solutions. We show strong approximation hardness results for this problem unless the algorithm gets to select at least a logarithmic factor more seeds than the optimum solution. However, when enough extra seeds may be selected, we show that techniques of can be used to approximate the optimum robust influence to within a factor of 1−1 e. We evaluate this bicriteria approximation algorithm against natural heuristics on several real-world datasets. Our experiments indicate that the worst-case hardness does not necessarily translate into bad performance on real-world datasets; all algorithms perform fairly well.