 |
Measurement based analysis of operational paths in complex networks
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
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.
|
|
|
|
|
|
|
|
|
|
