Social and Technological Networks

Time/place:

• Tuesdays & Fridays: 12:10 -- 13:00.
• 7 Bristo square, Lecture theatre 2.
• Office hours: Wednesdays, 15:30. IF 3.45.

Lecturer: Dr. Rik Sarkar

Announcements:

1. Submission instruction and tips are up on
2. Projects page.
3. Office hours Friday Nov 11, 3pm -- 5pm.
4. Exercises 3 and solutions to exercises 2 are online.
5. Project plan submission instrcutions are up on Project page.
6. No Class on Tuesday 11 and Friday 14 October.
7. Project topics have been given out. Deadline Oct 14.
8. Please sign up on the Piazza Forum
9. Solutions to sample problems are up. Check your soilutions and rigor of your technical presentation.

10. Second class: Deduce properties of Random Graphs. Bring pen and paper to take notes!

11. Preliminary Sample problems are up. Check that you have the background for the course.

12. First class is on Tuesday, September 20. See you there!

Introduction: Networks represent relations or connections between entities. They are relevant in science, engineering, society, humanitires, and in any 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.

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):

• David Easley, Jon Kleinberg - Networks, Crowds and Markets.

• David Kempe - Structure and dynamics of information in networks

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

Additional Books:

• Albert Laszlo Barabasi - Network Science

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