Korištenje PageRank metrike u analizi prometne mreže

Je li "Google mjera" dobra i za (cestovne) prometne mreže?

Uz Google se veže PageRank algoritam koji nam u desetinki sekunde pretraži nekoliko milijuna Internet stranica i, najčešće, ponudi relevantne izvore u prvih 10-tak odgovora. Naziv upućuje na "rangiranje stranice", ali ime duguje gospodinu Larryju Pageu koji je s gospodinom Sergeyjom Brinom autor algoritma. Isto je zanimljivo da je vlasnik patenta američko Sveučilište Stanford, a Google posjeduje ekskluzivnu licencu i prava na korištenje.

Može li se nešto tako učinkovite i većinom (ne)pogrešivo koristiti i u prometu? Odgovor je može, jer se radi o izvedenici poznate mjere društvene mreže – centralitetu svojstvenog vektora (eigenvector). O metrici socijalnih mreža na primjeru zagrebačkih tramvaja pisao sam u ovoj temi.

Algoritam PageRank je jednostavan, zato je i brz, i zasniva se na iterativnom postupku. Za Internet dušu dalo jer se stalno nešto događa/mijenja pa stalno treba nanovo mjeriti, usklađivati provjeravati. Nas inženjere zanima primjena matematike (linearne algebre), a ne teorija, pa je najbolje pokazati na jednostavnom primjeru. Imamo četiri Internet stranice, od kojih stranica "1" upućuje na preostale tri stranice pa njezine usmjerene spojnice imaju vrijednost 1/3. Stranica "2" upućuje samo na stranicu "1" pa taj link ima vrijednost 1, itd..

Lako je napisati stohastičku matricu po stupcima. Neki, kao ja, napišu klasičnu stohastičku matricu (po redcima) pa onda transponiraju. Vektor-stupac (v) je vektor vrijednosti svakog čvora (Internet stranice) i na početku se kreće s jednakom vrijednosti svake stranice. Postupak je iterativan dok se ne postigne stacionaran proces, gdje rješenje predstavlja vrijednost (težinu) svake stranice.

Rješenje pokazuje da je čvor "1" najutjecajniji, a iza njege slijede čvorovi: "2", "4" i "3". Internet je dinamičan, svakog sata se pojavi novih 10.500 Internet stranica!? Promet, posebice cestovni, ipak nije toliko "dinamičan". Gledano mrežno topološki, cestovna mreža je statična, raskrižja/čvorovi (ili ostala prometna infrastruktura) uvijek su na istom mjestu u istom odnosu, u istoj organizaciji i regulaciji prometa. Isključujemo izvanredne situacije i privremene regulacije prometa. Ono što se može promijeniti je asignirati neke atribute na linkove umjesto jednakih (normiranih) vrijednosti. U prethodnom primjeru iz čvora "1" izlaze tri spojnice jednakih (normiranih) vrijednosti. Ako umjesto njih stavimo neki prometni atribut (prometni tok, vrijeme putovanja, prometni pokazatelj i sl.) onda možemo dobiti bolju (vjerodostojniju) prometnu situaciju.

Ponekad se do nekih web-stranica ne može, neke privremeno nestanu, na nekima se promijeni organizacija (prioritet) usmjeravanja na druge stranice, ponekad jednostavno krivo "kliknemo" i dr.. U (cestovnom) prometu se (pretpostavljeni, uobičajeni) asignirani promet promijeni jer: ljudi promijene svoju uobičajenu dnevnu rutinu (zbog trenutne ili nove obveze), pojavljuju se novi vozači(ce), promjena rada prometnih svjetala čini neku spojnicu (cestovni koridor) (ne)atraktivnijim, ljudi pogriješe skretanje ili se zaborave pa krenu drugim putem i dr..

Takve "anomalije" se rješavaju faktorom prigušenja (dumping factor) kojim se kreira nova matrica, koja se naziva Google matrica (M), jer se njome kreće u rangiranje web-stranica. Faktor prigušenja (p) može imati malu vrijednost pa će konvergencija rješenju biti brža, ali rezultat neprecizniji, dok za veći faktor dobivamo točniji rezultat, ali i sporiju konvergenciju. U Internet svijetu se uzima p = 0,85; dok je u prometu taj faktor obično p = 0,95; dozvoljavamo da 5 % vozač(ic)a mijenja svoj uobičajeni itinerer.

Za primjer ću uzeti dio zagrebačke mreže, na način da "pobijedi" raskrižje Ulica grada Vukovara – Avenija Marina Držića; na slici broj (9). Južnije je čvor u tri razine Držićeva petlja (15). Budući cestovna mreža nije razvijena južno od Ulice Grada Vukovara (koridor raskrižja od (7) do (12)) zanimalo me koliko će raskrižje (9) biti važnije od ostalih raskrižja u okolini, a poglavito od Držićeve petlje (15). 

