Sampling degree sequence realizations (DegreeSampling)  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
126853
Type KH
Principal investigator Erdos, Péter
Title in Hungarian Fokszámsorozatok realizációjának mintavételezése (DegreeSampling)
Title in English Sampling degree sequence realizations (DegreeSampling)
Keywords in Hungarian hálózatelmélet, kombinatorika, fokszámsorozatok, mintavételezés
Keywords in English network theory, combinatorics, degree sequences, sampling
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Gyori, Ervin
Mezei, Tamás Róbert
Miklós, István
Soltész, Dániel
Starting date 2017-12-01
Closing date 2019-11-30
Funding (in million HUF) 16.435
FTE (full time equivalent) 3.00
state closed project
Summary in Hungarian
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.
Summary
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.




 

Final report

  
Results in Hungarian
A projekt fő témája a grafikus fokszámsorozatok realizációinak vizsgálata a switch (swap) Markov láncok módszerével. Tradicionálisan ez 3 fő modellt foglal magába: az egyszerű, a páros illetve az irányított modellt. A téma a valós életben (társadalom tudományok, biológia, mérnöki tudományok, fizika, stb.) felmerülő komplex hálózatok vizsgálatában játszik központi szerepet. (8 cikk.) Négy fő területen sikerült eredményeket elérnünk: 1./ Egységesítettük a témában eddig használt módszereket. 2./ A 2018-ig ismert összes pozitív eredmény egy közös általánosítását bizonyítottuk be "P-stabil" fokszám sorozatokra. 3./ Beláttuk, hogy ez az új fogalom még nem jelöl áttörhetetlen akadályt a switch Markov láncokkal kapcsolatban. 4./ Részt vettünk egy véletlen reguláris gráfok növő sorozatát előállító új gráf-dinamika kifejlesztésében. Folytattuk korábbi munkáinkat extremális gráfelméleti problémákon (11 cikk). Több, phylogenetikus hálózatokkal kapcsolatos, kutatásba kapcsolódtunk be. Bevezettük az "orchard" hálózatok fogalmát, és több hálózat típus összefüggőségi tulajdonságait vizsgáltuk lokális operációk használatával (4 cikk). Végezetül több sporadikus kutatásba is bekapcsolódtunk. (További 4 publikáció.) Ezek közül a legfontosabb Miklós István megjelent monográfiája.
Results in English
The main goal of this project was to study the switch (swap) Markov chain based sampling process of the realizations of graphic degree sequences. Traditionally it means three main models: the simple, the bipartite, and the directed degree sequence models. This study emerged from the need of analysing real-life complex networks, originating from social sciences, biology, engineering, physics, etc (8 papers). We achieved four contributions: 1./ Successful unification of the proof techniques in the above mentioned models. 2./ We found a common generalization of all previously known partial results for the class of "P-stable" degree sequence classes. 3./ We have also shown that the P-stability means a natural obstacle for the applicability of the original method, but we proved that this obstacle is not a hard border. 4./ Finally we participated in the introduction of a new, random network growing dynamics that does not change the degree of any, already introduced vertex. So it is suitable for generating a growing series of random regular networks. Furthermore, we continued our research in classical extremal graph theory (11 papers). We also got involved in research on phylogenetic networks. We introduced the class of orchard networks, and studied the connectivity problems of phylogenetic networks under different local operations (4 papers). Finally, we also participated in some sporadic researches, including the writing an important research monograph (by Miklos).
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=126853
Decision
Yes





 

List of publications

  
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




 

Events of the project

  
2017-11-27 08:57:47
Résztvevők változása



Back »