CS4980:001: Peer-to-peer and Social Networks
Fall 2017


Sukumar Ghosh, 201P Maclean Hall, 319-335-0738, sukumar-ghosh@uiowa.edu
Class meeting time: 1:30-2:20PM MWF 113 MLH (3 sh)
Office hours: 2:30-3:45 PM Mondays and Fridays, or by appointment

Teaching Assistant

Ruoyu Zhang, ruoyu zhang@uiowa.edu


There is no required textbook. Good reference books in social networks are
[1] Albert-Laszlo Barabasi: Linked: How Everything Is Connected to Everything Else and What It Means. Perseus publishing (2002)
[2] David Easley, Jon Kleinberg: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010 [A pre-publication draft is available for free download here )
[3] Mark Newman: Networks: An Introduction. Oxford University Press, 2010
[4] Matthew Russel: Mining the Social Web (2nd Ed.] Orielly Media, 2013

For peer-to-peer networks, here is a list of papers. The list will be updated from time to time. This list also contains a few articles on social networks.`

Course Outline

Attempts to understand how social networks evolve and to quantify their characteristics started some fifty years ago. Since then, much work has been done to measure, classify and derive important properties of these networks. These include structural properties like random topology, power-law topology and small-world networks, connectedness, community structure in networks, various centrality measures, and social network analysis. Comparatively, Peer-to-Peer (P2P) systems are a more recent development in Internet information systems. The major focus is to see how a meaningful distributed system can be built by the millions of machines at the edges of the Internet without the help of a distinguished node like a central server. Important applications include file sharing, searching, storage, streaming, multicast, publish-subscribe etc. Topics will include:

Introduction to Social and P2P networks
Evolution of Networks: Random graphs, power-law graphs, small-world graphs
Various centrality measures, Communities and Community detection, influence spreading
Historic first generation P2P networks: Napster, Gnutella
Unstructured vs. DHT-based structured networks
KaZaA, Chord, CAN, Pastry, BitTorrent, Kademlia, Skip graph
Self-organization, routing, replication, storage, security, selfishness
Blockchain and BitCoin
P2P Services: Uber, AirBnB, Spotify
P2P Content Distribution

Tests and assignments

Two quizzes (20%), two assignments (20%), a project (40%) one class presentation (10%), and attendance and participation (10%); There is no final examination. Project topics will be posted during the third week of classes.

Quiz 1: Monday, September 25, 2017 (in class: duration 30 mins)
Quiz 2: Monday November 6, 2017 (in class: duration 30 mins)

Letter grades will be tentatively assigned roughly as follows:

A+ = 95-100             B+ = 80-84              C+ = 65-69              D+ = 50-54
A  = 90-94              B  = 75-79              C  = 60-64              D  = 45-49
A- = 85-89              B- = 70-74              C- = 55-59              D- = 40-44
F = 0-39

The instructor reserves the right to make minor modifications in the grading scale.

Course webpage http://www.cs.uiowa.edu/~ghosh/19617.html

Assignments will also be posted on ICON/CANVAS, and completed assignments must be submitted via CANVAS. Late assignments will not be accepted without prior approval.

Lecture Notes

August 21-25, 2017
Week 1. Introduction to Social and P2P Networks and Random graphs
August 28-September 1, 2017
Week 2. Powerlaw graphs and Small world graphs
September 4-9, 2017
Week 3. Algorithms for Content Delivery Networks
September 11-15, 2017
Week 4. P2P Network Gnutella and KaZaA
Read paper number 3 from the reading list
September 18-22, 2017
Week 5. The Chord Network
Read paper number 1 from the reading list
Advanced Issues Read the technical report under [1]
September 25-29, 2017
Week 6. Plaxton Routing
Read paper number 5 from the reading list
Tapestry Read paper number 22 from the reading list
Notes on Self-stabilization
October 9-13, 2017
Week 8. Skip List & Skip Graph
October 16-20, 2017
Week 9. Kademlia
October 16-20, 2017
Week 10. Revisiting BitTorrent , Video distribution on the Internet
October 23-27, 2017
Week 11. Centrality measures and community detection in Social Networks
October 30-November 3, 2017
Week 12. Strength of Weak Ties
Structural Balance
Introduction to Game Theory
November 13-17, 2017
Week 13. Network Creation Game
Koorde: A degree optimal DHT
November 27-30, 2017
Week 14. Byzantine Generals Problem