×

How to choose friends strategically. (English) Zbl 1444.91177

Summary: Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person \(v\) in the network has a certain threshold \(t(v)\) for activation, i.e. adoption of the product or idea. If \(v\) has at least \(t(v)\) activated neighbors, then \(v\) will also become activated. If Alice wants to make \(k\) new friends in the network, and thereby activate the most number of people, how should she choose these friends? We study the problem of choosing the \(k\) people in the network to befriend, who will in turn activate the maximum number of people. This maximum influence with links problem has applications in viral marketing and the study of epidemics. We show that the solution can be quite different from the related and widely studied influence maximization problem where the objective is to choose a seed or target set with maximum influence. We prove that the maximum influence with links problem is NP-complete even for bipartite graphs in which all nodes have threshold 1 or 2. In contrast, we give polynomial time algorithms that find optimal solutions for the problem for trees, paths, cycles, and cliques.

MSC:

91D30 Social networks; opinion dynamics
68Q25 Analysis of algorithms and problem complexity

Software:

CELF++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 702-715 (2011) · Zbl 1248.90068
[2] Borgs, C.; Brautbar, M.; Chayes, J.; Lucier, B., Maximizing social influence in nearly optimal time, (Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA’14 (2014)), 946-957 · Zbl 1420.68248
[3] Brown, J. J.; Reingen, P. H., Social ties and word-of-mouth referral behavior, J. Consum. Res., 350-362 (1987)
[4] Chen, N., On the approximability of influence in social networks, (Proceedings of the Symposium on Discrete Algorithms. Proceedings of the Symposium on Discrete Algorithms, SODA’08 (2008)), 1029-1037 · Zbl 1192.91169
[5] Chen, W.; Wang, Y.; Yang, S., Efficient influence maximization in social networks, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’09 (2009)), 199-208
[6] Cicalese, F.; Cordasco, G.; Gargano, L.; Milanic, M.; Peters, J. G.; Vaccaro, U., How to go viral: cheaply and quickly, (Fun with Algorithms. Fun with Algorithms, Lecture Notes in Computer Science, vol. 8496 (2014)), 100-112
[7] Cicalese, F.; Cordasco, G.; Gargano, L.; Milanic, M.; Vaccaro, U., Latency-bounded target set selection in social networks, (The Nature of Computation. Logic, Algorithms, Applications. The Nature of Computation. Logic, Algorithms, Applications, Lecture Notes in Computer Science, vol. 7921 (2013)), 65-77 · Zbl 1390.91262
[8] Cordasco, G.; Gargano, L.; Rescigno, A. A.; Vaccaro, U., Optimizing spread of influence in social networks via partial incentives, (Proceedings of SIROCCO (2015)), 119-134 · Zbl 1471.91391
[9] de Caen, D., An upper bound on the sum of squares of degrees in a graph, Discrete Math., 185, 245-248 (1998) · Zbl 0955.05059
[10] Demaine, E. D.; Hajiaghayi, M. T.; Mahini, H.; Malec, D. L.; Raghavan, S.; Sawant, A.; Zadimoghadam, M., How to influence people with partial incentives, (Proceedings of the International Conference on World Wide Web. Proceedings of the International Conference on World Wide Web, WWW’14 (2014)), 937-948
[11] Dinh, T. N.; Zhang, H.; Nguyen, D. T.; Thai, M. T., Cost-effective viral marketing for time-critical campaigns in large-scale social networks, IEEE/ACM Trans. Netw., 22, 6 (2014)
[12] Domingos, P.; Richardson, M., Mining the network value of customers, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’01 (2001)), 57-66
[13] Eftekhar, M.; Ganjali, Y.; Koudas, N., Information cascade at group scale, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’13 (2013)), 401-409
[14] Fazli, M. A.; Ghodsi, M.; Habibi, J.; Khalilabadi, P. J.; Mirrokni, V.; Sadeghabad, S. S., On the non-progressive spread of influence through social networks, (LATIN 2012: Theoretical Informatics. LATIN 2012: Theoretical Informatics, Lecture Notes in Computer Science, vol. 7256 (2012)), 315-326 · Zbl 1353.68302
[15] Gargano, L.; Hell, P.; Peters, J.; Vaccaro, U., Influence diffusion in social networks under time window constraints, (Proceedings of SIROCCO. Proceedings of SIROCCO, Lecture Notes in Computer Science, vol. 8179 (2013)), 141-152 · Zbl 1408.91176
[16] Goldenberg, J.; Libai, B.; Muller, E., Talk of the network: a complex systems look at the underlying process of word-of-mouth, Mark. Lett., 12, 211-223 (2001)
[17] Goyal, A.; Bonchi, F.; Lakshmanan, L. V.S., A data-based approach to social influence maximization, Proc. VLDB Endow., 5, 73-84 (2011)
[18] Goyal, A.; Bonchi, F.; Lakshmanan, L. V.S.; Venkatasubramanian, S., On minimizing budget and time in influence propagation over social networks, Soc. Netw. Anal. Min., 3, 179-192 (2013)
[19] Goyal, A.; Lu, W.; Lakshmanan, L. V.S., Celf++: optimizing the greedy algorithm for influence maximization in social networks, (Proceedings of the International Conference Companion on World Wide Web. Proceedings of the International Conference Companion on World Wide Web, WWW’11 (2011)), 47-48
[20] Gunnec, D.; Raghavan, S., Integrating Social Network Effects in the Share-of-Choice Problem (2012), University of Maryland: University of Maryland College Park, Technical report
[21] Gunnec, D.; Raghavan, S.; Zhang, R., The Least Cost Influence Problem (2013), University of Maryland: University of Maryland College Park, Technical report
[22] He, J.; Ji, S.; Beyah, R.; Cai, Z., Minimum-sized influential node set selection for social networks under the independent cascade model, (Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing. Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc’14 (2014)), 93-102
[23] Kempe, D.; Kleinberg, J.; Tardos, É., Maximizing the spread of influence through a social network, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’03 (2003)), 137-146
[24] Kempe, D.; Kleinberg, J.; Tardos, É., Influential nodes in a diffusion model for social networks, (Proceedings of the International Conference on Automata, Languages and Programming. Proceedings of the International Conference on Automata, Languages and Programming, ICALP’05 (2005)), 1127-1138 · Zbl 1084.91053
[25] Lafond, M.; Narayanan, L.; Wu, K., Whom to befriend to influence people, (Proceedings of SIROCCO (2016)) · Zbl 1446.91050
[26] Lamba, H.; Pfeffer, J., Maximizing the spread of positive influence by deadline, (Proceedings of the International Conference Companion on World Wide Web. Proceedings of the International Conference Companion on World Wide Web, WWW’16 (2016)), 67-68
[27] Leskovec, J.; Adamic, L. A.; Huberman, B. A., The dynamics of viral marketing, (Proceedings of the ACM Conference on Electronic Commerce (2006)), 228-237
[28] Lu, W.; Bonchi, F.; Goyal, A.; Lakshmanan, L. V.S., The bang for the buck: fair competitive viral marketing from the host perspective, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’13 (2013)), 928-936
[29] Lv, S.; Pan, L., Influence maximization in independent cascade model with limited propagation distance, (Web Technologies and Applications. Web Technologies and Applications, Lecture Notes in Computer Science, vol. 8710 (2014)), 23-34
[30] Mossel, E.; Roch, S., Submodularity of influence in social networks: from local to global, SIAM J. Comput., 39, 2176-2188 (2010) · Zbl 1232.91583
[31] Nguyen, H. T.; Thai, M. T.; Dinh, T. N., Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks, (Proceedings of the International Conference on Management of Data. Proceedings of the International Conference on Management of Data, SIGMOD’16 (2016)), 695-710
[32] Nichterlein, A.; Niedermeier, R.; Uhlmann, J.; Weller, M., On tractable cases of target set selection, Soc. Netw. Anal. Min., 3, 2, 233-256 (2012)
[33] Richardson, M.; Domingos, P., Mining knowledge-sharing sites for viral marketing, (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’02 (2002)), 61-70
[34] Tang, S.; Yuan, J., Going viral: optimizing discount allocation in social networks for influence maximization (2016), CoRR
[35] Tang, Y.; Shi, Y.; Xiao, X., Influence maximization in near-linear time: a martingale approach, (Proceedings of the ACM SIGMOD International Conference on Management of Data. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD’15 (2015)), 1539-1554
[36] Tang, Y.; Xiao, X.; Shi, Y., Influence maximization: near-optimal time complexity meets practical efficiency, (Proceedings of the ACM SIGMOD International Conference on Management of Data. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD’14 (2014)), 75-86
[37] Yang, Y.; Mao, X.; Pei, J.; He, X., Continuous influence maximization: what discounts should we offer to social network users?, (Proceedings of the International Conference on Management of Data. Proceedings of the International Conference on Management of Data, SIGMOD’16 (2016)), 727-741
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.