A természet által használt útvonalak tulajdonságainak vizsgálata valós hálózatokban
Angol cím
Measurement based analysis of operational paths in complex networks
magyar kulcsszavak
valós hálózatok, komplex hálózatok, útvonalválasztás, terheléspredikció
angol kulcsszavak
real networks, complex networks, path selection, stress predicition
megadott besorolás
Fizika (Műszaki és Természettudományok Kollégiuma)
100 %
Ortelius tudományág: Fizika
zsűri
Informatikai–Villamosmérnöki
Kutatóhely
Távközlési és Mesterséges Intelligencia Tanszék (Budapesti Műszaki és Gazdaságtudományi Egyetem)
résztvevők
Bíró József Körösi Attila Rétvári Gábor
projekt kezdete
2017-09-01
projekt vége
2021-08-31
aktuális összeg (MFt)
28.719
FTE (kutatóév egyenérték)
5.01
á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 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.
angol összefoglaló
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.
Zárójelentés
kutatási eredmények (magyarul)
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.
kutatási eredmények (angolul)
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.
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
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
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
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
