81943 - Complex Systems & Network Science

Learning outcomes

At the end of the course, the student has basic notions of complexity and network sciences and is able to identify, formulate, model and analyze new problems that arise in modern computing systems that can be studied using them.

Course contents

Description: Modern information systems and services often rely on large numbers of independent interacting components to provide their functions. Under certain conditions, the behavior that results from these interactions can be unexpected and surprising. Complexity Science is an interdisciplinary field for studying global behaviors resulting from many simple local interactions in an effort to characterize and control them. Networks allow us to formalize the structure of interactions. They play a central role in the transmission of information, transportation of goods, spread of diseases, diffusion of innovation, formation of opinions and adoption of new technologies. Network Science is an interdisciplinary field for studying the interconnectedness of modern life by exploring fundamental properties that govern the structure and dynamic evolution of networks.

Contents: Complex systems: definitions, methodologies; Dynamical systems, Nonlinear dynamics; Chaos, Bifurcations and Feigenbaum constant, Predictability, Randomness and Chaos; Models of complex systems, Cellular automata, Wolfram's classification, Game of life; Autonomous agents, Flocking, Schooling, Synchronization, Formation creation; Cooperation and Competition, Game theory basics, Nash equilibrium; Game theory: Prisoner's Dilemma, Coordination games, Mixed strategy games; Adaptation, Evolution, Genetic algorithms, Evolutionary games; Network Science: Definitions and examples; Graph theory, Basic concepts and definitions; Diameter, Path length, Clustering, Centrality metrics; Structure of real networks, Degree distribution, Power-laws, Popularity; Models of network formation; The Erdos-Renyi random model; Clustered models; Models of network growth, Preferential attachment; Small-world networks, Network navigation; Peer-to-peer systems and overlay networks; Structured overlays, DHTs, Key-based routing, Chord; Distributed network formation: Newscast, Cyclon, T-Man; Processes on networks: Aggregation; Rational dynamics: Cooperation in selfish environments, Homophily, Segregation; Diffusion, Percolation, Tipping points, Peer-effects, Cascades.

Prerequisites: Basic notions of computer system architecture, computer networks, operating systems, and probability theory.

Readings/Bibliography

1. Networks, Crowds, and Markets: Reasoning about a Highly Connected World, D. Easley, J. Kleinberg. Cambridge University Press, 2010.
2. Graph Theory and Complex Networks: An Introduction, M. van Steen. 2010.
3. The Computational Beauty of Nature, G. W. Flake. MIT Press, Cambridge MA. 2000
4. Complex Adaptive Systems: An Introduction to Computational Models of Social Life, J. H. Miller, S. E. Page. Princeton University Press, 2007.

Teaching methods

The course will be delivered according to the "blended" model where lessons can be followed either in person or online through MS Teams.  The number of students that can be present in person is limited by classroom capacity and the health and safety regulations due to the pandemic.  To follow the lectures in person, you must reserve your seat one week in advance through the site presente.  In any case, the entire course can be followed online through MS Teams.

Assessment methods

Evaluation will be through the development of a project and an oral exam. The project aims to evaluate the student's basic understanding and practical skills. The oral exam consists of the student presenting a research paper and discussing how it relates to the topics covered in the course.

Teaching tools

Teaching material: Copies of slides used during certain lectures will be made available for downloading and printing through the course web site before each lecture.

Links to further information

http://www.cs.unibo.it/babaoglu/courses/csns/

Office hours

See the website of Ozalp Babaoglu

See the website of Angelo Trotta