Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems

Authors

  • Abhijin Adiga University of Virginia
  • Chris Kuhlman University of Virginia
  • Madhav Marathe University of Virginia
  • S. Ravi University of Virginia
  • Daniel Rosenkranz University at Albany – SUNY
  • Richard Stearns University at Albany – SUNY
  • Anil Vullikanti University of Virginia

DOI:

https://doi.org/10.1609/aaai.v34i04.5710

Abstract

Using a discrete dynamical system model for a networked social system, we consider the problem of learning a class of local interaction functions in such networks. Our focus is on learning local functions which are based on pairwise disjoint coalitions formed from the neighborhood of each node. Our work considers both active query and PAC learning models. We establish bounds on the number of queries needed to learn the local functions under both models. We also establish a complexity result regarding efficient consistent learners for such functions. Our experimental results on synthetic and real social networks demonstrate how the number of queries depends on the structure of the underlying network and number of coalitions.

Downloads

Published

2020-04-03

How to Cite

Adiga, A., Kuhlman, C., Marathe, M., Ravi, S., Rosenkranz, D., Stearns, R., & Vullikanti, A. (2020). Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3138-3145. https://doi.org/10.1609/aaai.v34i04.5710

Issue

Section

AAAI Technical Track: Machine Learning