Measurement based analysis of operational paths in complex networks  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
123957
Type FK
Principal investigator Gulyás, András
Title in Hungarian A természet által használt útvonalak tulajdonságainak vizsgálata valós hálózatokban
Title in English Measurement based analysis of operational paths in complex networks
Keywords in Hungarian valós hálózatok, komplex hálózatok, útvonalválasztás, terheléspredikció
Keywords in English real networks, complex networks, path selection, stress predicition
Discipline
Physics (Council of Physical Sciences)100 %
Ortelius classification: Physics
Panel Informatics and Electrical Engineering
Department or equivalent Department of Telecommunications and Media Informatics (Budapest University of Technology and Economics)
Participants Bíró, József
Körösi, Attila
Rétvári, Gábor
Starting date 2017-09-01
Closing date 2021-08-31
Funding (in million HUF) 28.719
FTE (full time equivalent) 5.01
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 hálózattudomány meggyőző eredményeinek hatására, mára jól ismert tény, hogy a
valós hálózatok topológiái sok tekintetben hasonlóak egymáshoz. Legtöbbjük (köztük biológiai, közösségi, Internet és egyéb szervezeti hálózatok) kisvilág tulajdonságú, skálafüggetlen fokszámeloszlású és nagy klaszterezettségű, amelyet valós mérések ezrei tanúsítanak.

Nézetünk szerint, a hálózatokon használt útvonalak tulajdonságai
legalább olyan fontosak, mint maga a topológia. A sejtek stresszre
adott reakciói, a légi közlekedési hálózat stabilitása vagy éppen az
Internet viselkedése nagy mennyiségű forgalom esetén nagy mértékben
azon múlik, hogy a hálózat a jelet/utasokat/csomagokat milyen
útvonalakon vezeti el. Még a különféle gyógyszerek mellékhatása is
nagyban azon múlik, hogy a molekulák milyen láncolatával lép
kölcsönhatásba a szervezetbe kerülés után. Nyilvánvaló fontosságuk
ellenére nem tudunk olyan mérés alapú kutatásról, amely a valós
hálózatokban ténylegesen használt útvonalak tulajdonságainak
feltérképezésére irányult volna.

Pályázatunkkal egy határozott lépést szeretnénk tenni a valós rendszerekben kialakult és a természet által használt útvonalak megértése felé. Projektünkben létező és saját magunk által
létrehozott mérési adatbázisok alapján, melyek a hálózat topológiája
mellett elegendő mennyiségű empirikusan megfigyelt útvonalat is
tartalmaznak, arra keressük a választ, hogy a természet milyen
mechanizmust használ amikor kiválaszt egy konkrét
útvonalat. Megfigyeléseink alapján valósághű szintetikus útválasztási
algoritmusokat javasolunk, melyek lehetővé teszik
hogy komplex rendszerek stresszre adott válaszát sokkal pontosabban
feltérképezzük.

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.

Projektünk fő kérdése, hogy a topológiához hasonlóan a valós
hálózatokon haszált útvonalak természete hasonló-e. Hipotézisünk, hogy
létezik egy közös szabályrendszer melyhez a természet igazodik, amikor
útvonalat választ annak ellenére, hogy a vizsgált hálózatok nagyon
különböző alapokon szerveződnek. A közösségi hálózatok alkotóelemei
emberek, az Internet autonóm hálózatokból áll, a protein hálózatok
fehérjékből, de egy dolog közös: az önszerveződő fejlődés. Ha az
önszerveződés hasonlóvá szervezte ezen hálózatok topológiáját, akkor
van rá esély hogy az útvonalakkal is így tett.

Első lépésünk az ügyben az útvonalak hosszára fog koncentrálni. Sok
szakcikk egyszerűen azt feltételezi, hogy a természet a legrövidebb
utakat használja. Jó okunk van azt gondolni, hogy ez nem minden
esetben van így. Internetes körökben például köztudomású, hogy az
útvonalak nem elhanyagolható része hosszabb mint a lehetséges
legrövidebb. Azt várjuk, hogy valami hasonlót találunk más
rendszerekben is. Megvizsgáljuk az ``útvonalnyúlás'' eloszlását és
amennyiben hasonlítanak akkor kapunk egy megerősítést, hogy jó irányba
haladunk.

