CDI-Type I: Modeling and Predicting State-Topology Coevolution of Complex Adaptive Networks

Project Homepage

This project was supported by the NSF Cyber-enabled Discovery and Innovation Program (Award #: NSF BCS-1027752).
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

[About] [Software] [Team] [Publications] [Events] [Resources] [Contact Us]

About the Project

The rapidly growing complex network science has presented novel approaches to complex systems modeling that were not fully foreseen even in a few decades ago. It addresses the self-organization of complex network structure and its implications for system behavior, which holds significant cross-disciplinary relevance to many fields of natural and social sciences, particularly in today's highly networked social/political/economical circumstances.

Interestingly, complex network science has traditionally addressed either "dynamics on networks" (state transition on a network with a fixed topology) or "dynamics of networks" (topological transformation of a network with no dynamic state changes) almost separately. In many real-world complex biological and social networks, however, these two dynamics interact with each other and often coevolve over the same time scales. Modeling and predicting state-topology coevolution is now recognized as one of the most significant challenges in complex network science.

The goals of this NSF-funded project were to establish a generalized modeling framework that could effectively describe state-topology coevolution of complex adaptive networks and to develop computational methods for automatic discovery of dynamical rules that best capture both state transition and topological transformation in empirical data. To achieve these goals, graph rewriting systems were used as a means of unified representation of state transition and topological transformation. Network evolution was formulated in two parts, extraction and replacement of subnetworks. For each part, algorithms for automatic rule discovery were explored and developed. Their effectiveness was evaluated through application to simulated and real-world network data. This project has produced a novel theoretical framework and a computational toolkit that are expected to become the basis of transformational ways of studying the coevolution of dynamics on and of complex networks in the coming years.

The outcomes of this project have been disseminated via various channels and integrated in multiple educational programs at Binghamton University and other institutions. The developed algorithms and software tools are made freely available to researchers and other professionals for their own use. The developed framework has served as a generalized conceptual/mathematical "language" for modeling, analyzing and discussing the dynamics of various complex systems, which has galvanized interdisciplinary discussion and collaboration across many different areas of applications.

Software

• Current version of PyGNA on Github.com (version 0.8; released on 12/6/2014)
• Old version of PyGNA on SourceForge.net (version: 0.7; released on 8/15/2013)
• Python implementation of G-Trie fast motif search algorithm (released on 12/6/2014)

Research Team

Principal investigator

• Hiroki Sayama, D.Sc. (PI; Associate Professor, Departments of Bioengineering & Systems Science and Industrial Engineering)

Students

• Jeffrey Schmidt (PhD in Systems Science)
• Benjamin James Bush (PhD in Systems Science)
• Chun Wong (undergraduate in Bioengineering; graduated)
• Sam Heiserman (MS in Systems Science; graduated)

Collaborators

Research:

• Thilo Gross, Ph.D. (Director, Dynamics of Biological Networks Group, University of Bristol, UK)
• Jin Akaishi, Ph.D. (Assistant Professor, Kumamoto National College of Technology, Japan)
• Junichi Yamanoi, Ph.D. (Associate Professor, Chuo University, Japan)
• Zhirong Bao, Ph.D. (Memorial Sloan-Kettering Cancer Center, NY)

Education (NetSci High):

• Stephen Uzzo, Ph.D. (Vice President of Science and Technology, New York Hall of Science, NY)
• Catherine Cramer (New York Hall of Science, NY)
• H. Eugene Stanley, Ph.D. (Boston University, MA)
• Paul Trunfio, Ph.D. (Boston University, MA)
• Lori Sheez (USMA West Point, NY)
• Genki Ichinose (Assistant Professor, Anan National College of Technology, Japan)

Non-Academic Partners

• Irene Pestov, Ph.D. (Defence Research and Development Canada Centre for Operational Research and Analysis, Ottawa, ON, Canada)

Publications

Journal Articles

• Jeffrey Schmidt and Hiroki Sayama, Automated discovery of temporal network models based on generative network automata, in preparation.
• Benjamin James Bush and Hiroki Sayama, Think, talk, listen: How to succeed in an idea exchanging adaptive social network, in preparation.
• Hiroki Sayama, Catherine Cramer, Mason A. Porter, Lori Sheetz, and Stephen Uzzo, What are essential concepts about networks?, Journal of Complex Networks, 2015. Abstract/PDF Preprint
• Hiroki Sayama and Roberta Sinatra, Social diffusion and global drift on networks. Physical Review E, 91, 032809, 2015. Abstract/PDF Preprint
• Hiroki Sayama, Irene Pestov, Jeffrey Schmidt, Benjamin James Bush, Chun Wong, Junichi Yamanoi, and Thilo Gross, Modeling complex systems with adaptive networks, Computers and Mathematics with Applications, 65, 1645-1664, 2013. Abstract/PDF Preprint
• Deanna Blansky, Christina Kavanaugh, Cara Boothroyd, Brianna Benson, Julie Gallagher, John Endress, and Hiroki Sayama, Spread of academic success in a high school social network, PLOS ONE, 8(2), e55944, 2013. Available online
• Junichi Yamanoi and Hiroki Sayama, Post-merger cultural integration from a social network perspective: A computational modeling approach, Computational and Mathematical Organization Theory, 2012. Abstract/PDF
• Hiroki Sayama and Jin Akaishi, Characterizing interdisciplinarity of researchers and research topics using web search engines, PLoS ONE, 7(6): e38747, 2012. Available online.
• Shelley D. Dionne, Jin Akaishi, Xiujian Chen, Alka Gupta, Hiroki Sayama, Francis J. Yammarino, Andra Serban, Chanyu Hao, Hadassah J. Head and Benjamin James Bush, Retrospective relatedness reconstruction: Applications to adaptive social networks and social sentiment, Organizational Research Methods, 15: 663-692, 2012. Abstract/PDF

Conference Proceedings

• Catherine Cramer, Lori Sheetz, Hiroki Sayama, Paul Trunfio, H. Eugene Stanley, and Stephen Uzzo, NetSci High: Bringing network science research to high schools, Complex Networks VI: Proceedings of the Sixth Workshop on Complex Networks (CompleNet 2015), Studies in Computational Intelligence Volume 597, 2015, pp. 209-218, Springer. Abstract/PDF Preprint
• Hiroki Sayama, Social diffusion and global drift in adaptive social networks, Proceedings of Collective Intelligence 2014, paper 123, June 10-12, 2014, Cambridge, MA. Available online
• Jeffrey Schmidt and Hiroki Sayama, Designing and evaluating algorithms for automated discovery of adaptive network models based on Generative Network Automata, Proceedings of the Fourth IEEE Symposium on Artificial Life (IEEE ALIFE 2013), Singapore, 2013, IEEE, pp.27-34. (Won the Best Student Paper Award)
• Hiroki Sayama, Modeling co-evolution of states and topologies of adaptive networks, Proceedings of EvoNet2012: ALIFE 13 Workshop on Evolving Networks, from Systems/Synthetic Biology to Computational Neuroscience, pp.3-6. Proceedings available online.
• Irene Pestov, Hiroki Sayama and Chun Wong, Modeling discrete distributed heterogeneous systems, Proceedings of the Ninth International Conference on Modeling, Simulation and Visualization Methods (MSV'12), Las Vegas, NV, 2012.
• Hiroki Sayama, Adaptive networks: An emerging research theme on state-topology coevolution in complex networks, in Hiroki Sayama, Ali A. Minai, Dan Braha, and Yaneer Bar-Yam, eds., Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems (ICCS 2011), New England Complex Systems Institute Series on Complexity, NECSI Knowledge Press, 2011, p.416. PDF
• Jeffrey Schmidt, Benjamin James Bush, and Hiroki Sayama, A Python implementation of generative network automata, in Hiroki Sayama, Ali A. Minai, Dan Braha, and Yaneer Bar-Yam, eds., Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems (ICCS 2011), New England Complex Systems Institute Series on Complexity, NECSI Knowledge Press, 2011, pp.439-440. PDF
• Hiroki Sayama and Junichi Yamanoi, An adaptive network model of cultural integration in corporate merger, in Hiroki Sayama, Ali A. Minai, Dan Braha, and Yaneer Bar-Yam, eds., Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems (ICCS 2011), New England Complex Systems Institute Series on Complexity, NECSI Knowledge Press, 2011, pp.435-436. PDF
• Benjamin James Bush, Jeffrey Schmidt, and Hiroki Sayama, Behavior and centrality in idea exchanging adaptive social networks, in Hiroki Sayama, Ali A. Minai, Dan Braha, and Yaneer Bar-Yam, eds., Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems (ICCS 2011), New England Complex Systems Institute Series on Complexity, NECSI Knowledge Press, 2011, pp.437-438. PDF
• Hiroki Sayama, Adaptive networks: An emerging research theme on state-topology coevolution in complex networks, IPSJ SIG Mathematical Modelling and Problem Solving Technical Report 2010-MPS-081, no. 28, Fukuoka, Japan, December 16-17, 2010. PDF (Won the Best Presentation Award)
• Hiroki Sayama, An algorithm for automatically discovering dynamical rules of adaptive network evolution from empirical data, Proceedings of the 5th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS 2010 -- Boston, MA, December 1-3, 2010), Jun Suzuki and Tadashi Nakano, eds., LNICST 87, pp.497–504, 2012. Springer. PDF
• Jin Akaishi, Hiroki Sayama, Shelley D. Dionne, Xiujian Chen, Alka Gupta, Chanyu Hao, Andra Serban, Benjamin James Bush, Hadassah J. Head, and Francis J. Yammarino, Reconstructing history of social network evolution using web search engines, Proceedings of the 5th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS 2010 -- Boston, MA, December 1-3, 2010), Jun Suzuki and Tadashi Nakano, eds., LNICST 87, pp.155–162, 2012. Springer. PDF

