Real-world Networks and Random Graph Models

点击翻译按钮获取中文摘要

Modeling the topology of large networks is a fundamental problem that has attracted considerable attention in the last decades. Networks provide an abstract way of describing relationships and interactions between elements of complex and heterogeneous systems. Examples include technological networks, like the World Wide Web or the Internet, biological networks, like the human brain, and social networks, which describe various kinds of interactions between individuals. An accurate mathematical model can have enormous impact on several research areas. From the viewpoint of computer science, an obvious benefit is that it could enable us to design more efficient algorithms that exploit the underlying topology. Moreover, the process of modeling may suggest and reveal novel types of qualitative network features, which become patterns to look for in datasets. Finally, an appropriate model will allow us to generate artificial instances, which resemble realistic instances to a high degree, for simulation purposes. Unfortunately, from today’s point of view, a significant proportion of the current literature is devoted only to experimental studies of properties of real-world networks, and there has been only little rigorous mathematical work. The aim of this project is twofold. First, by studying the typical structural properties of random networks generated by two carefully selected models, I want to investigate rigorously the fundamental underlying mechanisms that determine the formation of real-world networks. As a second step, I want to use the acquired knowledge to develop algorithms for many important optimization problems, like routing and information dissemination