Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Canada Research Chairs

McGill University

$200,000.00

discrete probability

EF 2024-25

Résumé
Suppose at some time t we observe a computer virus which has randomly spread through a network. If we know the network structure, and the set of sites which have already been exposed to the virus (but not precisely when), can we determine the likely time-zero source of the virus? How can this question be tackled mathematically? On the one hand, one can develop algorithms to try to reconstruct the source location. On the other hand, there are network topologies for which any reconstruction is essentially guesswork; so, some hypotheses about the structure of the network are needed in order to make progress or to prove that a given algorithm has a reasonable chance of success. For large, complex networks whose construction occurs through the organic interaction of many independent agents, random models are then natural. Questions such as this one are the domain of discrete probability, which investigates the structure and dynamics of random discrete systems. This flourishing area connects probability theory with statistical physics, combinatorics, population genetics, analysis of algorithms, and computational complexity. Research in this field focusses on large random structures -- such as random networks or random graphs-- which are frequently endowed with a second layer of randomness -- such an interacting particle system or a spreading virus. One goal of discrete probability is to study models which are rich enough to predict aspects of the phenomenology of large complex real-world systems, but simple enough to be analytically tractable (and mathematically beautiful).
Programme
Canada Research Chairs
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
CRC-2022-00226
Name nom
Addario-Berry, Louigi
Department département
Mathematics and Statistics - McGill University
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
2024
Competition year année de concours
2022
Award amount
200000
Program id
CRC
Program name en
Canada Research Chairs
Program name fr
Chaires de recherche du Canada
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
9998
Committee name en
Canada Research Chair Selection Committee
Committee name fr
Comité de sélection des Chaires de recherche du Canada
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Non disponible
Research subject en
Not available
Research subject fr
Non disponible
Field of research list codes
RDF1010312
Field of research list names en
Probability theory
Field of research list names fr
Théorie des probabilités
Socioeconomic objective list codes
RDS10199
Socioeconomic objective list names en
Exploration and exploitation of the earth, n.e.c.
Socioeconomic objective list names fr
Exploration et exploitation du milieu terrestre, n.c.a.
Application title
discrete probability
Keywords
Discrete probability; Random trees; Analysis of algorithms; Branching processes; Random graphs; Planar maps; Random networks; Phase transitions
Application summary
Suppose at some time t we observe a computer virus which has randomly spread through a network. If we know the network structure, and the set of sites which have already been exposed to the virus (but not precisely when), can we determine the likely time-zero source of the virus? How can this question be tackled mathematically? On the one hand, one can develop algorithms to try to reconstruct the source location. On the other hand, there are network topologies for which any reconstruction is essentially guesswork; so, some hypotheses about the structure of the network are needed in order to make progress or to prove that a given algorithm has a reasonable chance of success. For large, complex networks whose construction occurs through the organic interaction of many independent agents, random models are then natural. Questions such as this one are the domain of discrete probability, which investigates the structure and dynamics of random discrete systems. This flourishing area connects probability theory with statistical physics, combinatorics, population genetics, analysis of algorithms, and computational complexity. Research in this field focusses on large random structures -- such as random networks or random graphs-- which are frequently endowed with a second layer of randomness -- such an interacting particle system or a spreading virus. One goal of discrete probability is to study models which are rich enough to predict aspects of the phenomenology of large complex real-world systems, but simple enough to be analytically tractable (and mathematically beautiful).