Time/place:

- Tuesdays: 12:10 -- 13:00. Lister Learning and teaching Centre, 5 Roxburgh Place. Room G1.
- Fridays: 12:10 -- 13:00. 7 George Square. Room F21.

Lecturer: Dr. Rik Sarkar

Office Hours: Thursdays 1:30 -- 2:15. IF 3.45.

Monday 12th Nov. 14:00 -- 15:30.

### Announcements:

**Special office hours Monday 12th. 14:00 -- 15:30.****No class on Tuesday Nov 13.**Notes 5 on community detection are out.

Solutions to notes 3 and 4 are out.

Guideline for writing Project plan.

No class on Tuesday 16th october.

Project list is out. See Piazza and email.

Notes 4 are out.

Solutions to notes 1 are up.

Notes and questions on metric spaces are up. Read them before Friday 5th.

Piazza Forum at: http://piazza.com/ed.ac.uk/fall2018/infr11124/

Notes with exercises for random graphs.

Solutions are up for Exercise 0 on Exercises page. Check that you are aready for the course.

Background preparation questions are up at Exercise 0 on Exercises page.

First class is on Tuesday, September 18 at Lister teaching and learning center. See you there!

**Introduction:** The aim of the course is to learn computational and mathematical techniques for network analysis, and apply those ideas to real networks. We will also study some recent developments and research in this area.

Networks are ubiquitous -- from social networks and computer networks, to networks of roads, power grids, chemicals, biological elements etc. We will study fundamental concepts and algorithms that are relevant to many different types of network systems.

We will also see how networks can be constructued from general datasets, and network analysis can be applied to other types of data. The course will have a small coursework project, where you can be creative and try out original, crazy ideas!

**Update: New in 2018: Relations to machine learning.**

### Preliminary Topic List

- Introduction: Motivation and overview the course
- Community detection & Clustering
- Metric spaces and networks. Creating networks from arbitrary data
- Embedding of networks, relations to machine learning
- Pagerank, HITS & structure of the web
- Finding influential people
- 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
- Spectral graph theory and applications
- Cascades and epidemics
- Other current topics

These topics will be updated as we go. If there are specific topics you would like discussed, talk to the lecturer.

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

See Last Year's web page for some typical content, but as explained above, we will have some new exciting topics this year.

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

#### Similar and relevant courses at other universities

- Cornell - https://courses.cit.cornell.edu/info2040_2017fa/
- USC - http://www-bcf.usc.edu/~dkempe/CS673/index.html
- Stanford - http://web.stanford.edu/class/cs224w/

### 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 with official descriptor of the course.