{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T14:25:02Z","timestamp":1773671102586,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PROCORE France\u2013Hong Kong Joint Research Scheme"},{"name":"Research Grants Council of Hong Kong and the Consulate General of France in Hong Kong","award":["F-HKU702\/16"],"award-info":[{"award-number":["F-HKU702\/16"]}]},{"name":"Hong Kong RGC","award":["17200817 and 17201220"],"award-info":[{"award-number":["17200817 and 17201220"]}]},{"name":"Simons Investigator"},{"name":"Vannevar Bush Faculty Fellowship"},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-19-1-0183"],"award-info":[{"award-number":["FA9550-19-1-0183"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100018953","name":"Intesa Sanpaolo Innovation Center","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018953","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>A long line of work in social psychology has studied variations in people\u2019s susceptibility to persuasion\u2014the extent to which they are willing to modify their opinions on a topic. This body of literature suggests an interesting perspective on theoretical models of opinion formation by interacting parties in a network: in addition to considering interventions that directly modify people\u2019s intrinsic opinions, it is also natural to consider interventions that modify people\u2019s susceptibility to persuasion.<\/jats:p>\n          <jats:p>In this work, motivated by this fact, we propose an influence optimization problem. Specifically, we adopt a popular model for social opinion dynamics, where each agent has some fixed innate opinion, and a resistance that measures the importance it places on its innate opinion; agents influence one another\u2019s opinions through an iterative process. Under certain conditions, this iterative process converges to some equilibrium opinion vector. For the unbudgeted variant of the problem, the goal is to modify the resistance of any number of agents (within some given range) such that the sum of the equilibrium opinions is minimized; for the budgeted variant, in addition the algorithm is given upfront a restriction on the number of agents whose resistance may be modified.<\/jats:p>\n          <jats:p>We prove that the objective function is in general non-convex. Hence, formulating the problem as a convex program as in an early version of this work (Abebe et\u00a0al., KDD\u201918) might have potential correctness issues. We instead analyze the structure of the objective function, and show that any local optimum is also a global optimum, which is somehow surprising as the objective function might not be convex. Furthermore, we combine the iterative process and the local search paradigm to design very efficient algorithms that can solve the unbudgeted variant of the problem optimally on large-scale graphs containing millions of nodes. Finally, we propose and evaluate experimentally a family of heuristics for the budgeted variant of the problem.<\/jats:p>","DOI":"10.1145\/3466617","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T21:25:55Z","timestamp":1626902755000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Opinion Dynamics Optimization by Varying Susceptibility to Persuasion via Non-Convex Local Search"],"prefix":"10.1145","volume":"16","author":[{"given":"Rediet","family":"Abebe","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, CA"}]},{"given":"T.-H. HUBERT","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]},{"given":"Zhibin","family":"Liang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong"}]},{"given":"David","family":"Parkes","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA"}]},{"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com ParisTech University, Palaiseau, France"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI, 241\u2013248","author":"Abebe Rediet","unstructured":"Rediet Abebe , Lada A. Adamic , and Jon M. Kleinberg . 2018. Mitigating overexposure in viral marketing . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI, 241\u2013248 . Rediet Abebe, Lada A. Adamic, and Jon M. Kleinberg. 2018. Mitigating overexposure in viral marketing. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI, 241\u2013248."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219983"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13235-010-0004-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0954579406060093"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330960"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican1155-31"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1086\/519142"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157531"},{"key":"e_1_2_1_9_1","volume-title":"C","author":"Bindel David","year":"2015","unstructured":"David Bindel , Jon M. Kleinberg , and Sigal Oren . 2015. How bad is forming your own opinion?Games and Economic Behavior 92 , C ( 2015 ), 248\u2013265. David Bindel, Jon M. Kleinberg, and Sigal Oren. 2015. How bad is forming your own opinion?Games and Economic Behavior 92, C (2015), 248\u2013265."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313509"},{"key":"e_1_2_1_11_1","unstructured":"T-H. Hubert Chan and Chui Shan Lee. 2021. On the hardness of opinion dynamics optimization with -budget on varying susceptibility to persuasion. arXiv:2105.04105. Retrieved from https:\/\/arxiv.org\/abs\/2105.04105  T-H. Hubert Chan and Chui Shan Lee. 2021. On the hardness of opinion dynamics optimization with -budget on varying susceptibility to persuasion. arXiv:2105.04105. Retrieved from https:\/\/arxiv.org\/abs\/2105.04105"},{"key":"e_1_2_1_12_1","volume-title":"Influence: Science and Practice(3rd. ed.)","author":"Cialdini Robert B.","year":"1993","unstructured":"Robert B. Cialdini . 1993 . Influence: Science and Practice(3rd. ed.) . HarperCollins College Publishers . Robert B. Cialdini. 1993. Influence: Science and Practice(3rd. ed.). HarperCollins College Publishers."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0201-76"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2016.02.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1086\/209370"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660460.2660479"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2559896"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487684"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3343483"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1974.10480137"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1746-1561.1992.tb01233.x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1086\/261848"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/764008.763957"},{"key":"e_1_2_1_25_1","volume-title":"Verlegh","author":"Fransen Marieke L.","year":"2015","unstructured":"Marieke L. Fransen , Edith G. Smit , and Peeter W. J . Verlegh . 2015 . Strategies and motives for resistance to persuasion: A integrative framework. Frontiers in Psychology 6 (Aug. 2015), 1201. Marieke L. Fransen, Edith G. Smit, and Peeter W. J. Verlegh. 2015. Strategies and motives for resistance to persuasion: A integrative framework. Frontiers in Psychology 6 (Aug. 2015), 1201."},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Social influence networks and opinion change","volume":"16","author":"Friedkin Noah E.","year":"1999","unstructured":"Noah E. Friedkin and Eugene C. Johnsen . 1999 . Social influence networks and opinion change . Advances in Group Processes 16 , 1 (Jan. 1999), 1\u201319. Noah E. Friedkin and Eugene C. Johnsen. 1999. Social influence networks and opinion change. Advances in Group Processes 16, 1 (Jan. 1999), 1\u201319.","journal-title":"Advances in Group Processes"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 28th Conference on Learning Theory.Vol. 40","author":"Ge Rong","year":"2015","unstructured":"Rong Ge , Furong Huang , Chi Jin , and Yang Yuan . 2015 . Escaping from saddle points\u2014online stochastic gradient for tensor decomposition . In Proceedings of the 28th Conference on Learning Theory.Vol. 40 , PMLR, 797\u2013842. Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. 2015. Escaping from saddle points\u2014online stochastic gradient for tensor decomposition. In Proceedings of the 28th Conference on Learning Theory.Vol. 40, PMLR, 797\u2013842."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157431"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2013 American Control Conference. IEEE","author":"Ghaderi Javad","unstructured":"Javad Ghaderi and R. Srikant . 2013. Opinion dynamics in social networks: A local interaction game with stubborn agents . In Proceedings of the 2013 American Control Conference. IEEE , 1982\u20131987. Javad Ghaderi and R. Srikant. 2013. Opinion dynamics in social networks: A local interaction game with stubborn agents. In Proceedings of the 2013 American Control Conference. IEEE, 1982\u20131987."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.43"},{"key":"e_1_2_1_31_1","volume-title":"On functions representable as a difference of convex functions.Pacific Journal of Mathematics 9, 3","author":"Hartman Philip","year":"1959","unstructured":"Philip Hartman . 1959. On functions representable as a difference of convex functions.Pacific Journal of Mathematics 9, 3 ( 1959 ), 707\u2013713. Retrieved from https:\/\/projecteuclid.org:443\/euclid.pjm\/1103039111. Philip Hartman. 1959. On functions representable as a difference of convex functions.Pacific Journal of Mathematics 9, 3 (1959), 707\u2013713. Retrieved from https:\/\/projecteuclid.org:443\/euclid.pjm\/1103039111."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/mksc.2014.0857"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1986822.1986823"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000058"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305559"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1287\/mksc.2015.0945","article-title":"Turf Wars: Product line strategies in competitive markets","volume":"35","author":"Joshi Yogesh V.","year":"2016","unstructured":"Yogesh V. Joshi , David J. Reibstein , and Z. John Zhang . 2016 . Turf Wars: Product line strategies in competitive markets . Marketing Science 35 , 1 (2016), 128 \u2013 141 . Yogesh V. Joshi, David J. Reibstein, and Z. John Zhang. 2016. Turf Wars: Product line strategies in competitive markets. Marketing Science 35, 1 (2016), 128\u2013141.","journal-title":"Marketing Science"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03655-2_13"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_39_1","volume-title":"KONECT: Konect Network Dataset. Retrieved","author":"Kunegis J\u00e9r\u00f4me","year":"2017","unstructured":"J\u00e9r\u00f4me Kunegis . 2017 . KONECT: Konect Network Dataset. Retrieved April 2017 from http:\/\/konect.uni-koblenz.de. J\u00e9r\u00f4me Kunegis. 2017. KONECT: Konect Network Dataset. Retrieved April 2017 from http:\/\/konect.uni-koblenz.de."},{"key":"e_1_2_1_40_1","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl . 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2014 from http:\/\/snap.stanford.edu\/data. Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2014 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2601(08)60052-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1257\/0002828041301687"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186103"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/10584609.2014.958258"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics.","volume":"54","author":"Park Dohyung","year":"2017","unstructured":"Dohyung Park , Anastasios Kyrillidis , Constantine Caramanis , and Sujay Sanghavi . 2017 . Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach . In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Vol. 54 , PMLR, 65\u201374. Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. 2017. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Vol. 54, PMLR, 65\u201374."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1037\/0012-1649.43.6.1531"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541725"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2632162"},{"key":"e_1_2_1_49_1","volume-title":"Petty","author":"Tormala Zakary L.","year":"2002","unstructured":"Zakary L. Tormala and Richard E . Petty . 2002 . What doesn\u2019t kill me makes me stronger: The effects of resisting persuasion on attitude certainty.Journal of Personality and Social Psychology 83, 6 (2002), 1298. Zakary L. Tormala and Richard E. Petty. 2002. What doesn\u2019t kill me makes me stronger: The effects of resisting persuasion on attitude certainty.Journal of Personality and Social Psychology 83, 6 (2002), 1298."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15327663jcp1404_11"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/10810730305686"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2538508"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3466617","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3466617","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3466617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:52Z","timestamp":1750195492000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3466617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3466617"],"URL":"https:\/\/doi.org\/10.1145\/3466617","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}