Social and Technological Networks

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


Lecturer: Dr. Rik Sarkar

Network analysis comes up in many domains and 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 are: Understanding (undergraduate level) of graphs, data structures, basic algorithms (spanning trees, BFS, DFS, sorting etc), Linear algebra, and probability.


  1. Revision class: Monday 18 April, 9AM, LG11, David Hume Tower

  2. Some sample questions are available. See email.

  3. No class on Tuesday 24. Final class on Friday 27.*

  4. Final Project submission instructions and tips are here

  5. Solutions to Lecture 3 & 4 are up.

  6. Instructions for project plan/proposal: here

  7. Lecture notes for Lectures 5 and 6: Small worlds, is online (see below).

  8. Please join the Piazza forum:

  9. Projects are out! See your email.

  10. No class on Friday 23rd

  11. Preliminary sample problems: here. Solutions: here

  12. In Lecture 2 we will prove properties of random graphs. Please bring pen and paper to take notes.

  13. First class is on Tuesday, September 22


Topic List

  1. Introduction: Network analysis, simple examples
  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


  1. Introduction

  2. Random graphs and graph properties
  3. Random graphs continued
  4. Power law networks
  5. Small World models: Combined with 6 below

  6. Small world models:
  7. Web graphs: Ranking pages

  8. Spectral analysis of ranking algorithms
  9. Spectral graph theory
  10. Strong and weak ties, social capital, betweenness, and homophily

  11. Community detection

  12. Community detection and cascades

  13. Submodular optimization: Influence maximization

  14. Submodular optimization continued

  15. Epidemics, and gossip algorithms

  16. Network curvature and structure of the internet
    • Slides
      • Note: Slide 16 and onward not in exam

  17. Internet curvature, friendship paradox and dispersion

  18. Conclusion

Main Books and reading (available online):

Additional Books:


Similar and relevant courses at other universities

Course Structure

Final theory exam: 60% of marks. One Project 40% of marks. The project will consist of using programming and existing network analysis tools, develop and implement algorithms, perform analysis on networks etc.

FEEDBACK: Assignment scores and comments on deduction of marks. Exercise theoretical problems and solutions will be given in class. Please use these to test your understanding and your precision in writing analytic answers.

DRPS page of the course.