Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Ryerson University

$20,000.00

Graphs and complex networks

EF 2010-11

Résumé
The last decade has witnessed a great deal of research on modelling real-world complex networks such as the link structure of the web. Graphs, consisting of vertices and edges between them, make natural models which simulate and predict properties of complex networks. My goals are to devise and analyze new realistic models for complex networks, using tools from geometry, infinite graphs, and probability theory. On-line social networks (where nodes represent people and edges correspond to social interactions) such as Facebook and Twitter, are an important type of complex network. Such networks contain many dense subgraphs representing tight-knit communities. I will propose new evolutionary models for on-line social networks, as an approach to classifying their community structure. Applications of graph models may lead, in the case of the web, to more efficient search engines; in on-line social networks, they may help map the spread of social influence. In addition to the applied graph modelling described above, I will study abstract graphs in their own right. One of these topics is the n-existentially closed (or n-e.c.) adjacency property, which states that all n-sets of vertices of a graph can be extended in all possible ways. Through probabilistic arguments we know that n-e.c. graphs exist, but finding explicit examples of them is more difficult. Constructing new examples of n-e.c. graphs will aid in my effort to tackle a conjecture of Erdos on finding the minimum order of such graphs. I will also study pursuit-evasion games on graphs such as Cops and Robbers, where a set of cops attempt to capture a robber who moves from vertex-to-vertex along edges. The minimum number of cops needed to capture the robber is the cop number of the graph. Cops and Robbers may be viewed as a model for network security (the higher the cop number, the less secure the graph). Meyniel's conjecture places an upper bound on the cop number of on a connected graph. I will study the cop number in infinite graphs, and resolve Meyniel's conjecture using tools from structural, probabilistic, and spectral graph theory.
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
227384-2010
Name nom
Bonato, Anthony
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
2010
Competition year année de concours
2010
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
1
Nb partie
5
Application title
Graphs and complex networks
Keyword
NSERC
Application summary
The last decade has witnessed a great deal of research on modelling real-world complex networks such as the link structure of the web. Graphs, consisting of vertices and edges between them, make natural models which simulate and predict properties of complex networks. My goals are to devise and analyze new realistic models for complex networks, using tools from geometry, infinite graphs, and probability theory. On-line social networks (where nodes represent people and edges correspond to social interactions) such as Facebook and Twitter, are an important type of complex network. Such networks contain many dense subgraphs representing tight-knit communities. I will propose new evolutionary models for on-line social networks, as an approach to classifying their community structure. Applications of graph models may lead, in the case of the web, to more efficient search engines; in on-line social networks, they may help map the spread of social influence. In addition to the applied graph modelling described above, I will study abstract graphs in their own right. One of these topics is the n-existentially closed (or n-e.c.) adjacency property, which states that all n-sets of vertices of a graph can be extended in all possible ways. Through probabilistic arguments we know that n-e.c. graphs exist, but finding explicit examples of them is more difficult. Constructing new examples of n-e.c. graphs will aid in my effort to tackle a conjecture of Erdos on finding the minimum order of such graphs. I will also study pursuit-evasion games on graphs such as Cops and Robbers, where a set of cops attempt to capture a robber who moves from vertex-to-vertex along edges. The minimum number of cops needed to capture the robber is the cop number of the graph. Cops and Robbers may be viewed as a model for network security (the higher the cop number, the less secure the graph). Meyniel's conjecture places an upper bound on the cop number of on a connected graph. I will study the cop number in infinite graphs, and resolve Meyniel's conjecture using tools from structural, probabilistic, and spectral graph theory.