Short course on Network Science for UCAS

  Last update: Fri Jun 21 12:01:31

   Course information

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

   Course Description

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).

   Class materials

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.

   Learning Objectives

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.

   Course Evaluation

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.

   Background required and some advice

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.

   Work in groups

  • 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.

Lectures Topic Notes Homework* Due date
slides 1 Fundamentals of Networks Sections 1-3 Questions 1-12 Wed Jun 19
slides 2 Game Theory Section 6 Questions 32,33 Wed Jun 19
slides 3r Strong/Weak Ties Section 6 Questions 14,16 Thu Jun 20
slides 4 Network Models Section 7 Question 43 Sat Jun 22
slides 5 Web/Oral exam Section 8 Q. 47 (group) Sat Jun 22

  * Hard or soft copy. Bring in class or email it to me.

  * Model solutions here (zip).

   Oral presentation/examination on Friday

  • 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

# Team Size Topic Leader
1 X-man 5 Game Theory 201818020428003
2 Newbie 5 Game Theory 2018E8015161024
3 Nintendo Switch 4 Game Theory 2018E8016061011
4 anonymous_1 3 Game Theory 201828013229047
5 Winter is coming! 5 Strong/Weak Ties 2018E8008661007
6 Strong Ties 5 Strong/Weak Ties 201818013229052
7 Mouse 5 Strong/Weak Ties 201828011230002
8 It doesn't matter 5 Strong/Weak Ties 201828007329016
9 fosari 5 Strong/Weak Ties 2018E8017761040
10 Strong trees 5 Strong/Weak Ties 201828007329011
11 BUT 4 Fundamentals of Networks 2018E8015061003
12 Anonymous_2 4 Fundamentals of Networks 201618013229003

  Last updated: Wednesday, 26 June 2019 Copyright © 2022 Barmpalias