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.

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:

• OpenOrd Layout
• Circular Layout
• GeoLayout
• Geometric Transformations
• Noverlap Layout

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:

• Autostab strength = 2000 (większe wartości powodują wolniejszy ruch wierzchołków)
• Repulsion strength = 1000 (siła wzajemnego odpychania się przez wierzchołki)
• Attraction strength = 1 (siła, z jaką połączone wierzchołki się przyciągają)
• Gravity = 100 (ogólna siła przyciągania wszystkich wierzchołków w kierunku centrum sieci aby uniknąć nadmiernego rozrzucenia wierzchołków)
• Attraction distrib. = true (powoduje przesunięcie hubów w kierunku peryferiów a autorytetów w kierunku centrum sieci).

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:

• Area = 100 (obszar, na którym może być rysowana sieć)
• Area = 100 000
• Gravity = 1000 (siła przyciągania wszystkich wierzchołków w kierunku centrum sieci aby uniknąć rozproszenia komponentów)
• Gravity = 100

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:

• Step ratio = 0.99 (większe wartości powodują poprawę jakości kosztem szybkości działania)
• Optimal distance = 200 (naturalna długość „sprężyn”, większe wartości powodują większe rozrzucenie wierzchołków)
• Theta = 1.0 (parametr algorytmu Barnesa-Huta, mniejsze wartości powodują większą precyzję wyliczeń)

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:

• Edge cut = 0.95 (procentowa odległość między dwoma najbardziej odległymi wierzchołkami w sieci, większe wartości prowadzą do większej separacji klastrów)
• Num iterations = 100, 800 (ściąganie i rozciąganie klastrów)

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:

• LinLog mode = true (siła przyciągania wierzchołków rośnie liniowo, a siła odpychania wierzchołków rośnie logarytmicznie, w efekcie klastry stają się widoczniejsze)
• Scaling = 100 (większe wartości generują bardziej rozrzedzone sieci)
• Edge weight influence = 0, 0.5, 1 (wpływ wagi krawędzi na algorytm)

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:

• Order nodes by = Degree
• Diameter size = 50 (wielkość okręgu)

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:

• Group nodes by = Degree
• Group nodes by = Modularity class
• Order nodes by = Degree
• Draw spar/axis spiral = true (w ten sposób bardziej uwypuklone zostają związki wewnątrz grupy)
• Ascending order = true (w ten sposób bardziej uwypuklone zostają związki pomiędzy grupami)

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:

• speed = 0.1
• ratio = 2
• margin = 10

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.