Modelling and 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.