Seminars in Computer Networks -- Academic Year 2014/15

(Click here to go to the page for year 2013/14.)


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

The exam originally scheduled for 11/06/2015 will be held on 18/06/2015 (same hour and room)

The exam originally scheduled for 16/07/2015 will be held on 23/07/2015 (same hour and room)


Instructor

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


When and Where

When: Thursdays, 10.15-13.40
Where: Via Ariosto 25, Room A3


Office Hours

Thursdays, 15.00-16.00 (Via Ariosto 25, Room B118)
All meetings have to be confirmed by email


Book(s)

Most material will be from one of the books

They will be complemented by lecture notes for some of the lectures.


Syllabus

  1. Aspects of networks. Social networks and networks of information.
  2. Mathematics of networks. Networks and their representation. Adjacency matrix, incidence matrix and other data structures. Connectivity and distances. Independent paths and cuts. Graph Laplacian.
  3. Measures of centrality. Degree centrality, Eigenvector centrality, Pagerank. Ranking of web pages. Closeness centrality, betweenness centrality. Similarity measures: cosine similarity, Pearson coefficient. Homophily and assortative mixing.
  4. Large-scale structure of networks. Shortest paths and small-world phenomenon. Degree distributions. Power laws and scale-free networks. Clustering coefficients.
  5. Matrix algorithms and graph partitioning. Power method for eigenvector centrality and Pagerank. Clustering problem and spectral partitioning. Community detection and modularity maximization methods.
  6. Network models. Random graphs. Preferential attachment. Vertex copying models. Network optimization models. The small-world model.
  7. Processes on networks. Information cascades and cascading in networks. Epidemics and influence processes. Network search and message passing. Random walks on networks. Network traffic and equilibria.

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

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

DateTopicsRequired readingOptional reading
26/02/2015

Introduction

Graph theory basics

[slides]

[notes 1-4]

[N1, EK1]

[N6.1-6.4, EK2]

05/03/2015

Connectivity, planarity

Independent paths, cuts

[notes 5-8]

[N6.5-6.12]

12/03/2015

Graph Laplacian

Degree, eigenvector centralities

[notes 9]

[notes 1-2.2]

[N6.13-6.14]

[N7.1-7.2;N11.1]

19/03/2015

"Kolmogorov meets Turing" workshop

 

 

26/03/2015

Power method

Katz centrality, Pagerank

[notes 2-4]

[N7.3-7.4;N11.1.1-N11.1.2]

[EK14.3,14.B]

02/04/2015

Spring break

 

 

09/04/2015

Closeness, betweenness

Cosine similarity, Pearson coefficient

[notes 5-6], [EK3.6-3.6B]

[N7.12-7.12.2]

 

16/04/2015

Graph partitioning

[notes 1]

[N11.4-11.5]

23/04/2015

Assortativity and clustering

Random graphs

[notes 2], [N7.13;N11.8]

[notes 1-2.2], [N12.1-12.4]

[EK3.6A]

 

30/04/2015

Giant and small components

Small world phenomenon

[notes 2.3-2.4], [N12.5-12.6.1]

[EK20.3,20.4,20.7.A]

 

[article 1, 2, 3]

07/05/2015

Power-law distributions

Generative models of networks

[article]

[EK18]

[article]

[C10] [article]

14/05/2015

Game theory I

[notes 1] [slides]

[EK6]

21/05/2015

Game theory II

Network cascading

 

[EK19] (excluding EK19.4, EK19.6)

 

[EK19.4, EK19.6]

28/05/2015

Network traffic equilibria

[notes 2] [EK8]

[article 1, 2]


Projects

The instructions to prepare your project are here.