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
Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems
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
- NSF-PAR ID:
- 10376919
- Date Published:
- Journal Name:
- Journal of machine learning research
- Volume:
- 23
- ISSN:
- 1533-7928
- Page Range / eLocation ID:
- 1-43
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
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
-
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