A magyar vasúti infrastruktúra gráfelméleti elemzése

Bevezetés, irodalmi áttekintés Gráfelméleti alapok Reprezentációs kérdések, adatszerzés Gráftulajdonságok az I téren (fizikai infrastruktúra)

A magyar vasúti infrastruktúra gráfelméleti elemzése Ferenci Tamás [email protected]

2012. június 3.

Ferenci Tamás [email protected]

A magyar vasúti infrastruktúra gráfelméleti elemzése


Tartalom 1

Bevezetés, irodalmi áttekintés

2

Gráfelméleti alapok

3

Reprezentációs kérdések, adatszerzés Reprezentációs kérdések Adatszerzés

4

Gráftulajdonságok az I téren (fizikai infrastruktúra) Általános tulajdonságok Kisvilág-hatás Skálafüggetlenség Ellenállóképesség




Köszönetnyilvánítás

Gecse Gergelynek (BCE, Vállalatgazdaságtan Intézet, Logisztika és Ellátási Lánc Menedzsment Tanszék), amiért megtanította nekem az infrastruktúra alapjait Balázs Mártonnak (BME, Matematika Intézet, Sztochasztika Tanszék), amiért megtanította nekem rendesen a valószínűségszámítást . . . és a http://www.vasutallomasok.hu/-nak (majd kiderül miért)




Tartalom 1


2


3


4





Problémafelvetés

Komplex hálózatok empirikus vizsgálata: rengeteg eredmény az utóbbi 10 évben Newman (2003) csoportosítása: társadalmi, információs, technológiai, biológiai hálózatok Matematikai alap: gráfelmélet, ill. véletlen gráfmodellek által sugalltak A munka célja: a magyar vasúti infrastruktúra vizsgálata a fentiekben fontos jellemzőkre




Irodalmi előzmények Latora–Machiori (2002): kis világ effektus a bostoni metrón, lokális és globális hatékonyság Sen et al (2003): kis világ effektus az indiai vasúthálózaton Seaton–Hackett (2004): bostoni (reanalízis) és bécsi metró Kurant–Thiran (2006): svájci és európai vasúthálózat, varsói metró Li–Cai (2007): kínai vasút skálafüggetlensége Lee et al (2008): szöüli metró Sienkiewicz–Holyst (2008): 22 lengyel város tömegközlekedése Wang et al (2009): kínai vasút (mégegyszer, másképp) Nem találtam még csak utalást sem arra, hogy a magyar vasúti infrastruktúrát valaha vizsgálta volna bárki ilyen szempontból. Ferenci Tamás [email protected]



Tartalom 1


2


3


4





Pár fontos definíció I. A gráf egy G = (V , E ) rendezett pár A számunkra most érdekes esetben (véges, irányítatlan gráf) V egy tetszőleges nemüres, véges (∅ = 6 |V | < ∞) halmaz, elemeinek neve: csúcs, pont (vagy szögpont) E egy V -beli rendezetlen párokból álló halmaz (tehát e ∈ E -re e = (v1 , v1 ) ahol v1 , v2 ∈ V ), elemeinek neve: él

A legtipikusabb interpretációban a csúcsok bizonyos „objektumoknak” felelnek meg, az élek a köztük lévő „kapcsolatoknak” Az élekhez súlyokat is rendelhetünk egy w : E → R függvény segítségével, w (e) az e él valamilyen (valós) jellemzője Ha e = (v1 , v1 ) akkor azt mondjuk, hogy az e él illeszkedik a v1 csúcsra (és persze a v2 -re is) Ferenci Tamás [email protected]



Pár fontos definíció II. Egy csúcs deg (v ) fokszáma a rá illeszkedő élek száma P (deg (v ) = e∈E :v ∈e 1) Egy (v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk ) sorozatot élsorozatnak nevezünk, ha ei = (vi−1 , vi ) (azaz végig lehet élek mentén lépkedni a v0 , v1 , . . . , vk csúcsokon) Egy élsorozat út, ha nem érinti kétszer ugyanazt a csúcsot (azaz ∀i 6= j-re vi 6= vj ) Azt mondjuk, hogy va és vb a gráf ugyanazon komponensében van, ha van köztük út (el lehet lépkedni az egyikből a másikban a gráf élei mentén) Ha a gráf összes csúcsa egyetlen komponensben van, akkor a gráfot összefüggőnek nevezzük (minden pontból minden pont elérhető az élek mentén lépkedve) Ferenci Tamás [email protected]



