Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T02:15:32.108Z Has data issue: false hasContentIssue false
  • English
  • Français

Logic and learning in network cascades

Published online by Cambridge University Press:  14 April 2021

Galen J. Wilkerson Open the ORCID record for Galen J. Wilkerson [Opens in a new window]  and
Sotiris Moschoyiannis Open the ORCID record for Sotiris Moschoyiannis [Opens in a new window]
Galen J. Wilkerson*
Affiliation:
University of Surrey, Guildford, UK GU2 7XH, UK (e-mail: [email protected])
Sotiris Moschoyiannis
Affiliation:
University of Surrey, Guildford, UK GU2 7XH, UK (e-mail: [email protected])
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Critical cascades are found in many self-organizing systems. Here, we examine critical cascades as a design paradigm for logic and learning under the linear threshold model (LTM), and simple biologically inspired variants of it as sources of computational power, learning efficiency, and robustness. First, we show that the LTM can compute logic, and with a small modification, universal Boolean logic, examining its stability and cascade frequency. We then frame it formally as a binary classifier and remark on implications for accuracy. Second, we examine the LTM as a statistical learning model, studying benefits of spatial constraints and criticality to efficiency. We also discuss implications for robustness in information encoding. Our experiments show that spatial constraints can greatly increase efficiency. Theoretical investigation and initial experimental results also indicate that criticality can result in a sudden increase in accuracy.

Keywords

percolationcritical cascadesinformation cascadeinformation diffusioninfluence maximizationnetwork rewiringneuronal avalanchesstatistical learninglinear threshold modeluniversal Boolean logic
Type
Research Article
Information
Network Science , Volume 9 , Special Issue S1: Complex Networks 2019 , October 2021 , pp. S157 - S174
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

Action Editor: Hocine Cherifi

References

