Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Dalhousie University

$34,000.00

Graphs and Networks - Pure and Applied

FY 2024-25

Summary
Graphs and their applied counterparts, networks, arise in data and give rise to data. Cliques, independent sets, and shortest paths are important subsets of vertices whose size and number can inform us about the structure of abstract graphs and social networks. In network reliability, we seek to measure and perhaps even optimize a network's underlying topology in terms of robustness to random component failures. Timetabling give rise to graph colourings. Music events yield melodic and harmonic sequences for which directed graphs are ideally suited. Theoretical results and algorithms can provide fresh insights and solutions to network data, even on large scales, while graphs and networks can, when viewed as data, lead to notions newly approachable by data analysis techniques. Network reliability, an important measure of network's robustness, is computationally intractable. The proposed research has a long-term goal of deriving radically new bounding and approximation techniques for these functions. One approach will use spectral clustering as well as the data-driven algorithm Ball Mapper, arising in topological data analysis, to group nodes into highly reliable communities. Modern edge ranking algorithms based on a network's structure and usage, along with a notion of average reliability, will be used to compare models and utilize resources efficiently to produce networks that are "optimal enough". Another method for reliability approximation will utilize recent analytical techniques on zero-free regions in the complex plane, and this brings us around to the plan of utilizing the data encoded not only in a graph polynomial's coefficients, but also in their roots. There are several fundamental conjectures about where roots of reliability, chromatic polynomial and independence polynomials lie in the complex plane, in terms of moduli and real and imaginary parts. New analytical approaches will be developed based on recent extensions to multiple variables. I also plan to utilize Mapper, a relative of Ball Mapper that can be more finely tuned, to innovatively treat chromatic and other graph polynomials and their roots as data sets by considering their sequence of coefficients as vectors. This approach will allow for the application of persistent homology to explore graph polynomials and the "shape" of the root sets. A drawback of machine learning is that is a "black box" that offers no insight into its output. The graphs and clique complexes arising from Mapper, Ball Mapper and persistent homology can lead to interpretations to data sets that are otherwise hidden. A long-term goal is to mine the combinatorial properties of mapper graphs that provide dimension reduction of data. I will leverage my years of experience in graph theory to explore and interpret the data, from music networks to distance functions on graphs. Applications include not only graph compression, but also applications to both the sciences and the arts.
Program
Discovery Grants Program - Individual
Location
Nova Scotia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-03846
Name nom
Brown, Jason
Department département
Mathematics and Statistics
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Graphs and Networks - Pure and Applied
Keywords
graphs; networks; reliability; polynomial; roots; colouring; topological data analysis; mapper; embeddings; music
Application summary
Graphs and their applied counterparts, networks, arise in data and give rise to data. Cliques, independent sets, and shortest paths are important subsets of vertices whose size and number can inform us about the structure of abstract graphs and social networks. In network reliability, we seek to measure and perhaps even optimize a network's underlying topology in terms of robustness to random component failures. Timetabling give rise to graph colourings. Music events yield melodic and harmonic sequences for which directed graphs are ideally suited. Theoretical results and algorithms can provide fresh insights and solutions to network data, even on large scales, while graphs and networks can, when viewed as data, lead to notions newly approachable by data analysis techniques. Network reliability, an important measure of network's robustness, is computationally intractable. The proposed research has a long-term goal of deriving radically new bounding and approximation techniques for these functions. One approach will use spectral clustering as well as the data-driven algorithm Ball Mapper, arising in topological data analysis, to group nodes into highly reliable communities. Modern edge ranking algorithms based on a network's structure and usage, along with a notion of average reliability, will be used to compare models and utilize resources efficiently to produce networks that are "optimal enough". Another method for reliability approximation will utilize recent analytical techniques on zero-free regions in the complex plane, and this brings us around to the plan of utilizing the data encoded not only in a graph polynomial's coefficients, but also in their roots. There are several fundamental conjectures about where roots of reliability, chromatic polynomial and independence polynomials lie in the complex plane, in terms of moduli and real and imaginary parts. New analytical approaches will be developed based on recent extensions to multiple variables. I also plan to utilize Mapper, a relative of Ball Mapper that can be more finely tuned, to innovatively treat chromatic and other graph polynomials and their roots as data sets by considering their sequence of coefficients as vectors. This approach will allow for the application of persistent homology to explore graph polynomials and the "shape" of the root sets. A drawback of machine learning is that is a "black box" that offers no insight into its output. The graphs and clique complexes arising from Mapper, Ball Mapper and persistent homology can lead to interpretations to data sets that are otherwise hidden. A long-term goal is to mine the combinatorial properties of mapper graphs that provide dimension reduction of data. I will leverage my years of experience in graph theory to explore and interpret the data, from music networks to distance functions on graphs. Applications include not only graph compression, but also applications to both the sciences and the arts.
Dalhousie University - $34,000 Grant (2024-25) | Canada Spends