Pár fontos definíció III. Egy (v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk ) út hosszának a Pk i=1 w (ei ) mennyiséget nevezzük (Élsúlyozatban gráfban legyen w ≡ 1, azaz minden élhez rendeljük az 1 súlyt, ekkor a fenti hossz a szükséges lépések száma) Két pont, va és vb között a legrövidebb út az az út, mely va és vb között húzódik, és az ilyen tulajdonságú utak között minimális hosszúságú Ez a hossz a két pont geodetikus távolsága a gráfban, jele dab Egy gráf diam (G) átmérője a legnagyobb geodetikus távolság, mely található pontjai között: diam (G) = max dij i,j∈V




Reprezentációs kérdések Adatszerzés

Tartalom 1


2


3


4






Tartalom 1


2


3


4






Miért elemezzük a vasútat gráfként?

A vasúti infrastruktúra is felfogható úgy, mint objektumok és köztük kapcsolatok Jó ötlet lehet tehát gráfként elemezni! (Persze alkalmasan kell definiálni, hogy mi legyen az objektum (csúcs) és a kapcsolat (él) a gráf-reprezentációban) Mint hálózat, Newman kategorizálásában: technológiai hálózat





Vasúti hálózat gráf-reprezentációja

Csúcsok az állomások/megállóhelyek (továbbiakban röviden: állomások), ez biztos De mi legyen az él? Ennek definíciója dönti el, hogy mit akarunk reflektálni a gráfban (mit fog jelenteni a távolság, fokszám stb.) Több lehetőséget is használtak már az irodalomban: Átszállások tere, P tér Állomások tere, I tér1 Menetrendi megállások tere, L tér

1

A szakirodalomban érdekes módon ennek az egynek nem adtak rövid nevet, úgyhogy én neveztem el I térnek (utalva az infrastruktúrára) Ferenci Tamás [email protected]




Átszállások tere, P tér

Két állomás össze van kötve, ha köztük átszállás nélkül el lehet jutni (legalább egy járat érinti mindkettőt) Fizikai távolság kimarad, az átszállások számát reflektáljuk Ilyen módon minden állomás, ahol ugyanazon vonat megáll, klikket képez (teljesen összekötött)





Állomások tere, I tér

(A szakirodalomban érdekes módon ennek az egynek nem adtak rövid nevet, úgyhogy én neveztem el I térnek (utalva az infrastruktúrára)) Két állomás össze van kötve, ha közvetlen szomszédok a fizikai infrastruktúrán (megy közöttük vonal, amin nincs más állomás) Menet közben érintetett állomások számát, vagy a fizikai távolságot reflektáljuk A vonalak végeinél a pontoknak 1 lesz a fokszáma („end-of-line” hatás)





Menetrendi megállások tere, L tér

Két állomás össze van kötve, ha van legalább egy vonat, ami közvetlenül egymás után a két állomáson áll meg Szükséges megállások számát reflektáljuk (ami persze több lehet, mint a menet közben érintett állomások száma)





Tartalom 1


2


3


4






Szóba jövő adatforrások MÁV: a vasútrendszer csak térképként, a menetrend csak PDF-ben, Elvira csak on-line lekérdezéssel. . . HÜSZ-ben csak bizonyos távolságok (nem is sok) Megoldás a http://www.vasutallomasok.hu/ lett





Adatgyűjtés Az oldalon a vasútvonalak struktúrája meglehetősen szabályos, HTML-kódban elérhető Saját fejlesztésű Visual C# programmal (HTMLAgilityPack segítségével) harvest





Az adatgyűjtés problémai

Sajnos az oldal a 2007-es állapotokat mutatja Továbbá egyéb, nem gépesíthető, mindenképp kézzel elvégzendő adattisztítási feladatok is vannak, amiket nem lehet ilyen módon megspórolni (pl. Szajol és Szolnok között nincsen fizikailag két összeköttetés csak azért, mert a 100-as és 120-as vonal is átmegy rajtuk – ezt a program magától persze nem tudja kitalálni) Itt tehát még lehetne javítani. . .





