Modelling and Searching Networks

建模和搜索网络

• 批准号: 418059-2012
• 负责人: Pralat, Pawel
• 金额: $ 1.46万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=573496
• 关键词: Modelling; Searching; Networks

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.

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