Algorithms and Complexity

"Structure of Large Real World Networks"
Summer term 2010
Junior-Prof. Dr. Robert Elsässer

The talks are in block at the end of the semester.


Our first meeting is on April 21st, 2010, at 1 pm, in room 00-019, Geb. 79.


In the daily life we encounter reams of examples for objects that interact with each other in some way. If we concentrate on items of similar type and their connections, we come across the term of a network. Prominent examples are the Internet and the World Wide Web. Real world networks also appear in aparently non-technical disciplines like social sciences, where certain relationships between individuals can be modeled as a network. Further examples occur in flight routes, citations between scientific papers, road maps, electric power grids, and so on...
Inspired by a huge amount of empirical study of such networks, researchers have developed several graph models which help us to understand the most fundamental properties of real world interactions. Simple characteristics observed in many realistic networks are

- a high clustering coefficient, i.e., if vertex u is connected to vertex v, and vertex v is connected to vertex w, then u is likely connected to w,
- a power law degree distribution, i.e., the number of nodes of degree d is proportional to d^{-alpha}, where alpha is some constant, and
- small mean geodesic distance, i.e., the minimal distance between two randomly chosen nodes is small.

The goal of this project is to analyze the structure of real world networks, and to study certain graph models which are well suited to model these systems.
Students attending the seminar are expected to read and present a selection of recently published research papers, and actively take part in discussions.