Elemzése Így rekonstruálható a magyar vasúthálózat Fizikailag az infrastruktúra, nem a rajta közlekedő vonatok: tehát most I terű elemzést fogunk végezni (Elvileg a P tér rekonstrukciója nem nehéz, általában ún. klikkesítéssel szokták megoldani, azaz egy adott vasútvonal valamennyi állomását összekötik mindegyik másikkal – ez lényegében azt feltételezi, hogy minden vonalon van legalább egy (személy)vonat, ami érinti a vonal összes állomását) Elemzés R statisztikai programcsomag alatt, az igraph könyvtár használatával történt (a szkript a szerzőnél elérhető kérésre) Még rengeteg további dolgot lehetne vizsgálni, ez csak ízelítő. . . Ferenci Tamás [email protected]



Általános tulajdonságok Kisvilág-hatás Skálafüggetlenség Ellenállóképesség

Tartalom 1


2


3


4






Tartalom 1


2


3


4






Alapvető adatok |V | = 1256 |E | = 1406 Összefüggő gráf . . . de még csak nem is kétszeresen (pont)összefüggő: 160 állomás van (ún. artikulációs pontok), amit elhagyva nő a komponensek száma (155 esetben 2-re, 5 esetben 3-ra) Gyakorlati jelentősége csekély: legfeljebb 20 állomás választható le (Mátészalka elhagyásával) (Emiatt egy állomás elhagyásával okozott „kár” mérésére nem ez lesz a jó mérőszám)





Átmérő

diam (G) = 622 km, Mándok és Rédics között





Átmérő diam (G) = 622 km, Mándok és Rédics között











120 állomást kell érinteni, minimum 3 átszállás, minimum 11:37 menetidő (de ehhez már 5 átszállás kell!), minimum 6 780 Ft másodosztályon Ferenci Tamás [email protected]




Átlagos fokszám, sűrűség

Átlagos fokszám: z=

|E | = 1,12 |V |

Sűrűség (megvalósult élek aránya a maximális lehetségeshez viszonyítva): ρ=

|E | = 0,0018 |V | (|V | − 1) /2





Tartalom 1


2


3


4






Átlagos távolságok Átlagos geodetikus távolság: l=

X 1 dij = 237,2 km 1 2 n (n + 1) i≥j

Harmada az átmérőnek Harmonikus jellegű átlag (az ellenállóképességhez jön majd jól, mert l = ∞, ha nem összefüggő a gráf és így dij = ∞ is lesz): 

−1

X 1 lh =  1 dij−1  n (n + 1) 2 i≥j

= 143,9 km

Felfogható úgy is, hogy dij−1 egyfajta közelség; a nulla távolságokat elhagytuk Ferenci Tamás [email protected]




Geodetikus távolságok eloszlása A geodetikus távolságok eloszlása (hisztogram és magfüggvényes sűrűség-becslő):

0.0020 0.0015 0.0010 0.0000

0.0005

Relatív gyakoriság

0.0025

0.0030

Állomások közötti legrövidebb távolságok eloszlása

0

100

200

300

400

500

600

700

Távolság [km]

A harmonikus átlag tehát a balra ferdeség miatt kisebb Ferenci Tamás [email protected]




Klasztereződés (tranzitivitás)

Globális tranzitivitás (a szomszédom szomszédja mekkora valószínűséggel az én szomszédom is?): C (1) =

3 · háromszögek száma = 0,001868 összekötött hármasok száma

Lokális tranzitivitás (a fenti kiszámolva a csúcsokra, majd ez átlagolva): C (2) = 0, 001091





A kisvilág-hatás értékelése

Az I terű reprezentáció nem igazán alkalmas a kisvilág-hatás megítélésére (A tranzitivitás például nyilvánvalóan megkérdőjelezhető értelmű fogalom az I téren) Ehhez jobban illene valamilyen súlyozatlan (tehát bináris), kapcsolatokat reprezentáló tér, például a P





Tartalom 1


2


3


4






Fokszám-eloszlás Az állomások fokszámainak eloszlása:

0.6 0.4 0.0

0.2


0.8

1.0

A magyar vasúthálózat fokszámeloszlása

1

2

3

4

5

6

7

8

Fokszám

A továbbiakban az 1-et elhagyjuk (end-of-line hatás) Ferenci Tamás [email protected]




Fokszám-eloszlás Az állomások fokszámainak eloszlása féllogaritmikus skálán: A magyar vasúthálózat fokszámeloszlása (féllogaritmikus skála)

0.050

●

●

0.020


0.200

0.500

●

●

0.002

0.005

●

●

●

2

3

4

5

6

7

8

Fokszám

