Social Networks and Online Markets
Academic year 2019–2020
We are surrounded by networks. The Internet, one of the most advanced artifacts ever created by mankind, is the paradigmatic example of a "network of networks" with unprecedented technological, economical and social ramifications. Online social networks have become a major driving phenomenon on the web since the Internet has expanded as to include users and their social systems in its description and operation. Technological networks such as the cellular phone network or the energy grid support many aspects of our daily life. Moreover, there is a growing number of highly-popular user-centric applications in Internet that rely on social networks for mining and filtering information, for providing recommendations, as well as for ranking of documents and services. In this course we will present the design principles and the main structural properties and theoretical models of online social networks and technological networks, algorithms for data mining in social networks, and the basic network economic issues, with an eye towards the current research issues in the area.
Announcements
Homework 3 is out; it is due on June 14.
Homework 2 is out; it is due on June 7.
Homework 1 is out; it is due on May 3.
Because of COVID-19, courses are being performed online. Email the instructors for information about how to get access to oniine lectures.
Remember to register your email; details will be given in class.
Topics that we will cover
- Properties of social networks
- Models for social networks
- Community detection
- Spectral techniques for community detection
- Centrality measures
- Deep learning and network embeddings
- Cascading behavior in social networks and epidemics
- Influence maximization and viral marketing
- Influence and homophily
- Game theory on networks
- Network traffic
- Selfish routing and price of anarchy
- Auctions
- Algorithmic market design
- Market Equilibria: characterization and computation
- Two-sided markets and sharing economy
- Homework 1 (due: 3/5/2020, 23.59)
- Homework 2 (due: 7/6/2020, 23.59)
- Homework 3 (due: 14/6/2020, 23.59)
Instructors
Aris Anagnostopoulos, Sapienza University of Rome
Chris Schwiegelshohn, Sapienza University of Rome
Georgios Amanatidis, Sapienza University of Rome
When and where:
Monday 14.00–17.00, Via Ariosto 25, Room A5
Thursday 17.00–19.00, Via Ariosto 25, Room A5
Office hours
You can use the office hours for any question regarding the class material, general questions on networks, the meaning of life, pretty much anything. Send an email to the instructors for arrangement.
Textbook and references
The main textbook is the book Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by David Easley and Jon Kleinberg.
In addition, we will cover material from various other sources, which we will post online as the course proceeds.
Exam format
The evaluation has two parts: a set of three theoretical homeworks, which will be due during the semester, and a final project, or a final presentation. During the exam period we will assess the quality of the projects and the extent you have learned the class material. Students are highly encouraged to do the homeworks. Whoever does not do the homeworks will have to do a final written exam on the entire class material and a final project. In this case as well we will have an oral exam during the exam session.
Syllabus
Date | Topic | Reading |
February 24 | Introduction to social networks and online markets. | Chapters 1, 2, slides |
February 27 | Properties of social and complex networks, tie strength. | Chapter 3, slides |
March 2 | Tie strength (cont.), affiliation networks | Chapter 4 |
March 12 | Random-graph models for social networks | Notes |
March 16 | Epidemics and COVID-19 | |
March 19 | The Small-World model for SN, containment of COVID-19 | |
March 23 | Introduction to Community Detection, densest Subgraph | |
March 26 | Basics of Graph Clustering and linear algebra | |
March 30 | The Barabassi Albert preferential attachment model | |
April 3 | Introduction to the Graph Laplacian | |
April 6 | Cheeger's inequality | |
April 16 |
Spectral clustering | |
April 20 | LP-based approximation for sparsest cut | |
April 23 | Bourgain's theorem | |
April 27 | MAX Cut - SDP approximation | |
April 30 | Applications of community detection | |
May 4 | Introduction to neural networks and word2vec | |
May 7 | Neural network graph embeddings | |
May 11 | Introduction to game theory | Slides and slides |
May 14 | Equilibria and inefficiency | Slides |
May 18 | Introduction to mechanism design | Slides |
May 21 | Sponsored-search auctions | Slides |
May 25 | Matching markets | |
May 28 | Network models of markets with intermediaries |
Homeworks
Collaboration policy (read carefully!): You can discuss with other students of the course about the homeworks and the projects. However, you must understand well your solutions and the final writeup must be yours and written in isolation. In addition, even though you may discuss about how you could implement an algorithm, what type of libraries to use, and so on, the final code must be yours. You may also consult the internet for information, as long as it does not reveal the solution. If a question asks you to design and implement an algorithm for a problem, it's fine if you find information about how to resolve a problem with character encoding, for example, but it is not fine if you search for the code or the algorithm for the problem you are being asked. For the homeworks and projects, you can talk with other students of the course about questions on the programming language, libraries, some API issue, and so on, but both the solutions and the programming must be yours. If we find out that you have violated the policy and you have copied in any way you will automatically fail. If you have any doubts about whether something is allowed or not, ask the instructor.