Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person @math in the network has a certain threshold @math for activation , i.e adoption of the product or idea. If @math has at least @math activated neighbors, then @math will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This Minimum Links Problem has applications in viral marketing and the study of epidemics. Its solution can be quite different from the related and widely studied Target Set Selection problem. We prove that the Minimum Links problem cannot be approximated to within a ratio of @math , for any fixed @math , unless @math , where @math is the number of nodes in the network. On the positive side, we give linear time algorithms to solve the problem for trees, cycles, and cliques, for any given set of external influencers, and give precise bounds on the number of links needed. For general graphs, we design a polynomial time algorithm to compute size-efficient link sets that can activate the entire graph.
This paper provides an overview of recent developments concerning the process of local majority voting in graphs, and its basic properties, from graph theoretic and algorithmic standpoints. Online social networks (OSNs) have become one of the most effective channels for marketing and advertising. Since users are often influenced by their friends, “word-of-mouth” exchanges, so-called viral marketing, in social networks can be used to increase product adoption or widely spread content over the network. The common perception of viral marketing about being cheap, easy, and massively effective makes it an ideal replacement of traditional advertising. However, recent studies have revealed that the propagation often fades quickly within only few hops from the sources, counteracting the assumption on the self-perpetuating of influence considered in literature. With only limited influence propagation, is massively reaching customers via viral marketing still affordable? How do we economically spend more resources to increase the spreading speed? We investigate the cost-effective massive viral marketing problem, taking into the consideration the limited influence propagation. Both analytical analysis based on power-law network theory and numerical analysis demonstrate that the viral marketing might involve costly seeding. To minimize the seeding cost, we provide mathematical programming to find optimal seeding for medium-size networks and propose VirAds, an efficient algorithm, to tackle the problem on large-scale networks. VirAds guarantees a relative error bound of @math from the optimal solutions in power-law networks and outperforms the greedy heuristics that realizes on the degree centrality. Moreover, we also show that, in general, approximating the optimal seeding within a ratio better than @math is unlikely possible.  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.