Ez az ábra a pk ∼ e −k/c jellegű exponenciális fokszám-lecsengés megítéléséhez hasznos Ferenci Tamás [email protected]




Fokszám-eloszlás Az állomások fokszámainak eloszlása logaritmikus skálán: A magyar vasúthálózat fokszámeloszlása (logaritmikus skála)

0.050

●

●

0.020


0.200

0.500

●

●

0.002

0.005

●

●

●

2

3

4

5

6

7

8

Fokszám

Ez az ábra a pk ∼ k −α jellegű hatványfüggvény szerinti (power law) fokszám-lecsengés megítéléséhez hasznos Ferenci Tamás [email protected]




Fokszám-eloszlás Itt nehéz dönteni a kettő között; hatványfüggvényt használva az illesztéshez: A magyar vasúthálózat fokszámeloszlása (logaritmikus skála) és az illesztett power law eloszlás 95%−os CI−vel

0.050

●

0.020 0.010

● ●

0.005


●

0.002

●

●

3

4

5

6

7

8

Fokszám

(Az illesztés az eredeti fokszámokból történt, ML-elven, ezért nem a „legjobban illeszkedő” egyenest kaptuk, az nem is lenne jó módszer) Konkrét paraméterek: xmin = 3 (illeszteni amúgyis az eloszlás szélére kell), α = 4,805 Ferenci Tamás [email protected]




Fokszám-korreláció Vizualizálható az élek végén lévő fokszámok kontingenciatáblájával, mozaik ábrát használva: Fokszámok mozaikábrája 2

3

4

5

6

7 8

876

5

4

3

2

1

1





Fokszám-korreláció

Szokták ezt a (Pearson-féle) lineáris korrelációs együtthatóval jellemezni; itt most r = 0,45 Mivel r > 0, pozitív asszortivitású hálózatról beszélhetünk (a nagyobb fokszámú pontok preferenciálisan nagyobb fokszámú pontokkal kapcsolódnak) Itt érzékelhető az ismérvek diszkrét jellege, így az r használata némiképp megkérdőjelezhető; a Goodman–Kruskal γ értéke 0,67 (egybevág az előbbivel)





A skálafüggetlenség értékelése

A skálafüggetlenség kis jóindulattal megvalósul Az értékelést nehezíti, hogy kicsi a maximális fokszám





Tartalom 1


2


3


4






Kérdésfeltevés Hogy viselkedik a hálózat, ha csúcsokat eltávolítunk belőle („támadás”)? Itt most: terroristák felrobbantják az állomást, műszaki hiba miatt használhatatlanná válik stb. „Viselkedés” mérése: mennyit romlik a hálózat funkcionalitása (Funkcionalitás értsd: nehezebb (vagy akár lehetetlen) lehet eljutni vasúttal két pont között) Ennek mérése: hogyan változik az átlagos geodetikus távolság Mivel adott esetben a hálózat több komponensre is széteshet, a harmonikus jellegű átlagot fogjuk használni Eltérő feltevések a támadás jellegéről Ferenci Tamás [email protected]




Legérzékenyebb pontok Egyetlen állomás eltávolítására a legnagyobb romlás az elérhetőségben (emlékeztetőül: kezdetben lh = 143,9 km): Állomás neve Bp.-Keleti Bp.-Kelenföld Bp.-Déli Kőbánya-Kispest Budafok Székesfehérvár Füzesabony Debrecen Rákosrendező Hatvan Ferenci Tamás [email protected]

lh0 155,1 153,7 153,5 152,6 151,0 148,7 148,6 148,0 147,9 147,9

∆lh /lh +7,73% +6,81% +6,61% +5,99% +4,93% +3,32% +3,27% +2,80% +2,78% +2,78%




A romlás szemléltetése Bp.-Keleti példáján A fentiek szerint a magyar vasúti infrastruktúra legérzékenyebb pontja Bp.-Keleti Az ennek eltávolításakor fellépő +7, 73 % romlás közelebbi szemléltetése az eltávolítás előtti és utáni távolság-eloszlással: 0.0030 0.0015 0.0000


Állomások közötti legrövidebb távolságok eloszlása, teljes hálózat

0

100

200

300

400

500

600

700

Távolság [km]

0.0015 0.0000


Állomások közötti legrövidebb távolságok eloszlása, Bp.−Keleti eltávolítása után

0

100

200

300

400

500

600

700

Távolság [km]





