{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:47:55Z","timestamp":1760240875524,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T00:00:00Z","timestamp":1569888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Political parties recently learned that they must use social media campaigns along with advertising on traditional media to defeat their opponents. Before the campaign starts, it is important for a political party to establish and ensure its media presence, for example by enlarging their number of connections in the social network in order to assure a larger portion of users. Indeed, adding new connections between users increases the capabilities of a social network of spreading information, which in turn can increase the retention rate and the number of new voters. In this work, we address the problem of selecting a fixed-size set of new connections to be added to a subset of voters that, with their influence, will change the opinion of the network\u2019s users about a target candidate, maximizing its chances to win the election. We provide a constant factor approximation algorithm for this problem and we experimentally show that, with few new links and small computational time, our algorithm is able to maximize the chances to make the target candidate win the elections.<\/jats:p>","DOI":"10.3390\/a12100207","type":"journal-article","created":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T11:11:16Z","timestamp":1569928276000},"page":"207","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Recommending Links to Control Elections via Social Influence"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7321-3467","authenticated-orcid":false,"given":"Federico","family":"Cor\u00f2","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yllka","family":"Velaj","sequence":"additional","affiliation":[{"name":"ISI Foundation, 10126 Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1038\/nature11421","article-title":"A 61-million-person experiment in social influence and political mobilization","volume":"489","author":"Bond","year":"2012","journal-title":"Nature"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ferrara, E. (2017). Disinformation and social bot operations in the run up to the 2017 French presidential election. First Monday, 22.","DOI":"10.5210\/fm.v22i8.8005"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1473","DOI":"10.1177\/1461444814562445","article-title":"Seizing the moment: The presidential campaigns\u2019 use of Twitter during the 2012 electoral cycle","volume":"18","author":"Kreiss","year":"2016","journal-title":"New Media Soc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1080\/10584609.2017.1334728","article-title":"Election Campaigning on Social Media: Politicians, Audiences, and the Mediation of Political Communication on Facebook and Twitter","volume":"35","author":"Stier","year":"2018","journal-title":"Political Commun."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Allcott, H., and Gentzkow, M. (2017). Social Media and Fake News in the 2016 Election, National Bureau of Economic Research. Working Paper 23089.","DOI":"10.3386\/w23089"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Rothe, J., and Moulin, H. (2016). Control and Bribery in Voting. Handbook of Computational Social Choice, Cambridge University Press.","DOI":"10.1017\/CBO9781107446984.008"},{"key":"ref_7","unstructured":"Wilder, B., and Vorobeychik, Y. (2018, January 10\u201315). Controlling Elections through Social Influence. Proceedings of the AAMAS 2018 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","article-title":"Maximizing the Spread of Influence through a Social Network","volume":"11","author":"Kempe","year":"2015","journal-title":"Theory Comput."},{"key":"ref_9","unstructured":"Cor\u00f2, F., Cruciani, E., D\u2019Angelo, G., and Ponziani, S. (2019, January 13\u201317). Vote For Me!: Election Control via Social Influence in Arbitrary Scoring Rule Voting Systems. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems AAMAS \u201919, Montrea, QC, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., Cruciani, E., D\u2019Angelo, G., and Ponziani, S. (2019, January 10\u201316). Exploiting Social Influence to Control Elections Based on Scoring Rules. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI, Macao, China.","DOI":"10.24963\/ijcai.2019\/29"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Gonen, R., Kouteck\u00fd, M., and Talmon, N. (2018, January 13\u201319). Opinion Diffusion and Campaigning on Society Graphs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18. International Joint Conferences on Artificial Intelligence Organization, Stockholm, Germany.","DOI":"10.24963\/ijcai.2018\/30"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bredereck, R., and Elkind, E. (2017, January 19\u201325). Manipulating Opinion Diffusion in Social Networks. Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/124"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.tcs.2018.01.017","article-title":"Recommending links through influence maximization","volume":"764","author":"Severini","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","unstructured":"D\u2019Angelo, G., Severini, L., and Velaj, Y. (2017, January 21\u201325). Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network. Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, Aalborg, Denmark."},{"key":"ref_15","unstructured":"Sheldon, D., Dilkina, B., Elmachtoub, A.N., Finseth, R., Sabharwal, A., Conrad, J., Gomes, C., Shmoys, D., Allen, W., and Amundsen, O. (2010, January 8\u201311). Maximizing the spread of cascades using network design. Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Amelkin, V., and Singh, A.K. (2019, January 4\u20138). Fighting Opinion Control in Social Networks via Link Recommendation. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330960"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Adiga, A., Vullikanti, A., and Prakash, B.A. (2015, January 14\u201317). Controlling propagation at group scale on networks. Proceedings of the 2015 IEEE International Conference on Data Mining (ICDM), Atlantic City, NJ, USA.","DOI":"10.1109\/ICDM.2015.59"},{"key":"ref_18","first-page":"9","article-title":"Greedily improving our own closeness centrality in a network","volume":"11","author":"Crescenzi","year":"2016","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Parotsidis, N., Pitoura, E., and Tsaparas, P. (2016, January 22\u201325). Centrality-aware link recommendations. Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2835776.2835818"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2757281","article-title":"Refining social graph connectivity via shortcut edge addition","volume":"10","author":"Papagelis","year":"2015","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., and Wang, Y. (2010, January 25\u201328). Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/1835804.1835934"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions-I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Program."},{"key":"ref_24","unstructured":"Aboueimehrizi, M., Cor\u00f2, F., Cruciani, E., and D\u2019Angelo, G. (2019). Election Control with Voters\u2019 Uncertainty: Hardness and Approximation Results. arXiv."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., D\u2019Angelo, G., and Velaj, Y. (2019, January 10\u201316). Recommending Links to Maximize the Influence in Social Networks. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI, Macao, China.","DOI":"10.24963\/ijcai.2019\/304"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Cohen, E., Delling, D., Pajor, T., and Werneck, R.F. (2014, January 3\u20137). Sketch-based Influence Maximization and Computation: Scaling Up with Guarantees. Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, Shanghai, China.","DOI":"10.1145\/2661829.2662077"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). KONECT-The Koblenz Network Collection. Proceedings of the International World Wide Web Conferen, Rio de Janeiro, Brazi.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_28","unstructured":"(2015, January 15). Arnetminer. Available online: http:\/\/arnetminer.org."},{"key":"ref_29","unstructured":"Leskovec, J., and Krevl, A. (2019, September 28). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_30","unstructured":"Bollob\u00e1s, B., Borgs, C., Chayes, J., and Riordan, O. (2003, January 12\u201314). Directed scale-free graphs. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"025102","DOI":"10.1103\/PhysRevE.64.025102","article-title":"Clustering and preferential attachment in growing networks","volume":"64","author":"Newman","year":"2001","journal-title":"Phys. Rev. E"},{"key":"ref_32","first-page":"547","article-title":"\u00c9tude comparative de la distribution florale dans une portion des Alpes et des Jura","volume":"37","author":"Jaccard","year":"1901","journal-title":"Bull. Soc. Vaudoise Sci. Nat."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1080\/15427951.2013.865686","article-title":"Axioms for centrality","volume":"10","author":"Boldi","year":"2014","journal-title":"Internet Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/207\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:26:37Z","timestamp":1760189197000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,1]]},"references-count":33,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100207"],"URL":"https:\/\/doi.org\/10.3390\/a12100207","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,10,1]]}}}