Time/place:

- Tuesdays, 14:10 - 15:00, Appleton Tower,
**Lecture Theatre 4** - Fridays, 14:10 - 15:00, Appleton Tower,
**Lecture Theatre 2**

Lecturer: Dr. Rik Sarkar

- Office hours: Wednesdays 1:30.

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.

**Revision class: Monday 18 April, 9AM, LG11, David Hume Tower****Some sample questions are available. See email.**No class on Tuesday 24. Final class on Friday 27.*

Final Project submission instructions and tips are here

Solutions to Lecture 3 & 4 are up.

Instructions for project plan/proposal: here

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

Please join the Piazza forum: https://piazza.com/ed.ac.uk/fall2015/infr11124

Projects are out! See your email.

No class on Friday 23rd

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

First class is on Tuesday, September 22

- Final deadline: Nov 25, 4pm.
- Deadline for project proposal: Nov 5.
- Instructions for proposal here
- Final project submission instructions here

- Introduction: Network analysis, simple examples
- Strong and weak ties, triadic closure, betweenness measures
- Definitions and properties of Random graphs, growth
- Power Law networks and Preferential attachment model
- Small world models
- Pagerank, HITS & structure of the web
- Spectral graph theory and applications
- Community detection & Clustering
- Cascades and epidemics
- Influence maximization
- Other current topics

- Introduction
Class Slides

Lecture notes: Basic definitions and exercises || solutions to exercises

- Reading.
- David Easley, Jon Kleinberg - Networks, Crowds and Markets. Chapter [1 and 2]

Test your background: Read Chapter 2 or chapter 7 of David Kempe - Structure and dynamics of information in networks and see that you are comfortable with it.

Sample problems to test your background.. Solutions to sample problems

- Random graphs and graph properties
- Random graphs continued
- Power law networks
- Reading:
- Kempe 2011 – Chapter 6, Beginning to Sec 6.1
- Kleinberg & Easley 2010 – Chapter 18

- Additional readings.

Small World models: Combined with 6 below

- Small world models:
- Reading
- Collective Dynamics of Smalls world networks (accessible from university network or vpn)
- Navigation in a small world (accessible from university network or vpn)
- Kempe 2011 Chapter 7.
- Kleinberg & Easley 2010 – Chapter 20.

- Additional readings

- Web graphs: Ranking pages
- Slides
- Notebook code || pdf version
- Lecture notes
- Reading
- Kleinberg & Easley 2010 – Chapter 13 & 14.

- Additional reading:

- Spectral analysis of ranking algorithms
- Reading
- Kleinberg & Easley 2010 Chapter 14 (including advanced material)

- Additional reading:

- Spectral graph theory
- Reading
*

- Strong and weak ties, social capital, betweenness, and homophily
- Slides
- No Lecture notes.
- Reading
- Kleinberg & Easley 2010 Chapter 3 (including advanced material), Chapter 4, upto Sec 4.4.
- Tie strength in mobile nets

- Additional reading.
- Rest of Kleinberg & Easley 2010 Chapter 4
- Granovetter, Strength of Weak ties

- Community detection
- Slides
- Lecture notes
- Reading
- Kempe 2011 Chapter 3. Upto Sec. 3.5.2.

- Additional reading

- Community detection and cascades
- Slides
- No Lecture notes
- Reading
- Spectral and other clustering slides by Leskovec
- AGM slides by leskovec
- Kleinberg & Easley 2010 Chapter 19: cascades.

- Additional reading

- Submodular optimization: Influence maximization
- Slides
- No Lecture notes
- Reading
- Kleinberg & Easley 2010 Chapter 19.
- Maximizing spread of influence
- Kempe 2011 Chapter 8.6

- Additional reading
- Rest of Kempe 2011 Chapter 8.

- Submodular optimization continued
- Slides
- Slides 20 onward not in exam

- No lecture notes
- Reading

- Slides
- Epidemics, and gossip algorithms
- Slides
- No Lecture notes
- Reading
- Kleinberg & Easley 2010 Chapter 21.

- Additional reading
- Kleinberg & Easley 2010 Chapter 21: Additional materials.

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

- Slides
- Internet curvature, friendship paradox and dispersion
- Slides
- Note: Upto slide 11 not in exam

- Reading

- Slides
- Conclusion

David Kempe - Structure and dynamics of information in networks

Jure Leskovec, Anand Rajaraman, Jeff Ullman - Mining of massive datasets

Recent papers. These will be given along with relevant lecture materials.

- Mark Newman - Networks, an Introduction
- Philip S. Yu, Jiawei Han, Christos Faloutsos - Link mining: Models, applications and algorithms

- Setting up networkx and IPython notebook in your DICE account
- NetworkX - Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks
- SNAP - complex network database
- Gephi - software package for visualization and analysis of graphs
- NetLogo - agent programming environment

- Cornell - http://www.cs.cornell.edu/Courses/cs6850/2013fa/
- USC - http://www-bcf.usc.edu/~dkempe/CS673/index.html
- Stanford - http://snap.stanford.edu/class/cs224w–2013/index.html

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.