Social Networks and Online Markets

Academic year 2023–2024

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 1 is out. It is due June 9.

For the second part of the course you need to register to Google classroom. Email Stefano Leonardi for details.

Remember to register your email; email Aris for details.

Classes start on Monday, February 26.

 

Topics that we will cover

  • Properties of social networks
  • Models for social networks
  • Community detection
  • Spectral techniques for community detection
  • Cascading behavior in social networks and epidemics
  • Influence maximization and viral marketing
  • Influence and homophily
  • Opinion dynamics
  • Machine learning on graphs
  • Introduction to Game Theory and Computational issues
  • Price of Anarchy and Selfish Routing
  • Stable matching, Markets, Competitive equilibria
  • Sponsored Search Auctions, VCG, Revenue Maximization
  • Voting and Fair division
  • Equilibria and Incentives in blockchains and cryptocurrencies

 

Instructors

Aris Anagnostopoulos, Sapienza University of Rome

Aristides Gionis, KTH Royal Institute of Technology

Stefano Leonardi, Sapienza University of Rome

 

When and where:

Monday 15.00–17.00, Via Ariosto 25, Room A5

Wednesday 12.00–16.00, Via Ariosto 25, Room A7

 

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 for the first part is the book Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by David Easley and Jon Kleinberg.

The main textbook for the second part is the book Twenty Lectures on Algorithmic Game Theory, by Tim Roughgarden.

In addition, we will cover material from various other sources, which we will post online as the course proceeds.

 

Evaluation format

You will be evaluated for the two parts of the course (social networks, online markets) independently from each other, and your grade will be the average of the two parts.

For the part of social networks, there will be (1) an individual homework (deadline in the first week of June), (2) a small project that can be done in groups of at most two people (deadline 4 working days before the date that you try the oral exam), and (3) a light oral exam.

For the part of online markets, Stefano Leonardi will provide more details.

Alternatively, there is also the option of a written exam for both parts.

 

Syllabus

Date Topic Reading
February 26 Introduction to social networks and online markets, Properties of complex networks. Chapters 1, 2, slides
February 28 Properties of social networks, tie strength, homophily, triadic closure, affiliation networks Chapters 3–3.1, 4–4.3, slides, notes
March 4 Modeling phenomena and social networks, the Erdős–Rényi random-graph model Notes
March 6 The preferential attachment model, Epidemics and influence Notes, slides
March 11 Models of influence, influcence maximization in social networks Paper by D. Kempe, J. Kleinberg, and E. Tardos, slides
March 13 Social influence vs. social correlation, the densest subgraph problem Chapter 8.4 of the book Social Media Mining by R. Zafarani, M. Ali Abbasi, and H. Liu, slides on influce vs. correlation, notes on Charikar's greedy algorithm on densest sugraph
March 18 Community detection and sparsest cut Notes on spectral graph theory.
March 20 Community detection and sparsest cut (cont.)
March 25 Node embeddings based on random walks, introduction to neural networks Chapter 3.3.0 of Graph Representation Learning by Hamilton, papers on DeepWalk and node2vec; for NNs there are various sources online, for example, Chapter 6 of Deep Learning by Goodfellow, et al.
March 27 Graph neural networks There are a lot of resources on GNNs. I linke the chapter of The Science of Deep Learning by Drori, however it is not available online. A starting point could be this video although it does not talk about the concept of computation graph.
April 3 Opinion formation in social network Slides on opinion formation.
April 8 Signed networks Slides on signed networks.
April 10 Temporal networks Slides on temporal networks.

Homeworks

 

Collaboration policy (read carefully!): You can discuss with other students of the course about 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 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.
The same applies for generative AI tools, such as ChatGPT. These can be useful tools in your work and there are some homework questions in which we ask you explicitly to use them. However, the use of such tools when it is not explicitly allowed will be treated as plagiarism and is strictly prohibited.