×

Inferring local transition functions of discrete dynamical systems from observations of system behavior. (English) Zbl 1371.68184

Summary: We consider the problem of inferring the local transition functions of discrete dynamical systems from observed behavior. Our focus is on synchronous systems whose local transition functions are threshold functions. We assume that the topology of the system is known and that the goal is to infer a threshold value for each node so that the system produces the observed behavior. We show that some of these inference problems are efficiently solvable while others are NP-complete, even when the underlying graph of the dynamical system is a simple path. We identify a fixed parameter tractable problem in this context. We also consider constrained versions of threshold inference problems where the input includes a set of equality or inequality constraints (which specify pairs of nodes which must have the same threshold value or different threshold values). We present algorithmic and complexity results for several constrained threshold inference problems.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lum, K.; Swarup, S.; Eubank, S.; Hawdon, J., The contagious nature of imprisonment: an agent-based model to explain racial disparities in incarceration rates, J. R. Soc. Interface, 11, 98 (2014)
[2] Halloran, M. E.; Ferguson, N. M.; Eubank, S.; Longini, I. M.; Cummings, D. A.; Lewis, B.; Xu, S.; Fraser, C.; Vullikanti, A.; Germann, T. C., Modeling targeted layered containment of an influenza pandemic in the United States, Proc. Natl. Acad. Sci. USA, 105, 12, 4639-4644 (2008)
[3] Diekmann, O.; Heesterbeek, H.; Britton, T., Mathematical Tools for Understanding Infectious Disease Dynamics (2012), Princeton University Press · Zbl 1304.92009
[4] Gruhl, D.; Guha, R.; Liben-Nowell, D.; Tomkins, A., Information diffusion through blogspace, (Proceedings of the 13th International Conference on World Wide Web (2004), ACM), 491-501
[5] Prakash, B. A.; Chakrabarti, D.; Valler, N. C.; Faloutsos, M.; Faloutsos, C., Threshold conditions for arbitrary cascade models on arbitrary networks, Knowl. Inf. Syst., 33, 3, 549-575 (2012)
[6] Granovetter, M., Threshold models of collective behavior, Amer. J. Sociol., 1420-1443 (1978)
[7] Kuhlman, C. J.; Kumar, V. A.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J., Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results, Data Min. Knowl. Discov., 29, 2, 423-465 (2015) · Zbl 1405.91522
[8] Trucano, T. G.; Swiler, L. P.; Igusa, T.; Oberkampf, W. L.; Pilch, M., Calibration, validation, and sensitivity analysis: what’s what, Reliab. Eng. Syst. Saf., 91, 10, 1331-1357 (2006)
[9] González-Bailón, S.; Borge-Holthoefer, J.; Rivero, A.; Moreno, Y., The dynamics of protest recruitment through an online network, Sci. Rep., 1 (2011), 7 pages
[10] Romero, D. M.; Meeder, B.; Kleinberg, J., Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter, (Proceedings of the 20th International Conference on World Wide Web (2011), ACM), 695-704
[11] Ugander, J.; Backstrom, L.; Marlow, C.; Kleinberg, J., Structural diversity in social contagion, Proc. Natl. Acad. Sci. USA, 109, 16, 5962-5966 (2012)
[12] Easley, D.; Kleinberg, J., Networks, Crowds, and Markets: Reasoning About a Highly Connected World (2010), Cambridge University Press · Zbl 1205.91007
[13] Mortveit, H.; Reidys, C., An Introduction to Sequential Dynamical Systems (2007), Springer Science & Business Media: Springer Science & Business Media New York, NY
[14] Barrett, C.; Hunt, H. B.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J.; Stearns, R. E., Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems, Theoret. Comput. Sci., 412, 30, 3932-3946 (2011) · Zbl 1216.91025
[15] Crane, J., The epidemic theory of ghettos and neighborhood effects on dropping out and teenage childbearing, Amer. J. Sociol., 1226-1259 (1991)
[16] Gaviria, A.; Raphael, S., School-based peer effects and juvenile behavior, Rev. Econ. Stat., 83, 2, 257-268 (2001)
[17] Xu, Y. J., Advance to and persistence in graduate school: identifying the influential factors and major-based differences, J. Coll. Stud. Ret., Res. Theory Pract., 16, 3, 391-417 (2014)
[18] v. Zalk, M. H.W.; Kerr, M.; Branje, S. J.; Stattin, H.; Meeus, W. H., Peer contagion and adolescent depression: the role of failure anticipation, J. Clin. Child Adolesc. Psychol., 39, 6, 837-848 (2010)
[19] Stevens, E. A.; Prinstein, M. J., Peer contagion of depressogenic attributional styles among adolescents: a longitudinal study, J. Abnorm. Child Psychol., 33, 1, 25-37 (2005)
[20] De la Higuera, C., Grammatical Inference: Learning Automata and Grammars (2010), Cambridge University Press · Zbl 1227.68112
[21] Heinz, J.; De la Higuera, C.; van Zaanen, M., Grammatical inference for computational linguistics, Synth. Lect. Hum. Lang. Technol., 8, 4, 1-139 (2015)
[22] Murphy, K. P., Passively learning finite automata (1996), Santa Fe Institute: Santa Fe Institute Santa Fe, NM, Tech. rep. 96-04-017
[23] Kearns, M. J.; Vazirani, U. V., An Introduction to Computational Learning Theory (1994), MIT Press: MIT Press Cambridge, MA
[24] Macy, M. W.; Willer, R., From factors to actors: computational sociology and agent-based modeling, Annu. Rev. Sociol., 28, 143-166 (2002)
[25] Barrett, C.; Hunt, H. B.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J.; Stearns, R. E.; Thakur, M., Predecessor existence problems for finite discrete dynamical systems, Theoret. Comput. Sci., 386, 1, 3-37 (2007) · Zbl 1137.68410
[26] Green, F., NP-complete problems in cellular automata, Complex Systems, 1, 3, 453-474 (1987) · Zbl 0648.68067
[27] Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J.; Stearns, R. E., Complexity of reachability problems for finite discrete dynamical systems, J. Comput. System Sci., 72, 8, 1317-1345 (2006) · Zbl 1119.68095
[28] Kosub, S.; Homan, C. M., Dichotomy results for fixed point counting in Boolean dynamical systems, (Proceedings of the 10th Italian Conference on Theoretical Computer Science (2007)), 163-174
[29] Sutner, K., Computational classification of cellular automata, Int. J. Gen. Syst., 41, 6, 595-607 (2012) · Zbl 1283.68232
[30] Abrahao, B.; Chierichetti, F.; Kleinberg, R.; Panconesi, A., Trace complexity of network inference, (Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2013), ACM), 491-499
[31] Gomez Rodriguez, M.; Leskovec, J.; Krause, A., Inferring networks of diffusion and influence, (Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2010), ACM), 1019-1028
[32] Soundarajan, S.; Hopcroft, J. E., Recovering social networks from contagion information, (Proceedings of the 7th Annual Conference on Theory and Models of Computation (2010), Springer), 419-430 · Zbl 1284.91494
[33] Shah, D.; Zaman, T., Rumors in a network: who’s the culprit?, IEEE Trans. Inform. Theory, 57, 8, 5163-5181 (2011) · Zbl 1366.91126
[34] Kleinberg, J., Cascading behavior in networks: algorithmic and economic issues, (Algorithmic Game Theory (2007), Cambridge University Press: Cambridge University Press UK), 613-632, Ch. 24 · Zbl 1151.91376
[35] Goles, E.; Martínez, S., Neural and Automata Networks: Dynamical Behavior and Applications (1990), Kluwer: Kluwer Dordrecht, The Netherlands · Zbl 1103.37302
[36] Durand, B., A random NP-complete problem for inversion of 2D cellular automata, Theoret. Comput. Sci., 148, 1, 19-32 (1995) · Zbl 0873.68140
[37] Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J.; Stearns, R. E.; Tosic, P. T., Gardens of Eden and fixed points in sequential dynamical systems, (Proceedings of the Discrete Mathematics and Theoretical Computer Science Conference (2001)), 95-110 · Zbl 1017.68055
[38] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, (Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003)), 137-146
[39] Bazgan, C.; Chopin, M.; Nichterlein, A.; Sikora, F., Parameterized approximability of maximizing the spread of influence in networks, J. Discrete Algorithms, 27, 54-65 (2014) · Zbl 1361.68105
[40] Bazgan, C.; Chopin, M., The complexity of finding harmless individuals in social networks, Discrete Optim., 14, 170-182 (2014) · Zbl 1308.91134
[41] Bazgan, C.; Chopin, M.; Cygan, M.; Fellows, M. R.; Fomin, F. V.; van Leeuwen, E. J., Parameterized complexity of firefighting, J. Comput. System Sci., 80, 7, 1285-1297 (2014) · Zbl 1411.68046
[42] Abu-Khzam, F. N.; Egan, J.; Fellows, M. R.; Rosamond, F. A.; Shaw, P., On the parameterized complexity of dynamic problems with connectivity constraints, (Combinatorial Optimization and Applications (2014), Springer), 625-636 · Zbl 1434.68204
[43] Boria, N.; Monnot, J.; Paschos, V. T., Reoptimization under vertex insertion: max \(P_k\)-free subgraph and max planar subgraph, Discrete Math. Algorithms Appl., 5, 2 (2013), 25 pages · Zbl 1271.05063
[44] Ito, T.; Demaine, E. D.; Harvey, N. J.; Papadimitriou, C. H.; Sideri, M.; Uehara, R.; Uno, Y., On the complexity of reconfiguration problems, (Proceedings of the 19th International Symposium on Algorithms and Computation (2008), Springer), 28-39 · Zbl 1183.68310
[45] Fernau, H.; Rodriguez-Velazquez, J. A., A survey on alliances and related parameters in graphs, Electron. J. Graph Theory Appl., 2, 1, 70-86 (2014) · Zbl 1306.05180
[46] Łacki, J.; Oćwieja, J.; Pilipczuk, M.; Sankowski, P.; Zych, A., The power of dynamic distance oracles: efficient dynamic algorithms for the Steiner tree, (Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (2015), ACM), 11-20 · Zbl 1321.68389
[47] van den Heuvel, J., The complexity of change, (Blackburn, S. R.; Gerke, S.; Wildon, M., Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 409 (2013), Cambridge University Press), 127-160 · Zbl 1307.05005
[48] Berglund, M.; Björklund, H.; Drewes, F., On the parameterized complexity of linear context-free rewriting systems, (Proceedings of the 13th Meeting on the Mathematics of Language, Association for Computational Linguistics (2013)), 21-29 · Zbl 1376.68077
[49] Florêncio, C. C.; Fernau, H., On families of categorical grammars of bounded value, their learnability and related complexity questions, Theoret. Comput. Sci., 452, 21-38 (2012) · Zbl 1252.68169
[50] Downey, R. G.; Fellows, M. R.; Kapron, B. M.; Hallett, M. T.; Wareham, H. T., The parameterized complexity of some problems in logic and linguistics, (Proceedings of the Third International Symposium on Logical Foundations of Computer Science. Proceedings of the Third International Symposium on Logical Foundations of Computer Science, Lecture Notes in Comput. Sci., vol. 813 (1994), Springer), 89-100 · Zbl 0946.03046
[51] Fernau, H.; Heggernes, P.; Villanger, Y., A multi-parameter analysis of hard problems on deterministic finite automata, J. Comput. System Sci., 81, 4, 747-765 (2015) · Zbl 1320.68090
[52] Niedermeier, R., Invitation to Fixed Parameter Algorithms (2006), Oxford University Press: Oxford University Press New York, NY · Zbl 1095.68038
[53] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press and McGraw-Hill: MIT Press and McGraw-Hill Cambridge, MA · Zbl 1187.68679
[54] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman & Co.: W.H. Freeman & Co. San Francisco · Zbl 0411.68039
[55] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer: Springer Heidelberg, Germany · Zbl 1143.68016
[56] Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), Acta Math., 182, 105-142 (1999) · Zbl 0989.68060
[57] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and Approximation: Combinatorial Problems and Their Approximability Properties (1999), Springer: Springer Berlin, Germany · Zbl 0937.68002
[58] Graham, R.; Knuth, D.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0836.00001
[59] West, D. B., Introduction to Graph Theory (2003), Prentice-Hall, Inc.: Prentice-Hall, Inc. Englewood Cliffs, NJ
[60] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, (Proceedings of the 39th Annual Symposium on Foundations of Computer Science (1998), IEEE), 653-662
[61] Lokshtanov, D.; Marx, D.; Saurabh, S., Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 105, 41-72 (2011) · Zbl 1258.68068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.