Altafini, C. (2012). Consensus problems on networks with antagonistic interactions. IEEE Transactions on Automatic Control, 58(4), 935–946.CrossRefGoogle Scholar
Bak, P., Tang, C., & Wiesenfeld, K. (1987). Self-organized criticality: An explanation of the 1/f noise. Physical Review Letters, 59(4), 381.CrossRefGoogle ScholarPubMed
Barra, A., Genovese, G., Sollich, P., & Tantari, D. (2017). Phase transitions in restricted boltzmann machines with generic priors. Physical Review E, 96(4), 042156.CrossRefGoogle ScholarPubMed
Barthélemy, M. (2011). Spatial networks. Physics Reports, 499(1–3), 1–101.CrossRefGoogle Scholar
Bassett, D. S., Wymbs, N. F., Porter, M. A., Mucha, P. J., Carlson, J. M., & Grafton, S. T. (2011). Dynamic reconfiguration of human brain networks during learning. Proceedings of the National Academy of Sciences, 108(18), 7641–7646.CrossRefGoogle Scholar
Beggs, J. M., & Plenz, D. (2003). Neuronal avalanches in neocortical circuits. Journal of Neuroscience, 23(35), 11167–11177.CrossRefGoogle ScholarPubMed
Bengio, Y., Lee, D.-H., Bornschein, J., Mesnard, T., & Lin, Z. (2015). Towards biologically plausible deep learning. arxiv preprint arxiv:1502.04156.Google Scholar
Bohte, S. M, Kok, J. N., & La Poutre, H. (2002). Error-backpropagation in temporally encoded networks of spiking neurons. Neurocomputing, 48(1–4), 17–37.CrossRefGoogle Scholar
Bruce, A. D., Gardner, E. J., & Wallace, D. J. (1987). Dynamics and statistical mechanics of the hopfield model. Journal of Physics A: Mathematical and General, 20(10), 2909.CrossRefGoogle Scholar
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2000). Network robustness and fragility: Percolation on random graphs. Physical Review Letters, 85(25), 5468.CrossRefGoogle ScholarPubMed
Chen, D., Lü, L., Shang, M.-S., Zhang, Y.-C., & Zhou, T. (2012). Identifying influential nodes in complex networks. Physica A: Statistical Mechanics and Its Applications, 391(4), 1777–1787.CrossRefGoogle Scholar
Conte, T., DeBenedictis, E., Ganesh, N., Hylton, T., Still, S., Strachan, J. P., Williams, R. S., Alemi, A., Altenberg, L., Crooks, G., et al. (2019). Thermodynamic computing. arxiv preprint arxiv:1911.01968.Google Scholar
Coolen, A. C. C. (1998). A beginner’s guide to the mathematics of neural networks. In Concepts for neural networks (pp. 13–70). Springer.CrossRefGoogle Scholar
Dayan, P., & Abbott, L. F. (2001). Theoretical neuroscience: computational and mathematical modeling of neural systems. Computational Neuroscience Series.Google Scholar
Demirel, Y. (2013). Nonequilibrium thermodynamics: transport and rate processes in physical, chemical and biological systems. Newnes.Google Scholar
Domingos, P., & Richardson, M. (2001). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining (pp. 57–66).CrossRefGoogle Scholar
Easley, D., Kleinberg, J, et al. (2010). Networks, crowds, and markets. Vol. 8. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Gao, J., Zhou, T., & Hu, Y. (2015). Bootstrap percolation on spatial networks. Scientific Reports, 5, 14662.CrossRefGoogle ScholarPubMed
Gleeson, J. P., & Cahalane, D. J. (2007). Seed size strongly affects cascades on random networks. Physical Review E, 75(5), 056103.CrossRefGoogle ScholarPubMed
Granovetter, M. (1978). Threshold models of collective behavior. American Journal of Sociology, 83(6), 1420–1443.CrossRefGoogle Scholar
Gray, C., Mitchell, L., & Roughan, M. (2018). Super-blockers and the effect of network structure on information cascades. In Companion proceedings of the the web conference 2018 (pp. 1435–1441).CrossRefGoogle Scholar
Häggström, O. (2000). Markov random fields and percolation on general graphs. Advances in Applied Probability, 32(1), 39–66.CrossRefGoogle Scholar
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media.CrossRefGoogle Scholar
Hebb, D. O. (2005). The organization of behavior: A neuropsychological theory. Psychology Press.CrossRefGoogle Scholar
Hesse, J., & Gross, T. (2014). Self-organized criticality as a fundamental property of neural systems. Frontiers in Systems Neuroscience, 8, 166.CrossRefGoogle ScholarPubMed
Jalili, M., & Perc, M. (2017). Information cascades in complex networks. Journal of Complex Networks, 5(5), 665–693.Google Scholar
Jarman, N., Steur, E., Trengove, C., Tyukin, I. Y., & van Leeuwen, C. (2017). Self-organisation of small-world networks by adaptive rewiring in response to graph diffusion. Scientific Reports, 7(1), 1–9.CrossRefGoogle ScholarPubMed
Karrer, B., & Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107.CrossRefGoogle ScholarPubMed
Kato, H., & Ikeguchi, T. (2008). Self-organized complex neural networks through nonlinear temporally asymmetric hebbian plasticity. In International conference on artificial neural networks (pp. 623–631). Springer.Google Scholar
Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 137–146).CrossRefGoogle Scholar
Khalil, E. B., Dilkina, B., & Song, L. (2014). Scalable diffusion-aware optimization of network topology. In Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 1226–1235).CrossRefGoogle Scholar
Leskovec, J., Huttenlocher, D., & Kleinberg, J. (2010). Signed networks in social media. In Proceedings of the sigchi conference on human factors in computing systems (pp. 1361–1370). ACM.CrossRefGoogle Scholar
Lynn, C. W., & Bassett, D. S. (2019). The physics of brain network structure, function and control. Nature Reviews Physics, 1(5), 318.CrossRefGoogle Scholar
Mano, M. M. (1993). Computer system architecture. Prentice-Hall, Inc.Google Scholar
McCulloch, W. S., & Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics, 5(4), 115–133.CrossRefGoogle Scholar
Minsky, M. L., & Papert, S. (1969). Perceptrons; an introduction to computational geometry. MIT Press.Google Scholar
Murphy, K. P. (2012). Machine learning: a probabilistic perspective. MIT press.Google Scholar
Newman, M. (2018). Networks. Oxford university press.CrossRefGoogle Scholar
Newman, M. E. J. (2002). Spread of epidemic disease on networks. Physical Review E, 66(1), 016128.CrossRefGoogle ScholarPubMed
Penrose, M. (2003). Random geometric graphs. Vol. 5. Oxford University Press.CrossRefGoogle Scholar
Prokopenko, M. (2009). Guided self-organization. Taylor & Francis.CrossRefGoogle ScholarPubMed
Rojas, R. (2013). Neural networks: a systematic introduction. Springer Science & Business Media.Google Scholar
Rubin, R., Abbott, L. F., & Sompolinsky, H. (2017). Balanced excitation and inhibition are required for high-capacity, noise-robust neuronal selectivity. Proceedings of the National Academy of Sciences, 114(44), E9366–E9375.CrossRefGoogle Scholar
Sakoda, J. M. (1971). The checkerboard model of social interaction. The Journal of Mathematical Sociology, 1(1), 119–132.CrossRefGoogle Scholar
Savage, J. E. (1998). Models of computation. Vol. 136. Addison-Wesley Reading, MA.Google Scholar
Sayood, K. (2012). Introduction to data compression. Newnes.Google Scholar
Schelling, T. C. (1971). Dynamic models of segregation. Journal of Mathematical Sociology, 1(2), 143–186.CrossRefGoogle Scholar
Shew, W. L., & Plenz, D. (2013). The functional benefits of criticality in the cortex. The Neuroscientist, 19(1), 88–100.CrossRefGoogle ScholarPubMed
Smith, S. W., et al.. (1997). The scientist and engineer’s guide to digital signal processing. California Technical Pub. San Diego.Google Scholar
Stauffer, D., & Aharony, A. (2018). Introduction to percolation theory. CRC press.CrossRefGoogle Scholar
Vapnik, V. (1999). The nature of statistical learning theory . Information Science and Statistics. Springer New York.Google Scholar
Wang, C., Komodakis, N., & Paragios, N. (2013). Markov random field modeling, inference & learning in computer vision & image understanding: A survey. Computer Vision and Image Understanding, 117(11), 1610–1627.CrossRefGoogle Scholar
Watts, D. J. (2002). A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, 99(9), 5766–5771.CrossRefGoogle Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440.CrossRefGoogle ScholarPubMed
Wilkerson, G., & Moschoyiannis, S. (2019). Universal boolean logic in cascading networks. In International conference on complex networks and their applications (pp. 601–611). Springer.Google Scholar
Wilkerson, G. J. (2021). Logic and learning in network cascades. https://github.com/galenwilkerson/Logic-and-Learning-in-Network-Cascades CrossRefGoogle Scholar