A romlás szemléltetése Bp.-Keleti példáján Kicsit közvetlenebbül összehasonlíthatóan: Bp.−Keleti eltávolításának hatása az átlagos távolságra 0.0030

Teljes hálózat

0.0020 0.0015 0.0010 0.0000

0.0005


0.0025

Bp.−Keleti eltávolítása után

0

100

200

300

400

500

600

700

Távolság [km]





Egy állomás eltávolítása Általában, egy pont eltávolítása esetén a romlás eloszlása (boxplot-tal): Az átlagos távolságok eloszlása egy állomás eltávolítása után (egzakt)

Teljes hálózat átlagos távolsága

● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ●●● ● ● ● ● ● ● ● ●●● ●

144

● ●● ● ●● ● ●●

●●●●

146

●

● ●

148

●●

●

150

●

152

●

●

●

154

Átlagos távolság eltávolítás után [km]

(Az nem ellentmondás, hogy az átlagos távolság csökkenhet is, hiszen az elhagyás után a gráf mérete is kisebb lesz) Ferenci Tamás [email protected]




Két állomás eltávolítása

Az előbbi olyan értelemben volt „egzakt”, hogy mind az 1256 állomás elhagyásának esetére kiszámoltuk az elhagyás utáni átlagos távolságot Két (és pláne több) állomás esetére ez már nem járható út, a lehetőségek kombinatorikusan nőnek (két állomást 1256 = 788140 módon lehet elhagyni) 2 Ehelyett Monte Carlo-szimulációt használtam: 1000 véletlenszerű eltávolítási szituációból (pl. itt: véletlenül, visszatevés nélkül választott állomás-pár eltávolítása 1000-szer megismételve) számoltam az eloszlást





Két állomás eltávolítása Az átlagos távolságok eloszlása két állomás eltávolítása után (MC−szimuláció, 1000 futtatás) Teljes hálózat átlagos távolsága

● ● ● ●● ● ●● ●●● ● ● ● ●●● ●● ●●● ● ● ●●

144

146

148

● ●

●●●

●

150

●

152

●

●

154

Átlagos távolság eltávolítás után [km]





Az MC-szimulációs módszer megbízhatósága Az eloszlás szélei nem lesznek olyan pontosak (függ a szerencsétől, hogy pont kisorsuljuk-e az extrém eseteket). . . . . . de egyébként megbízható módszer Ezt szemléltethetjük az eloszlás stabilizálódásával:

148

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

147

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●

● ●

146

● ● ●

145

Eltávolítás utáni átlagos távolság eloszlása (boxplot)

149

Két állomás eltávolítása utáni átlagos távolság eloszlásának alakulása az MC−szimulációs futtatások számának függvényében

1

3

5

7

9

12

15

18

21

24

27

30

33

36

39

42

45

48

Az MC−szimuláció futtatásainak száma





Az MC-szimulációs módszer megbízhatósága A medián stabilizálódása:

145.1 145.0 144.9 144.8 144.7 144.6 144.5

Eltávolítás utáni átlagos távolság mediánja

145.2

Két állomás eltávolítása utáni átlagos távolság mediánjának alakulása az MC−szimulációs futtatások számának függvényében

0

200

400

600

800

1000






Az MC-szimulációs módszer megbízhatósága Látványos, ha az 0-, 0,1-, 0,25-, 0,5-, 0,75-, 0,9-, 1-kvantiliseket („seven number summary”) vizsgáljuk, ezzel ragadva meg az eloszlást: Két állomás eltávolítása utáni átlagos távolság nevezetes kvantiliseinek alakulása az MC−szimulációs futtatások számának függvényében

154

0.9 0.75 0.5

152

0.25 0.1

146

148

150

0

144

Eltávolítás utáni átlagos távolságok nevezeti kvantilisei

1

0

200

400

600

800

1000






Az MC-szimulációs módszer megbízhatósága Látványos, ha az 0-, 0,1-, 0,25-, 0,5-, 0,75-, 0,9-, 1-kvantiliseket („seven number summary”) vizsgáljuk, ezzel ragadva meg az eloszlást: 1

146.0

0.9 0.75 0.5

145.5

0.25 0.1

144.0

144.5

145.0

0

143.5

Eltávolítás utáni átlagos távolságok nevezeti kvantilisei

146.5

Két állomás eltávolítása utáni átlagos távolság nevezetes kvantiliseinek alakulása az MC−szimulációs futtatások számának függvényében

0

200

400

600

800

1000