e-Book

• Catherine Cramer, Mason A. Porter, Hiroki Sayama, Lori Sheetz, and Stephen Uzzo, eds., Network Literacy: Essential Concepts and Core Ideas, 2015, NetSciEd. Available online

Presentations

• Hiroki Sayama and Roberta Sinatra, Social diffusion and global drift on networks, presented at NetSci 2015 Satellite Symposium on Controlling Complex Networks: When Control Theory Meets Network Science, June 2, 2015, Zaragoza, Spain. Slides
• Catherine Cramer, Mason Porter, Hiroki Sayama, Lori Sheetz, and Stephen Uzzo, What are essential concepts about networks?, presented as a talk at NetSci 2015: International School and Conference on Network Science, June 1-5, 2015, Zaragoza, Spain. Slides
• Catherine Cramer, Russell Faux, Hiroki Sayama, Lori Sheetz, H. Eugene Stanley, Paul Trunfio, and Stephen Uzzo, NetSci High -- Bringing network science research to high schools: An evaluation, presented at NetSciEd4: NetSci 2015 Satellite Symposium on Network Science in Education, June 1, 2015, Zaragoza, Spain. Slides
• Hiroki Sayama, Modeling complex systems with adaptive networks, an invited seminar talk at the Collective Behavior Study Group at Cornell University, April 14, 2015, Ithaca, NY.
• Hiroki Sayama and Roberta Sinatra, Social diffusion and global drift on networks, presented as a poster at CompleNet 2015: The 6th International Workshop on Complex Networks, March 25-27, 2015, New York, NY.
• Maitri Mangal, Christopher Murphy, Hamza Aamir, Ryan Wood, Carol Reynolds, Alan Troidl, Jeffrey Schmidt, and Hiroki Sayama, Comparing post-secondary institutions across the United States, presented as a NetSci High poster at CompleNet 2015: Sixth Workshop on Complex Networks, March 25-27, 2015, New York, NY.
• Haashim Shah, Noor Rehman, Jacob King, Vika Rauzin, Alan Troidl, Carol Reynolds, Jeffrey Schmidt, and Hiroki Sayama, Drug combinations and adverse side effects, presented as a NetSci High poster at CompleNet 2015: Sixth Workshop on Complex Networks, March 25-27, 2015, New York, NY.
• Yousuf Shah, Ibraheem Rehman, Cheryl Limer, Zach Eaton, Carol Reynolds, Alan Troidl, Kristie McHugh, Hiroki Sayama, and Genki Ichinose, Comparing two human disease networks: Gene-based and symptom-based perspectives, presented as a K-12 poster paper at the 2015 IEEE Integrated STEM Education Conference, March 7, 2015, Princeton, NJ.
• Hiroki Sayama, Modeling complex systems with adaptive networks, an invited research seminar at Grupo de Sistemas Complejos, Universidad Politecnica de Madrid, Spain, December 4, 2014.
• Jeffrey Schmidt, Uncovering the Underlying Dynamics of Real World Temporal Network Data Using Generative Network Automata, Collective Dynamics of Complex Systems (CoCo) Seminar, Binghamton University, Binghamton, NY, November 19, 2014. Video
• Hiroki Sayama, Modeling the coevolution of states and topologies of adaptive networks, presented as an invited talk at AFOSR/NCI/DARPA Strategic Workshop on Convergence of Physical Sciences for Biomedical Applications: Phase Transition and Network Dynamics in Living and Non-Living Systems, August 28, 2014, Arlington, VA.
• Jeffrey Schmidt and Hiroki Sayama, Uncovering the underlying dynamics of real world temporal network data using Generative Network Automata, presented as a contributed talk at NetSci 2014 Satellite Symposium on Statistical Inference for Network Models, June 2, 2014, Berkeley, CA.
• Hiroki Sayama, Modeling dynamics of and on networks simultaneously: Theory-driven and data-driven approaches, presented as a contributed talk at NetSci 2014 Satellite Symposium on Higher-Order Models in Network Science, June 3, 2014, Berkeley, CA.
• Ibraheem Rehman, Cheryl Limer, Yousuf Shah, Zach Eaton, Carol Reynolds, Alan Troidl, Kristie McHugh, Genki Ichinose, and Hiroki Sayama, Comparing two human disease networks: Gene-based and symptom-based perspectives, presented as a poster at the International School and Conference on Network Science (NetSci 2014), June 2-6, 2014, Berkeley, CA.
• Jared Vargason, Gregory Taylor, Tyler Walters, Bolong Yu, Carol Reynolds, Alan Troidl, Kristie McHugh, Genki Ichinose, and Hiroki Sayama, How does one become successful in reddit.com?: Correlation between user karma and subreddit diversity, presented as a poster at the International School and Conference on Network Science (NetSci 2014), June 2-6, 2014, Berkeley, CA.
• Hiroki Sayama, Social diffusion and global drift in adaptive social networks, presented as a poster at the Third Network Science In Education Satellite Symposium (NetSciEd3), June 2, 2014, Berkeley, CA.
• Hiroki Sayama, Computational modeling and prediction of adaptive network dynamics, presented as a talk at Uncertainty in Interaction Networks, June 12-13, 2013, Bath, UK.
• Jeffrey Schmidt and Hiroki Sayama, Automatic discovery of adaptive network dynamics from temporal network data, presented as a poster at NetSci 2013: International School and Conference on Network Science (also as a talk at STCAN 2013: Satellite Symposium on State-Topology Coevolution in Adaptive Networks), June 3-7, 2013, Copenhagen, Denmark.
• Hiroki Sayama, Make geeks popular: An adaptive network approach to induce positive drift of students' grades diffusing in their social network, presented as a talk at NetSci 2013: International School and Conference on Network Science, June 3-7, 2013, Copenhagen, Denmark.
• Dan Seel, Per Andre Stromhaug, Carol Reynolds, Kristie Shirreffs, and Hiroki Sayama, An analysis of the networks of product creation and trading in the virtual economy of Team Fortress 2, presented as a poster at NetSciEd2: Second NetSci Satellite Symposium on Network Science in Education, June 3, 2013, Copenhagen, Denmark.
• Hiroki Sayama, Spatial artificial chemistries: From cellular automata to adaptive networks and swarms, an invited seminar talk at Cornell University Creative Machines Laboratory, Ithaca, NY, April 1, 2013.
• Benjamin James Bush, Behavior and centrality in idea exchanging adaptive social networks, Collective Dynamics of Complex Systems (CoCo) Seminar, Binghamton University, Binghamton, NY, March 6, 2013. Video
• Jeffrey Schmidt, PyGNA: Designing and evaluating algorithms for automated discovery of adaptive network models based on generative network automata, Collective Dynamics of Complex Systems (CoCo) Seminar, Binghamton University, Binghamton, NY, December 5, 2012. Video
• Hiroki Sayama, Computer programming for adaptive network modeling, a one-day seminar given at Defence Research and Development Canada Centre for Operational Research and Analysis, September 30, 2012, Ottawa, ON, Canada.
• Junichi Yamanoi and Hiroki Sayama, Post-merger cultural integration from a social network perspective: A computational modeling approach, Collective Dynamics of Complex Systems (CoCo) Seminar, Binghamton University, Binghamton, NY, September 19, 2012. Video
• Hiroki Sayama, An informal seminar talk about adaptive networks and generative network automata, given to graduate students at the Institute for Complex Systems Simulation of the University of Southampton, UK, August 7, 2012, Southampton, UK.
• Deanna Blansky, Christina Kavanaugh, Cara Boothroyd, Brianna Benson, Julie Gallagher, John Endress, and Hiroki Sayama, A possible spread of academic success in a high school social network: A two-year study, presented as a poster at NetSci 2012: International School and Conference on Network Science, June 18-22, 2012, Evanston, IL.
• Hiroki Sayama, Introducing network science to high schools: Merits, issues, and tips, from a professor's perspective, to be presented at NetSciEd Satellite Symposium at NetSci2012: Education -- Infuse Network Science into K-12 and Undergraduate Education, June 18, 2012, Evanston, IL.
• Junichi Yamanoi and Hiroki Sayama, Post-merger cultural integration from a social network perspective: A computational modeling approach, presented at the Fifth Intra-Organizational Network Conference (ION 5), April 14-15, 2012, Lexington, KY.
• Jeffrey Schmidt, GNApy: A Python implementation of generative network automata, Collective Dynamics of Complex Systems (CoCo) Seminar, Binghamton University, Binghamton, NY, October 5, 2011. Video
  
