Véleltlen gráfok és korrelált perkolációs modellek  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
121165
típus PD
Vezető kutató Ráth Balázs
magyar cím Véleltlen gráfok és korrelált perkolációs modellek
Angol cím Random graphs and correlated percolation models
magyar kulcsszavak önszerveződő kritikus viselkedés, perkoláció, véletlen bolyongás, kölcsönható részecskerendszer
angol kulcsszavak self-organized criticality, percolation, random walk, interacting particle system
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Valószínűségelmélet
zsűri Matematika–Számítástudomány
Kutatóhely Sztochasztika Tanszék (Budapesti Műszaki és Gazdaságtudományi Egyetem)
projekt kezdete 2016-10-01
projekt vége 2019-09-30
aktuális összeg (MFt) 15.264
FTE (kutatóév egyenérték) 2.10
állapot lezárult projekt
magyar összefoglaló
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

1. Véletlen gráfok:

1.1: Az erdőtűz-modellt [Ráth, Tóth, 2009, EJP] és a fagyott perkolációs modellt [Ráth, 2009, JSP] vizsgálni:
(i) bizonyítani, hogy az erdőtűz-modell gráfja inhomogén véletlen gráf, lásd [Bollobás, Janson, Riordan, RSA, 2007].
(ii) az összefüggő komponensek dinamikájára határeloszlás-tételt bizonyítani, a "multiplicative coalescent" [Aldous, 1997, AoP] módosításával.
(iii) A fagyott perkolációs modell villámcsapási rátája és a leégett komponensek mérete közti összefüggésre képletet adni, lásd [Ráth, 2009, JSP], Conjecture 1.1.

1.2: a [Lalley, PTRF, 2009]-ben definiált egydimenziós "falu"-gráfmodellen értelmezett szuperkritikus SIR járványterjedést vizsgálni.
(i) a SIR járvány metastabilis állapotát jellemezni.
(ii) vizsgálni, hogy mi a legolcsóbb stratégia arra, hogy a metastabilis állapotból indítva stabilis (gyógyult) állapotba jussunk.
(iii) Beazonosítani, hogy a falvak és a lakosok számának függvényében mely esetekben lesz fertőzés minden faluban.

2. Korrelált perkolációs modellek:

2.1: A [Sznitman, 2010]-ben definiált "random interlacement" modell I^u gráfjának geometriáját vizsgálni, ha u<<1, d>=5.
(i) Belátni, hogy hogy az I^u gráf-metrikája forgásinvariánssá válik, amint u->0, lásd [Cerny, Popov, 2012] Remark 1.2.
(ii) megtalálni, hogy milyen sebességgel konvergál az I^u gráf Bernoulli-perkolációs küszöb-értéke 1-hez, amint u->0, lásd [Ráth, Sapozhnikov, 2013, EJP].

2.2: a [Ráth, Valesin, 2016+, AoP] perkolációs modelljére (azaz a "voter model" stacionárius eloszlásaira) a
[Popov, Teixeira, JEMS, 2015] eredményeihez hasonló dekorrelációs egyenlőtlenségeket belátni.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

1. Véletlen gráfok:

1.1: Mi a erdőtűz-modell és a fagyott perkolációs modell önszerveződő kritikus viselkedésének pontos mechanizmusa?
(i) Milyen inhomogén véletlen gráfot látunk az erdőtűz-modellre nézve egy adott pillanatban?
(ii) Ugyanaz-e a skálalimesze az erdőtűz-modell és a fagyott perkolációs modell nagy komponenseinek?
(iii) Mi az összefüggés a villámcsapási ráta és a leégett komponensek nagysága közt?

1.2: Mikor és milyen módon hal ki a szuperkritikus SIR járvány az egydimenziós "falu"-modellben?
(i) Milyen alakú a metastabil állapot állóhulláma?
(ii) Mi a legkevésbé költséges stratégia arra, hogy a járvány a metastabilis állapotból stabilis (gyógyult) állapotba jusson?
(iii) A falvak és lakosok számának függvényében mikor terjed a fertőzés át minden falura?

2. Korrelált perkolációs modellek:

2.1: Milyen hatással van a "véletlen gubanc" (random interlacement) geometriájára az, ha a gubanc sűrűsége nullához tart?
(i) Forgás-invariánssá válik-e a gubanc makroszkopikus belső geometriája, amint a gubanc sűrűsége nullához tart?
(ii) A ritka gubanc milyen kicsi hányadát kell törölni ahhoz, hogy véges nagyságú darabokra essen szét?

