Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems
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.
Cite
Text
Adiga et al. "Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I04.5710Markdown
[Adiga et al. "Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/adiga2020aaai-bounds/) doi:10.1609/AAAI.V34I04.5710BibTeX
@inproceedings{adiga2020aaai-bounds,
title = {{Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems}},
author = {Adiga, Abhijin and Kuhlman, Chris J. and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J. and Stearns, Richard Edwin and Vullikanti, Anil},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {3138-3145},
doi = {10.1609/AAAI.V34I04.5710},
url = {https://mlanthology.org/aaai/2020/adiga2020aaai-bounds/}
}