Az MC-szimuláció értékelése

Tökéletesen látszik, hogy az extrémebb kvantilisek stabilizálódnak lassabban De 500 futtatás tulajdonképpen már ezeknek is elég (1000 biztosan) Ha nem nagyon az eloszlás széle érdekel minket, akkor gyors eredményhez már 2-300 futtatás is elég





Véletlen támadás

Feltételezés: a támadók véletlenszerűen választanak állomásokat és kapcsolják ki őket Hogyan függ a hálózat teljesítménye (itt: átlagos úthossz) a kiiktatott állomások számától? Lényegében tehát: az előbbiek folytatása több állomásra Az összehasonlíthatóság kedvéért minden esetre MC-szimulált az eloszlás, 1000 futtatással





Véletlen támadás A magyar vasúthálózat leromlása különbözo számú, véletlenszeruen választott állomás eltávolítására ●

●

●

165

● ●

● ● ●

●

● ● ● ● ●

●

●

● ● ● ●

●

160

●

●

●

● ● ● ●

● ●

150

155

● ●

145

Eltávolítás utáni átlagos távolság eloszlása [km]

170

● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ●

1

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

2

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

3

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

4

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

5

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

6

● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

7

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

8

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ●

9

10

Kiesett állomások száma MC−szimuláció, 1000 futtatás





Véletlen támadás Csak a mediánokat ábrázolva:

154 152 150 148 146 144

Eltávolítás utáni átlagos távolság eloszlásának mediánja [km]

A magyar vasúthálózat leromlása különbözo számú, véletlenszeruen választott állomás eltávolítására

1

2

3

4

5

6

7

8

9

10

Kiesett állomások száma MC−szimuláció, 1000 futtatás





Véletlen támadás – értékelés

Megállapíthatjuk, hogy a magyar vasúthálózat meglehetősen védett a véletlen állomás-kiesésekkel szemben: még 10 állomás kiesésekor is csak 4,36% a medián romlás az átlagos távolságban (Már ebből is sejthető, hogy célirányos támadásnál rosszabb lesz a helyzet, hiszen olyan állomást is lehet találni, aminek elhagyásával önmagában ennél nagyobb a kár. . . )





Koncentrált támadás – módszertan Szokásos feltételezés: a támadók a legnagyobb fokszámú pontokkal kezdik a támadást, és haladnak a kisebb fokszámú pontok felé Itt nem a leglogikusabb, mert a legnagyobb fokszám nem feltétlenül a legkritikusabb csúcs (Például a két legnagyobb fokszámú állomás (8, Debrecen és Szolnok) egyike sincs benne a 10 legérzékenyebb állomásban, sőt, még a kettő együttes elhagyásakor is lh0 = 150,7 km, ami +4,69%-os növekedés csak) Ehelyett: megpróbáljuk megkeresni, hogy melyik állomáskombináció elhagyása okozza ténylegesen a legnagyobb kárt A kimerítő keresés, mint láttuk, nem reális Ferenci Tamás [email protected]




Koncentrált támadás – módszertan De most az MC-szimuláció helyett egy másik trükköt alkalmazunk A legnagyobb kárt okozó 1 állomás megtalálásához még kimerítő keresés (már csináltuk is) Viszont a legnagyobb kárt okozó 2 állomáshoz már nem kimerítő keresést csinálunk, hanem megnézzük, hogy az előbbi állomás után a megmaradt |V | − 1 állomásból melyik állomást kell még elhagyni, hogy a legnagyobb legyen a kárt (Lényegében azt feltételezzük, hogy a legnagyobb kárt okozó 2 állomás tartalmazza azt is, ami önmagában a legnagyobb kárt okozza)





Koncentrált támadás – módszertan

És így tovább: a legnagyobb kárt okozó 3 állomás megtalálásához a legnagyobb kárt okozó 2 állomás elhagyása után maradt gráfban keressük (feltesszük, hogy a legnagyobb kárt okozó 3 állomásban benne van az a 2 is, amik önmagukban a legnagyobb kárt okozó 2 állomást jelentik) stb. Lényegében mohó keresést csinálunk





Koncentrált támadás – eredmény Állomás neve Bp.-Keleti +Rákosrendező +Kiskunhalas +Aszód +Újszász +Kál-Kápolna +Debrecen +Karcag +Almásfüzítő +Görögszállás


lh0 155,1 167,4 206,8 221,7 230,1 239,3 247,2 268,2 278,1 288,3

