Algorithmic Aspects of Large and Complex Networks

Summary

Information systems like the internet, the World Wide Web, telecommunication networks, sensor networks, or peer-to-peer networks have reached a size and a dynamics that puts them beyond our ability to deploy them and to keep them functioning correctly through traditional algorithmic techniques. Their complexity arises from their growth and dynamics: They change their size and structure over time, large components may be modified deleted or replaced. Challenges for algorithms research include development of models for the dynamics of such systems, the design of decentralized, scalable and adaptive mechanisms for regulation and improvement, and the design, the analysis, and the experimental evaluation of algorithms for analyzing and optimizing such systems.

Today, networks play an important role in many areas of our society. Information acquisition and dissemination as well as the further growing mobility is based on the understanding and employment of such huge networks. Interesting relations between networks in areas like traffic and transport, politics and society make it promising to strengthen the joint effort to tackle them. Dealing with large networks is a big topic also in areas like physics, biology, and economy, with very different, mainly non-algorithmic methods and different optimization goals.

The seminar brought together 46 researchers from different European countries, Australia and USA. Most participants were from algorithms research, but several also came from other branches of Computer Science as well as from Physics and Biology. As in previous meetings there were not only scientific talks on results respectively ongoing research, but also fruitful and stimulating discussions.

The seminar also offered an opportunity to meet and intensify collaboration for resrachers involved in the DFG research cluster "Algorithmic Aspects of Large and Complex Networks" (DFG Schwerpunktprogramm 1126) and from the EU Integrated Project DELIS (Dynamically Evolving Large-scale Information Systems).

Schloss Dagstuhl and its staff provided a very convenient and stimulating environment. The seminar participants appreciated the cordial atmosphere which improved mutual understanding and inspiration. The organizers wish to thank all those who helped make the workshop a fruitful research experience.