Másodsorban, valós méréseink segítségével szeretnénk megérteni a
természet által használt útvonalválasztási szabályokat. Ezen szabályok
ismerete elősegíti majd a hálózatok viselkedésének előrejelzését
specifikus terhelések (pl. stressz) hatásá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!

Az útvonalak jobb megértése hatással lehet az élet számos
területére. Közösségi hálózatokban az információ terjedése ilyen
utakon keresztül valósul meg, így ezek ismerete hatékonyabbá teheti az
emberi közösségeket. Pl. az útvonalak megmutatják azokat a személyeket
akik a stratégiailag fontos útvonalakon vannak, ez pedig sokkal jobb
emberi erőforrástervezést tesz lehetővé. Közlekedési hálózatokban az
emberek által használt útvonalak ismerete kiemelkedően fontos. A
közlekedési kapacitások tervezése sokkal hatékonyabb lehet ezen
információ birtokában. A neurológiai kutatások is profitálhatnak
ebből, hiszen kicsit jobban érthetjük majd, hogy az agy hogyan
dolgozza fel a kapott ingereket.

Sok szakcikk tesz (gyakran nem tudatosan) feltételezéseket
tulajdonságaival kapcsolatban. A leggyakoribb feltevés a legrövidebb
őt feltételezése (ami tudjuk, hogy pl. az Internet esetében nem
teljesen igaz), de vannak mások is pl. háttérhierarchiákon és rejtett
metrikus tereken alapuló útvonalhipotézisek. Viszont nem tudunk olyan
munkáról, ami valós hálózatokból származó útvonalak analízisével
validálta volna ezeket a hipotéziseket. Ennek lehetséges oka, hogy egy
általános kutató mindennapi életének nem része az útvonalak figyelése
és állítgatása. Mi viszont éveket töltöttünk forgalmi utak
konfigurálásával és megfigyelésével az Interneten mielőtt a
hálózattudomány területére tévedtünk. Ezzel talán nálunk van a hazai
pálya előnye ebben a témában.

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.

Sokminden, ami körülvesz minket hálózatnak képzelhető. Elsőként, mi
magunk is sejtekből álló hálózat vagyunk, de hálózatok vannak a
sejtjeinken belül, az agyunkban, sőt mi emberek építőelemei vagyunk a
közösségi hálózatoknak. Áramszolgáltatás, légiközlekedés. vagy pl. az
Internet olyan példák ahol a hálózatot egész konkrétan látni is
lehet. A hálózattudomány mögött álló két évtized minden kétséget
kizáróan meggyőzött minket arról, hogy ezen hálózatok felépítése
meglepően hasonló.

Bár a hálózatok felépítésének hasonlóságát valós mérések ezrei
támasztják alás, arról nagyon keveset tudunk, hogy a
jelek/utasok/csomagok hogyan közlekednek ezekben a
rendszerekben. Pályázatunk témája a hálózatokban használt útvonalak
feltérképezése valós mérések segítségével.Az útvonalak jobb megértése
hatással lehet az élet számos területére. Közösségi hálózatokban az
információ terjedése ilyen utakon keresztül valósul meg, így ezek
ismerete hatékonyabbá teheti az emberi közösségeket. Pl. az útvonalak
megmutatják azokat a személyeket akik a stratégiailag fontos
útvonalakon vannak, ez pedig sokkal jobb emberi erőforrástervezést
tesz lehetővé. Közlekedési hálózatokban az emberek által használt
útvonalak ismerete kiemelkedően fontos. A közlekedési kapacitások
tervezése sokkal hatékonyabb lehet ezen információ birtokában. A
neurológiai kutatások is profitálhatnak ebből, hiszen kicsit jobban
érthetjük majd, hogy az agy hogyan dolgozza fel a kapott ingereket.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

Due to the convincing results of network science, the fact that real networks are similar to each other in many topological characteristics is well known today. Most of them (including many biological, social, transportation, and organizational networks) are small worlds, have scale-free degree distribution and large clustering confirmed by thousands of real measurements.

We argue that the system of operational paths used over these networks is at least that important as topology. The reaction of cells to stress, the stability of airport networks or the behavior of the Internet in case of massive workloads are all fundamentally determined by the operational paths the signals/passengers/packets go
through. Even the effects and side effects of drugs are mainly characterized by the path of molecules which the drug interacts. Despite its clear importance we are not aware of any measurement based studies targeting the characterization of operational paths in real networks.

