Given a network represented by a weighted directed graph G, we consider the problem of finding a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible. The dynamic that governs the spread of influence is the following: initially only elements in S are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. We prove that the problem is NP-hard, even in simple networks like complete graphs and trees. We also derive a series of positive results. We present exact pseudo-polynomial time algorithms for general trees, that become polynomial time in case the trees are unweighted. This last result improves on previously published results. We also design polynomial time algorithms for general weighted paths and cycles, and for unweighted complete graphs.
The first authors to study problems of the spread of influence in networks from an algorithmic point of view were Kempe @cite_36 @cite_25 . However, they were mostly interested in networks with randomly chosen thresholds. Chen @cite_28 studied the following minimization problem: given an unweighted graph @math and fixed thresholds @math , for each vertex @math in @math , find a set of minimum size that eventually influences all (or a fixed fraction of) the nodes of @math . He proved a strong inapproximability result that makes unlikely the existence of an algorithm with approximation factor better than @math . Chen's result stimulated a series of papers @cite_16 @cite_4 @cite_31 @cite_32 @cite_33 @cite_27 @cite_34 @cite_44 @cite_7 @cite_11 @cite_39 @cite_2 that isolated interesting cases in which the problem (and variants thereof) become tractable.
@cite_4 @cite_33 @cite_7 @cite_36 @cite_28 @cite_32 @cite_34 @cite_39 @cite_44 @cite_27 @cite_2 @cite_31 @cite_16 @cite_25 @cite_11
2119218916 2293971114 2170002160 2139297408
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value thr(v) attached to each vertex v, the spread of influence is modeled as follows: A vertex v becomes ''active'' (influenced) if at least thr(v) of its neighbors are active. In the corresponding optimization problem the objective is then to find a fixed number k of vertices to activate such that the number of activated vertices at the end of the propagation process is maximum. We show that this problem is strongly inapproximable in time f(k)@?n^O^(^1^), for some function f, even for very restrictive thresholds. In the case that the threshold of each vertex equals its degree, we prove that the problem is inapproximable in polynomial time and it becomes r(n)-approximable in time f(k)@?n^O^(^1^), for some function f, for any strictly increasing function r. Moreover, we show that the decision version parameterized by k is W[1]-hard but becomes fixed-parameter tractable on bounded degree graphs. Given a network represented by a graph @math G=V,E, we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given @math S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes Sa target set that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known [6] that the above optimization problem is hard to approximate within a factor of @math 2log1-∈|V|, for any @math ∈>0. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: 1 when applied to trees, cycles, or complete graphs, it always produces an optimal solution i.e., a minimum size target set; 2 when applied to arbitrary networks, it always produces a solution of cardinality matching the upper bound given in [1], and proved therein by means of the probabilistic method; 3 when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms for which no proof of optimality or performance guarantee is known in any class of graphs. In this paper we consider a fundamental problem in the area of viral marketing, called T ARGET S ET S ELECTION problem. In a a viral marketing setting, social networks are modeled by graphs with potential customers of a new product as vertices and friend relationships as edges, where each vertex @math is assigned a threshold value @math . The thresholds represent the different latent tendencies of customers (vertices) to buy the new product when their friend (neighbors) do. Consider a repetitive process on social network @math where each vertex @math is associated with two states, active and inactive, which indicate whether @math is persuaded into buying the new product. Suppose we are given a target set @math . Initially, all vertices in @math are inactive. At time step 0, we choose all vertices in @math to become active. Then, at every time step @math , all vertices that were active in time step @math remain active, and we activate any vertex @math if at least @math of its neighbors were active at time step @math . The activation process terminates when no more vertices can get activated. We are interested in the following optimization problem, called T ARGET S ET S ELECTION : Finding a target set @math of smallest possible size that activates all vertices of @math . There is an important and well-studied threshold called strict majority threshold, where for every vertex @math in @math we have @math and @math is the degree of @math in @math . In this paper, we consider the T ARGET S ET S ELECTION problem under strict majority thresholds and focus on three popular regular network structures: cycle permutation graphs, generalized Petersen graphs and torus cordalis. In this work, we study the notion of competing campaigns in a social network and address the problem of influence limitation where a "bad" campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation. The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing (or "good") campaign so as to minimize the number of people that adopt the "bad" campaign at the end of both propagation processes. We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular. We experimentally compare the performance of the greedy method to various heuristics. The experiments reveal that in most cases inexpensive heuristics such as degree centrality compare well with the greedy approach. We also study the influence limitation problem in the presence of missing data where the current states of nodes in the network are only known with a certain probability and show that prediction in this setting is a supermodular problem. We propose a prediction algorithm that is based on generating random spanning trees and evaluate the performance of this approach. The experiments reveal that using the prediction algorithm, we are able to tolerate about 90 missing data before the performance of the algorithm starts degrading and even with large amounts of missing data the performance degrades only to 75 of the performance that would be achieved with complete data.