zbMATH — the first resource for mathematics

On the complexity of reasoning about opinion diffusion under majority dynamics. (English) Zbl 07228995
This paper studies complexity analysis of opinion diffusion problems under majority dynamics in social networks. A key problems studied in this paper is consensus problem. Given a graph \(G=(N,E)\) and a rational number \(\alpha\) such that \(\alpha\in(0,1)\), this problem requires to compute a set \(S\subseteq N\) of seeds such that \(|S|\le\alpha|N|\) and there is a dynamic \(c\) tends to \(1\) with \(N_{1/c}=S\) or check that there is no set of seeds satisfying the above conditions. Here \(N_{1/c}\) is the set of nodes with opinion \(1\) under a given configuration \(c:N\rightarrow\{0,1\}\). It is shown that consensus problem is a NP-hard problem. Two other problems called double problem and plural problem are also proved to be NP-hard. Double problem refers to computing a configuration \(c\) such that \(|N_{1/c}|\le\varepsilon|N|\) and there exists a dynamic \(c\) tending to \(c^*\) with \(|N_{1/c^*}|>2\varepsilon |N|\) or check that there is no such configuration satisfying the above conditions. Plural problem refers to computing a configuration \(c\) such that \(c\) is stable and \(N_{0/c}\not=\emptyset\) and \(N_{0/c}\not=N\) or check that there is no configuration satisfying the above conditions.
91D30 Social networks; opinion dynamics
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Auletta, V.; Ferraioli, D.; Greco, G., Reasoning about consensus when opinions diffuse through majority dynamics, (Proc. of IJCAI’18 (2018)), 49-55
[2] Granovetter, M., Threshold models of collective behavior, Am. J. Sociol., 83, 6, 1420-1443 (1978)
[3] Degroot, M. H., Reaching a consensus, J. Am. Stat. Assoc., 69, 345, 118-121 (1974) · Zbl 0282.92011
[4] Memon, N.; Alhajj, R., From Sociology to Computing in Social Networks: Theory, Foundations and Applications (2010), Springer Publishing Company, Incorporated
[5] Easley, D.; Kleinberg, J., Networks, Crowds, and Markets: Reasoning About a Highly Connected World (2010), Cambridge University Press · Zbl 1205.91007
[6] Grandi, U., Social choice and social networks, Trends in Computational Social Choice. Trends in Computational Social Choice, AI Access, 169-184 (2017)
[7] Salehi-Abari, A.; Boutilier, C.; Larson, K., Empathetic decision making in social networks, Artif. Intell., 275, 174-203 (2019) · Zbl 07099227
[8] Christoff, Z.; Grossi, D., Stability in binary opinion diffusion, (Proc. of LORI ‘17 (2017)), 166-180 · Zbl 06810780
[9] Tambe, M.; Rice, E., Artificial Intelligence and Social Work (2018), Cambridge University Press
[10] Domingos, P.; Richardson, M., Mining the network value of customers, (Proc. of KDD’01 (2001)), 57-66
[11] Richardson, M.; Domingos, P., Mining knowledge-sharing sites for viral marketing, (Proc. of KDD ‘02 (2002)), 61-70
[12] Long, C.; Wong, R. C.-W., Viral marketing for dedicated customers, Inf. Sci., 46, 1-23 (2014)
[13] Misner, I. R.; Devine, V., The World’s Best-Known Marketing Secret: Building Your Business with Word-of-Mouth Marketing (1999), Bard Press
[14] Li, Y.; Fan, J.; Wang, Y.; Tan, K., Influence maximization on social graphs: a survey, IEEE Trans. Knowl. Data Eng., 30, 10, 1852-1872 (2018)
[15] Kempe, D.; Kleinberg, J.; Tardos, E., Influential nodes in a diffusion model for social networks, (Proc. of ICALP’05 (2005)), 1127-1138 · Zbl 1084.91053
[16] Schelling, T. C., Micromotives and Macrobehavior (1978), W. W. Norton & Company
[17] Granovetter, M., The strength of weak ties, Am. J. Sociol., 78, 6, 1360-1380 (1973)
[18] Shakarian, P., A multidisciplinary survey of social network diffusion models, IEEE Intel. Inform. Bull., 16, 1, 3-7 (2015)
[19] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Theory Comput., 11, 4, 105-147 (2015) · Zbl 1337.91069
[20] Gursoy, F.; Gunnec, D., Influence maximization in social networks under deterministic linear threshold model, Knowl.-Based Syst., 161, 111-123 (2018)
[21] Goyal, A.; Bonchi, F.; Lakshmanan, L. V., Learning influence probabilities in social networks, (Proc. of WSDM ‘10 (2010)), 241-250
[22] Shakarian, P.; Eyre, S.; Paulo, D., A scalable heuristic for viral marketing under the tipping model, Soc. Netw. Anal. Min., 3, 4, 1225-1248 (2013)
[23] Borodin, A.; Filmus, Y.; Oren, J., Threshold models for competitive influence in social networks, (Saberi, A., Proc. of WINE’10 (2010)), 539-550
[24] Bharathi, S.; Kempe, D.; Salek, M., Competitive influence maximization in social networks, (Proc. of WINE’07 (2007)), 306-311
[25] Budak, C.; Agrawal, D.; El Abbadi, A., Limiting the spread of misinformation in social networks, (Proc. of WWW ‘11 (2011)), 665-674
[26] Chen, W.; Collins, A.; Cummings, R.; Ke, T.; Liu, Z.; Rincon, D.; Sun, X.; Wei, W.; Wang, Y.; Yuan, Y., Influence maximization in social networks when negative opinions may emerge and propagate, (Proc. of SDM’11 (2011)), 379-390
[27] Fazli, M.; Ghodsi, M.; Habibi, J.; Jalaly, P.; Mirrokni, V.; Sadeghian, S., On non-progressive spread of influence through social networks, Theor. Comput. Sci., 550, 36-50 (2014) · Zbl 1360.91120
[28] Goles, E.; Olivos, J., Periodic behaviour of generalized threshold functions, Discrete Math., 30, 2, 187-189 (1980) · Zbl 0444.94038
[29] Frischknecht, S.; Keller, B.; Wattenhofer, R., Convergence in (social) influence networks, (Afek, Y., Proc. of DISC’13 (2013)), 433-446 · Zbl 1400.91461
[30] Lou, V. Y.; Bhagat, S.; Lakshmanan, L. V.; Vaswani, S., Modeling non-progressive phenomena for influence propagation, (Proc. of COSN ‘14 (2014)), 131-138
[31] V. Tzoumas, C. Amanatidis, E. Markakis, A game-theoretic analysis of a competitive diffusion process over social networks, in: Proc. of WINE’12, pp. 1-14.
[32] Bredereck, R.; Elkind, E., Manipulating opinion diffusion in social networks, (Proc. of IJCAI’17 (2017)), 894-900
[33] Dong, Y.; Zha, Q.; Zhang, H.; Kou, G.; Fujita, H.; Chiclana, F.; Herrera-Viedma, E., Consensus reaching in social network group decision making: research paradigms and challenges, Knowl.-Based Syst., 162, 3-13 (2018)
[34] Osborne, M. J.; Rubinstein, A., A Course in Game Theory (1994), The MIT Press: The MIT Press Cambridge, USA · Zbl 1194.91003
[35] Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A. D., Handbook of Computational Social Choice (2016), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1436.91001
[36] Endriss, U., Trends in Computational Social Choice. Trends in Computational Social Choice, AI Access (2017)
[37] R. Angell, G. Schoenebeck, Proc. of WINE’17, pp. 16-29.
[38] Dreyer, P.; Roberts, F. S., Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 1615-1627 (2009) · Zbl 1163.92035
[39] Auletta, V.; Caragiannis, I.; Ferraioli, D.; Galdi, C.; Persiano, G., Minority becomes majority in social networks, (Proc. of WINE’15 (2015)), 74-88 · Zbl 1406.91317
[40] Ferraioli, D.; Ventre, C., Social pressure in opinion games, (Proc. of IJCAI’17 (2017)), 3661-3667
[41] Robertson, N.; Seymour, P., Graph minors III: planar tree-width, J. Comb. Theory, Ser. B, 36, 1, 49-64 (1984) · Zbl 0548.05025
[42] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340 (1991) · Zbl 0734.68073
[43] Gottlob, G.; Greco, G.; Leone, N.; Scarcello, F., Hypertree decompositions: questions and answers, (Proc. of PODS’16 (2016)), 57-74
[44] Dechter, R., Constraint Processing (2003), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA
[45] Gottlob, G.; Greco, G.; Scarcello, F., Treewidth and hypertree width, (Tractability: Practical Approaches to Hard Problems (2013), Cambridge University Press)
[46] Chen, N., On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 3, 1400-1415 (2009) · Zbl 1203.68314
[47] Khoshkhah, K.; Soltani, H.; Zaker, M., On dynamic monopolies of graphs: the average and strict majority thresholds, Discrete Optim., 9, 2, 77-83 (2012) · Zbl 1246.91115
[48] Peleg, D., Local majorities, coalitions and monopolies in graphs: a review, Theor. Comput. Sci., 282, 2, 231-257 (2002) · Zbl 0997.68088
[49] Peleg, D., Size bounds for dynamic monopolies, Discrete Appl. Math., 86, 2, 263-273 (1998) · Zbl 0910.90286
[50] Chen, N., On the approximability of influence in social networks, (Proc. of SODA’08 (2008)), 1029-1037 · Zbl 1192.91169
[51] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman & Co. · Zbl 0411.68039
[52] Greenlaw, R.; Petreschi, R., Cubic graphs, ACM Comput. Surv., 27, 4, 471-495 (1995)
[53] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074
[54] Gaifman, H., On local and non-local properties, (Stern, J., Proceedings of the Herbrand Symposium. Proceedings of the Herbrand Symposium, Studies in Logic and the Foundations of Mathematics, vol. 107 (1982), Elsevier), 105-135
[55] Rossi, F.; v. Beek, P.; Walsh, T., Handbook of Constraint Programming (Foundations of Artificial Intelligence) (2006), Elsevier Science Inc.: Elsevier Science Inc. New York, NY, USA
[56] Maniu, S.; Senellart, P.; Jog, S., An experimental study of the treewidth of real-world graph data, (Proc. of ICDT’19 (2019)), 12:1-12:18
[57] Greco, G.; Lupia, F.; Scarcello, F., The tractability of the shapley value over bounded treewidth matching games, (Proc. of IJCAI’17 (2017)), 1046-1052
[58] Demetrescu, C.; Lupia, F.; Mendicelli, A.; Ribichini, A.; Scarcello, F.; Schaerf, M., On the shapley value and its application to the italian vqr research assessment exercise, J. Informetr., 13, 1, 87-104 (2019)
[59] Grohe, M., Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23, 4, 613-632 (2003) · Zbl 1089.05503
[60] Demaine, E. D.; Hajiaghayi, M. T.; Kawarabayashi, K., Algorithmic graph minor theory: decomposition, approximation, and coloring, (Proc. of FOCS’05 (2005)), 637-646
[61] Baker, B. S., Approximation algorithms for np-complete problems on planar graphs, J. ACM, 41, 1, 153-180 (1994) · Zbl 0807.68067
[62] Bazgan, C.; Chopin, M.; Nichterlein, A.; Sikora, F., Parameterized approximability of maximizing the spread of influence in networks, J. Discret. Algorithms, 27, 54-65 (2014) · Zbl 1361.68105
[63] Bazgan, C.; Chopin, M.; Nichterlein, A.; Sikora, F., Parameterized inapproximability of target set selection and generalizations, Computability, 3, 2, 135-145 (2014) · Zbl 1320.68088
[64] Nichterlein, A.; Niedermeier, R.; Uhlmann, J.; Weller, M., On tractable cases of target set selection, Soc. Netw. Anal. Min., 3, 2, 233-256 (2013)
[65] Cordasco, G.; Gargano, L.; Mecchia, M.; Rescigno, A. A.; Vaccaro, U., Discovering small target sets in social networks: a fast and effective algorithm, Algorithmica, 80, 6, 1804-1833 (2018) · Zbl 1390.05224
[66] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 1, 87-96 (2011) · Zbl 1248.90068
[67] Robertson, N.; Seymour, P., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017
[68] Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theor. Comput. Sci., 411, 44, 4017-4022 (2010) · Zbl 1235.90168
[69] Reichman, D., New bounds for contagious sets, Discrete Math., 312, 10, 1812-1814 (2012) · Zbl 1242.05265
[70] Chang, C.; Lyuu, Y., On irreversible dynamic monopolies in general graphs (2009), CoRR
[71] Chang, C.-L.; Lyuu, Y.-D., Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades, Theor. Comput. Sci., 468, 37-49 (2013) · Zbl 1258.05041
[72] Flocchini, P.; Královič, R.; Ružička, P.; Roncato, A.; Santoro, N., On time versus size for monotone dynamic monopolies in regular topologies, J. Discret. Algorithms, 1, 2, 129-150 (2003) · Zbl 1074.68045
[73] Khoshkhah, K.; Nemati, M.; Soltani, H.; Zaker, M., A study of monopolies in graphs, Graphs Comb., 29, 5, 1417-1427 (2013) · Zbl 1272.05149
[74] Sigarreta, J. M.; Rodríguez, J. A., On the global offensive alliance number of a graph, Discrete Appl. Math., 157, 2, 219-226 (2009) · Zbl 1191.05072
[75] Cicalese, F.; Cordasco, G.; Gargano, L.; Milanič, M.; Peters, J.; Vaccaro, U., Spread of influence in weighted networks under time and budget constraints, Theor. Comput. Sci., 586, C, 40-58 (2015) · Zbl 1327.68175
[76] Rautenbach, D.; dos Santos, V. F.; Schäfer, P. M., Irreversible conversion processes with deadlines, J. Discret. Algorithms, 26, 69-76 (2014) · Zbl 1298.05282
[77] Mossel, E.; Neeman, J.; Tamuz, O., Majority dynamics and aggregation of information in social networks, Auton. Agents Multi-Agent Syst., 28, 3, 408-429 (2014)
[78] Feldman, M.; Immorlica, N.; Lucier, B.; Weinberg, S. M., Reaching consensus via non-Bayesian asynchronous learning in social networks, (Proc. of APPROX/RANDOM’14 (2014)), 192-208 · Zbl 1360.91121
[79] Auletta, V.; Caragiannis, I.; Ferraioli, D.; Galdi, C.; Persiano, G., Information retention in heterogeneous majority dynamics, (Proc. of WINE’17 (2017)), 30-43 · Zbl 1405.91515
[80] Auletta, V.; Ferraioli, D.; Fionda, V.; Greco, G., Maximizing the spread of an opinion when tertium datur est, (Proc. of AAMAS’19 (2019)), 1207-1215
[81] Fortunato, S., On the consensus threshold for the opinion dynamics of krause-hegselmann, Int. J. Mod. Phys. C, 16, 02, 259-270 (2005) · Zbl 1112.91353
[82] Lorenz, J.; Urbig, D., About the power to enforce and prevent consensus by manipulating communication rules, Adv. Complex Syst., 10, 02, 251-269 (2007) · Zbl 1135.91029
[83] Carvalho, A.; Larson, K., A consensual linear opinion pool, (Proc. of IJCAI’13 (2013)), 2518-2524
[84] Auletta, V.; Fanelli, A.; Ferraioli, D., Consensus in opinion formation processes in fully evolving environments, (Proc. of AAAI’19 (2019)), 6022-6029
[85] Yoshinaka, R., Higher-order matching in the linear lambda calculus in the absence of constants is np-complete, (Proc. or RTA ‘05 (2005)), 235-249 · Zbl 1078.68045
[86] Chierichetti, F.; Kleinberg, J.; Oren, S., On discrete preferences and coordination, J. Comput. Syst. Sci., 93, 11-29 (2018) · Zbl 1408.91041
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.