2.2: Milyen hatással van a "voter model" stacionárius állapotában az azonos állapotú egyedek makroszkopikus mintázatára
model korrelált jellege?
Beletartozik-e a "voter model" is a korrelált perkolációs modellek azon osztályába, amelyekre olyan erős dekorrelációs
egyenlőtlenségek igazak, mint pl. a "véletlen gubanc"-ra?

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A kutatásom kérdéseit valódi jelenségek ihlették, és a megoldási módszereim is gyakran statisztikus fizikai eredetűek. A célom ezen jelenségek kellően egyszerű modelljeinek matematikai precizitású vizsgálata.

A kutatási témáim és a jelenségek, amit modelleznek:

1.1 : erdőtűz-modell: önszerveződő kritikus viselkedés
1.2 : szuperkritikus SIR járvány-modellek: metastabilitás
2.1 : "véletlen gubanc" (random interlacements): inhomogén közegben terjedő folyadék által átnedvesített térrész geometriája (perkoláció)
2.2 : "voter model": egymással versengő fajok térbeli eloszlásának makroszkopikus mintázatait modellezi

A tervezett eredmények elméleti jelentősége, címszavakban:

1.1 : a modell-specifikus részletek mögött rejlő univerzális viselkedés körülírását adná
1.2 : annak a leírása lenne, hogy mi a legevésbé költséges stratégia arra, hogy a modellbeli járvány megszűnjön
2.1 : az átnedvesedett térrész forgás-invarianciája más perkolációs modellekben híres nyitott kérdést oldana meg
2.2 : univerzális viselkedésre utaló eredmény és egyúttal hasznos elméleti eszköz lenne

A kutatási projektjeim nagy részét külföldi társszerőimmel közösen tervezem véghezvinni. Ez, valamint a kutatási eredményeim elismert folyóiratokban való publikációja és jelentős konferenciákon való ismertetése hozzájárul
a kutatói közegem nemzetközi elismertségének fenntartásához is.

A nemzetközi élvonalt érdeklő kutatási témákkal foglalkozom, és ez időnként valóban versenyhelyzeteket idéz elő, de a tapasztalatom szerint a "versenytársaimmal" egymás iránt táplált kölcsönös tisztelet olykor "harcostárssá" tesz minket a megoldatlan probléma ellen vívott csatában.

A BME-n végzett oktatási tevékenységem részeként 2015-2016-ban a kutatásomba illeszkedő témájú színvonalas MSc szakdolgozatok témavezetője voltam. Ezt a jövőben is folytatni fogom, ezen kívül a TDK-témavezetés, illetve amint az egyetemi pozícióm lehetővé teszi, a PhD-témavezetés is ambícióm. A kutatási területeim módszereit és nyitott kérdéseit nagy kedvvel fogom a leendő doktoranduszaimmal megosztani.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

Matematikus vagyok, a kutatásom tehát gondolatkísérlet, amely az empirikus kisérletek kiegészítéséül szolgál -- az elméleti és gyakorlati kutatás hitelesítik egymást és utat mutatnak egymásnak.

A kutatásom elméleti jellegű, de a kérdéseit valódi jelenségek ihlették. A célom ezen jelenségek kellően egyszerű modelljeinek matematikai precizitású vizsgálata -- ez a precizitás ugyan sok energiabefektetést igényel, de a gondolatkísérlet eredményének hitelességét csak így lehet garantálni.

Az általam vizsgált matematikai modellek nevei is az őket ihlető jelenségekről árulkodnak. A következő kérdéseket vizsgálom:

1. Véletlen gráfok:

1.1: erdőtűz-modell: az önszerveződő kritikus viselkedés jelenségét hivatott modellezni: az állandóan növekvő és ritka villámcsapások által gyújtott tüzektől tizedelt erdőben mi az összefüggés a villámcsapási ráta és a leégett erdő-részek nagysága közt?

1.2: járványterjedés-modell: falvak sorakoznak egy út mellett. A lakosok közt dúló járvány egy látszólag megállíthatatlan hullámként terjed tovább. Mi a legkevésbé költséges stratégia arra, hogy a járvány megálljon?

2. Korrelált perkolációs modellek:

2.1: "véletlen gubanc" (random interlacements): egy pórusoktól átszőtt közegben terjedő folyadék által átnedvesített térrész geometriáját vizsgáljuk. Igaz-e, hogy az átnedvesített térrész szinte gömb alakú?

2.2: "voter model": egymással versengő politikai pártok harcolnak egy óriási sakktáblán ülő szavazókért. Az azonos párt által uralt térrészek spontán lokális klaszterekbe hajlamosak rendeződni. Milyen erős kapcsolatot teremt ez a távoli térrészeken megfigyelhető makroszkopikus mintázatok között?
angol összefoglaló
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

1. Random graphs:

1.1: to study the forest fire model [Ráth, Tóth, 2009, EJP] and the frozen percolation model [Ráth, 2009, JSP]:
(i) to prove that the graph of the forest fire model is an inhomogeneous random graph, see [Bollobás, Janson, Riordan, RSA, 2007].
(ii) to find the scaling limit of the dynamics of connected components by modifying the "multiplicative coalescent" [Aldous, 1997, AoP].
(iii) to express the size of burnt components as a function of the lightning rate, see [Ráth, 2009, JSP], Conjecture 1.1.

1.2: to study supercritical SIR epidemics on the one dimensional "village" graph model of [Lalley, PTRF, 2009].
(i) to characterize the metastable state of the SIR epidemic.
(ii) to find the cheapest strategy for reaching a stable (healed) state from the metastable state.
(iii) to identify the cases where infection reaches all villages as a function of the number of villages and villagers.

2. Correlated percolation models:

2.1: to study the geometry of [Sznitman, 2010]'s "random interlacement" graph I^u for u<<1, d>=5.
(i) showing that the graph metric of I^u becomes rotationally invariant as u->0, see [Cerny, Popov, 2012], Remark 1.2.
(ii) to find the rate of convergence to 1 of the Bernoulli percolation threshold of the graph I^u as u->0, see [Ráth, Sapozhnikov, 2013, EJP].

2.2: to prove decoupling inequalities similar to [Popov, Teixeira, JEMS, 2015] for voter model percolation [Ráth, Valesin, 2016+, AoP].

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

1. Random graphs:

1.1: What is the precise mechanism behind the self-organized criticality of the forest fire and frozen percolation models?
(i) What kind of inhomogeneous random graph do we see if we look at the forest fire model at a given moment?
(ii) Do the large component sizes of the forest fire and frozen percolation models have the same scaling limit?
(iii) What is the relation between the lightning rate and the size of burnt components?

1.2: When and how does the supercritical SIR epidemic stop in the one dimensional "village" model?
(i) What is the shape of the travelling wave corresponding to the metastable state?
(ii) What is the least costly strategy for the epidemic to reach a stable (healed) state from the metastable state?
(iii) As a function of the number of villages and villagers, when does the infection reach every village?

2. Correlated percolation models:

2.1: What effect does it have on the geometry of "random interlacements" if the density of the interlacement goes to zero?
(i) Does the macroscopic internal geometry of the interlacement become rotationally invariant as the density goes to zero?
(ii) How small fraction of the interlacement should we delete in order to disconnect it into finite connected components?

2.2: What effect does the correlated nature of the stationary state of the voter model have on the large-scale patterns
of voters with the same opinion?
Does the voter model belong to the class of correlated percolation models for which we have decoupling inequalities as powerful as for, e.g., random interlacements?

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

The questions of my research are inspired by real-world phenomena and the methods of my solutions often come from statistical physics. My goal is to analyze simple enough models of these phenomena with mathematical rigor.

My research topics and the phenomena that they model:

1.1 : forest fire model: self-organized criticality
1.2 : supercritical SIR epidemics: metastability
2.1 : random interlacements: the geometry of the wet region created by water filtrating through an inhomogeneous material (percolation)
2.2 : voter model: it models the macroscopic spatial patterns created by the competition of biological species

Theoretical relevance of the planned results, in a nutshell:

1.1 : it would give a description of the universal behavior underlying the model-specific details
1.2 : it would give a description of the least costly strategy for the epidemic to stop
2.1 : it would show the rotational invariance of the wet region, a famous open question in other percolation models
2.2: it would be useful theoretical result that also indicates universal behavior

I plan to carry out the majority of my research projects with my international collaborators. This, as well as the the publication of my results in quality journals and the presentation of my results in notable conferences will contribute to the maintenance of the international recognition of my research environment.

I am involved in research that fits well into the international cutting edge, and sometimes this creates competition, but, according to my experience, the mutual respect between me and my "competitors" sometimes makes us "comrades" fighting in the battle against the unsolved problem.

As a part of my teaching activity at BME, in 2015-2016 I was the supervisor of two MSc theses with topics that fit into my research spectrum. I will continue doing this in the future. It is also my ambition to become a supervisor of students entering the National Scientific Students Associations Conference, and as soon as my position at BME permits, I would like to supervise PhD students. I will share the methods and open questions of my field of research with my to-be PhD students with great enthusiasm.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

I am a mathematician, thus my research involves thought experiments, which complement empirical experiments -- theoretical and applied research validate and guide each other.

My research is theoretical, but the questions are inspired by real-world phenomena. My goal is to analyze simple enough models of these phenomena with mathematical rigor -- this rigor requires time and dedication, but this is the only way to guarantee the validity of the result of the thought experiment.

The mathematical models that I work with have telltale names. These are the questions that I study:

1. Random graphs:

1.1: forest fire model: it models the phenomenon called self-organized criticality: a permanently growing forest is occasionally hit by lightnings. What is the relation between the rate of lightnings and the size of the burnt forest patches?

