Time/place:

- Tuesdays: 12:10 -- 13:00.
- 7 Bristo square, Lecture theatre 2.
- Fridays: 12:10 -- 13:00.
- 1 George square, G.8 Gaddum LT.

Lecturer: Dr. Rik Sarkar

### Announcements:

- Exercise 1 and sample problems:Do these as a preparation for the course and to test your background.
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

- Introduction: Motivation and overview the course
- 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

### Main Books and reading (available online):

David Kempe - Structure and dynamics of information in networks

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

#### Additional Books:

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

Mark Newman - Networks, an Introduction

- Philip S. Yu, Jiawei Han, Christos Faloutsos - Link mining: Models, applications and algorithms

### Resources

- Notes on 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

#### Similar and relevant courses at other universities

- 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

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