Tramwajem po grafie

Dzisiaj trochę o grafach. Po drodze na nie się powoływałem, czasem nawet jakieś można było zobaczyć.

Ale co to są te grafy? Był wpis “edukacyjny” o metodach klasyfikacji, czas na kolejny.

Grafy to stwory matematyczne, które przydatne są na przykład w analizie sieci społecznych (wykrywanie “grup wzajemnej adoracji” albo ważnych osób wokół których skupiają się inni), logistyce (planowanie tras transportu). My zajmiemy się warszawskimi tramwajami. Bo to sieć, jakby nie było.

Dane o trasach pobrałem ze strony Warszawa.wikia.com ręcznie przepisując (Ctrl-C + Ctrl-V plus trochę Ctrl-H oraz USUŃ.ZBĘDNE.ODSTĘPY() w Excelu) do tabeli, w której w pierwszej kolumnie jest numer linii, a w drugiej – kolejne przystanki na tej linii (ich nazwy).

Mamy przygotowany graf, możemy go teraz narysować. Na początek wybierzemy jeden z “layoutów” – czyli algorytmów (konkretnie Fruchterman-Reingold) do ustawiana węzłów na obrazku:

A teraz zastąpimy punkty w których zostały umieszczone węzły prawdziwym położeniem przystanków.

Dane o położeniu przystanków pobrałem ze plików wystawionych przez Zarząd Transportu Miejskiego w Warszawie, tutaj obróbka była trudniejsza, wynikowe dane to uśrednione współrzędne wszystkich przystanków o takiej samej nazwie (bo może być kilka przystanków o tej samej nazwie – w dwóch kierunkach, autobusowe i tramwajowe itp.). Pod uwagę brałem tylko przystanki występujące na liniach tramwajowych. Te dane nie są konieczne, ale pomogą w poprawnym (zgodnym z geografią) narysowaniu grafu.

Prawda, że od razu można rozpoznać co to za miasto?

Centrality

Centrality opisuje liczbę krawędzi, które są przychodzące lub wychodzące z/do węzłów. Sieć o wysokiej koncentracji ma kilka węzłów z wieloma połączeniami, sieć o niskiej koncentracji ma wiele węzłów o podobnej liczbie krawędzi.

Stopień węzła

Stopień Węzła lub stopień koncentracji opisuje, jak bardzo “centralny” jest węzeł sieci, czyli ile ma wchodzących i wychodzących krawędzi, albo inaczej mówiąc – ile innych węzłów jest z nim bezpośrednio połączonych (za pośrednictwem jednej krawędzi).

rowname degree degree_std
Okopowa 18 0.0765957
Dworzec Wileński 18 0.0765957
Centrum 18 0.0765957
Metro Ratusz Arsenał 16 0.0680851
Dworzec Centralny 16 0.0680851
Rondo Radosława 14 0.0595745
Plac Zawiszy 14 0.0595745
Kijowska 14 0.0595745
Zajezdnia Wola 14 0.0595745
Plac Narutowicza 13 0.0553191

Okopowa, Dworzec Wileński, Centrum – to przystanki, przez które przechodzi najwięcej linii tramwajowych. Jest ich po 9.

Bliskość

Bliskość węzła opisuje jego odległość do wszystkich innych węzłów. Węzeł o najwyższej bliskości jest bardziej centralny i może rozprzestrzeniać informacje na wiele innych węzłów.

rowname closeness closeness_std
Kino Femina 0.0004148 1.8e-06
Metro Ratusz Arsenał 0.0004049 1.7e-06
Hala Mirowska 0.0004018 1.7e-06
Wola-Ratusz 0.0003992 1.7e-06
Rondo ONZ 0.0003922 1.7e-06
Okopowa 0.0003915 1.7e-06
Nowolipki 0.0003912 1.7e-06
Stare Miasto 0.0003867 1.6e-06
Muranów 0.0003867 1.6e-06
Plac Bankowy 0.0003839 1.6e-06

Kino Femina to węzeł o największej “bliskości”, pozostałe są w niedalekiej okolicy. To środek miasta, a precyzyjniej – środek sieci tramwajowej. Co ciekawe, przez ten przystanek przechodzi tylko 6 linii.

Centralność

Centralność (ang. betweenness) opisuje liczbę najkrótszych ścieżek między węzłami. Węzły o dużej koncentracji znajdują się na ścieżce między wieloma innymi węzłami. W naszym przypadku znaczy to, że przystanki te są kluczowymi połączeniami między różnymi grupami węzłów, dogodne miejsca przesiadek. W sieciach społecznościowych te węzły byłyby bardzo ważne, ponieważ dzięki nim informacje mogą przechodzić do szerokiego grona odbiorców, z jednej grupy do drugiej. To w przypadku węzłów.

W przypadku krawędzi – są to te najbardziej istotne połączenia, “mosty” przenoszące informacje, łączące grupy.

Najpierw węzły:

rowname betweenness betweenness_std
Okopowa 50269.76 1.828324
Dworzec Centralny 47927.15 1.743122
Centrum 47845.63 1.740158
Zajezdnia Wola 46459.45 1.689742
Plac Zbawiciela 45267.84 1.646403
Hoża 45264.19 1.646270
Plac Konstytucji 45083.44 1.639696
Trasa Łazienkowska 44979.42 1.635913
Plac Unii Lubelskiej 44784.34 1.628818
Rakowiecka 44588.58 1.621698

A teraz krawędzie:

edge betweenness
Reduta Wolska|Elekcyjna 22339.624
Centrum|Hoża 11369.797
Hoża|Plac Konstytucji 11321.047
Plac Konstytucji|Plac Zbawiciela 11279.424
Okopowa|Muzeum Powstania Warszawskiego 10445.831
Muzeum Powstania Warszawskiego|Rondo Daszyńskiego 10427.894
Rondo Daszyńskiego|Plac Zawiszy 10366.649
Plac Zbawiciela|Trasa Łazienkowska 9038.885
Trasa Łazienkowska|Plac Unii Lubelskiej 8999.884
Plac Unii Lubelskiej|Rakowiecka 8960.852

Przez odcinek Reduta Wolska – Elekcyjna (z przystankiem Cmentarz Prawosławny po środku) przejeżdża w sumie pięć linii.

Narysujmy to. Wielkość punktu i grubość krawędzi określają ważność węzła/krawędzi:

Średnica

Możemy też obliczyć najdłuższą ścieżkę pomiędzy węzłami – czyli średnicę grafu:

Są to połączone trasy – dwójką z Nowodworów do np. Tarchomina, przesiadka w 17, podróż na przykład do Rondo Radosława, a na koniec przesiadka w 35 i jazda do Wyścigów. Moje dziecko starsze, kochające jazdę tramwajami, byłoby szczęśliwe!

Przejście

Przejście (ang. transitivity) to miara prawdopodobieństwa że sąsiednie wierzchołki (węzły) danego węzła są połączone ze sobą. Czasami nazywa się to również współczynnikiem klastrowania.

name transitivity
KS Polonia 0.3333333
Zajezdnia Żoliborz 0.1666667
Świderska 0.1666667
Cmentarz Włoski 0.1666667
Ratuszowa 0.1666667
Dzielna 0.1333333
Żytnia 0.1333333
Dworzec Gdański 0.0714286
Cmentarz Żydowski 0.0666667
Ratuszowa-Zoo 0.0666667

Czyli 1/3 sąsiadów przystanku “KS Polonia” jest ze sobą połączona. Sąsiedzi tego przystanku to: Dworzec Gdański, Park Traugutta i Muranowska. Mamy więc trzy możliwe połączenia. Muranowska połączona jest z Dworcem Gdańskim, tak samo jak Park Traugutta – czyli mamy dwa z trzech na tak. Park Traugutta i Muranowska nie są połączone – zatem jedno na nie.

Klastrowanie (ang. clustering)

Możemy poszukać grup w naszej sieci poprzez grupowanie węzłów w zależności od centralności (ang. betweenness) ich krawędzi:

lub na podstawie propagujących etykiet (czymkolwiek by to nie było):

Inne metody klastrowania (albo inaczej: “wykrywania klik”“) to cluster_fast_greedy, który nie działa dla grafów, gdzie dwa węzły łączy więcej niż jedna krawędź – nie zobaczymy zatem wyniku.

Kolejna metoda to cluster_walktrap:

Na koniec cluster_spinglass:

Szczegóły poszczególnych algorytmów można znaleźć w dokumentacji igraph oraz w artykułach, do których ta dokumentacja odsyła.

Wyznaczenie najkrótszej trasy

Grafy to najprostszy sposób wyznaczania najkrótszej trasy. Wagi poszczególnych krawędzi mogą określać na przykład czas przejazdu lub odległość pomiędzy wierzchołkami. Jeśli mamy grafy skierowane to krawędź A->B może mieć inną wagę niż B->A, wówczas może się okazać, że najkrótsza (albo najszybsza) droga pomiędzy dwoma wierzchołkami wydaje się być naokoło. Z tego typu algorytmów korzystają wszelakie nawigacje. Ale też inne systemy – na przykład w sieci społecznej (mając bardzo duży graf) możemy policzyć wszystkie odległości każdy z każdym i sprawdzić czy zasada “sześciu uścisków dłoni” jest prawdziwa. Jakiś czas temu Facebook opublikował tekst o tym, że owe “sześć uścisków dłoni” to obecnie coś w okolicach 2.3… ale oni mają wielki graf.

My poszukamy najkrótszej (w rozumieniu najmniejszej ilości przystanków – nie mamy czasów przejazdu pomiędzy przystankami) drogi z jednego przystanku na drugi. Wybierzmy trasę z jednego końca miasta na drugi, ale nie jakąś prostą – na przykład z przystanku Kondratowicza na Czumy:

Dla porównania zamiast Czumy wybierzmy sąsiedni przystanek (jadąc od Młocin 11 jest to przystanek wcześniejszy) – Bemowo-Ratusz:

Widać, że różnica jednego przystanku diametralnie zmieniła trasę.

Grafy są fajne, prawda?

1 myśl na temat “Tramwajem po grafie

Dodaj komentarz