In this article, we consider a dynamic model for competition in a social network, where two strategic agents have fixed beliefs, and the nonstrategic/regular agents adjust their states according to a distributed consensus protocol. We suppose that one strategic agent must identify k+ target agents in the network to maximally spread his/her own opinion and alter the average opinion that eventually emerges. In the literature, this problem is cast as the maximization of a set function and, by leveraging on the submodularity property, is solved in a greedy manner by solving k+ separate single targeting problems. Our main contribution is to exploit the underlying graph structure to build more refined heuristics. First, we provide the analytical solution for the optimal targeting problem over complete graphs. This result provides a rule to understand whether it is convenient or not to block the opponent.s influence by targeting the same nodes. The argument is then extended to generic graphs, leading to more effective solutions compared to the greedy approach. Second, we derive some useful properties of the objective function for trees by an electrical analogy. Inspired by these findings, we define a new algorithm, which selects the optimal solution on trees in a much faster way with respect to a brute-force approach and works well also over tree-like/sparse graphs. The proposed heuristics are then compared to zero-cost heuristics on randomly generated graphs and real social networks.

Graph Structure-Based Heuristics for Optimal Targeting in Social Networks

Frasca, Paolo
Secondo
;
Ravazzi, Chiara;Dabbene, Fabrizio
Ultimo
2022

Abstract

In this article, we consider a dynamic model for competition in a social network, where two strategic agents have fixed beliefs, and the nonstrategic/regular agents adjust their states according to a distributed consensus protocol. We suppose that one strategic agent must identify k+ target agents in the network to maximally spread his/her own opinion and alter the average opinion that eventually emerges. In the literature, this problem is cast as the maximization of a set function and, by leveraging on the submodularity property, is solved in a greedy manner by solving k+ separate single targeting problems. Our main contribution is to exploit the underlying graph structure to build more refined heuristics. First, we provide the analytical solution for the optimal targeting problem over complete graphs. This result provides a rule to understand whether it is convenient or not to block the opponent.s influence by targeting the same nodes. The argument is then extended to generic graphs, leading to more effective solutions compared to the greedy approach. Second, we derive some useful properties of the objective function for trees by an electrical analogy. Inspired by these findings, we define a new algorithm, which selects the optimal solution on trees in a much faster way with respect to a brute-force approach and works well also over tree-like/sparse graphs. The proposed heuristics are then compared to zero-cost heuristics on randomly generated graphs and real social networks.
2022
Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni - IEIIT
Multi-agent systems, network topology, networked control systems, social network theory
File in questo prodotto:
File Dimensione Formato  
TCNS3163665.pdf

accesso aperto

Descrizione: Graph Structure-Based Heuristics for Optimal Targeting in Social Networks
Tipologia: Documento in Post-print
Licenza: Altro tipo di licenza
Dimensione 2.45 MB
Formato Adobe PDF
2.45 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/414915
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact