Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McGill University

$62,000.00

The Combinatorics of Complex Networks

FY 2012-13

Summary
Transportation Networks, Communications Networks, and Social Networks have all played a crucial role in humanity's progress. While quite different, these various networks are all sets of objects connected by links. Extracting this common feature leads to an abstract model which allows us to study the properties these and other networks share. A graph consists of a set of objects called vertices joined by a set of links called edges (formally, each edge is an unordered pair of vertices). If the links have an associated directions (e.g. a web hyperlink leading from one web page to another), we obtain a directed graph . The simplicity of this model of connectivity makes it widely applicable. When modeling transportation networks, the nodes may be cities and the edges roads, railway lines, or airline routes. Molecular chemists consider graphs whose nodes are atoms and whose edges are molecular bonds. Self organizing biological networks are also modeled using graphs. Statisitical physicists use graphs to model crystal formation. In fact the connections of any physical or conceptual network can be modelled using a graph. The size of the networks modelled by graphs has grown exponentially. The first problem in graph theory, concerned seven bridges and the four land masses they linked, Graph theorists now study the graph formed by the billions of devices linked by the web and help sequence the billions of base pairs which occur in the human genome. The study of such large and complex networks is intimately linked to advances in computer science in two ways. Firstly, this area gives rise to many of the networks studied: the web, fibreoptic networks, the connections burned into a computer chip. More importantly, sophisticated computers are necessary to model, design, and solve problems with respect to the large and complex networks of the modern era. I develop and apply mathematical machinery which can handle such large and complex networks. My principal focus is on using local analysis to obtain information about the global properties of the network.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
36501-2012
Name nom
Reed, Bruce
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
62000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
The Combinatorics of Complex Networks
Keyword
NSERC
Application summary
Transportation Networks, Communications Networks, and Social Networks have all played a crucial role in humanity's progress. While quite different, these various networks are all sets of objects connected by links. Extracting this common feature leads to an abstract model which allows us to study the properties these and other networks share. A graph consists of a set of objects called vertices joined by a set of links called edges (formally, each edge is an unordered pair of vertices). If the links have an associated directions (e.g. a web hyperlink leading from one web page to another), we obtain a directed graph . The simplicity of this model of connectivity makes it widely applicable. When modeling transportation networks, the nodes may be cities and the edges roads, railway lines, or airline routes. Molecular chemists consider graphs whose nodes are atoms and whose edges are molecular bonds. Self organizing biological networks are also modeled using graphs. Statisitical physicists use graphs to model crystal formation. In fact the connections of any physical or conceptual network can be modelled using a graph. The size of the networks modelled by graphs has grown exponentially. The first problem in graph theory, concerned seven bridges and the four land masses they linked, Graph theorists now study the graph formed by the billions of devices linked by the web and help sequence the billions of base pairs which occur in the human genome. The study of such large and complex networks is intimately linked to advances in computer science in two ways. Firstly, this area gives rise to many of the networks studied: the web, fibreoptic networks, the connections burned into a computer chip. More importantly, sophisticated computers are necessary to model, design, and solve problems with respect to the large and complex networks of the modern era. I develop and apply mathematical machinery which can handle such large and complex networks. My principal focus is on using local analysis to obtain information about the global properties of the network.