More Like this

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

   Adiga, A. ; Kuhlman, C. ; Marathe, M. ; Ravi, S. ; Rosenkranz, D. ; Stearns, R. ; Vullikanti, A. ( April 2020 , Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   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. 

   more » « less
2. Learning Coalition-Based Interactions in Networked Social Systems

   Adiga, Abhijin ; Kuhlman, Chris J. ; Marathe, Madhav V. ; Ravi, S. S. ; Rosenkrantz, Daniel J. ; Stearns, Richard E. ; Vullikanti, Anil ( April 2020 , Association for the Advancement of Artificial Intelligence Conference 2020)

   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. 

   more » « less
3. Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems

   Adiga, A. ; Kuhlman, C. ; Marathe, M. ; Rosenkrantz, D. ; Ravi, S.S. ; Stearns, R. ( August 2022 , Journal of machine learning research)

   Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks. 

   more » « less
4. Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

   Rosenkrantz, D. J. ; Adiga, A. ; Marathe, M. ; Qiu, Z. ; Ravi, S. S. ; Stearns, R. ; Vullikanti, A. ( June 2022 , International Conference on Machine Learning)

   Many papers have addressed the problem of learning the behavior (i.e., the local interaction function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the network topology and the behavior of such a system through active queries. Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present inference algorithms under both batch and adaptive query models for dynamical systems with symmetric local functions. These algorithms show that the structure and behavior of such dynamical systems can be learnt using only a polynomial number of queries. Further, we establish a lower bound on the number of queries needed to learn such dynamical systems. We also present experimental results obtained by running our algorithms on synthetic and real-world networks. 

   more » « less
5. Inferring users' choice functions in networked social systems through active queries

   Adiga, A ; Kuhlman, C ; Marathe, M ; Ravi, S ; Rosenkrantz, D ; Stearns, D ( January 2018 , The 7th International Workshop on Computational Social Choice (COMSOC-2018))

   Using synchronous dynamical systems (SyDSs) as a formal model for networked social systems, we study the problem of inferring users’ choices in such systems. We observe that SyDSs with deterministic and probabilistic threshold functions as local functions can capture users’ choices in the context of contagion propagation in social networks. We use an active query mechanism where a user interacts with a system by submitting queries, and the responses to the queries are used to infer the local functions. We develop methods that provide provably efficient query sets for inferring both deterministic and probabilistic forms of threshold functions. We also present experimental results using real world social networks. 

   more » « less