Social and Technological Networks

University of Edinburgh. Autumn 2017. Level: Year4/5/Msc/CDT.


Lecturer: Dr. Rik Sarkar

Office Hours: Wenesdays 12:00 -- 13:00.

Extra office hours:


  1. Ex 3 and exam guide are up on Exercises page
  2. No class in week 9: Nov 14 and Nov 17.
  3. Solutions to Ex 2 are up here.
  4. Proposal feedbacks are on Piazza.
  5. Project plan/proposal guidelines are up here.
  6. Exercise 2 is up here.
  7. Piazza Forum is up at:
  8. Solutions to Exercise 1: sample problems. Check your solutions ideas and writing.
  9. Exercise 1 and sample problems:Do these as a preparation for the course and to test your background.
  10. First class is on Tuesday, September 19. See you there!

Introduction: Networks represent relations or connections between entities. They are relevant in science, engineering, society, humanitires, and in almost every area. Examples include Social networks, internet, world-wide-web, search engines, biochemical reaction networks, road networks, power grid, etc. Analysis of networks is currently a fast developing topic. This course covers some of the mathematical and computational foundations for understanding networks. It also studies some recent developments and research in this area.

The aim of the course is to teach basic techniques for analyzing networks, designing and analyzing network algorithms and presenting your understanding in a formal way.

Pre-requisites Understanding (undergraduate level) of graphs, data structures, basic algorithms (spanning trees, BFS, DFS, sorting etc), Linear algebra, and probability. Programming is highly recommended for the coursework.

See the DRPS page. for the official descriptor. Last Year's web page for typical content.

Preliminary Topic List

  1. Introduction: Motivation and overview the course
  2. Strong and weak ties, triadic closure, betweenness measures
  3. Definitions and properties of Random graphs, growth
  4. Power Law networks and Preferential attachment model
  5. Small world models
  6. Pagerank, HITS & structure of the web
  7. Spectral graph theory and applications
  8. Community detection & Clustering
  9. Cascades and epidemics
  10. Influence maximization
  11. Other current topics

Main Books and reading (available online):

Additional Books:


Similar and relevant courses at other universities

Last Year's web page

Course Structure

Final theory exam: 60% of marks. One Project 40% of marks. The project is an opportunity to develop or try something new in network science. It will consist of using programming or mathematical tools to analyze a network dataset or model.

FEEDBACK: Assignment scores and comments on deduction of marks will be given for the project. Exercise theoretical problems and solutions will be given in class. Please attempt these as they are posted and use them to test your understanding and your precision in writing analytic answers.

DRPS page of the course.