Social and Technological Networks

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

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.

Announcements:

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: https://piazza.com/ed.ac.uk/fall2015/infr11124

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

Project

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

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

Lectures

1. Introduction

   • Class Slides

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

   • Notebook code from class

   • 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

2. Random graphs and graph properties

   • Slides

   • Lecture notes || solutions to exercises

   • Notebook code

   • Reading:
     • Kleinberg’s notes on random graphs

3. Random graphs continued

   • Slides

   • Lecture notes || solutions of exercises

   • Reading
     • Kleinberg’s notes on random graphs

4. Power law networks

   • Slides

   • Lecture notes || solutions of exercises

   • Notebook code

   • Reading:
     • Kempe 2011 – Chapter 6, Beginning to Sec 6.1
     • Kleinberg & Easley 2010 – Chapter 18
   • Additional readings.
     • Rest of [Kempe 2011, Chapter 6].
     • Graphs over time.
     • Mean field theory of complex networks.
     • Power law relationships of Internet topology.
     • Brief history of generative models for power law and log-normal distributions

5. Small World models: Combined with 6 below

6. Small world models:

   • Slides

   • Lecture notes

   • 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
     • Complex networks and decentralized search
     • The Small-World Phenomenon: An Algorithmic Perspective
     • Distributed compact routing using spatial distributions
     • Power of lookahead in randomized p2p networks

7. Web graphs: Ranking pages
   • Slides
   • Notebook code || pdf version
   • Lecture notes
   • Reading
     • Kleinberg & Easley 2010 – Chapter 13 & 14.
   • Additional reading:
     • Network of global corporate control. Vitali et al.

8. Spectral analysis of ranking algorithms

   • Slides

   • Lecture notes

   • Reading
     • Kleinberg & Easley 2010 Chapter 14 (including advanced material)
   • Additional reading:
     • Kempe 2011. Chapter 2.
     • Perron’s theorem on wikipedia
     • Topic sensitive pagerank
     • Making eigen vector based reputation systems robust to collusion

9. Spectral graph theory

   • Slides

   • Lecture notes

   • Notebook code || pdf version

   • Reading

     *

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

11. Community detection
    • Slides
    • Lecture notes
    • Reading
      • Kempe 2011 Chapter 3. Upto Sec. 3.5.2.
    • Additional reading
      • Newman: Fast clustering for detecting community
      • Bansal: Correlation clustering

12. 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
      • Luxburg: Tutorial on spectral clustering

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

14. Submodular optimization continued
    • Slides
      • Slides 20 onward not in exam
    • No lecture notes
    • Reading
      • Maximizing spread of influence

15. Epidemics, and gossip algorithms
    • Slides
    • No Lecture notes
    • Reading
      • Kleinberg & Easley 2010 Chapter 21.
    • Additional reading
      • Kleinberg & Easley 2010 Chapter 21: Additional materials.

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

17. Internet curvature, friendship paradox and dispersion
    • Slides
      • Note: Upto slide 11 not in exam
    • Reading
      • Romantic partnerships and dispersion of ties

18. Conclusion
    • Slides

Main Books and reading (available online):

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

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

Additional Books:

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

Resources

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