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