Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems
Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems
复制标题
DOI：
10.1609/aaai.v34i04.5710
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Abhijin Adiga;C. Kuhlman;M. Marathe;S. Ravi;D. Rosenkrantz;R. Stearns;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Abhijin Adiga;C. Kuhlman;M. Marathe;S. Ravi;D. Rosenkrantz;R. Stearns;A. Vullikanti
利用离散动力系统模型的网络社会系统，我们考虑的问题，学习一类局部相互作用函数在这样的网络。我们的重点是学习局部函数，这些函数是基于从每个节点的邻域形成的成对不相交的联盟。我们的工作考虑了主动查询和PAC学习模型。我们建立了两种模型下学习局部函数所需的查询数量的界限。我们还建立了一个复杂性的结果，关于有效的一致性学习者这样的功能。我们在合成和真实的社交网络上的实验结果证明了查询的数量如何取决于底层网络的结构和联盟的数量。
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.