• Hiroki Sayama, Adaptive networks: An emerging research theme on state-topology coevolution in complex networks, invited talk at Electrical & Computer Engineering Research Seminar Series, Binghamton University, Binghamton, NY, September 20, 2011.
• Hiroki Sayama, Spatial artificial chemistries: Recent developments, a tutorial talk at the Artificial Chemical Computing Systems Tutorial at the Eleventh European Conference on Artificial Life (ECAL 2011), Paris, France, 2011.
• Hiroki Sayama and Jin Akaishi, Characterizing interdisciplinarity of scientists and research topics using web search engines, presented as a talk at NetSci 2011: International School and Conference on Network Science, June 6-10, 2011, Budapest, Hungary.
• Hiroki Sayama and Junichi Yamanoi, An adaptive network model of cultural integration in corporate merger, presented as a talk at NetSci 2011: International School and Conference on Network Science, June 6-10, 2011, Budapest, Hungary.
• Cara Boothroyd, Brianna Benson, Deanna Blansky, Christina Kavanaugh, Julie Gallagher, John Endress, Benjamin James Bush, and Hiroki Sayama, Academic achievement and personal satisfaction in high school social networks, presented as a poster at the NetSci High: International High School Student Poster Competition on Network Science, in NetSci 2011: International School and Conference on Network Science, June 6-10, 2011, Budapest, Hungary.
• Jessica Calderone, Emma Valentine, Josie Trichka, Julie Gallagher, Benjamin James Bush, Jin Akaishi, and Hiroki Sayama, A comparative study on the social networks of fictional characters, presented as a poster at the NetSci High: International High School Student Poster Competition on Network Science, in NetSci 2011: International School and Conference on Network Science, June 6-10, 2011, Budapest, Hungary.
• Hiroki Sayama, Computational approaches to adaptive network modeling, invited talk at the Adaptive Network Dynamics minisymposium in SIAM Conference on Applications of Dynamical Systems (DS11), Snowbird, UT, May 22-26, 2011.

