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

  • 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


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.

AAAI Technical Track: Machine Learning