Analiza sieci społecznościowych w narzędziu Gephi (część II)

W drugiej części ćwiczenia studenci uczą się korzystać z algorytmów badania modularności sieci oraz analizują sieci dynamiczne oraz ich własności. Samodzielne ćwiczenie studenci wykonują na sieci reprezentującej geopolityczne i ekonomiczne powiązania między krajami.

zaawansowana wizualizacja

1. Otwórz menu Tools i wybierz opcję Plugins. W zakładce Settings upewnij się, że zaznaczone są opcje Gephi Thirdparties plugins oraz Gephi Update Center. Przejdź do zakładki Available plugins i zainstaluj następujące wtyczki:

W razie konieczności zrestartuj program.

2. Pobierz zbiór danych les.miserables.gephi i otwórz go w Gephi. Wybierz layout Force Atlas i uruchom go korzystając z domyślnych parametrów.

3. Ustaw parametr Repulsion strength na 10 000 i zaobserwuj wynik. Ustaw Autostab strength na 100 000, a następnie wykorzystaj narzędzie do przenoszenia aby zmienić lokalizację zbioru punktów. Zaobserwuj wynik.

4. Algorytm Force Atlas ma złożoność rzędu $O(n^2)$ i bazuje na balansie sił, biorąc pod uwagę wagę krawędzi. Nadaje się do sieci o rozmiarze do 10 000 wierzchołków. Uruchom jeszcze raz ten rozkład, zmieniając (w trakcie działania algorytmu) następujące parametry:

W trakcie działania algorytmu kliknij na dowolnym wierzchołku prawym klawiszem myszy i z menu kontekstowego wybierz opcję Settle. Zaobserwuj wynik. Postaraj się uzyskać podobną wizualizację (do pokolorowania wierzchołków użyto cechy Modularity class).

5. Algorytm Fruchterman-Reingold symuluje sieć jako zbiór cząstek obdarzonych masą (wierzchołki) i połączonych za pomocą sprężyn (krawędzie) o określonych siłach (wagi krawędzi). Ostateczny rozkład wierzchołków próbuje minimalizować całkowitą energię układu. Złożoność algorytmu to $O(n^2)$, a główną wadą jest długi czas obliczeń. Algorytm nadaje się do sieci o liczbie wierzchołków nieprzekraczającej 1000. Uruchom ten rozkład, zmieniając (w trakcie działania algorytmu) następujące parametry:

Postaraj się tak dobrać obszar i ciążenie, aby uzyskać wizualizację podobną do poniższej.

6. Algorytm Yifan-Hu Multilevel to bardzo szybki algorytm wykorzystujący połączenie idei ukierunkowania wierzchołków przez siły reprezentujące krawędzie oraz odpychania wierzchołków przez odległe klastry. Klastry wierzchołków są aproksymowane do jednego meta-wierzchołka przez algorytm Barnesa-Huta. Złożoność algorytmu to $O(n log(n))$. Algorytm dobrze się sprawdza dla sieci o rozmiarze od 100 do 100 000 wierzchołków. Nie uwzględnia wag krawędzi. Uruchom rozkład Yifan-Hu Multilevel zmieniając (w trakcie działania algorytmu) następujące parametry:

Postaraj się tak dobrać parametry rozkładu, aby uzyskać wizualizację podobną do poniższej.

7. Algorytm OpenOrd Layout służy przede wszystkim do takiego rozmieszczenia wierzchołków, które wizualnie najbardziej separuje klastry występujące w sieci. Podstawą algorytmu jest algorytm Fruchtmana-Reingolda realizowany iteracyjnie z wykorzystaniem techniki symulowanego wyżarzania. Złożoność algorytmu jest rzędu $O(n log(n))$, algorytm radzi sobie z sieciami do 1 000 000 wierzchołków. Uruchom rozkład OpenOrd Layout zmieniając (w trakcie działania algorytmu) następujące parametry:

Postaraj się tak dobrać parametry rozkładu, aby uzyskać wizualizację podobną do poniższej.

