Grant: Discovery Grants Program - Individual
Ryerson University
$20,000.00
Complex networks and vertex pursuit games
FY 2017-18
Summary
Fundamental questions arise from studying networks, which emerge in every aspect of the natural and technological world. How can we model the spread of influence in a network? Do networks have an underlying geometry, and if so, how can we use the network structure to uncover the geometry? How do we most efficiently neutralize adversarial activity in a network? The proposed project addresses these questions using state-of-the-art mathematical tools from graph theory, probability, and geometry, and aims to achieve the following objectives: to analyze new and existing models for real-world networks, to uncover the interaction between the underlying geometry of the network and graph structures, and to advance the frontier of knowledge in the mathematical study of vertex pursuit games. Major emphasis will be placed on building models of on-line social networks and simulating the spread of influence in these networks, with special attention to practical applications. Complex networks pose big data challenges to researchers. The results of our research will be important to those concerned with data environments such as the ones found, for example, on Google where over 60 trillion pages are indexed, or on Facebook, which contains over one billion user accounts. The research will also benefit our understanding of the extremely complicated environments found in network models of sophisticated biological processes like those representing the metabolic pathways of complex carbohydrates, signaling systems, or various life threatening diseases such as the major cancers. Vertex pursuit games are combinatorial models for the halting of an adversary?s activity on a network. In these games, agents or cops are attempting to capture an intruder or robber who is loose on the vertices of a network. The most studied such game is Cops and Robbers, and the minimum number of cops needed to capture the robber in a graph is its cop number. Cops and Robbers and its variants form an active topic in graph theory, with new results rapidly appearing in the literature. Our specific contribution to the field will be to settle special cases of Meyniel?s conjecture, which provides bounds on the cop number, with a view of eventually settling the conjecture. Rigorous graph models tailored to experimental data provide rich insight into the structure and evolution of complex networks. Our research on complex networks responds to central theoretical questions in the field, and has potential applications ranging from improved recommender systems, mapping the spread of emotional contagion in a social network, and the treatment of disease using properties of protein interaction networks. The research in vertex pursuit games such as Cops and Robbers will accelerate discoveries in that field, spur new directions and problems in graph theory, and have applications to the monitoring or halting of adversarial activity in complex networks.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-05409
Name nom
Bonato, Anthony
Department département
Mathematics - Mathematics
Organization id
43
Institution établissement
Ryerson University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
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
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
3
Nb partie
5
Application title
Complex networks and vertex pursuit games
Keyword
NSERC
Application summary
Fundamental questions arise from studying networks, which emerge in every aspect of the natural and technological world. How can we model the spread of influence in a network? Do networks have an underlying geometry, and if so, how can we use the network structure to uncover the geometry? How do we most efficiently neutralize adversarial activity in a network? The proposed project addresses these questions using state-of-the-art mathematical tools from graph theory, probability, and geometry, and aims to achieve the following objectives: to analyze new and existing models for real-world networks, to uncover the interaction between the underlying geometry of the network and graph structures, and to advance the frontier of knowledge in the mathematical study of vertex pursuit games. Major emphasis will be placed on building models of on-line social networks and simulating the spread of influence in these networks, with special attention to practical applications. Complex networks pose big data challenges to researchers. The results of our research will be important to those concerned with data environments such as the ones found, for example, on Google where over 60 trillion pages are indexed, or on Facebook, which contains over one billion user accounts. The research will also benefit our understanding of the extremely complicated environments found in network models of sophisticated biological processes like those representing the metabolic pathways of complex carbohydrates, signaling systems, or various life threatening diseases such as the major cancers. Vertex pursuit games are combinatorial models for the halting of an adversary?s activity on a network. In these games, agents or cops are attempting to capture an intruder or robber who is loose on the vertices of a network. The most studied such game is Cops and Robbers, and the minimum number of cops needed to capture the robber in a graph is its cop number. Cops and Robbers and its variants form an active topic in graph theory, with new results rapidly appearing in the literature. Our specific contribution to the field will be to settle special cases of Meyniel?s conjecture, which provides bounds on the cop number, with a view of eventually settling the conjecture. Rigorous graph models tailored to experimental data provide rich insight into the structure and evolution of complex networks. Our research on complex networks responds to central theoretical questions in the field, and has potential applications ranging from improved recommender systems, mapping the spread of emotional contagion in a social network, and the treatment of disease using properties of protein interaction networks. The research in vertex pursuit games such as Cops and Robbers will accelerate discoveries in that field, spur new directions and problems in graph theory, and have applications to the monitoring or halting of adversarial activity in complex networks.