1.2: epidemic model: we consider villages along a road. An epidemic sweeps through the villagers like an unstoppable wave. What is the least costly strategy for the epidemic to stop?


2. Correlated percolation models:

2.1: random interlacements: water percolates through a porous material. We study the geometry of the wet region. Does it look like a sphere?

2.2: voter model: political parties compete for voters that sit on a large chessboard. The regions ruled by the same political party tend to spontaneously form local clusters. How strong dependence does this effect create between the macroscopic patterns of distant regions?





 

Zárójelentés

 
kutatási eredmények (magyarul)
Egy új és egyszerű formulát találtunk, ami karakterizálja a binomiális Erdős-Rényi gráf egy összefüggő komponensének méretének eloszlását [Ráth, 2018, ECP]. Ezt az eredményt felhasználjuk olyan skálalimeszek levezetésében, amelyek leírják a teljes gráfon értelmezett enyhén szubkritikus fagyott perkolációs modell önszerveződő kritikus viselkedését irányító erőket [Ráth, Yeo, preprint]. Kapcsolatot teremtünk az inhomogén véletlen gráfok elmélete és a mean field erdőtűz-modell elmélete közt a [Crane, Ráth, Yeo, 2018, benyújtva] cikkünkben, amiben levezetünk egy olyan mértékeken ható differenciálegyenletet is, amely leírja a kapcsolódó többtípusú elágazó folyamat típus-eloszlásának időfejlődését. Két olyan, Z^d-n értelmezett kölcsönható részecskerendszer stacionárius eloszlásának perkolatív tulajdonságait vizsgáljuk, melynek a kölcsönhatási rádiusza nagy: az egyik a voter model [Ráth, Valesin, 2017, ECP], a másik a contact process [Ráth, Valesin, preprint]. Mindkét esetben azt bizonyítjuk, hogy a kritikus sűrűség konvergál a Z^d rácson értelmezett Bernoulli perkoláció kritikus sűrűségéhez, amint a kölcsönhatási sugár végtelenhez tart. A contact process esetében ezzel megválaszoljuk a [Liggett, Steif, 2006, AIHP] cikk egyik nyitott kérdését (a kiterjedt esetben). Bizonyítjuk, hogy a bináris fán értelmezett fagyott perkolációs folyamat nem endogén [Swart, Ráth, Terpai, 2019, benyújtva], megválaszolva ezzel [Aldous, 2000, MPCPS] egyik nyitott kérdését.
kutatási eredmények (angolul)
We derive a new simple formula that characterizes the distribution of the size of the connected component of a fixed vertex in the binomial Erdős-Rényi random graph [Ráth, 2018, ECP]. This result is used in the derivation of various scaling limits that describe the driving forces behind the self-organized criticality of slightly subcritical frozen percolation on the complete graph [Ráth, Yeo, preprint]. We connect the theory of inhomogeneous random graphs with that of the mean field self-organized critical forest fire model in [Crane,Ráth,Yeo, 2018, submitted] and derive a measure-valued differential equation that governs the time evolution of the type distribution of the associated multi-type branching process. We study the percolative properties of the stationary distributions of two interacting particle systems on Z^d with spread-out interactions: the voter model [Ráth, Valesin, 2017, ECP] and the contact process [Ráth, Valesin, preprint]. In both cases, we show that the critical density converges to that of Bernoulli percolation on Z^d as the interaction radius goes to infinity. In the case of the contact process, this solves a variant of an open question of [Liggett, Steif, 2006, AIHP]. We prove that frozen percolation on the binary tree is nonendogenous [Swart, Ráth, Terpai, 2019, submitted], solving an open question posed by [Aldous, 2000, MPCPS].
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=121165
döntés eredménye
igen





 

Közleményjegyzék

 
Edward Crane, Balázs Ráth, Dominic Yeo: Age evolution in the mean field forest fire model via multitype branching processes, benyújtva, 2018
Balázs Ráth, Jan M. Swart, Tamás Terpai: Frozen percolation on the binary tree is nonendogenous, benyújtva, 2019
Balázs Ráth, Daniel Valesin: On the threshold of spread-out voter model percolation., Electron. Commun. Probab. Volume 22 (2017), paper no. 50, 12 pp., 2017
Balázs Ráth: A moment-generating formula for Erdős-Rényi component sizes, submitted for publication, 2017
Vladas Sidoravicius, Balázs Ráth: One-dimensional Multi-particle DLA -- a PDE approach, submitted for publication, 2017
Ráth Balázs: A moment-generating formula for Erdős-Rényi component sizes, Electron. Commun. Probab., Volume 23 (2018), paper no. 24, 14 pp., 2018
Balázs Ráth, Dominic Yeo: The window process of slightly subcritical frozen percolation, preprint, 2019




vissza »