Jednostavan algoritam se lako aplicira u Excelu. Na slici je početna matrica, na koju sam djelovao faktorom prigušenja 0,95; i početni vektor-stupac s jednakim vrijednostima 1/16 = 0,063.

Trebalo je 12 iteracija za postizanje stacionarnog procesa i rezultat je prikazan u sljedećoj tablici. Raskrižje (9) je očekivano najbolje, na drugom mjestu je (ne)očekivano raskrižje (3), na trećem (8), a tek na četvrtom Držićeva petlja (15) za 22,09 % slabija od (9). Na petom mjestu je raskrižje (10). Očekivano, najbolje je središnje raskrižje (9), a onda dolaze njegovi susjedi, u malo drugačijem redoslijedu od očekivanog. 

Raditi ovakve stvari pješice nema smisla. Jednostavan Python kod omogućuje analizu složenijih mreža ili nekih promjena i/ili dopuna. U ovom kodu je dodano novo raskrižje: Branimirova – Heinzelova (17) da se vidi (moguća) promjena važnosti pojedinih raskrižja. 

Dopunom mreže raskrižjem Branimirova – Heinzelova (17), raskrižje (12) postaje puno značajnije i dolazi na peto mjesto. 

Je li ovakvo mrežno topološko promatranje s motrišta prometa opravdano/vjerodostojno? Budući da PageRank upućuje na "klikanje" na određene stranice, nije li točniji (objektivniji) rezultat ako asigniramo sve sveze koje se događaju u mreži? Zasigurno postoje vozači koji putuju iz (7) prema (16) i to mogu učiniti na četiri načina: preko (14), putem (9) i (15), ravno do (11) i prema (16) ili ravno sve do (12) i onda prema (16). Opravdano je tako promatrati problem, ali se to ne radi "pješice".

Profesionalnu uporabu ću ilustrirati jednim aktualnim projektom. Radi se o mreži s više od 90 raskrižja/objekata. Mogu pokazati dio mreže bez narušavanja interesa Investitora i integriteta projekta. Spojnice (prometni koridori) imaju različite atribute, od osnovnih mrežnih atributa (matrica susjedstva), preko količine prometa pa sve do specifičnih parametara/pokazatelja propisanih projektnim zadatkom. Koristim otvorenu platformu Gephi. Prikazane su četiri mjere centralnosti:

• Closeness (centralnost bliskosti); koliko je pojedino raskrižje (čvor) dostupno iz drugih dijelova mreže,
• Betweenness (centralnost između čvorova); u kojoj se mjeri raskrižje (čvor) nalazi na najkraćim putovima između drugih raskrižja (čvorova),
• PageRank; važnost raskrižja (čvora) temeljem njegovih ulaznih sveza,
• Eigenvector (centralnost svojstvenih vektora); utjecaj raskrižja (čvora) i povezanost s drugim važnim raskrižjima (čvorovima).

U prometu tumačimo da Closeness ukazuje na središnji položaj u mreži, Betweenness na najbolji položaj, a Eigenvector na najutjecajniji položaj. U prometu nas PageRank upućuje više na okolne prometne objekte nego na njega samog. Kako promijeniti PageRank u prometnoj mreži? Jednostavno i vrlo "jednostavno". Promjenom organizacije i regulacije prometa mijenjamo usmjerenje prometnih tokova i time s pozicije PageRank mijenjamo značajnost pojedinih čvorova. Tko je bavi praktičnim problemima (gradskog) prometa zna koliko je "jednostavno" napraviti nešto jednostavno.

Na gornjoj slici mjere Closeness, Betweenness i Eigenvector upućuju na jedan ili nekoliko prometnih objekata, dok PageRank pokazuje značajnost jednog drugog prometnog objekta. Po četiri različite mjere centraliteta ključni prometni objekti u prikazanom dijelu mreže se nalaze na jednom prometnom koridoru. Može biti dobra vijest jer su svi problemi (ključni objekti) grupirani na jednom mjestu pa rješenje možda traži manje prostornih, tehnoloških i u konačnici financijskih resursa, a može biti i (vrlo) loša vijest jer je moguće previše bliskih (ne)rješivih problema što zahtijeva povećanje raspoloživog prometnog prostora, a to je uvijek povezano s (pre)velikim investicijama. Hoću li se odlučiti za neki postupak demokratske procedure uzimajući u obzir sve kriterije, kako sam opisao u ovoj temi, ili ću se prikloniti rješenju temeljem jednog pokazatelja, ovisi o mojem znanju, iskustvu i uvjetima projektnog zadatka (stavovima i zahtjevima Investitora).

Kod primjene analize socijalnih mreža u svakoj mjeri pojedino raskrižje, ili neki drugi prometni objekt, je važno na svoj način. Kako to protumačiti i ponuditi adekvatno (konkretno) rješenje, to je slatka inženjerska briga kada su ponuđena rješenja temeljena na relevantnim (objektivnim) ulaznim podatcima. Mjera PageRank nije "za baciti" kako je pokazala ova tema.