Background and Motivation. Graphical discrete dynamical systems are used in a variety of settings to understand population-level contagion dynamics in terms of individual (human) agent behavior. Examples include the spread of health behaviors (Valente 2010) such as drug overdose (Sherman et al. 2009); obesity (Christakis and Fowler 2007); segregation (Schelling 1971); becoming a user of an online communications tool (Karsai et al. 2014); coordination (Rosenthal et al. 2015); and financial contagions (Gai and Kapadia 2010). The frameworks in these works and in ours here are network representations of populations, where nodes and edges represent entities such as humans and pairwise interactions, respectively. Each of the cited works can be viewed as capturing influence through threshold models (Granovetter 1978;Schelling 1978), where a node v i contracts a contagion if at least a specified number of its neighbors has already contracted it. This number for v i is called its threshold t i . We are interested in complex contagions (Centola and Macy 2007) that are characteristic of social contagions, where t i ≥ 1; i.e., agents need multiple reinforcing interactions to adopt a contagion. (Watts 2002) argues that threshold models are useful in a host of settings where incomplete information exists or when there is insufficient time to make more deliberate decisions.
In particular, small changes in the thresholds of nodes can make a large difference in population dynamics. An example is provided in (Granovetter 1978), where a change in one node's threshold by a value of 1 in a large graph, changes population-level collective action from non-existent to full collective action. Several works have used mined data to infer thresholds for applications ranging from protests, to Twitter messaging, to joining social media (González-Bailón et al. 2011;Romero, Meeder, and Kleinberg 2011;Ugander et al. 2012); see also (Easley and Kleinberg 2010). Importantly, in all of these cases, heterogeneous (i.e., nonuniform) thresholds among agents have been inferred. Thus, node thresholds must be determined based on a node 's individual behavior, its (local) neighborhood structure, and behaviors (and states) of its neighbors. Symmetric functions, which generalize threshold functions, arise in game theoretic settings (Papadimitriou and Roughgarden 2003).
Some works have studied threshold inference in a passive setting (e.g., (Adiga et al. 2017a)) where observations are given and the problem is to infer thresholds from those observations. In this work, we study the case where an algorithm has control over what information it extracts from the system via querying the system for desired information. In particular, the algorithm gives a set of configurations (or queries) to the system and infers properties based on the system's outputs. We study two query modes, namely batch and adaptive modes, that differ in their degrees of control. Under the batch mode, all the queries must be submitted together. In the adaptive mode, queries can be submitted in several stages, and queries at a stage can depend on the answers to previous queries, a strategy similar to that used in games such as "Twenty questions"foot_0 .
We relate inference problems to well-studied graph theoretic problems such as coloring, using combinatorial and algorithmic perspectives. The formulation also enables us to quantify rigorously the complexity of inferring such systems. Motivation for these problems comes in part from the DARPA Next Generation Social Science (NGS2) Program, where experimental data on social networks are used to infer properties of predictive models. Our work is similar in spirit-but quite different in problem domain and resultsto some of the recent works on inference (e.g. (Kleinberg, Mullainathan, and Ugander 2017)).
Our focus is on the following problem: Given the underlying graph of a graphical discrete dynamical system, construct queries to identify all the local functions. The optimization goal is to minimize the number of queries. Our results are summarized below. Due to space limitations, detailed proofs can be found in (Adiga et al. 2017b;2017c). 1. We develop algorithms for generating query sets under both batch and adaptive modes to identify local functions of dynamical systems. As can be expected, adaptive query mode can produce significantly smaller query sets compared to the batch mode. We also show that if the goal is to find a query set which can identify symmetric functions with high probability, the size of the query set can be further reduced. 2. We prove lower bounds on the number of queries needed under both batch and query modes. We also present complexity results that point out the difficulty of efficiently generating small query sets. 3. We present an approximation algorithm with a provable performance guarantee to make a query set compact by eliminating redundant queries. 4. We evaluate our algorithms on a large number of realworld and synthetic networks. For the batch mode, one of our approaches based on greedy graph coloring generated query sets of minimum size for most of the real-world networks. We also demonstrate the effectiveness of a simple approach based on sampling queries from a particular distribution followed by a compaction algorithm. 5. We develop a greedy adaptive heuristic based on binary search and evaluate it by generating query sets for various settings of networks and threshold assignments. Our results show that for most cases, it significantly outperforms the batch mode algorithms.
Related Work. There are several works on the passive mode of inference. Many researchers have studied the problem of learning automata (e.g., (Murphy 1996)). In (Kearns and Vazirani 1994), the problems of learning normal forms and Boolean functions are discussed. Works such as (González-Bailón et al. 2011;Romero, Meeder, and Kleinberg 2011) present methods to infer thresholds from social media data. Learning the source nodes of infection for contagions is addressed in (Zhu, Chen, and Ying 2017). Many of these problems are formally hard even for simple local functions. The work of (Adiga et al. 2017a) studies several problems aimed at inferring thresholds in discrete dynamical systems.
Active querying is studied in (Kleinberg, Mullainathan, and Ugander 2017) in the context of determining user choices from a finite set of ranked options-the choice set problem. The goal is to minimize the number of queries of arbitrary subsets S of size k, of a universal set U , to learn a user's choice from among the elements of each set S. With these results, the algorithm can then predict the user's choice for any subset S ⊆ U of size k. They show that this can be accomplished with O(n log n) queries where n = |U |.
Although error-tolerant approaches for querying systems are beyond the scope of this work, several authors study inference problems wherein errors are allowed. These include (Valiant 1984;Juba 2016;He et al. 2016;Zhang, Mathew, and Juba 2017;Kleinberg, Mullainathan, and Ugander 2017).
While many of the above studies address social systems, other network-based dynamical systems, such as Boolean networks, gene regulatory networks, and polynomial dynamical systems are used to study inference problems. Boolean networks are inferred from data in (Berestovsky and Nakhleh 2013). Polynomial dynamical systems are inferred using biochemical network data in (Laubenbacher and Stigler 2009).
2 Synchronous Dynamical Systems (SyDSs)
We consider two classes of local functions, namely threshold and symmetric functions. They are defined below. (i) Threshold functions: The local function f i associated with node v i of a SyDS S is a t i -threshold function for some integer t i ≥ 0 if the following condition holds: the value of f i is 1 if the number of 1's in the input to f i is at least t i ; otherwise, the value of the function is 0. Let d i denote the degree of node v i , and let t i denote the threshold of node v i . The number of inputs to the function f i is d i + 1. Thus, we assume that 0 ≤ t i ≤ d i + 2. (The threshold values 0 and d i + 2 allow us to realize local functions that always output 1 and 0 respectively.) (ii) Symmetric functions: A local function f i at node v i is symmetric if the value of the function depends only on the number of 1's in the input. Thus, a symmetric function f i with k inputs can be specified using a table with k + 1 rows, with row j specifying the value of the function when the number of 1's in the input to the function is exactly j, 0 ≤ j ≤ k. Note that each threshold function is also a symmetric function.
We will use the term "symmetric SyDS" ("threshold SyDS") to refer to a SyDS whose local functions are all symmetric (threshold).
Example: Consider the threshold SyDS shown in Figure 1. Suppose the local transition functions at each of the nodes v 1 , v 5 and v 6 is the 1-threshold function and the functions at v 2 , v 3 and v 4 are 2-threshold functions. Assume that initially, v 3 is in state 1 and all other nodes are in state 0. During the first time step, the states of nodes v 1 , v 5 and v 6 change to 1 since each of them has a neighbor (namely, v 3 ) in state 1. Also, the state of v 3 changes to 0 since its threshold is 2 and none of its neighbors is in state 1. The states of v 2 and v 4 don't change; they continue to be 0. During time step 2, v 2 and v 3 change to 1 but v 4 remains at 0. Once the system reaches the configuration C = (1,1,1,0,1,1) at time step 2, it remains in that configuration forever. Given a graph G(V, E) and a node
The general problem addressed in this paper is that of correctly identifying the local functions of a SyDS by querying the system. We assume that the underlying network is known. Each query specifies a configuration C and the response from the system is the successor C of C. Since the state of each node is either 0 or 1, each query q and the response to q are bit vectors of length n. We consider two query modes. In the batch query mode, a user must submit all the queries together as a single batch. In the adaptive query mode, a user may submit the queries in several batches; the queries chosen in a batch may rely on the responses received from the system for the previous batches of queries. As will be seen, for threshold SyDSs, the adaptive query mode can significantly decrease the number of queries. The following additional definitions regarding queries will be used throughout this paper.
Given a query q and a node v i , the score of q with respect to v i , denoted by score(q,v i ), is the number of nodes in the closed neighborhood N [v i ] of v i that are set to 1 in q. Thus, score(q,v i ) gives the number of 1's in the input provided by q to the local function f i at v i .
Definition 1 Let S be a symmetric SyDS. For any node v i , let
When a query set Q covers a node v, the local symmetric function f v can be correctly inferred from the responses to the queries in Q. Thus, complete query sets have the following property.
Observation 1 Let S be a symmetric SyDS. If Q is a complete query set for S, then each local function of S can be determined given the successor of each query in Q.
In this section, we first present an algorithm for generating query sets under the batch mode for symmetric SyDSs. We then show that for threshold SyDSs, the number of queries can be substantially reduced under the adaptive query mode. We also establish lower bounds on the number of queries needed under both modes. We present complexity results that suggest that in general, generating complete query sets of minimum size is computationally intractable. We also develop an efficient heuristic to reduce the size of query sets by eliminating redundant queries.
We begin by defining the notion of a monotone query sequence. The sequence of queries constructed can be submitted as a batch to learn all the local functions of a symmetric SyDS. Using the notion of "sequence" allows us to point out an interesting connection between the problem of identifying local symmetric functions and a variant of the node coloring problem for the underlying graph.
Definition 2 (a) Given two queries q 1 and q 2 , we use the notation q 1 ≤ q 2 to mean that every bit which is 1 in q 1 is also 1 in q 2 . (b) A query sequence q 1 , q 2 , . . . , q r is monotone if for each i, 1 ≤ i ≤ r -1, q i ≤ q i+1 . (c) Let S be a SyDS in which each local function is symmetric and let M be a monotone query sequence. If M is also a complete query set for S (i.e., each node v of S is covered by M ), then M is a complete monotone query sequence.
We now present an algorithm to show that if the underlying graph G has n nodes, then there is a monotone complete query sequence M for S with at most min{Δ 2 + 2, n + 1} queries, where Δ is the maximum node degree of G. This sequence of queries can be submitted as a batch to learn all the symmetric local functions. To establish this result, we recall the following definitions.
Definition 3 (a) Given an undirected graph H(V H , E H ) and an integer k ≥ 1, a k-coloring of H assigns a color from the set {1, 2, . . . , k} to each node of H such that for each edge {u, v} ∈ E H , the colors assigned to u and v Input: Graph G(V, E) of a symmetric SyDS S. Output: A monotone complete query sequence M for S.
Steps:
3. Let C1, C2, . . ., C k denote the color classes created in Step 2.
(Color class Cj consists of all nodes assigned color j, 1 ≤ j ≤ k.) Create the query sequence M = q0, q1, . . . , q k with k + 1 queries as follows.
(a) Query q0 is a bit vector where every element is 0. (b) for j = 1 to k do Create query q j by choosing the value 1 for all the nodes in C1 ∪ . . . ∪ Cj and 0 for the other nodes.
4. Output the query sequence M . We will also use the following result (West 2001): a graph H(V H , E H ) with maximum node degree Δ H can be colored efficiently using at most Δ H + 1 colors.
Our algorithm ALG-MONOTONE-SEQ for generating a monotone complete query sequence M for the given SyDS S is shown in Figure 2. It is easy to see that the algorithm runs in polynomial time. The following theorem shows its correctness and estimates the number of queries generated. Proof sketch: The sequence is produced by coloring G 2 . Since the maximum node degree of G 2 is ≤ Δ 2 , G 2 can be efficiently colored with min{Δ 2 + 1, n} colors. The sequence produced has one query with all 0's and one query from each color class, for a total of at most min{Δ 2 +2, n+ 1} queries. A proof that this is a monotone and complete query sequence appears in (Adiga et al. 2017b).
For some graphs with maximum node degree Δ, Algorithm ALG-MONOTONE-SEQ may generate a query sequence with Ω(Δ 2 ) queries but it guarantees that the resulting query sequence is complete for a symmetric SyDS. We show in (Adiga et al. 2017c) that for graphs where Δ ≥ (log n) 2 , the number of queries can be reduced to O(Δ 1.5 log n), if we only need the query set to be complete with high probability.
For threshold SyDSs, the adaptive query mode can reduce the number of queries significantly. To illustrate this, consider a SyDS whose underlying graph is a star graph with n nodes; that is, there is one node v 1 with degree n-1 which is the root of the tree and each of the other nodes v 2 through v n is a child of the root. As will be shown in the section on lower bounds, in the batch mode, n+1 queries are necessary even for the star graph to identify all the thresholds. However, under the adaptive mode, using the following method, O(log n) queries are sufficient.
The idea is simple: use binary search to identify the threshold of node v 1 whose degree is n -1 using O(log n) queries. After this, the following 3 additional queries are sufficient to identify the thresholds of the remaining n -1 nodes: a query with all 0's, a second query with all 1's and a third one in which v 1 has the value 1 and all the remaining nodes have the value 0. Thus, all the thresholds can be identified in O(log n) queries under the adaptive mode. Thus: Proposition 1 For a threshold-SyDS whose graph is a star with n nodes, all the threshold values can be found using O(log n) queries under the adaptive mode.
The above idea can be applied to more general classes of graphs. Let a class of graphs with n nodes be called (α, β)-simple, if at most α nodes have degree > β (the degree may be Ω(n)) and all the remaining nα nodes have a degree of at most β, with α and β being constants independent of n. Thus, each star graph belongs to the class of (1, 1)-simple graphs. It is shown in (Adiga et al. 2017b) that O(log n) queries are sufficient under the adaptive mode for any for (α, β)-simple graph with n nodes. As an extension of this result, it is also shown in (Adiga et al. 2017b) that if a graph with n nodes is scale-free (Easley and Kleinberg 2010) with exponent γ ≥ 1, then O(n 2 γ+1 ) queries are sufficient under the adaptive mode.
Here, we present lower bounds under batch and adaptive query modes. We begin with a result that provides a lower bound for any symmetric SyDS under the batch mode. Proposition 2 Let S be a symmetric SyDS where the underlying graph G(V, E) has a maximum node degree Δ. Under the batch query model, every complete query set must contain at least Δ + 2 queries. Proof sketch: Consider a node v i with degree Δ. The symmetric function f i at v i has Δ + 2 entries, since the number of 1's in the input to f i varies from 0 to Δ + 1. Thus, any query set Q with |Q| < Δ + 2, cannot fully determine f i .
As a simple consequence of the above proposition, the following result points out that there are SyDSs with n nodes for which every complete query set must have n + 1 queries. This lower bound matches the upper bound of n + 1 given by Theorem 1 for all such graphs. Corollary 1 For a symmetric SyDS whose graph is a clique on n nodes, every complete query set under the batch mode must have at least n + 1 queries.
The following result shown in (Adiga et al. 2017b) points out that there are threshold SyDSs for which a large number of queries are needed even under the adaptive query mode. However, this result does not rule out the possibility of smaller query sets for special graph classes.
Theorem 2 For every n ≥ 1, there is a threshold SyDS whose underlying graph is a clique on n nodes such that at least n + 1 queries are necessary under the adaptive query mode to correctly identify all the threshold values.
Here, we present a result that provides an indication of the difficulty of efficiently generating small query sets. Our complexity result is for the following problem which we call the Short Monotone Complete Query Sequence (SMCQS) problem: given the underlying graph G(V, E) of a symmetric SyDS S and a positive integer k, is there a monotone complete query sequence Q with at most k queries for S? We use a reduction from the Distance-2 coloring problem for graphs (McCormick 1983) to prove the following result; for details, see (Adiga et al. 2017b).
Theorem 3 Problem SMCQS is NP-complete.
Under the batch mode, after generating a complete set of queries, it is useful to reduce the size of the set by eliminating redundant queries. This Query Set Compaction (QSC) problem can be formulated as follows: given the underlying graph G(V, E) of a symmetric SyDS S, a complete query set Q and an integer k ≤ |Q|, is there a subset Q ⊆ Q such that |Q | ≤ k and Q is also a complete query set for S?
The following result shows the complexity of QSC. The proof in (Adiga et al. 2017c) uses a reduction from the Minimum Set Cover (MSC) problem (Garey and Johnson 1979).
Theorem 4 Unless P = NP, QSC cannot be approximated in polynomial time to within the factor o(log n), where n is the number of nodes in the graph of the symmetric SyDS, even when the underlying graph has no edges.
To complement the above hardness result, we present an efficient approximation algorithm with a performance guarantee of O(log n) for the QSC problem. The idea is to use a reduction from the QSC problem to the MSC problem and use a well known (greedy) approximation algorithm for MSC (Vazirani 2001) which provides a performance guarantee of O(log n).
The steps of our approximation algorithm Approx-QSC for QSC are shown in Figure 3. The performance of Approx-QSC is shown in the following theorem, whose proof appears in (Adiga et al. 2017c).
Theorem 5 Algorithm Approx-QSC provides a performance guarantee of O(log n) where n is the number of nodes in the underlying graph of the SyDS.
We performed extensive experiments on more than 20 diverse real-world and synthetic networks. They are listed in Table 1 along with some of their properties. We present representative results for selected networks, with other networks exhibiting the same behavior unless stated otherwise.
Input: The underlying graph G(V, E) of a symmetric SyDS S and a complete query set Q. Output: A subset Q ⊆ Q such that Q is also a complete query set and |Q | is as small as possible.
Steps:
1. To construct the base set X of the MSC instance, consider each node vi; let di denote the degree of vi. Create a set Ai of di + 1 elements, given by Ai = {a ik : 0 ≤ k ≤ di}, for vi. The set X is given by X = ∪ n i=1 Ai. 2. From each query qj ∈ Q, construct a subset Yj of X as follows.
Initially, Yj = ∅. For each vi ∈ V , 1 ≤ i ≤ n, if qj sets k of the inputs to vi to 1, then add the element a ik to Yj.
3. Use the greedy algorithm (Vazirani 2001) to get an approximate solution Y to the resulting MSC instance.
4. Construct the query set Q by choosing the query corresponding to each subset in Y and output Q . We studied three approaches for inferring thresholds, two of which correspond to the batch mode and hence are applicable to symmetric SyDSs as well, and one being an adaptive approach. The first batch mode approach is based on coloring G 2 and the other is a probabilistic query approach mentioned in Section 3.1. In both cases, we applied the compaction algorithm (Figure 3) on the resulting complete query sets. Next, we developed a greedy algorithm for inferring thresholds under the adaptive mode and evaluated its performance.
Our theoretical results indicate that both network structure and the threshold assignments influence the number of queries required to infer the system. The experiments conducted were designed to further explore these aspects.
We studied the performance of ALG-MONOTONE-SEQ (Figure 2). The results are in Table 2. For most real world networks considered in this paper, it gives the best possible performance, i.e., the number of colors used to color G 2 , denoted by n c (G 2 ), is equal to Δ + 1; this along with the query of all 0's is a lower bound on the size of a complete set (Proposition 2). For synthetic networks (random regular and Erdős-Rényi graphs) though, n c (G 2 ) is significantly higher than Δ + 1, yet much lower than Δ 2 + 1. The reader should note that the observed performance is due to a combination of the structure of G 2 and the nature of the greedy coloring scheme. We observe that unlike the synthetic networks considered, most of the real-world networks are scale-free with maximum degree much larger than the average degree d avg . This is a possible reason for the superior performance of this approach. We also compared the results to the spectral radius bound, that is, the number of colors needed to color G 2 is at most 1 + λ 2 max (Miao and Fan 2014). It is wellknown that √ Δ ≤ λ max ≤ Δ, and for the real-world networks considered, λ max is indeed much less than Δ. However, despite this fact, we observe that λ 2 max + 1 is much , 50, 100, 200, 250, 400, 500, 700, 800. For davg = 50, 100, nc(G 2 ) + 1 = 348-358, 988-996, and for greater davg, nc(G 2 ) = 1000. larger than n c (G 2 ) + 1 in these cases. Compaction. For the reasons mentioned above, query sets generated by this approach are already compact. Thus, the compaction algorithm of Section 3.5 did not eliminate any queries. A formal explanation for this appears in (Adiga et al. 2017c).
In this approach, we use the probabilistic method mentioned in Section 3.1 to construct a complete set. The query set contains the configurations of all zeros, of all ones and Δ random queries where queries are sampled from distributions D(i/Δ) for 1 ≤ i ≤ Δ. Compared to Method 1, this is a very simple approach not requiring construction of G 2 or graph coloring. However, it is not guaranteed that the constructed query set is complete and therefore the process may have to be repeated a number of times. Further, the resulting set, even though large, can be compressed using the compaction algorithm.
We constructed 50 such query sets for three values of (2, 5 and 10) and checked if each of them is a complete set. For = 2, out of the 50 sets none of them were complete. However, for = 10, from 5 to 50 query sets turned out to be complete sets depending on the network. We applied the compaction algorithm on the complete sets generated by the randomized algorithm. The results for = 10 are in Table 2. The compaction ratio depends on the size of complete set which was given as input. On an average, the combination of randomized algorithm and compaction gives query sets of size around 1.5 to 2 times that of Method 1 ( Performance of compaction. We note that compaction of query sets generated by Method 2 consistently yields 80% reduction in the size of the query set (Table 2).
While the two previous methods are for the batch mode, here we discuss an adaptive algorithm to infer the thresholds.
We give an outline of the approach; a complete description appears in (Adiga et al. 2017b). For every node, let t L (v) and t H (v) be the minimum and maximum possible values of threshold that v can be assigned. These values quantify the uncertainty about the threshold. The threshold is said to have been inferred when t H (v) = t L (v). In a query q, if score(q, v) falls in the range [t L (v), t H (v) -1], then, the v), score(q, v)] depending on the state in the successor configuration. In this heuristic, we use a greedy adaptive approach where the current query is constructed iteratively in the following way. To begin with, all nodes are in state 0. We first choose that node, say v max , for which the threshold range is a maximum. We set exactly (t L (v) + t H (v))/2 of nodes in its closed neighborhood to state 1. This guarantees a reduction of the range by half. In the next iteration, we ignore all nodes in G within distance-2 of v max and repeat this process. The query is fully constructed when there are no more vertices to consider. After each query, the range [t L (v), t H (v) -1] for every v is updated based on its state in the successor. We terminate this process when for all v, t L (v) = t H (v). The analysis of our experimental results follows.
Influence of threshold values and ranges. In general, the number of queries required is highly dependent on the possible threshold values of nodes. We conducted experiments in the following manner. Let 0 ≤ θ ≤ 1 be a real number. For a fixed value of θ, each node v was assigned a threshold value uniformly at random from the interval (d(v) + 2)(1θ)/2, (d(v) + 2)(1 + θ)/2 . For θ = 0, the interval corresponds to the fixed threshold of (d(v) + 2)/2; for θ = 1, any value from 0 to d(v) + 2 is possible. The results are in Figure 4(a) and 5(a) for random k-regular and real-world networks respectively. For the random-regular graphs, the number of queries (averaged over 10 instances of graphs for each k) increases from O(log k) to as high as n, the size of the graph. We note that for k = n -1, this is in accordance with Theorem 2. For the real-world graphs, we see that increasing the range of threshold has the effect of gradually increasing the number of queries, but the number is less than 1.5Δ. In Figure 4(b), we investigate the influence of the threshold value on query set size. Again, we considered random k-regular graphs with varying k. Every node was assigned the same threshold. We see that the number of queries required is maximum when the threshold is around Δ/2, and it decreases as the threshold approaches either 0 or Δ. Influence of network structure. Theoretical bounds on query set sizes developed in Section 3 were in terms of Δ and n. Here, our objectives are two-fold. Firstly, we compare our adaptive approaches to the non-adaptive bounds, partic-ularly the number of queries required relative to log Δ, Δ and Δ 2 . Secondly, we investigate the effect of graph density and degree distribution on the performance of the heuristic.
We note that graph density plays an important role in the performance of the algorithm. First, we consider synthetic k-regular networks. In Figure 4(b), we see that for low values of k, the number of queries required is very small, but it increases rapidly (for higher values of thresholds). When the graph is sparse, for any node, the number of nodes within distance two (namely, k 2 + 1) is small. Therefore, for every query constructed by the heuristic, the uncertainty range of around n/k 2 nodes (the "v max " vertices) is halved. However, as k increases, this number decreases drastically. Hence we see that the number of queries required increases. However, as the graph density increases, the intersection of the neighborhoods of any two nodes is large, and this has the effect of reducing the variation in the scores of nodes. Therefore, particularly when the range of threshold values is limited, far fewer queries are required to infer thresholds in dense networks. Progress towards inferring thresholds. In Figure 5(b), we plot the accumulated threshold ranges for all vertices as the algorithm moves from one query to the next. We note that within one-fifth of the total query set size, the total accumulated threshold range decreases well below 5% of its original value for the majority of studied networks.
One limitation of our work is that queries and the responses from the system are assumed to specify the states of all the nodes in the system. An important research direction is to extend the results to allow specifications of partial configurations in queries and responses. Further, our focus was on dynamical systems with threshold and symmetric functions. Thus, another research direction is to consider other classes of functions. Finally, it is also of interest to explore the use of queries to infer other components of a dynamical system (e.g., the network topology).
See the Wikipedia entry on this game.The Thirty-Second AAAI Conference on Artificial Intelligence