81943 - Complex Systems & Network Science

Learning outcomes

At the end of the course, the student will have acquired the basic notions of complexity as it arises through interactions among simple agents in nature and in modern computing systems. The student will be able to identify, formulate, model and analyze new problems using the mathematical framework of dynamical systems and network science.

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 in classroom with students attending lectures exclusively in person.

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