Our project is aimed at filling this gap and take a step towards the correct interpretation of paths used in real systems. We will make use of existing and build new databases having both the topology of the network and
a satisfactory large number of operational paths over it. From the analysis of these paths we will infer the path selection mechanism used by nature when picking a path. Building upon these observations, we propose a synthetic routing algorithms which can recover the basic statistical properties of used paths in networks. These results enable estimating the reaction of complex systems for stress coming from the outside more accurately.

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.

The main question of our project is whether the operational paths used in real networks are resemble to each other similarly as their topology does. Our main hypotheses is that there are common rules of paths selection that nature uses when picking a path despite the fact that entities that the various real network are build upon are completely different. Social networks are built among humans, the Internet's consists of Autonomous Systems, protein networks contain proteins, but the common ground of these networks is self-organization. If self-organization have driven these networks in such a way that they topology developed extremely similarly, then there is hope that the operational paths over these networks are pretty similar.

The first step we will address is the length of the paths. Many papers in the literature (sometimes implicitly) simply assume that operational paths are the ones with the shortest length. We have good reasons to believe that nature does not always use the shortest path. For example of Internet practitioners it is well known that on the Internet a non-negligible portion of the paths are longer than their counterparts. We expect that we will find something similar in other real networks. So we will check the "stretch" distribution of the measured paths and if they will be similar then we will have light confirmation about the similarity of the paths.

Secondly, we plan to characterize the rules of path selection used in nature based on our ground truth measurements. These rules will enable us to predict the behavior of networks in the presence of specific workloads (e.g. cell behavior upon the insertion of drugs).

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.

Gaining accurate knowledge about the nature of paths in real networks has strong implications in many areas of life. Information on social networks is disseminated over such paths so the capabilities of human communities can be enhanced by this information. The uncovered paths will identify the persons lying on the strategic paths which provides input to more effective human resource planning. In transportation networks the knowledge of paths is of particular importance. The accurate planning of hardware resources (e.g. routers and links in the internet or aircrafts in the airport network) along the most used paths can increase the availability and stability of these networks. Neuroscientists are also among the beneficiaries of path prediction. The models about the processing of information inside the brain can be significantly improved along the information about the structure of paths.

There are many papers in the literature having (sometimes implicit) assumptions regarding the
structure of the paths. The most frequent is the shortest path assumption (which e.g. in case of the Internet seems to be imperfect as a non-negligible portion of Internet paths are longer then their shortest counterpart), but there are many other hypotheses based on underlying hierarchies or hidden metric spaces. However, we are not aware of any works relying on empirical data extracted from real datasets that analyzed the nature of operational paths. One possible reason for this is that working with paths is not an everyday exercise for a regular scientist. However, we have spent many years with configuring and observing paths over the Internet before entering the field of network science. This can give us the home field advantage in this area.

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.

Many thing surrounding us can be considered as networks. We are networks of cells in the first place, but there are networks inside our cells, our brain, but we are also building elements of larger social networks. Power grids, airport systems or the Internet are examples of networks of clear manifestations with all of their nodes and links. The two decades efforts of researching these networks revealed that their topology are stunningly similar in many aspects which creates a common ground to speak about them.

Although the structural resemblance of these networks is well established by thousands of measurements, we are seem to know very little about the paths over which the information/passengers/packet are transferred in these networks. Our proposal targets the direct measurements of such paths in real networks. Gaining accurate knowledge about the nature of paths in real systems has strong implications in many areas of life. Information on social networks is disseminated over such paths so the capabilities of human communities can be enhanced by this information. The uncovered paths will identify the persons lying on the strategic paths which provides input to more effective human resource planning. In transportation networks the knowledge of paths is of particular importance. The accurate planning of hardware resources (e.g. aircrafts in the airport network) along the most used paths can increase the availability and stability of these networks. Neuroscientists are also among the beneficiaries of path prediction. The models about the processing of information inside the brain can be significantly improved along the information about the structure of paths.





 