8. Algorytm OpenOrd Layout jest jednym z najlepszych algorytmów do wizualizacji dużych sieci. Pobierz plik internet_routers.gml.zip i otwórz go w nowym obszarze roboczym. Sprawdź, ile wierzchołków i krawędzi zawiera ta sieć, reprezentująca strukturę sieci Internet na poziomie systemów autonomicznych (jest to obraz z lipca 2006 r.) Wykorzystaj rozkład OpenOrd Layout w celu wizualizacji ogólnej struktury tej sieci.

9. Algorytm Force Atlas 2 to ulepszona wersja algorytmu Force Atlas, mogąca obsługiwać duże sieci do 1 000 000 wierzchołków. Złożoność algorytmu to $O(n log(n))$ dzięki zastosowaniu algorytmu Barnesa-Huta do agregacji wierzchołków. Algorytm wykorzystuje do rozkładu wagę krawędzi. Uruchom rozkład Force Atlas 2 zmieniając (w trakcie działania algorytmu) następujące parametry:

Postaraj się tak dobrać parametry rozkładu, aby uzyskać wizualizację podobną do poniższej.

10. Algorytm Circular Layout jest jednym z najprostszych algorytmów. Wierzchołki są umieszczane na okręgu zgodnie z podanym kryterium. Złożoność algorytmu to $O(n)$, algorytm działa dla dowolnie dużych sieci, ale żadko udaje się wyprodukować przydatną wizualizację na podstawie surowych danych źródłowych. Wykorzystaj rozkład Circular Layout dokonując w nim następujących zmian:

Przejdź do zakładki Ranking i wskaż chęć zróżnicowania wielkości i kolorów wierzchołków w zależności od stopnia. Postaraj się, aby Twój ostateczny efekt był podobny do poniższego (być może musisz też mniejszych intensywność rysowania krawędzi)

11. Przydatnym sposobem wizualizacji jest algorytm Radial Axis Layout, umożliwiający dodatkowo grupowanie wierzchołków według zadanego kryterium. Upewnij się, że analizowana sieć ma wyznaczoną przynależność wierzchołków do modułów. Następnie wykorzystaj rozkład Radial Axis Layout ustalając następujące wartości parametrów:

Postaraj się, aby Twój ostateczny efekt był podobny do poniższego.

12. Załaduj zbiór danych airlines.gexf. Algorytm Geo Layout narysuje sieć w taki sposób, aby położenie każdego wierzchołka odpowiadało jego szerokości i długości geograficznej, przy zadanej metodzie odwzorowania na 2D. Wyświetl sieć, włącz wyświetlanie etykiet z nazwami lotnisk, a następnie sprawdź wpływ metod odwzorowania 2D na ostateczny wygląd sieci.

13. Ostatnie dwa rozkłady należy wykonać po przeprowadzeniu głównego rozkładu, ponieważ służą one do wprowadzania niewielkich poprawek do istniejącego rozkładu. Algorytm Noverlap Layout redukuje do minimum wzajemne nakładanie się węzłów. Powróć do obszaru pracy z danymi z „Nędzników” i uruchom algorytmy Yifan Hu z domyślnymi parametrami, zmieniając jedynie wielkość wyświetlania wierzchołka na 10 i optymalną odległość na 50. Po zakończonym algorytmie uruchom Noverlap Layout. Sprawdź efekt działania. Następnie, wprowadź następujące zmiany w parametrach, każdorazowo obserwując efekt:

Następnie, włącz wyświetlanie etykiet wierzchołków i tak dobierz rozmiar etykiet, aby nieznacznie na siebie nachodziły. Wybierz rozkład Label Adjust i go uruchom. Postaraj się, aby ostateczna wizualizacja wyglądała podobnie do poniższej.

14. Włącz algorytm rozkładu Transformation i spróbuj dokonać obrotów i translacji dowolnego rozkładu wokół osi OX, OY i OZ.