×

Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems. (English) Zbl 1216.91025

Summary: Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete graphical dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also address other problems that deal with the time evolution of such stochastic dynamical systems. Further, we point out the implications of our results to problems for other computational models such as Hopfield networks, communicating finite state machines and systolic arrays. In particular, our polynomial time algorithms for the predecessor existence problem for stochastic dynamical systems imply similar results for one-dimensional finite cellular automata.

MSC:

91D30 Social networks; opinion dynamics
37N99 Applications of dynamical systems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Axelrod, R., The Complexity of Cooperation (1994), Princeton University Press: Princeton University Press Princeton, NJ
[2] Barrett, C.; Bissett, K.; Eubank, S.; Marathe, M.; Kumar, V.; Mortveit, H., Modeling and simulation of large biological, information and socio-technical systems: an interaction-based approach, (Modeling and Simulation of Biological Networks. Modeling and Simulation of Biological Networks, Proceedings of Symposia in Applied Mathematics, vol. 64 (2007), American Mathematical Society) · Zbl 1398.68646
[3] Barrett, C.; Eubank, S.; Marathe, M., Modeling and simulation of large-scale biological, information and socio-technical systems: an interaction based approach, (Goldin, D.; Smolka, S.; Wegner, P., Interactive Computation: The New Paradigm (2006), Springer), 353-392
[4] C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, in: Proc. 26th Mathematical Foundations of Computer Science, MFCS 2001, Sept. 2001, pp. 159-172.; C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, in: Proc. 26th Mathematical Foundations of Computer Science, MFCS 2001, Sept. 2001, pp. 159-172. · Zbl 1006.37012
[5] Barrett, C.; Hunt, H.; Marathe, M.; Ravi, S.; Rosenkrantz, D.; Stearns, R., Reachability problems for sequential dynamical systems with threshold functions, Theoret. Comput. Sci., 295, 1-3, 41-64 (Feb. 2003)
[6] C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, in: Proceedings of the International Conference on Discrete Models for Complex Systems, DM-CS 2003, Lyon, France, June 2003, pp. 69-80.; C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, in: Proceedings of the International Conference on Discrete Models for Complex Systems, DM-CS 2003, Lyon, France, June 2003, pp. 69-80. · Zbl 1073.68684
[7] Barrett, C.; Hunt, H.; Marathe, M.; Ravi, S.; Rosenkrantz, D.; Stearns, R., Complexity of reachability problems for finite discrete dynamical systems, J. Comput. Syst. Sci., 72, 8, 1317-1345 (Dec. 2006)
[8] C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, M. Thakur, Computational aspects of analyzing social network dynamics, in: Proceedings of the International Joint Conference on AI, IJCAI 2007, Hyderabad, India, Jan. 2007, pp. 2268-2273.; C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, M. Thakur, Computational aspects of analyzing social network dynamics, in: Proceedings of the International Joint Conference on AI, IJCAI 2007, Hyderabad, India, Jan. 2007, pp. 2268-2273.
[9] Barrett, C.; Hunt, H.; Marathe, M.; Ravi, S.; Rosenkrantz, D.; Stearns, R.; Thakur, M., Predecessor existence problems for finite discrete dynamical systems, Theoret. Comput. Sci., 386, 1-2, 3-37 (Oct. 2007)
[10] Barrett, C.; Mortveit, H.; Reidys, C., Elements of a theory of simulation II: sequential dynamical systems, Appl. Math. Comput., 107, 2-3, 121-136 (2000) · Zbl 1049.68149
[11] Barrett, C.; Mortveit, H.; Reidys, C., Elements of a theory of simulation III: equivalence of SDS, Appl. Math. Comput., 122, 325-340 (2001) · Zbl 1050.68161
[12] Barrett, C.; Reidys, C., Elements of a theory of simulation I: sequential CA over random graphs, Appl. Math. Comput., 98, 241-259 (1999) · Zbl 0927.68114
[13] H. Bodlaender, Treewidth: algorithmic techniques and results, in: Proceedings of the 22nd Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36.; H. Bodlaender, Treewidth: algorithmic techniques and results, in: Proceedings of the 22nd Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36. · Zbl 0941.05057
[14] Epstein, J.; Axtell, R., Growing Artificial Societies: Social Science from the Bottom Up (1996), Brookings/MIT Press
[15] Eubank, S.; Guclu, H.; Kumar, V.; Marathe, M.; Srinivasan, A.; Toroczkai, Z.; Wang, N., Monitoring and mitigating smallpox epidemics: strategies drawn from a census data instantiated virtual city, Nature, 429, 180-184 (May 2004)
[16] D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, To be published by Cambridge University Press, 2010. (Pre-publication draft available from http://www.cs.cornell.edu/home/kleinber/; D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, To be published by Cambridge University Press, 2010. (Pre-publication draft available from http://www.cs.cornell.edu/home/kleinber/
[17] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman and Co.: W. H. Freeman and Co. San Francisco, CA · Zbl 0411.68039
[18] Green, F., NP-complete problems in cellular automata, Complex Systems, 1, 3, 453-474 (1987) · Zbl 0648.68067
[19] Harel, D.; Kupferman, O.; Vardi, M., On the complexity of verifying concurrent transition systems, Inform. and Comput., 173, 143-161 (2002) · Zbl 1009.68082
[20] Hunt, H.; Marathe, M.; Radhakrishnan, V.; Stearns, R., The complexity of planar counting problems, SIAM J. Comput., 27, 4, 1142-1167 (Aug. 1998)
[21] Jeras, I.; Dobnikara, A., Algorithms for computing preimages of cellular automata configurations, Physica D, 233, 2, 95-111 (Sept. 2007)
[22] Kari, J., Theory of cellular automata: a survey, Theoret. Comput. Sci., 334, 1-3, 3-33 (2005) · Zbl 1080.68070
[23] D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for social networks”, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, ICALP, Lisbon, Portugal, Jul. 2005, pp. 1127-1138.; D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for social networks”, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, ICALP, Lisbon, Portugal, Jul. 2005, pp. 1127-1138. · Zbl 1084.91053
[24] S. Kosub, C. Homan, Dichotomy results for fixed-point counting in boolean dynamical systems, in: Proc. 10th Italian Conference on Theoretical Computer Science, ICTCS 2007, Rome, Italy, Oct. 2007, pp. 163-174.; S. Kosub, C. Homan, Dichotomy results for fixed-point counting in boolean dynamical systems, in: Proc. 10th Italian Conference on Theoretical Computer Science, ICTCS 2007, Rome, Italy, Oct. 2007, pp. 163-174. · Zbl 1318.68089
[25] Kosub, S., Dichotomy results for fixed-point existence problems for boolean dynamical systems, Math. Comput. Sci., 1, 3, 487-505 (Mar. 2008)
[26] V. Kumar, M. Macauley, H. Mortveit, Limit set reachability in asynchronous graph dynamical systems, in: Proc. Third International Workshop on Reachability Problems, RP 2009, Palaiseau, France, Sept. 2009, pp. 217-232.; V. Kumar, M. Macauley, H. Mortveit, Limit set reachability in asynchronous graph dynamical systems, in: Proc. Third International Workshop on Reachability Problems, RP 2009, Palaiseau, France, Sept. 2009, pp. 217-232. · Zbl 1260.68248
[27] Kung, H., Why systolic architectures, IEEE Comput., 15, 1, 37-42 (1982)
[28] Laubenbacher, R.; Jarrah, A.; Mortveit, H.; Ravi, S., A mathematical formalism for agent-based modeling, (Encyclopedia of Complexity and System Science (Feb. 2008), Springer: Springer Berlin)
[29] Macauley, M.; Mortveit, H., On enumeration of conjugacy classes of coxeter elements, Proc. Amer. Math. Soc., 136, 4157-4165 (2008) · Zbl 1157.05008
[30] Mortveit, H.; Reidys, C., Discrete, sequential dynamical systems, Discrete Math., 226, 1-3, 281-295 (2001) · Zbl 1004.05056
[31] Mortveit, H.; Reidys, C., An Introduction to Sequential Dynamical Systems (2007), Springer: Springer Berlin
[32] Macy, M.; Willer, R., From factors to actors: computational sociology and agent-based modeling, Ann. Rev. Sociol., 28, 143-166 (2002)
[33] M. Mahajan, Studies in language classes defined by different types of time-varying cellular automata, Ph.D. Thesis, Indian Institute of Technology, Madras, 1992.; M. Mahajan, Studies in language classes defined by different types of time-varying cellular automata, Ph.D. Thesis, Indian Institute of Technology, Madras, 1992.
[34] C. Nichitiu, E. Remila, Simulations of graph automata, in: Proc. MFCS’98 Satellite Workshop on Cellular Automata, Brno, Czech Republic, Aug. 1998, pp. 69-78.; C. Nichitiu, E. Remila, Simulations of graph automata, in: Proc. MFCS’98 Satellite Workshop on Cellular Automata, Brno, Czech Republic, Aug. 1998, pp. 69-78.
[35] P. Orponen, An overview of the computational power of recurrent neural networks, in: Proc. 9th Finnish AI Conference STeP 2000 - Millennium of AI, H. Hyotyniemi, ed. Espoo, Finland, 2000, pp. 89-96.; P. Orponen, An overview of the computational power of recurrent neural networks, in: Proc. 9th Finnish AI Conference STeP 2000 - Millennium of AI, H. Hyotyniemi, ed. Espoo, Finland, 2000, pp. 89-96.
[36] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049
[37] J. Simon, Space-bounded probabilistic turing machine complexity classes are closed under complement, in: Proc. ACM STOC,1981, pp. 158-167.; J. Simon, Space-bounded probabilistic turing machine complexity classes are closed under complement, in: Proc. ACM STOC,1981, pp. 158-167.
[38] M. Saks, S. Zhou, RSPACE \(( n ) ( n^{3 / 2} )\); M. Saks, S. Zhou, RSPACE \(( n ) ( n^{3 / 2} )\)
[39] Sarkar, P., A brief history of cellular automata, ACM Comput. Surv., 32, 1, 80-107 (2000)
[40] Soto, J., Computation of explicit preimages in one-dimensional cellular automata applying the De Bruijn diagram, J. Cellular Automata, 3, 3, 219-230 (2008) · Zbl 1158.68025
[41] Sutner, K., On the computational complexity of finite cellular automata, J. Comput. Syst. Sci., 50, 1, 87-97 (Feb. 1995)
[42] Tosic, P.; Agha, G., On computational complexity of counting fixed points in symmetric boolean graph automata, (Proc. UC’05 - Fourth International Conference on Unconventional Computation. Proc. UC’05 - Fourth International Conference on Unconventional Computation, LNCS series, vol. 3699 (October 2005), Springer-Verlag: Springer-Verlag Sevilla, Spain), 191-205 · Zbl 1161.68608
[43] (Wolfram, S., Theory and Applications of Cellular Automata (1987), World Scientific)
[44] Wooldridge, M., An Introduction to MultiAgent Systems (2002), John Wiley & Sons: John Wiley & Sons Chichester, England
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.