# Course Details

#### Name:

**Autonomous Networks / Autonomous Networks**

### Basic information

##### Credits:

*Master Degree in Computer Science:* 3 Ects (b)+3 Ects (c)

##### Term:

*Module Non-cooperative networks:* 1° semester

*Module Social Networks:* 1° semester

##### Degree(s):

Compulsory 2^{nd} year Master Degree in Computer Science curriculum NEDAS

Elective 2^{nd} year Master Degree in Computer Science curriculum SEAS

Elective Master Degree in Computer Science curriculum UBIDIS

##### Language:

English

### 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.

### Course Content

##### 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.

### Learning Outcomes (Dublin Descriptors)

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.

### Prerequisites and Learning Activities

**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.

### Teaching Methods

**Language**: English

**Module Non-cooperative networks:** Lectures

**Module Social Networks:** Lectures and exercises.

### Assessment Methods and Criteria

**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.

### 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. * *

### Online Teaching Resources

### Course page updates

This course page is available (with possible updates) also for the following academic years:

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