Title: Network Science

Lecturer: George Barmpalias (from the Institute of Software, CAS)

Dates and Times: Monday 17 June to Friday 21 June, 13:30 - 17:10

Location: Computer Science and Technology School; Room 1-009

Scientists have been studying networks in some form or another for many years. In the last thirty years or so, however, various developments have seen network science rise to prominence. Today an interdisciplinary community of researchers in universities and tech companies such as Google, Microsoft and Facebook are busy applying techniques from mathematics, physics, computer science, economics and other social sciences in an intensive effort to understand the structure and functioning of the multitude of networks which help shape the world around us. Globalisation and the growth of the Internet have certainly highlighted the need to understand network structures and the way in which things like information and goods flow around them. At the same time, the digital revolution has suddenly meant that a wealth of data is available, ready to be put to use in the study of these giant network structures. Whereas fifty years ago social scientists studying networks of personal contacts might have to restrict themselves to observing contacts between a small collection of tens or possibly a few hundred people, nowadays Facebook records the interactions of over one billion users in real time.

The aim of this course is to give an introduction to this new and exciting area, and to equip students with the tools they will need in order to carry on and persue research in the field should they choose to. We will focus on the science and dynamics of networks (social, technological etc.) and the mathematical or game-theoretic analysis of conflict in them. Given the short duration of the course, the content will be of varried mathematical depth (part is expositional while in some places rigorous mathematical arguments will be carried out).

Main: The Course notes draw topics from a few books but mainly the textbook below.

Textbook: Networks, Crowds, and Markets, by David Easley and Jon Kleinberg

Exercises: Many problems can be found in the notes, whose solutions will be given online at the end of the course (some will be given as assignments).

More resources: Articles, datasets, software...

Additional reading: Barabasi's book.

You will learn about random networks, giant components, generating small-world networks and investigating their properties, scale-free networks, epidemics on networks.

Game-theoretic topics include pure and mixed strategies, and Nash equilibria.

Given the tight schedule of 5 days of lectures, we may be selective on the topics.

I aim at covering at least sections 1-7 from the notes.

Take-home assignments (60%) + oral examination (40%)

Students are expected to work creatively towards understanding the material and completing the assignments, as well as interacting with the course topics during the classes.

You should be able to carry out a rigorous mathematical argument. Hopefully you have an interest in probability, games and can count. You know what a mathematical proof is and have performed some in the past.

Background in linear algebra or algorithms and their analysis would be useful. We will not have time to use software in the class for the analysis of networks (so if you can't code, that's fine) but interestred students will be pointed to relevant resources.

No need to copy the slides durinng class -- this will be made available for download after each class.

Instead, pay attention to what is discussed and try to engage with the class -- questions are welcome.

• Class is divided into groups of around 4 or 5 students.

• Why? Because you can discuss and confirm solutions with others, avoiding mistakes.

• You are encouraged to discuss the class and assignment problems in the group.

• You could split the assignment questions withing the group if you like, but joint work might be safer.

• Each student should produce their own write-up, although solutions may have been obtained in the group.

• Each group should pick one of the sections 3-7 as a topic

• Please talk to me before deciding your target section

• On Friday each group will give a presentation on some topics from their section

• The choice of topics in the chosen section will be random (conducted by me)

• The member of the group presenting each topic will also be random

• So each member of each group should master all the topics in the chosen section