Grant: Canada Research Chairs
McGill University
$200,000.00
discrete probability
EF 2023-24
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
2023
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
10000
Area of application group en
The socioeconomic objective available
Area of application group fr
L'objectif socioéconomique disponible
Area of application en
The socioeconomic objective available
Area of application fr
L'objectif socioéconomique disponible
Research subject code
10000
Research subject group en
The field of research available
Research subject group fr
The field of research available
Research subject en
Le domaine de recherche disponible
Research subject fr
Le domaine de recherche 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
Keyword
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).