∆lh /lh +7,73% +16,3% +43,7% +54,0% +59,9% +66,2% +71,7% +86,3% +93,2% +100,3%




Koncentrált támadás – eredmény, grafikusan

250 200 150

Eltávolítás utáni átlagos távolság

A magyar vasúthálózat leromlása különbözo számú, legnagyobb kárt okozó módon választott állomás eltávolítására

1

2

3

4

5

6

7

8

9

10

Eltávolított állomások száma Közelítés mohó algoritmussal





Koncentrált támadás – összevetés a véletlen támadással A koncentrált és a véletlen támadás hatásának összehasonlítása Koncentrált

250 200 150

Eltávolítás utáni átlagos távolság

Véletlen

1

2

3

4

5

6

7

8

9

10

Eltávolított állomások száma Közelítés mohó algoritmussal





Koncentrált támadás – értékelés Sokkal nagyobb károkozás (átlagos távolság értelemben) mint véletlen támadásnál 10 állomás kikapcsolásával akár meg is duplázható az átlagos távolság Furcsa lehet viszont, hogy jelentéktelennek tűnő, és önmagukban tényleg nem kritikus állomások is megjelennek a listán A magyarázat, hogy ezek azért fontosak most, mert szétejtik több komponensre a hálózatot Erre pedig érzékeny a harmonikus átlag (adott állomásból nem elérhető állomásokra dij−1 = 0 lesz)





Koncentrált támadás – értékelés A komponensek számának alakulása a fenti elhagyási sorrendnél:

6 4 0

2

Komponensek száma

8

10

Komponensek számának alakulása koncentrált támadáskor

1

2

3

4

5

6

7

8

9

10

Elhagyott állomások száma





Komponensek alakulása koncentrált támadáskor Még fontosabb a komponensek mérete:

800 600 400 0

200

Komponensek nagysága

1000

1200

Komponensek nagyságának alakulása koncentrált támadáskor

1

2

3

4

5

6

7

8

9

10

Elhagyott állomások száma

Látható, hogy drasztikus a szétesés, különösen a harmadik elhagyás után („megfeleződik” a magyar vasúthálózat)





Koncentrált támadás – értékelés Az is észrevehető, hogy az egyes állomások kiejtésének hatása között hatalmas „interakció” van: Bp.-Keleti és Rákosrendező együttes elhagyásának a hatása egészen más, mint a külön-külön történő elhagyásuk hatása: Bp.−Keleti és Rákosrendezo eltávolításának hatása az átlagos távolságra 0.0030

Teljes hálózat Rákosrendezo eltáv. után

0.0010

0.0015

0.0020

Mindketto eltávolítása után

0.0000

0.0005


0.0025

Bp.−Keleti eltávolítása után

0

200

400

600

800

Távolság [km]





Koncentrált támadás – értékelés

(Érdekes a létrejött bimodalitás, bár nem teszteltem rigorózusan, felteszem, hogy ennek oka az, hogy a kelet–nyugat összeköttetés nagyon megnehezül, vö. a magyar vasúthálózat Budapest-centrikus jellege)





Az ellenállóképesség értékelése A fenti számítások legnagyobb hibája, hogy tetszőleges két pont közötti eljutás azonos súllyal esik latba . . . noha stratégiai szempontból nyilván nem ugyanolyan fontos az országnak a Mándok és Rédics közötti eljutás biztosítása, mint a Budapest és Győr közötti (Esetleg valamiféle súlyozással (pl. forgalomarányos) kezelhető ez a probléma, hogy ne minden kilométer ugyanúgy „számítson”) A másik probléma, hogy a több komponensre esés meglehetősen érzékenyen érinti a harmonikusan átlagolt geodetikus távolságot Felmerül a lehetőség, hogy a hálózatban keletkezett kár mérésére ezért más metrikát (is) érdemes lenne alkalmazni Ferenci Tamás [email protected]




Ami még hátra van. . .

P terű reprezentáció (nem annyira nehéz) G terű reprezentáció (zűrös ügy, mert a menetrendi adatokra is szükség volna) Az állomások földrajzi koordinátáinak lementése után „térképes” illusztrációk is lehetségesek Az előbbiekben lehetőségként említett dolgok végigszámolása Kiszámolgatni mindent a cikkekből a magyar hálózatra is. . .



A magyar vasúti infrastruktúra gráfelméleti elemzése

Recommend Documents