Final report

 
Results in Hungarian
A projekt keretében sikerült megfelelő adatbázisokat összeállítanunk a valós hálózatokban használt útvonalak tanulmányozásához. Elemzéseink a valós útvonalak meglepő hasonlóságát tárták fel alapvetően különböző területről származó hálózatokban. Sikerült azonosítanunk alapvető törvényszerűségeket az útvonalakkal kapcsolatban, melyeket jól használhatunk a hálózati viselkedés előrejelzésére. Megmutattuk, hogy a valós útvonalak nem szükségképpen a legrövidebb utak a hálózatban, hanem olyan rövid útvonalak, melyek összhangban vannak a hálózat belső logikájával, egy hierarchiával. Ezt a hierarchiát emberi alanyok esetében részletesen tanulmányoztuk, bemutattuk annak alapvető tulajdonságait, illetve hogy a hierarchia használatával az emberi tájékozódás egy bonyolult hálózati rendszerben akár nagyságrendekkel is egyszerűsödhet. Eredményeinket magas szintű nemzetközi konferenciákon és folyóiratokban publikáltuk.
Results in English
In this project, we compiled appropriate databases to study the paths used in real networks. Our analyzes revealed surprising similarities in real paths in networks from fundamentally different areas. We were able to identify basic regularities about paths that we can use well to predict network behavior. We show that real paths are not necessarily the shortest paths in the network but short paths that are consistent with the internal logic of the network, a hierarchy. In the case of human subjects, we have studied this hierarchy in detail, presented its basic properties, and that by using the hierarchy, human orientation in a complex network system can be simplified by orders of magnitude. We have published our results at high-level international conferences and journals.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=123957
Decision
Yes





 

List of publications

 
Csoma A, Korösi A, Rétvári G, Heszberger Z, Bíró J, Slíz M, Avena-Koenigsberger A, Griffa A, Hagmann P, Gulyás A: Routes Obey Hierarchy in Complex Networks, SCI REP 7: (1) Paper 7412., 2017
Attila Kőrösi, Attila Csoma, Gábor Rétvári, Zalán Heszberger, József Bíró, János Tapolcai, István Pelle, Dávid Klajbár, Márton Novák, Valentina Halasi, András Gulyás: A dataset on human navigation strategies in foreign networked systems, SCI DATA 5: (5) Paper 180037. 6 p., 2018
István Pelle, András Gulyás: An Extensible Automated Failure Localization Framework Using NetKAT, Felix, and SDN Traceroute, FUTURE INTERNET 11 : 5 p. 107, 2019
András Gulyás: The role of detours in individual human navigation patterns of complex networks, Proc. of FENS Dynamics of the brain: temporal aspects of computation, Copenhagen, 2019
Heszberger Zalán, Majdán András, Gulyás András, Gyimóthy Tibor, Bilicki Vilmos, Bíró József: Robust Navigable Cores in the Human Brain Networks, Proc. of The 7th International Conference on Complex Networks and Their Applications, 2018
Tapolcai János, Rétvári Gábor, Babarczi Péter, Berczi-Kovács Erika: Scalable and Efficient Multipath Routing via Redundant Trees, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2019
András Gulyás, József Bíró, Gábor Rétvári, Márton Novák, Attila Kőrösi, Mariann Slíz, Zalan Heszberger: The role of detours in individual human navigation patterns of complex networks, PsyArXiv, 2019
Zalán Heszberger, András Gulyás, András Majdán, József Bíró: Robust Navigable Cores in the Human Brain Networks, Proc. of FENS Dynamics of the brain: temporal aspects of computation, Copenhagen, 2019
Gulyás, A., Bíró, J., Rétvári, G. et al.: The role of detours in individual human navigation patterns of complex networks, Sci Rep 10, 1098 (2020)., 2020
Gianni Antichi and Gábor Rétvári: Full-stack SDN: The next big challenge?, ACM SOSR, 2020., 2020
Z. Heszberger, J. Bíró, A. Gulyás, L. Balázs and A. Biró: he Skeleton of Hyperbolic Graphs for Greedy Navigation,, 2019 International Conference on Computational Science and Computational Intelligence (CSCI), Las Vegas, NV, USA, 2019, pp. 476-480, 2019
Zalan Heszberger, Andras Majdan, Andras Gulyas, Jozsef Biro: Greedy Navigational Cores in the Human Brain, The 18th International Conference on Scientific Computing (CSC'20: July 27-30, 2020, USA), 2020
Gulyás András, Heszberger Zalán, Bíró József: PATHS: Why is life filled with so many detours?, Springer/Birkhauser 2020, 2020
Ferenc Mogyorósi; Alija Pašić; Richard Cziva; Péter Revisnyei; Zsolt Kenesi; János Tapolcai: Adaptive Protection of Scientific Backbone Networks Using Machine Learning, IEEE Transactions on Network and Service Management ( Volume: 18, Issue: 1, March 2021), 2021




Back »