An exact almost optimal algorithm for target set selection in social networks

ABSTRACT

The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that "activates" a prespecified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i -- 1 exceeds its threshold. The activation process is "monotone" in the sense that once a vertex is activated, it remains active for the entire process.

Unsurprisingly perhaps, Target Set Selection is NPC. More surprising is the fact that both of its maximization and minimization variants turn out to be extremely hard to approximate, even for very restrictive special cases. The only known case for which the problem is known to have some sort of acceptable worst-case solution is the case where the given social network is a tree and the problem becomes polynomial-time solvable. In this paper, we attempt at extending this sparse landscape of tractable instances by considering the treewidth parameter of graphs. This parameter roughly measures the degree of tree-likeness of a given graph, e.g. the treewidth of a tree is 1, and has previously been used to tackle many classical NPhard problems in the literature.

Our contribution is twofold: First, we present an algorithm for Target Set Selection running in n^O(w) time, for graphs with n vertices and treewidth bounded by w. The algorithm utilizes various combinatorial properties of the problem; drifting somewhat from standard dynamic-programming algorithms for small treewidth graphs. Also, it can be adopted to much more general settings, including the case of directed graphs, weighted edges, and weighted vertices. On the other hand, we also show that it is highly unlikely to find an n^O(√w) time algorithm for Target Set Selection, as this would imply a sub-exponential algorithm for all problems in SNPclass. Together with our upper bound result, this shows that the treewidth parameter determines the complexity of Target Set Selection to a large extent, and should be taken into consideration when tackling this problem in any scenario.

REFERENCES

• 1: K.A. Abrahamson, R.G. Downey, and M.R. Fellows. Fixed parameter tractability and completeness iv: on completeness for w{p} and pspace analogues. Annals Of Pure And Applied Logic, 73:235--276, 1995.
• 2: Eyal Amir, Efficient Approximation for Triangulation of Minimum Treewidth, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.7-15, August 02-05, 2001
• 3: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 4: Eli Berger, Dynamic monopolies of constant size, Journal of Combinatorial Theory Series B, v.83 n.2, p.191-200, November 2001 [doi>10.1006/jctb.2001.2045]
• 5: S. Bharathi, D. Kempe, and M. Salek. Competitive influence maximization in social networks. In WINE, pages 306--311, 2007.
• 6: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 7: V. Bouchitté , D. Kratsch , H. Müller , I. Todinca, On treewidth approximations, Discrete Applied Mathematics, v.136 n.2-3, p.183-196, 15 February 2004 [doi>10.1016/S0166-218X(03)00440-2]
• 8: J. Brown and P. Reingen. Social ties and word-of-mouth referral behavior. Journal of Consumer Research: An Interdisciplinary Quarterly, 14(3):350--62, 1987.
• 9: Jianer Chen , Benny Chor , Mike Fellows , Xiuzhen Huang , David Juedes , Iyad Kanj , Ge Xia, Tight Lower Bounds for Certain Parameterized NP-Hard Problems, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.150-160, June 21-24, 2004 [doi>10.1109/CCC.2004.37]
• 10: Ning Chen, On the approximability of influence in social networks, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1029-1037, January 20-22, 2008, San Francisco, California
• 11: Z. Dezsö and A. Barabási. Halting viruses in scale-free networks. Phys. Rev. E, 65(5):055103, 2002.
• 12: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 13: R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
• 14: E. Even-Dar and A. Shapira. A note on maximizing the spread of influence in social networks. In WINE, volume 4858 of LNCS, pages 281--286. Springer, 2007.
• 15: M. Fellows, D. Hermelin, and F. Rosamond. On the parameterized complexity of multiple interval problems -- Manuscript. 2008.
• 16: L.C. Freeman. The Development of Social Network Analysis: A Study in the Sociology of Science. Vancouver, BC, Canada: Empirical Press, 2004.
• 17: J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, pages 211--223, 2001.
• 18: M.S. Granovetter. The strength of weak ties. American Journal of Sociology, 78, pages 1360--1380, 1973.
• 19: M. Kearns and L. Ortiz. Algorithms for interdependent security games. In Proceedings of the 17th Annual Conference on Advances in Neural Information Processing Systems (NIPS), pages 288--297, 2003.
• 20: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 21: D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 1127--1138, 2005.
• 22: Ton Kloks , Hans L. Bodlaender, Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs, Proceedings of the Third International Symposium on Algorithms and Computation, p.116-125, December 16-18, 1992
• 23: R.T. Mikolajczyk and M. Kretzschmar. Collecting social contact data in the context of disease transmission: Prospective and retrospective study designs. Social Networks, 30(2):127--135, 2008.
• 24: S. Milgram. The small world problem. Psychology Today, 2:60--67, 1967.
• 25: S. Morris. Contagion. The Review of Economic Studies, 67(1):57--78, 2000.
• 26: Elchanan Mossel , Sebastien Roch, On the submodularity of influence in social networks, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250811]
• 27: R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys. Rev. Lett., 86(14):3200--3203, 2001.
• 28: D. Peleg, Size bounds for dynamic monopolies, Discrete Applied Mathematics, v.86 n.2-3, p.263-273, Sept. 1998 [doi>10.1016/S0166-218X(98)00043-2]
• 29: David Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, v.282 n.2, p.231-257, 10 June 2002 [doi>10.1016/S0304-3975(01)00055-X]
• 30: N. Robertson and P. Seymour. Graph minors. II. Algorithmic aspects of tree-width. SIAM Journal of Algorithms, 7:309--322, 1986.
• 31: G. Silverman. The secrets of word-of-mouth marketing. AMACOM New York, 2001.
• 32: D.S. Wilson. Levels of selection: An alternative to individualism in biology and the human sciences. Social Networks, 11(3):257--272, 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
bounded tree-width algorithm, bounded tree-width lower-bound, social networks, target set selection, viral marketing