This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more
Browse the Department site:
Browse the Teaching site:

Programme of Course "Autonomous Networks"

The course is composed by the following modules: "Non-cooperative networks"   "Social Networks"  



Type of course unit:

Master Degree in Computer Science curriculum NEDAS: Compulsory
Master Degree in Computer Science curriculum SEAS: Elective
Master Degree in Computer Science curriculum UBIDIS: Elective

Level of course unit:

Postgraduate Degrees


Module Non-cooperative networks: 1° semester
Module Social Networks: 1° semester

Number of credits:

Master Degree in Computer Science: 6 (workload 150 hours)


Gianpiero Monaco (gianpierodotmonacoatunivaqdotit)
Guido Proietti (GuidodotProiettiatunivaqdotit)

1. Course Objectives

Module Non-cooperative networks: The course is focused on the algorithmic aspects of non-cooperative networks, where selfish agents own network components and influence through their rational but self-interested behaviour the quality of implemented solution. The set of topics analyzed ranges from the study of the equilibria space of classic network games, up to algorithmic mechanism design for classic network optimization problems.
Module Social Networks: The course investigates how the social, technological, and natural worlds are connected, and how the study of graphs and networks sheds light on these connections. Particular topics include: how opinions, fads, and political movements spread through society, the theory behind strong and weak ties in relationships, and the small-world phenomenon. Students will learn to use models and theory to explain and exploit the structure of information and social networks.

2. Course Contents and learning outcomes (Dublin Descriptors)

Topics of the course include:

Module Non-cooperative networks

  • Strategic equilibria theory in Non-Cooperative Networks (NCN): Nash equilibria and dominant stratgy equlibria. Selfish routing, Network Design games, Network Creation games.
  • Implementation theory in NCN: Algorithmic mechanism design (AMD). AMD for some basic graph optimization problems: Shortest path, Minimum Spanning Tree, Shortest-path Tree

Module Social Networks

  • The (tentative) schedule of the course is the following (with respect to the chapters of the textbook): Ch. 1 of the textbook: overview; Ch. 2 of the textbook: Graphs; Ch. 3 of the textbook: Strong and Weak Ties; Ch. 4 of the textbook: Networks in their Surrounding Contexts; Ch. 5 of the textbook: Positive and Negative Relationships; Part of Ch. 12 of the textbook: Bargaining and Power in Networks; Ch. 18 of the textbook: Power Laws and Rich-Get-Richer Phenomena; Ch. 19 of the textbook: Cascading Behavior in Networks; Ch. 20 of the textbook: The Small-World Phenomenon.

On successful completion of this course, the student should

Module Non-cooperative networks

  • By the end of this module students will be able to understand the difference between a canonical and a strategic distributed system.
  • The aim is to make the student capable of abstracting models and formal algorithmic problems from real (i.e. non-cooperative) distributed computational problems, and designing efficient algorithmic solutions.
  • Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
  • The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
  • The course aims to develop in graduate students competencies and abilities necessary in their future studies, especially with respect to doctoral studies on algorithmic topics.

3. Course Prerequisites

Module Non-cooperative networks: Knowledge of basic courses of discrete mathematcs and algorithms.
Module Social Networks: Students should have general knowledge of: Discrete Mathematics, Probability, Computer Networks, Algorithms and Complexity.

4. Teaching methods and language

Module Non-cooperative networks: Lectures
Module Social Networks: Lectures and exercises.


Reference textbooks

Module Non-cooperative networks

  • Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, Algorithmic Game Theory. Cambridge University Press. 2011.

Module Social Networks

  • David Easley, Jon Kleinberg., Networks Crowds and Market: Reasoning about a highly Connected World. Cambridge Press. 2010.

5. Assessment Methods

Module Non-cooperative networks: Mid-term written examination, followed by a final oral examination, which, for those who performed successfully in the mid-term examination, will be restricted to the second part of the course.
Module Social Networks: Written test followed by an optional oral exam. The oral exam can be required either by the student, to improve grades, or by the teacher, in presence of significant mistakes/misunderstandings in the written exam. The written test is aimed at: (1) verification of theoretical competence, and in particular of knowledge and comprehension of Course contents (2) verification of skills in understanding and solving significant exercises, and in explaining the proposed solutions. This in order to verify the ability of application of techniques learnt during the Course, of analysis of problems and synthesis of suitable solutions, and of evaluation of alternative solutions. Criteria of evaluation will be: the level of knowledge and practical ability; the property of use of the technical/mathematical language; the clarity and completeness of explanations. The written test (about 2 hours) consists in: (i) Short essays and open questions to cover point (1), 30-50% of total marks; (ii) Exercises, to cover point (2), 50-70% of total marks. All parts can result in negative marks if the answer is omitted or seriously flawed. The oral exam (max 1 hour) will occur within the same exam session of the written test and will typically cover the areas of the written answers that need clarification plus, possibly, additional subjects proposed by the teacher.

Course information last updated on: 12 ottobre 2016, 17:30