Node Conversion Optimization in Multi-hop Influence Networks

Jie Zhang, Yuezhou Lv, Zihe Wang

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

61 Downloads (Pure)

Abstract

In this paper, we study scenarios such as diffusion of innovations in a social system and belief propagation in social choice decision-making, which can be captured by a social influence network. In such networks, nodes are distributed and are connected by links between them. Nodes have two different states, s and r. They can change from state s to state r, but not backward [24]. Nodes are interested in changing to state r only if a sufficient number of their neighbors change to state r. In many scenarios, it is desired to design local decision algorithms that guarantee this feature, termed as the safety of node conversion. We design optimal algorithms that maximize the number of nodes that change to state r. In particular, we assume that each node can observe its neighbors up to a distance of k from itself, which introduces complexity to the setting that each node can only observe its immediate neighbors, i.e., k = 1. Moreover, we consider the models that nodes have the same threshold or different thresholds under which their conversion from s to r is safe. We first present the optimal algorithm for the uniform threshold model and establish its optimality by characterizing a monotonicity property. We then generalize the algorithm to maximize node conversion when they have different threshold values. The monotonicity properties and insights on nodes' recursive reasoning of their neighbors' status may be of independent interest.

Original languageEnglish
Title of host publicationProceedings of the 22nd International Joint Conference on Autonomous Agents and Multiagent Systems
Pages2205-2212
Number of pages8
Volume2023-May
Publication statusPublished - 2 Jun 2023
Event22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023 - London, UK United Kingdom
Duration: 29 May 20232 Jun 2023

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
ISSN (Print)1548-8403

Conference

Conference22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023
Country/TerritoryUK United Kingdom
CityLondon
Period29/05/232/06/23

Keywords

  • Influence network
  • local decision
  • multi-hop
  • node conversion optimization

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Node Conversion Optimization in Multi-hop Influence Networks'. Together they form a unique fingerprint.

Cite this