 |
Fokszámsorozatok realizációjának mintavételezése (DegreeSampling)
|
súgó 
nyomtatás 
|
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
| |
Projekt adatai |
|
|
| azonosító |
126853 |
| típus |
KH |
| Vezető kutató |
Erdos Péter |
| magyar cím |
Fokszámsorozatok realizációjának mintavételezése (DegreeSampling) |
| Angol cím |
Sampling degree sequence realizations (DegreeSampling) |
| magyar kulcsszavak |
hálózatelmélet, kombinatorika, fokszámsorozatok, mintavételezés |
| angol kulcsszavak |
network theory, combinatorics, degree sequences, sampling |
| megadott besorolás |
| Matematika (Műszaki és Természettudományok Kollégiuma) | 100 % | | Ortelius tudományág: Kombinatorika |
|
| zsűri |
Matematika–Számítástudomány |
| Kutatóhely |
HUN-REN Rényi Alfréd Matematikai Kutatóintézet |
| résztvevők |
Gyori Ervin
Mezei Tamás Róbert
Miklós István
Soltész Dániel
|
| projekt kezdete |
2017-12-01 |
| projekt vége |
2019-11-30 |
| aktuális összeg (MFt) |
16.435 |
| FTE (kutatóév egyenérték) |
3.00 |
| á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.
A modern hálózatkutatás egy tipikus módszere a gyakorlatban felmerülő hálózatok összehasonlítása a kutató által definiált paraméterek halmazának (S) megfelelően generált hálózatok mintájával. A mintavételezés megvalósításához a következő kérdésekre kell válaszolni: Jelölje G(S) a paraméter halmazt kielégítő összes lehetséges megoldás halmazát, akkor
1. Létezés: Milyen feltételek mellett lesz G(S) nem üres?
2. Konstrukció: Hogyan hozzuk létre G(S) egy elemét?
3. Listázás: Hogyan építhetjük fel az összes megoldást?
4. Mintavételezés: Hogyan mintavételezzünk G(S)-ből adott eloszlás szerint?
5. Leszámlálás: Mekkora G(S) mérete?
A legegyszerűbb paraméter az előírt fokszámsorozat. Erre az 1-2 kérdést korábban megválaszolták, a 3-t mi oldottuk meg. A technológiai ill. a social science alkalmazásokban felmerülő, azonos fokszámsorozatokkal rendelkező hálózatok elkülönítésére 2008-ban bevezetett JDM modellre 1 és 2 megoldása ismert volt. Mi oldottuk meg a 3 és 4 -et erre az esetre, egy 2015-ös cikkben, mely a pályázat alapja. A 4 megoldására egyelőre az importance sampling módszerét alkalmaztuk, de speciális esetekre egy Markov Chain Monte Carlo (MCMC) alapú módszert is sikerült kidolgoznunk.
Tovább kívánjuk fejleszteni a mindkét fenti osztály 4-5 -re eddig elért, MCMC alapú, részleges eredményeinket. Kidolgoztunk egy már alkalmazott dekompozíciós eljárást, célunk ennek továbbfejlesztése. További célunk újabb, a gyakorlatban alkalmazható megszorított fokszámsorozatos feladatok megfogalmazása és vizsgálata 1-5 alapján. Ebbe a körbe tartozik a JDM feladat is, de számos további lehetőség is ismert. Ezek egyike a PAM modell, ezekre is vannak már részleges eredményeink.
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.
A hálózatkutatás intenzíven fejlődik napjainkban, köszönhetően a nagyszámú alkalmazási lehetőségeknek, többek között a szociológiában, közgazdaságtanban, logisztikában, kommunikációban, biológiában, klímakutatásban, de még a kozmológiában is. Ezen hálózatok rendkívül komplexek és első ránézésre nagyon hasonlóak, a klasszikus gráfelméleti modellek nem tudták megkülönböztetni őket. Ezért új modellek kerültek bevezetésre amelyek alapján azután szintetikus hálózat mintákat generálnak. Ezeket aztán összehasonlítják a vizsgált hálózatokkal és eldöntik alkalmazhatóságukat.
Ezen módszer akkor megbízható, ha a szintetikus minta tényleg jól reprezentálja a modell megoldás terét. Ennek eldöntéséhez pedig az 1-5 feladatokat kell megválaszolni. A klasszikus fokszámsorozat esetén a 4-5 kérdésekre egyelőre csak részeredmények ismertek. A JDM modell esetén hasonló a helyzet. Egyéb modellekre (például az általunk bevezetett váz-gráffal (skeleton graph) leírt megszorított fokszámsorozatok esetén még kevesebb ismert.
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 hálózatkutatás fontos szerepet tölt be több tudományágban, többek között szociológiában, közgazdaságtudományban, logisztikában, kommunikációkutatásban, biológiában, éghajlatkutatásban és még kozmológiában is. Ezeken a területeken megjelenő hálózatok első ránézésre hasonlóak, de a finom struktúrájuk nagyon különbözik. Egy híres példa a biokémiai regulációs hálózatok és a szociológiai hálózatok. A fokszámeloszlásuk megegyezik, de míg a szociológiai hálózatokban a magas fokú pontok zömében egymással vannak összekötve, addig a regulációs hálózatokban a magas fokú pontok zömében alacsony fokúakkal. Ezen jelenség leírására vezették be a közös fokszám mátrixot, amely megadja, hogy adott fokú pontok összesen hány éllel vannak összekötve. Ilyen mátrixok előállítására a kutatócsoportunk publikált először hibáktól mentes bizonyításokat, majd megadtunk mintavételezési eljárásokat is.
Asszortivitást egyéb kényszerfeltételekkel is meg lehet adni. Ilyen például a partíció szomszédsági mátrix, amely adott partíciók közötti élek számát adja meg, valamint a váz-gráf kényszerfeltételek. Ezekben a modellekben már a megoldások létezésének a kérdése sem triviális. Bebizonyítottuk, hogy a kényszerfeltételek szigorítása mentén nagyon hamar NP-teljes problémákba futunk bele. Fontos kérdés, hogy mely kényszerfeltételek mellett egyszerű a létezés eldöntésének a problémája és mely feltételek mellett nehéz.
Az eredményeinken már most jól mérhető visszhangja van a hálózatkutatásban, a matematikában mind kombinatorika, mind elméleti számítástudomány területén, mind a modern statisztika területén, azon felül a komplex rendszerek fizikájában, bioinformatikában és szociológiában is. Reményeink szerint további kutatásaink is hasonló hatást fognak kiváltani.
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.
A hálózatkutatás intenzíven fejlődik napjainkban. A megjelenő komplex hálózatok nagyon hasonlóak első ránézésre, de közelebbről vizsgálva számos különbség van bennük. Fontos kérdés ezen különbségek megértése, és a kutatásaink ehhez szeretne hozzájárulni azzal, hogy adott kényszerfeltételeknek megfelelő hálózatokat szeretnénk előállítani. Ezen mesterséges hálózatok generálásával lehetőség nyílik a valódi és mesterséges hálózatok összehasonlítására és statisztikai hipotézisvizsgálatára.
A leggyakoribb kényszerfeltétel a fokszámsorozat előírása de számos egyéb lehetőség is felderítésre került.
A kutatásaink remélhetőleg hatással lesznek mind a matematikai tudományok fejlődésére (azon belül is elsősorban a kombinatorika, elméleti számítástudomány és a statisztika területére), mind a komplex rendszerek fizikája, szociológia, bioinformatika és más további tudományágak fejlődésére.
| angol összefoglaló Summary of the research and its aims for experts
Describe the major aims of the research for experts.
In modern network theory one typical approach is to compare the networks emerged in practice with sets of networks, synthetically generated on the basis of different sets S of parameters. For a good sampling process the following questions should be answered: Let G(S) be the set of all solutions compatible with S, then
1. Existence: under what conditions is G(S) non empty?
2. Construction: how can you build at least one element?
3. Listing: how can you build all elements?
4. Sampling: how to sample G(S) by some given distributions?
5. Counting: how to compute or estimate |G(S)|?
The simplest constraint is the degree sequence (DS) of the graph. For this model the 1 and 2 were solved already in the sixties, while we answered 3. Points 4 and 5 are only partly solved. In 2008 a new network model was introduced to separate networks having the same degree sequences but were emerged from different sources. For this Joint Degree Matrix model 1 and 2 were solved quickly. Our group solved problems 3 and 4, the latter with the method of importance sampling. (This often cited paper from 2015 is the basis of our grant proposal.) For the special case of balanced JDM realizations we also developed a Markov Chain Monte Carlo (MCMC) based sampling method.
In general we want to develop further our partial MCMC sampling results on these models. We have introduced a decomposition technique to study fast mixing MCMC methods. We want to further generalize this technique.
There are several refinements of DS constraints: Joint Degree Matrix, Partition Adjacency Matrix, skeleton graph constraints, etc. We want to study these classes in the framework of questions 1-5.
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.
Network science has been experiencing extensive growth with applications in social sciences, economics, transportation infrastructures (energy and materials), communications, biology, climate, and even in cosmology. The corresponding networks describe extremely complicated systems that at first sight look very similar. Unfortunately the classical graph theoretical models were unable to differentiate them. Therefore new models are introduced and on this basis large ensembles are generated synthetically. Then these ensembles are compared to the original networks and the applicability of the model is decided on the basis of these studies.
This method is applicable in the case, if the generated samples is well representing the solution space of the model. And for to decide it’s quality, questions 1-5 should be addressed. For the classical degree sequence model questions 4 and 5 have partial solution only. For the JDM model the situation is similar. For other restricted degree sequence models (like, for example, the skeleton graph model) even less is known
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.
Network science provides a powerful research environment for very diverse scientific disciplines. It is used, naming just some, in social sciences, economics, transportation infrastructures (energy and materials), communications, biology, climate, and even in cosmology.
The appearing networks look often alike, but their finer structures depend firmly on the problem under investigation. One famous example is the different assortativity properties of real-life social and biological networks. They may share their DS but in the first kind of networks typically there are a few very high degree vertices and many low degree vertices, where a vertex is likely to be adjacent to vertices of similar degree – this is called highly assortative. The second kind of networks are generally disassortative (in which low degree vertices tend to attach to those of high degree). To deal with this phenomenon the Joint Degree Matrix model was introduced, but there were several flawy papers about it. Our group provided the first correct proofs for the fundamental properties of the model. We also developed methods to list all solutions and making proper sampling procedure. So now the model is properly applicable.
Other disciplines may require other restricted DS models. Our group already developed some of them, for example the Partition Adjacency Matrix and its small-scale version, the skeleton graph restriction. In these models already the existence problem is highly non-trivial. We successfully proved that the restricted degree models soon hit the NP-completeness barrier. The development of the other technical tools is still ahead of us. The completed toolset will probably have high impact on network research.
With these researches we are alone in Hungary, while the newly developed tools would be useful for the research community. In general our group is in the forefront of the research connected to DS problems. We already published several research article in well regarded international journals
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.
Network science is experiencing extensive growth with widespread applications. At first sight the corresponding complex systems look very similar. Our goal is to discover the differences and fully understand their behavior. Our understanding of them is typically based on limited information. Therefore we need methods that exploit the available information to the maximum. But also, the methods should not cause uncontrolled biases.
(I) We want to understand to what extent a particular set of measures (from the observed or assumed data) determine other properties of a class of networks. (II) We want to understand how processes on networks (such as information flow, spread of epidemics, etc.) are affected by a particular set of measures and nothing else. Here "limited information" refers to the fact that we cannot collect enough conclusive knowledge about most networks.
In all the above the available data or information act as constraints. We are interested in finding constrains related to degree sequences. To deal with the related problems we apply classic combinatorial technics. The results will help researchers from different disciplines to build random ensembles to study their subjects.
|
|
|
|
|
|
|
|
| |
Közleményjegyzék |
|
|
| Erdős Péter L. ; A. Francis ; L. van Iersel ; Mezei Tamás Róbert: The tree-based, rooted binray phylogentics networks are closed under rNNI moves, in preparation, 2020 | | Colucci L., Erdős Péter L., Gyóri Ervin, Mezei Tamás Róbert: Terminal- Pairability in Complete Bipartite Graph of Non-Bipartite Demands, Theoretical Computer Science, DOI: 10.1016/j.tcs.2018.12.007, 2018 | | Ergemlidze B. , Győri Ervin, A. Methuku: Characterizing directed graphs with every edge in a fixed number of cycles, Manuscript, 2018 | | Győri Ervin , Katona Y. Gyula, Papp László F.: Optimal pebbling number of the square grid, submitted to Graphs and Combinatorics, arXiv:1810.05266, 2018 | | Győri Ervin, M.D. Plummer, Dong Ye, Xiaoya Zha: A Cycle Traversability Theorem for Claw-free Graphs, submitted to Combinatorica, arXiv 1803.04466v1, 2018 | | Colucci L., Erdős Péter L., Győri Ervin, Mezei Tamás Róbert: Terminal- Pairability in Complete Bipartite Graph of Non-Bipartite Demands, Theoretical Computer Science, 775, 16--25., 2019 | | Colucci L., Győri Ervin: On L(2,1)‐labelings of oriented graphs, arXiv:1902.05467, 2019 | | Colucci L., Győri Ervin, A. Methuku: Edge colorings of graphs without monochromatic stars, arXiv:1903.04541, 2019 | | Erdős Péter L., M. Ferrara, S.G. Hartke: Navigating Between Packings of Graphic Sequences, Discrete Applied Mathematics, 266 252--258., 2019 | | Erdős Péter L., C. Greenhill, Mezei Tamás Róbert, Miklós István, Soltész Dániel, Soukup Lajos: The mixing time of switch Markov chains: a unified approach, arXiv:1903.06600, 2019 | | Erdős Péter L., C. Greenhill, Mezei Tamás Róbert, Miklós István, Soltész Dániel, Soukup Lajos: Mixing time of the Swap Markov chain and P-Stability, Proc. EUROCOMB 2019, Acta Math. Univ. Comenianae, 88 (3) 659--665., 2019 | | Erdős Péter L., Győri Ervin, Mezei Tamás Róbert, Miklós István, Soltész Dániel: A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing, arXiv:1909.02308, 2019 | | Erdős Péter L., C. Semple, M. Steel: A Class of Phylogenetic Networks Reconstructable from Ancestral Profiles, Mathematical Biosciences, 313, 33-40., 2019 | | Erdős Péter L.; L. van Iersel; M. Jones: Not all phylogenetic networks are leaf-reconstructible, Journal of Mathematical Biology, 79 (5) 1623--1638, 2019 | | Fang, Chunqiu ; Győri Ervin ; Xiao, Jimeng: Minimal colorings for properly colored subgraphs in complete graphs, arXiv:1911.04358, 2019 | | Fang, Chunqiu ; Győri Ervin, Mei Lu ; Jimeng Xiao: On the anti‐Ramsey number of forests, arXiv:1908.04129, 2019 | | Győri Ervin, Nika Salia, Oscar Zamora: Connected Hypergraphs without long Berge paths, arXiv:1910.01322, 2019 | | Győri Ervin, Nika Salia, Casey Tompkins, Oscar Zamora: Turan numbers of Berge trees, arXiv:1904.06728, 2019 | | Miklós István: Computational Complexity of Counting and Sampling, Chapman and Hall/CRC , ISBN 9781138035577, 2018 | | Győri Ervin, Nathan Lemons, Nika Salia, Oscar Zamora: The Structure of Hypergraphs without long Berge cycles, arXiv:1812.10737, 2018 | | B. Ergemlidze, Győri Ervin, A. Methuku: Characterizing directed graphs with every edge in a fixed number of cycles, Manuscript, 2018 | | Győri Ervin, M.D. Plummer, Dong Ye, Xiaoya Zha: A Cycle Traversability Theorem for Claw-free Graphs, submitted to Combinatorica, 2018 | | Győri Ervin , Katona Y. Gyula, Papp László F.: Optimal pebbling number of the square grid, submitted to Graphs and Combinatorics, 2018 | | Erdős Péter L.; L. van Iersel; M. Jones: Not all phylogenetic networks are leaf-reconstructible, arXiv 1803.03197, submitted, 2018 | | Erdős Péter L, Mezei Tamás Róbert, Miklós István, Soltész Dániel: Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLOS One, 13 (8) e0201995, 2018 | | Erdős Péter L., M. Ferrara, S.G. Hartke: Navigating Between Packings of Graphic Sequences, Discrete Applied Mathematcs, in press, 2018 | | Janssen R., Jones M., Erdős Péter L., van Iersel L., Scornavacca C.: Exploring the tiers of rooted phylogenetic network space using tail moves, Bulletin of Mathematical Biology, 80, 2177–-2208, 2018 | | Erdős Péter L., Mezei Tamás Róbert, Miklós István: Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences, arXiv 1712.01709, 21 oldal, 2017 | | Hartarsky I., Mezei Tamás Róbert: Computing the Difficulty of Critical Bootstrap Percolation Models is NP-hard, arXiv 1809.01525v1, 13 oldal, submitted, 2018 | | Soltész Dániel: Even cycle creating paths, arXiv 1801.00737v1, 10 oldal, submitted, 2018 | | Harcos Gergely, Soltész Dániel: New Bounds On Even Cycle Creating Hamiltonian Paths Using Expander Graphs, arXiv:1904.04601, 2019 | | S. Kharel, Mezei Tamás Róbert, S. Chung, Soltász Dániel, Erdős Péter L., Z. Toroczkai: Degree-preserving network growth, manuscript, 2019 | | Krenn M., Gu X., Soltész Dániel: Questions On The Structure Of Perfect Matchings Inspired By Quantum Physics, Proceedings of the 2nd Croatian Combinatorial Days, DOI:10.5592/CO/CCD.2018, 2019 | | Soltész Dániel: Even cycle creating paths, Journal of Graph Theory, https://doi.org/10.1002/jgt.22490, 2019 |
|
|
|
|
|
|
|
|
|