Unpublished Notes

• Benjamin James Bush, Any N-state GNA can be simulated on a stateless GNA, 2013. PDF

Annual reports

• Project annual report 2010-2011
• Project annual report 2011-2012
• Project annual report 2012-2013
• Final report 2013-2014
  

Events

• STCAN 2010: Special Track on State-Topology Coevolution in Adaptive Networks. In the 5th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS 2010), Boston, MA, December 1-3, 2010.
• Adaptive Network Dynamics Mini-Symposium. In SIAM Conference on Applications of Dynamical Systems (DS11), Snowbird, UT, May 22-26, 2011.
• STCAN 2011: Workshop on State-Topology Coevolution in Adaptive Networks. In the Eighth International Conference on Complex Systems (ICCS 2011), Boston, MA, June 26-July 1, 2011.
• NetSci High: High School Student Research on Network Science
• NetSciEd Satellite Symposium at the 2012 International School and Conference on Network Science (NetSci 2012), Evanston, IL, June 18, 2012.
• Workshop on K-12 Science Education Outreach @ BU, Binghamton, NY, October 19, 2012.
• STCAN 2013: State-Topology Coevolution in Adaptive Networks. In NetSci 2013: International School and Conference on Network Science, Copenhagen, Denmark, June 3, 2013.
• NetSciEd2 Satellite Symposium. In NetSci 2013: International School and Conference on Network Science, Copenhagen, Denmark, June 3, 2013.
• NetSciEd3 Satellite Symposium. In NetSci 2014: International School and Conference on Network Science, Berkeley, CA, June 3, 2014.
• NetSciEd4 Satellite Symposium. In NetSci 2015: International School and Conference on Network Science, Zaragoza, Spain June 1, 2015.

