SCHOOL INFORMATION

Course: Social, Information, and Routing Networks: Models, Algorithms, and Strategic Behavior.

Date: 29/02/2012, 01/03/2012, 02/03/2012.

Lecture Hours: 9:00 – 10:30, 11:00 – 12.30, 14:30 – 16:00, 16:30 – 18:00.

Download - Lectures:

29/02/2012 - Prof. Dr. Aris Anagnostopoulos.

-Social Networks: Introduction, Properties, and Models [download]

-Epidemics in Social Networks [download]

-Influence Maximization in the Cascade Model [download]

-Page Rank [download]

01/03/2012 - Profa. Dra. Luciana Buriol.

-Algorithms for dealing with massive data [download]

-Web Graph compression [download]

02/03/2012 - Prof. Dr. Guido Schäfer.

-Strategic Behavior in Network Routing [download]

Local:

Informatics Institute/UFRGS

Universidade Federal do Rio Grande do Sul

Room: 102 - Building: 43424 (72)

91501-970 Porto Alegre - RS - Brasil

Instructors:

Prof. Dr. Aris Anagnostopoulos, Sapienza University or Rome, Italy

Profa. Dra. Luciana Buriol, Universidade Federal do Rio Grande do Sul

Prof. Dr. Guido Schäfer, CWI and VU University Amsterdam, The Netherland

Resume:

Social and information networks have a large impact in various areas of our lives. With the expansion of the internet, there has been a constant increase in the study of large networking systems in an attempt to understand their properties, how they are formed, how entities who are parts of these networks operate, as well as on the development of algorithms that are able to handle their large scale. In this short course we will give an overview of such issues.

We will start with a description of some of the global structural properties of social and information networks, such as the small-world phenomenon, power-law degree distributions, and so on. Next we will describe some of the models that can explain these phenomena. We will then talk about influence propagation in networks, their models and some basic problems, such as influence maximization. Subsequently we will switch to the discussion of algorithms that are able to handle the large-scale of online networks. We will describe graph-streaming techniques as well as algorithms for web compression.

Finally, we will study the effect of strategic behavior in network routing problems. These problems are often distributed and complex in nature in that they involve a large number of strategic decision makers who attempt to achieve their own goals. Typical examples include routing applications in road traffic, public transportation and the Internet. It is a well-known fact that strategic choices often result in outcomes that are inefficient for the society as a whole. We will study the impact of strategic behavior in network routing problems from an algorithmic game theory perspective. We will cover some classical highlights as well as

some more recent advances in developing effective means to reduce the inefficiency of selfish outcomes in network routing.

The course will have three days of lectures, each starting with a presentation of the relevant theory. At the end of each day, students will also be asked to do and discuss exercises on some selected topics of the course.

Topics will include:

• Network properties

• Models for network formation

• Influence processes in networks

• Stream algorithms

• Web graph compression

• Selfish routing game

• Inefficiency of equilibria

• Braess paradox

• Stackelberg routing

1. •Network toll
   

Prerequisites: Basic knowledge in algorithms, complexity and optimization is advantageous.

IMPORTANT DATES AND REGISTRATION

For registration please send an e-mail to netschool@inf.ufrgs.br including the following informations:

Email-Subject: registration

Name:

Affiliation/University:

E-mail:

Education Level (Master, Dr., Undergraduate student):

Research area:

Link to Lattes CV:

Deadline: 28.02.2012.

Contact: netschool@inf.ufrgs.br

TRAVEL INFORMATION

Staying in Porto Alegre

We suggest some hotels in Porto Alegre.

Hotel de Trânsito - Clube Farrapos

Av. Professor Cristiano Fischer,1331 - Fone: +55 51 3382.8000  

Single Room, Price: R$ 70,00

Double Room, Price: R$ 90,00

Hotel with easy access to the University.

Hotel Coral Tower Express

Av. Getúlio Vargas, 318 - Fone: +55 51 3226 5536

Single Room, Price: R$110.

Ritter Hotéis

Lrg. Vespasiano Julio Veppo, 55 - Fone: +55 51 3228 4044

Single Room, Price: R$150.

Master Express Cidade Baixa

R. Sarmento Leite, 865 - Fone: +55 51 3018 3636

Q Single Room, Price: R$150.

Blue Tree Towers Porto Alegre

Av. Coronel Lucas de Oliveira, 995 - Fone: +55 51 3019 8000

Single Room, Price: R$290.

Hostel Casa Azul

R. General Lima e Silva, 912 - Fone: +55 51 3084 5050

Quartos coletivos, Price R$30.

SPONSORED BY

Sponsored by Graduate Program in Computing, UFRGS and European South American network for Combinatorial Optimization under Uncertainty -Proj. Europeu FP7-People 2010-2014