Grant: Discovery Grants Program - Individual
Ryerson University
$20,000.00
Modelling and Searching Networks
EF 2016-17
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
418059-2012
Name nom
Pralat, Pawel
Department département
Mathematics
Organization id
43
Institution établissement
Ryerson University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
5
Nb partie
5
Application title
Modelling and Searching Networks
Keyword
NSERC
Application summary
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.