Online Resources

• Adaptive Networks Wiki
• Further readings
  • [Book] Thilo Gross and Hiroki Sayama, eds., Adaptive Networks: Theory, Models and Applications, Springer/NECSI Studies on Complexity Series, Springer, 2009.
  • [Book Chapter] Hiroki Sayama and Craig Laramee, Generative network automata: A generalized framework for modeling adaptive network dynamics using graph rewritings, in T. Gross and H. Sayama, eds., Adaptive Networks: Theory, Models and Applications, Springer/NECSI Studies on Complexity Series, pp.311-332, Springer, 2009. Preprint available (arXiv:0901.0216)
  • [Proceedings] Hiroki Sayama, Generative network automata: A generalized framework for modeling complex dynamical systems with autonomously varying topologies, Proceedings of the First IEEE Symposium on Artificial Life (IEEE-CI-ALife '07), Honolulu, HI, 2007, IEEE, pp.214-221. PDF

Contact Us

Please address any inquiries about this project to:

Hiroki Sayama, D.Sc.
Director, Center for Collective Dynamics of Complex Systems
Associate Professor, Department of Systems Science and Industrial Engineering
Binghamton University, State University of New York
P.O. Box 6000, Binghamton, NY 13902-6000
Email: sayama@binghamton.edu
Tel: (607) 777-3566

© Copyright 2011-2015 Center for Collective Dynamics of Complex Systems, Binghamton University