Seminars in Social Networks and Markets -- Academic Year 2016/17

(Click here to go to the page for year 2015/16.)



The social network of A Game of Thrones. Read how it was built

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 on-line social networks and technological networks, algorithms for data mining in social networks, and a few network economic issues, with an eye towards the current research issues in the area.


Announcements

Exam Rules

Each student that does not attend 75% of the lectures will undergo an oral exam on the contents of the course (as defined in the Syllabus and the Class Diary). Attendance in class is highly recommended.

Each student is required to complete any homework that will be assigned in class; any such assignment will also be published on this website.

Finally, each student will be assigned a project (either a software project or a literature survey) and will have to present and discuss the project at the exam. See the bottom of this webpage for more details about the project and some sample projects.


Instructors

Dr. Vincenzo Bonifaci, IASI-CNR
Contact address: (surname)@diag.uniroma1.it


When and Where

When: Tuesday 9.10-10.45, Wednesday 14.10-15.40 and Friday 9.10-9.55
Where: Via Ariosto 25, Rooms A3 (Tuesday), A7 (Wednesday) and A3 (Friday)


Office Hours

Fridays, 10.30-11.30 (Via Ariosto 25, Room B118)
All meetings have to be confirmed by email


Textbook(s)

The official textbook of the class is

The textbook will be complemented by lecture notes from the instructor for some of the lectures.
Another useful reference is


Syllabus

  1. Network structure: graph theory and social networks; measures of centrality; communities and assortative mixing; small worlds, power laws and scale-free networks.
  2. Network dynamics: network effects; information cascades and cascading in networks; epidemics and influence processes; network search and message passing.
  3. Strategic interaction in networks and online markets: network traffic and equilibria; algorithmic mechanism design and computerized auctions; market equilibria; matching markets; online labor marketplaces; voting mechanisms.

Class Diary (see here for last year's diary)

The notation [EKxx] refers to Chapter xx in the textbook by Easley and Kleinberg. Similarly, [Nxx] refers to a Chapter in the textbook by Newman.

DateTopicsRequired readingFurther reading

21/2/2017

Introduction

Graph theory basics

 

[slides, EK1]

[notes 1-3, EK2]

DFS.html, DFS.py

[N1]

[N6.1-6.4]

 

22/2/2017

Connectivity and distances

 
 
 

Triadic closure, strong and weak ties

[notes 4]

CC.html, CC.py
SCC.html, SCC.py
BFS.html, BFS.py

[slides, EK3.1-3.3]

[N6.5-6.11]

 

 
 
[N8.6]

24/2/2017

Graph matrices and eigenvalues:
the adjacency matrix

[notes 1]

SPARSEMAT.html, SPARSEMAT.py
MATRIX.py

[N6.1-6.4]

28/2/2017

Eigenvalues of an acyclic digraph
The Laplacian matrix

[notes 2-3]

[N6.1-6.4]

1/3/2017

Properties of the Laplacian matrix

Centrality measures: degree and closeness

[notes 3]

[notes 1-2]

 

[N7.6]

3/3/2017

Centrality measures: betweenness

[EK3.6, EK3.B, notes 3]

[N7.7]

7/3/2017

Centrality measures: eigenvector centrality

The Power Method

[notes 4]

SPRADIUS.html, SPRADIUS.py

[N7.2]

[N11.1]

8/3/2017

Analysis of the Power Method

[notes 4.1-4.4]

[N11.1]

10/3/2017

Power laws

[slides, EK18.1-18.2;18.5]

[N8.3-8.4]

14/3/2017

Computing the second dominant eigenvalue

Centrality measures: Katz centrality

[notes 4.5-5]

[N7.3]

15/3/2017

Centrality measures: Pagerank

[notes 6]

[N7.4]

17/3/2017

Community structure: cliques, cores, k-connectivity

[slides]

[N7.8;11.2]

21/3/2017

Graph partitioning: the Kernighan-Lin heuristic

[notes 3.1]

[N11.3-11.4]

22/3/2017

Graph partitioning: spectral partitioning

[notes 3.2]

[N11.5]

24/3/2017

Graph partitioning: spectral partitioning and conductance

[notes 3.2-3.3]

[N11.5]

28/3/2017

Community structure: assortativity and modularity

[EK4.1-4.2, slides, notes 4]

[N7.13;11.7-11.8]

29/3/2017

Small-world phenomenon

Network models: Erdős-Rényi

[EK2.3, slides]

[slides, notes 1-2.1]

[N3.6]

[N12.1-12.2]

31/3/2017

Erdős-Rényi: degree distribution

[slides, notes 2.2-2.3]

[N12.3-12.4]

4/4/2017

Erdős-Rényi: the giant component

Watts-Strogatz and Barabási-Albert

[notes 2.4]

[slides]

[N12.5]

[N14.2;15.1]

5/4/2017

Analysis of the Copying model

[EK18.3;18.7]

[N14.5]

7/4/2017

Game theory: normal form games, dominant strategies

[slides, EK6.1-6.3]

[notes 1, 2.1]

11/4/2017

Game theory: Nash equilibria, zero-sum games

[slides, EK6.4-6.8]

[notes 2.2, 2.3.2]

12/4/2017

Mixed Nash equilibria, graphical games

Auctions, stable marriages

[slides, EK6.7-6.8]

[slides, EK9.1-9.4]

[notes 2.3.1, 2.3.5]

Gale-Shapley 1962

19/4/2017

Evolutionarily stable strategies

[EK7.1-7.4]

Smith-Price 1973

21/4/2017

Mixed evolutionarily stable strategies

[EK7.5]

Smith-Price 1973

26/4/2017

Network traffic equilibria

[EK8.1-8.2]

Roughgarden 2007

2/5/2017

Potential energy and the social cost of equilibria

[EK8.3-8.4]

Rosenthal 1973

3/5/2017

Cascading behavior in networks

[EK19.1-19.2]

Morris 2000

5/5/2017

Cascade capacity

[EK19.3;19.7A]

Morris 2000

9/5/2017

Epidemics and branching processes

[EK21.1-2;21.8A]

Watson-Galton 1875

12/5/2017

Myopic search in a small world

[EK20.3-4;20.7A]

Kleinberg 1999

16/5/2017-26/5/2017

Lectures on markets by prof. S. Leonardi


Projects

The instructions to prepare your project are here.