Social Networks and Online Markets

Academic year 2021–2022

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

The first homework is out; it is due on May 22.

You can follow the class online, using zoom. For that you need to register; email Aris for details.

Classes start on Monday, February 21.

Remember to register your email; details will be given in the first class.

 

Topics that we will cover

  • Properties of social networks
  • Models for social networks
  • Community detection
  • Spectral techniques for community detection
  • Neural-network embeddings
  • Graph neural networks
  • 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
  •  

    Instructors

    Aris Anagnostopoulos, Sapienza University of Rome

    Stefano Leonardi, Sapienza University of Rome

     

    When and where:

    Monday 15.00–17.00, SPV, Via Eudossiana 18, Room 41

    Wednesday 13.00–17.00, Via Ariosto 25, Room A3

     

    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

    There are two main ways to be examined for the course (to be confirmed after the first classes):

    • Do two set of homeworks and a light oral exam
    • Do a project and a heavier oral exam
    There is also the option to write a final written exam (but discouraged).

     

     

    Syllabus

    Date Topic Reading
    February 21 Introduction to social networks and online markets, Properties of complex networks. Chapters 1, 2, slides
    February 23 Properties of complex networks (cont.), Tie strength Chapters 3.1, 4.1, notes
    February 28 Affiliation networks, the Erdős–Rényi random-graph model Chapter 4.3, notes
    March 7 The Erdős–Rényi random-graph model (cont.), the preferential attachment model notes
    March 9 The preferential attachment model (cont.), Epidemics and influence slides
    March 14 Influence vs. correlation in social networks Chapter 8.4 of the book Social Media Mining by R. Zafarani, M. Ali Abbasi, and H. Liu, slides
    March 16 Models of influence, influcence maximization in social networks Paper by D. Kempe, J. Kleinberg, and E. Tardos, slides
    March 21 Community detection and densest subgraph. Sections 1 and 3 of Moses Charikar's paper
    March 23 Graph clustering and sparsest cut. Chapters 1, 2–2.2, 3, 4.2 of Luca Trevisan's notes
    March 28 Spectral clustering. Paper by Ulrike von Luxburg
    March 30 Introduction to NNs and GNNs.
    April 4 Lab on graphs in Python Lab page by Andrea Mastropietro
    April 6 Lab on GNNs Lab page by Andrea Mastropietro
    April 11 Introduction to game theory. Slides, notes by Vincenzo Bonifaci.
    April 13 Solution concepts in games. Slides
    April 20 Solution concepts in games (cont). Slides
    April 27 Solution concepts in games (cont). Slides on solution concepts
    May 2 Introduction to congestion games Slides on congestion games
    May 4 Efficiency at an Equilibrium Slides on efficiency at equilibria
    May 9 Mechanism Design: Single Parameter Environments – Part 1 Slides on single parameter environments (part 1)
    May 11 Mechanism Design: Single Parameter Environments – Part 2 Slides on single parameter environments (part 2)
    May 16 Mechanism Design: Multi Parameter Environments Slides on multi parameter environments
    May 18 Computational Social Choice Slides on computational social choice
    May 23 Computational Social Choice – Distortion Slides on distortion in computational social choice
    May 25 Improving Distortion via Queries Slides on improving distortion via queries

     

    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.