Modelling and Searching Networks

许多复杂的现实世界网络的特征之一是幂函数度序列，其中大于k的点数按k的幂递减。由于在稀疏随机图的标准模型中，大度的点数随k呈指数下降，因此人们提出了许多新的概率网络图模型。这样的网络是大规模的、分散的，并且随着时间的推移动态发展。在过去的十年里，人们对复杂网络的结构、功能和建模进行了一系列的研究。 在一种更有趣的语言中，图形搜索通常被称为追逐-逃避游戏。在这个游戏中，一部分是一组逃逸的移动代理，称为逃避者，隐藏在代表网络的图中，另一部分是一组追逐代理，称为搜索者，在图中系统地移动。根据躲避者和追赶者在相对速度、传感器能力或可见度方面的能力，游戏可能会有很大的不同。这个游戏的目标是以一种最优的方式捕获逃避者。根据模型的不同，最优性的概念可能会有不同的解释。图搜索的应用出现在机器人运动规划、网络安全和病毒在网络中的传播建模中。 这项建议涉及网络建模以及搜索自组织网络的研究。许多重要的问题，虽然陈述简单和吸引人，但往往代表了数学中更普遍的现象，并导致许多意想不到的和有用的应用在其他领域。这些问题也导致了离散数学和理论计算机科学中新的工具和技术方法的发展。

One of the characteristic features of many complex, real-world networks is a power-law degree sequence, in which the fraction of vertices of degree larger than k decreases as a power of k. Since in the standard models of sparse random graphs the fraction of vertices of large degree decreases exponentially with k, a number of new probabilistic models of the web graph have been proposed. Such networks are large-scale, decentralized, and evolve dynamically over time. The last decade has seen a flurry of research on the structure, function, and modelling of complex networks. Graph searching is often referred to, in a more playful language, as a pursuit-evasion game. In this game one part is a set of escaping mobile agents, called evaders, that hide in a graph representing a network, and the other part is a set of chasing agents, called searchers, that move systematically in the graph. The game may vary significantly according to the capabilities of the evaders and the pursuers in terms of relative speed, sensor capabilities, or visibility. The objective of the game is to capture the evaders in an optimal way. The notion of optimality may be interpreted in different ways depending on the model. Applications of graph searching arise in robot motion planning, network security, and modelling the spread of viruses in a network. This proposal concerns research in network modelling as well as searching self-organizing networks. Many of the important problems, while simple to state and attractive, are often representative of more general phenomena in mathematics, and lead to many unexpected and useful applications in other areas. These problems also lead to developing new tools and techniques methods in discrete mathematics and theoretical computer science.