File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: On the Hardness of Opinion Dynamics Optimization with L1-Budget on Varying Susceptibility to Persuasion

TitleOn the Hardness of Opinion Dynamics Optimization with <i>L</i>1-Budget on Varying Susceptibility to Persuasion
Authors
Issue Date24-Oct-2021
PublisherSpringer
Abstract

Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered an opinion dynamics optimization problem that is based on a popular model for social opinion dynamics, in which each agent has some fixed innate opinion, and a resistance that measures the importance it places on its innate opinion; moreover, the agents influence one another's opinions through an iterative process. Under certain conditions, this iterative process converges to some equilibrium opinion vector. Previous works gave an efficient local search algorithm to solve the unbudgeted variant of the problem, for which 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. On the other hand, it was proved that the L-0-budgeted variant is NP-hard, where the L-0-budget is a restriction given upfront on the number of agents whose resistance may be modified.Inspired by practical situations in which the effort to modify an agent's resistance increases with the magnitude of the change, we propose the L-1-budgeted variant, in which the L-1-budget is a restriction on the sum of the magnitudes of the changes over all agents' resistance parameters. In this work, we show that the L-1-budgeted variant is NP-hard via a reduction from the vertex cover problem. However, contrary to the L-0-budgeted variant, a very technical argument is needed to show that the optimal solution can be achieved by focusing the given L-1-budget on as small a number of agents as possible, as opposed to spreading the budget over a large number of agents.


Persistent Identifierhttp://hdl.handle.net/10722/338116
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, THH-
dc.contributor.authorLee, CS-
dc.date.accessioned2024-03-11T10:26:22Z-
dc.date.available2024-03-11T10:26:22Z-
dc.date.issued2021-10-24-
dc.identifier.isbn978-3-030-89542-6-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/338116-
dc.description.abstract<p>Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered an opinion dynamics optimization problem that is based on a popular model for social opinion dynamics, in which each agent has some fixed innate opinion, and a resistance that measures the importance it places on its innate opinion; moreover, the agents influence one another's opinions through an iterative process. Under certain conditions, this iterative process converges to some equilibrium opinion vector. Previous works gave an efficient local search algorithm to solve the unbudgeted variant of the problem, for which 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. On the other hand, it was proved that the L-0-budgeted variant is NP-hard, where the L-0-budget is a restriction given upfront on the number of agents whose resistance may be modified.Inspired by practical situations in which the effort to modify an agent's resistance increases with the magnitude of the change, we propose the L-1-budgeted variant, in which the L-1-budget is a restriction on the sum of the magnitudes of the changes over all agents' resistance parameters. In this work, we show that the L-1-budgeted variant is NP-hard via a reduction from the vertex cover problem. However, contrary to the L-0-budgeted variant, a very technical argument is needed to show that the optimal solution can be achieved by focusing the given L-1-budget on as small a number of agents as possible, as opposed to spreading the budget over a large number of agents.</p>-
dc.languageeng-
dc.publisherSpringer-
dc.relation.ispartofLecture Notes in Computer Science-
dc.titleOn the Hardness of Opinion Dynamics Optimization with <i>L</i>1-Budget on Varying Susceptibility to Persuasion-
dc.typeConference_Paper-
dc.identifier.doi10.1007/978-3-030-89543-3_43-
dc.identifier.scopuseid_2-s2.0-85118102861-
dc.identifier.volume13025-
dc.identifier.spage515-
dc.identifier.epage527-
dc.identifier.eissn1611-3349-
dc.identifier.isiWOS:000767965300043-
dc.publisher.placeCHAM-
dc.identifier.eisbn978-3-030-89543-3-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats