Learning Influence Adoption in Heterogeneous Networks

Authors

  • Vincent Conitzer Duke University
  • Debmalya Panigrahi Duke University
  • Hanrui Zhang Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v36i6.20592

Keywords:

Machine Learning (ML)

Abstract

We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network.

Downloads

Published

2022-06-28

How to Cite

Conitzer, V., Panigrahi, D., & Zhang, H. (2022). Learning Influence Adoption in Heterogeneous Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6), 6411-6419. https://doi.org/10.1609/aaai.v36i6.20592

Issue

Section

AAAI Technical Track on Machine Learning I