Narzędzia użytkownika

Narzędzia witryny


laboratorium-pajek

Celem ćwiczenia jest zapoznanie się z narzędziem Pajek i wykonanie prostych analiz przy jego wykorzystaniu. Pajek to darmowy program do analizy sieci społecznościowych, przygotowany i napisany przez V.Batagelja i A.Mrvara z Uniwersytetu w Ljubljanie (Słowenia). Program jest dostępny pod adresem http://vlado.fmf.uni-lj.si/pub/networks/pajek/. Wraz z programem dostępne są:

Reprezentacja sieci

Podstawowym formatem zapisywania grafów jest plik *.net. Można w nim zapisać dane w następujących formatach:

  • lista krawędzi *Edges
  • lista łuków *Arcs
  • lista incydencji *Arcslist
  • macierz sąsiedztwa *Matrix

Oprócz pliku *.net Pajek korzysta jeszcze z następujących typów plików:

  • *.clu : pliki z etykietami wierzchołków, służą przede wszystkim do definiowania partycji w zbiorach wierzchołków
  • *.vec : pliki z danymi ilościowymi opisującymi wierzchołki
  • *.per : permutacje, czyli uszeregowania wierzchołków

Wszystkie dane o przetwarzanej sieci mogą być umieszczone w pojedynczym pliku *.paj, wewnątrz którego pojawiają się sekcje reprezentujące poszczególne komponenty sieci. Sekcje rozpoczynają się zawsze od nagłówków:

  • Network moja_siec (zawartość pliku *.net)
  • Partition moja_partycja (zawartość pliku *.par)
  • Permutation moj_porzadek (zawartość pliku *.per)
  • Vector moj_wektor (zawartość pliku *.ver)

Pojedynczy plik projektu może zawierać wiele sekcji tego samego typu. Poniżej znajduje się przykład pliku projektu.

*Network Pan network
*Vertices 5
1 "A"
2 "B"
3 "C"
4 "D"
5 "E"
*Edges
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1
*Partition Tail&Head
*Vertices 5
1
2
2
2
2

Praca z grafem nieskierowanym

1. Pobierz plik tekstowy friends.net stanowiący model następującej rzeczywistości (związek między osobami reprezentuje znajomość).

2. Załaduj utworzony plik do programu Pajek i narysuj graf, wybierając z menu opcję Draw→Network (lub korzystając ze skrótu klawiaturowego Ctrl+G)

3. Przeczytaj najbardziej podstawowe statystyki dotyczące załadowanej sieci. W tym celu skorzystaj z Network→Info→General (lub korzystając ze skrótu F7) i pozostaw wartość 0 w oknie dialogowym.

4. Wyznacz stopnie wszystkich wierzchołków, tworząc nową partycję i przypisując każdy wierzchołek do właściwej partycji. Wybierz Network→Create Partition→Degree→All, a następnie otwórz edytor partycji i sprawdź wyznaczone wartości. Wyświetl partycję za pomocą Draw→Network+First Partition (lub skorzystaj ze skrótu klawiaturowego Ctrl+P). W oknie z wizualizacją grafu zmień algorytm rysowania grafu wybierając Layout→Energy→Kamada-Kawai→Separate Components (lub wykorzystaj skrót Ctrl+K)

5. Wyznacz najkrótszą drogę między Barbarą i Filipem. W tym celu utworzysz nową sieć, na którą będą składały się jedynie wierzchołki należące do znalezionej ścieżki. Dodatkowo, utworzysz partycję dzielącą oryginalną sieć na wierzchołki należące i nienależące do najkrótszej ścieżki między Barbarą i Filipem. Wybierz Network→Create New Network→Subnetwork with Paths→One Shortest Path Between Two Vertices. W pierwszym oknie dialogowym wprowadź „Barbara”, w drugim oknie wprowadź „Filip”. Odpowiedz twierdząco na pytania o porzuceniu wartości na krawędziach i identyfikacji węzłów na ścieżce. Wyświetl uzyskaną sieć wykorzystując opcję Draw→Network.

6. W sekcji Networks powróć do oryginalnej sieci, składającej się z 7 wierzchołków. Narysuj partycje dzielące wierzchołki na te, które znajdują się na ścieżce z punktu 5, i te poza ścieżką.

7. Wyznacz miarę bliskości dla wszystkich węzłów, korzystając z menu Network→Create Vector→Centrality→Closeness→All. Obejrzyj uzyskany wektor, klikając na przycisk edycji. Zauważ, że wyznaczone wartości mieszczą się w przedziale [0;1]. Przemnóż wartości w wektorze przez 100 (Vector→Transform→Multipy By i w oknie dialogowym wpisz 100). Narysuj sieć, uzależniając wielkość wierzchołka od wyznaczonej miary bliskości (Draw→Network+First Vector).

8. Podziel wierzchołki na dwa zbiory reprezentujące niską i wysoką miarę bliskości. W tym celu wybierz Vector→Make Partition→by Intervals→Selected Thresholds i w oknie dialogowym wprowadź ”#2” (zauważ, że możesz także samodzielnie zdefiniować granice partycji). Wyświetl uzyskane partycje.

9. Dla każdego wierzchołka wylicz miarę pośrednictwa (Network→Create Vector→Centrality→Betweenness). Obejrzyj uzyskane wyniki i sprawdź, czy zgadzają się z Twoją intuicją. Narysuj sieć (Ctrl+G) i kliknij prawym klawiszem myszy na wierzchołku „Anna”. Kliknij dwukrotnie na słowie Newline i w oknie dialogowym wpisz „6” (tworzysz w ten sposób nową krawędź między Anną i Filipem). W oknie z wizualizacją sieci wybierz z menu opcję Redraw. Ponownie wyznacz miarę pośrednictwa dla wierzchołków i zinterpretuj uzyskany wynik.

10. Znajdź bliższych i dalszych znajomych Barbary. Wybierz Network→Create Partition→k-Neighbours→All, w oknie dialogowym wpisz „Barbara”, w następnym oknie dialogowym podaj odległość „2”. Narysuj uzyskaną partycję (Ctrl+P).

11. Pobierz plik friends.sex.clu zawierający partycję dzielącą wierzchołki na kobiety i mężczyzn. Wczytaj plik do programu Pajek korzystając z opcji File→Partition→Read i wyświetl partycję.

Praca z grafem skierowanym

12. Zamień sieć z poprzedniego ćwiczenia na poniższą sieć, w której krawędzie między węzłami reprezentują wysyłanie wiadomości e-mail, a wartości krawędzi reprezentują liczbę wymienionych wiadomości. W tym celu posłuż się plikiem friends.direct.net

13. Wyświetl stworzoną przez siebie sieć. Upewnij się, że wyświetlane są zarówno etykiety wierzchołków (Options→Mark Vertices Using→Labels, Ctrl+L) jak i wagi krawędzi (Options→Lines→Mark Lines→with Values, Ctrl+V)

14. Wyznacz stopnie wejściowe i wyjściowe wszystkich wierzchołków, zapisz wyznaczone wartości w postaci dwóch wektorów (Network→Create Vector→Centrality→Degree→Input,Output). Następnie w sekcji Vectors w pierwszym polu wybierz wektor o nazwie Input Degree of Nx (7), a w drugim polu wybierz wektor o nazwie Output Degree of Nx (7). Twój ekran powinien wyglądać jak poniżej.

15. Na bazie dwóch aktualnie wybranych wektorów wyznacz nowy wektor, którego wartości będą odpowiadały stosunkowi stopnia wejściowego i wyjściowego. Wybierz z menu opcję Vectors→Divide i wyświetl uzyskany wynik (Draw→Network+First Vector).

16. Znajdź silnie spójne komponenty sieci wykorzystując w tym celu opcję Network→Create Partition→Components→Strong (jako minimalny rozmiar partycji podaj „1”), a następnie wyświetl znalezione partycje. W analogiczny sposób znajdź słabo spójne komponenty sieci i wyświetl uzyskany wynik. Czy potrafisz wytłumaczyć różnicę? Dodaj do sieci jedną krawędź w taki sposób, aby liczba silnie spójnych komponentów sieci wyniosła 3.

17. Wyznacz miarę centralności węzłów wg. bliskości (weź pod uwagę krawędzie wychodzące). Kogo należy powiadomić, aby informacja rozniosła się między przyjaciółmi najszybciej?

18. Wylicz najkrótsze ścieżki między wszystkimi parami wierzchołków. Wybierz Network→Create New Network→SubNetwork with Paths→Geodesics Matrices. Zauważ, że ta operacja tworzy dwie nowe sieci, nazwane Geodesics Count Matrix of Nx (7) oraz Shortest Path Length Matrix of Nx (7). Wyświetl tę drugą sieć i zaobserwuj, ile wynoszą odległości między wierzchołkami, które należą do różnych składowych spójności sieci. Wyświetl średnicę sieci (Network→Create New Network→SubNetwork with Paths→Info on Diameter).

19. Wyznacz wszystkie ścieżki o długości co najwyżej 3 prowadzące od Barbary. W tym celu posłuż się opcją Network→Create Partition→k-Neighbours→Output, wskaż jako wierzchołek początkowy wierzchołek o etykiecie „Barbara” i podaj „2” jako maksymalną długość ścieżki. Czy Edward należy do najbliższych znajomych Barbary? Następnie utwórz podsieć składającą się z najbliższych znajomych Barbary. W pierwszym kroku zapisz wszystkie wierzchołki z partycji 0,1 i 2 (Barbara, jej przyjaciele, przyjaciele jej przyjaciół) do klastra korzystając z operacji Partition→Make Cluster→Vertices from Selected Clusters i podając w oknie parametrów wartość „0-2”. Następnie, stwórz nową sieć korzystając z opcji Operations→Network+Cluster→Extract Subnetwork. Twoja końcowa sieć powinna wyglądać następująco:

zadanie samodzielne

Pobierz dane potrzebne do wykonania ćwiczenia (dostarczone przez prowadzącego) i wypakuj z archiwum plik SanJuanSur2.paj. Załaduj projekt do programu Pajek korzystając z opcji File→Pajek Project File→Read. Plik zawiera informacje o związkach między 75 rodzinami wiejskimi z miejscowości San Juan Sur w Kostaryce, informacje zebrano w 1948 roku. Łuki reprezentują częste wizyty domowe (łuk prowadzi od rodziny wizytującej do rodziny goszczącej, dokładna liczba wizyt nie została odnotowana), przy czym łuki posiadają następujące wagi:

  • (1) wizyta sąsiedzka
  • (2) wizyta rodzinna
  • (3) wizyta rytualna (związana z jakimś obrzędem religijnym)

W zbiorze występują też dwie partycje:

  • SanJuanSur_status: przypisanie każdej z rodzin do jednej z 14 klas na podstawie statusu socjo-ekonomicznego, większa liczba oznacza bogatszą i ważniejszą rodzinę
  • SanJuanSur_leaders: binarna flaga reprezentująca fakt występowania w rodzinie liderki/lidera, tj. osoby cieszącej się w społeczności szczególną estymą

1. Wyświetl sieć i postaraj się dobrać optymalny algorytm rozmieszczenia wierzchołków

2. Dla każdego wierzchołka wyznacz stopień wejściowy wierzchołka (ile rodzin odwiedziło daną rodzinę) i zidentyfikuj pięć rodzin, które posiadają najwyższy stopień wejściowy. Następnie podziel wierzchołki na partycje w taki sposób, aby w pierwszej partycji znalazło się pięć najważniejszych rodzin, a pozostałe rodziny trafiły do drugiej partycji. Narysuj wynikową sieć z zaznaczonymi partycjami.

3. Załóżmy, że plotka potrafi propagować się przez dwa spotkania (tzn. jeśli plotka pojawi się w trakcie wizyty rodziny A u rodziny B, to B przekaże plotkę rodzinie C, a rodzina C może przekazać tę plotkę rodzinie D). Załóżmy, że źródłem plotki jest rodzina f21. Ile rodzin dowie się o plotce, jeśli plotka jest powielana w trakcie każdej wizyty?

4. Wykorzystaj partycję SanJuanSur_status i na jej podstawie stwórz nowy podział zbioru wierzchołków na rodziny biedne (status [1-5]), rodziny średniozamożne (status [6-10]) i rodziny bogate (status [11-14]). Na bazie oryginalnej sieci zbuduj nową sieć prezentującą jedynie związki między rodzinami średniozamożnymi.

5. Znajdź największy silnie spójny komponent sieci. Ile wynosi średnica tego komponentu?

6. Załóżmy, że rodzina f65 pragnie złożyć propozycję matrymonialną rodzinie f5. Wyświetl wszystkie ścieżki, jakimi ta propozycja trafi do adresatów. Ile jest potrzebnych wizyt „po drodze”?

kliki, p-kliki, komponenty, odległości

1. Załaduj sieć us-airlines.net reprezenującą regularne loty rejsowe między lotniskami w Stanach Zjednoczonych. Wyświetl sieć. Wylicz rozkład odległości między wszystkimi lotniskami (Network→Create Vector→Distribution of Distances). Jaka jest największa liczba przesiadek, jakich można się spodziewać w podróży?

2. Wyznacz główny komponent w sieci. Wykorzystaj do tego celu Network→Create Partition→k-Core→All. Ogranicz sieć jedynie do wierzchołków należących do tego komponentu poprzez stworzenie nowej sieci (Operations→Network+Partition→Extract Subnetwork). Obejrzyj strukturę komponentu.

3. Zredukuj sieć do głównego szkieletu zawierającego jedynie najważniejsze lotniska. Przyjmij, że lotnisko jest ważne, jeśli posiada co najmniej 20 połączeń. Wybierz Create New Network→Transform→Reduction→Degree→All i podaj jako próg odcięcia 20. Wylicz nowe wartości stopni wierzchołków i wyświetl szkielet sieci, rysując każdy wierzchołek proporcjonalnie do jego stopnia.

4. Znajdź p-kliki lotnisk, to jest takie zbiory lotnisk, które są bardzo mocno ze sobą połączone. Wybierz Network→Create Partition→p-Cliques→Weak i jako parametr podaj 80%. Wyświetl znalezione partycje. Czy potrafisz je zinterpretować? Znajdź partycję odpowiadającą lotniskom położonym na Alasce (np. Fairbanks, Anchorage) i zapisz ją w postaci klastra Partition→Make Cluster→Vertices from Selected Clusters. Następnie, wyznacz podobieństwa między lotniskami i zbuduj dendrogram opisujący strukturę lotniczą Alaski (Operations→Network+Cluster→Dissimilarity*→Network based→d1), wynikowy plik *.eps zapisz na dysku.

grafy dwudzielne

Pobierz plik davis.net zawierający dane zebrane przez Davisa w latach 30-tych XX wieku na temat aktywności towarzystkiej grupy kobiet w jednym z miast amerykańskiego Południa. W zbiorze odnotowano fakt obecności każdej z 18 kobiet w 14 organizowanych przez społeczność uroczystościach i imprezach.

  • ,,Breiger R. (1974). The duality of persons and groups. Social Forces, 53, 181-190.,,
  • ,,Davis, A et al. (1941). Deep South. Chicago: University of Chicago Press.,,

10. Wyświetl sieć, a następnie podziel zbiór wierzchołków na dwa rozłączne zbiory wykonując Network→2-Mode Network→Partition into 2-Modes i ponownie wyświetl uzyskaną sieć. Sprawdź, jaka wizualizacja pozwoli Ci najlepiej zapoznać się ze zbiorem danych. Czy potrafisz podać jakąś hipotezę tłumaczącą, dlaczego sieć ma taki a nie inny charakter?

11. Wyznacz trzy najważniejsze kobiety i trzy najważniejsze wydarzenia, które miały miejsce w tej społeczności (Network→2-Mode Network→Important Vertices). Czy wskazane węzły zgadzają się z Twoją intuicją?

12. Dokonaj transformacji grafu dwudzielnego do grafu z jednym zbiorem wierzchołków poprzez powiązanie ze sobą kobiet, które wspólnie wzięły udział w tych samych wydarzeniach (Network→2-Mode Network→2-Mode to 1-Mode→Rows). Wyświetl uzyskaną sieć.

13. Powróć do oryginalnej sieci i dokonaj transpozycji sieci. Następnie, analogicznie do punktu 12, zamień graf dwudzielny na graf afiliacyjny w którym wierzchołki reprezentują wydarzenia, a wagi krawędzi między wierzchołkami odpowiadają liczbie kobiet, które wzięły udział wspólnie w obu wydarzeniach. Wyświetl uzyskaną sieć, zmieniając sposób wyświetlania w taki sposób, aby grubość krawędzi odpowiadała jej wadze.

zadanie samodzielne

Pobierz plik football.net potrzebny do wykonania ćwiczenia. Plik zawiera informacje o 22 drużynach które wzięły udział w Mistrzostwach Świata w piłce nożnej w Paryżu w 1998 roku. Każdy wierzchołek reprezentuje jeden kraj. Łuki między wierzchołkami reprezentują transfer piłkarzy, tzn. jeśli istnieje łuk między wierzchołkiem A i B, oznacza to, że jakiś piłkarz urodzony w kraju A gra w kraju B. Waga łuku reprezentuje liczbę transferowanych piłkarzy. Graf jest silnie niesymetryczny, istnieją kraje trudniące się przede wszystkim eksportem piłkarzy, są też kraje które jedynie importują piłkarzy

  • ,,Dagstuhl seminar: Link Analysis and Visualization, Dagstuhl 1-6. July 2001,,

1. Wyznacz trzy kraje które eksportują najwięcej piłkarzy

2. Wyznacz kraj, który eksportuje piłkarzy do największej liczby innych krajów

3. Znajdź p-kliki składające się z krajów, które wymieniają na wzajem ze sobą piłkarzy. Warunkiem jest, aby w p-klice każdy kraj był połączony z co najmniej 80% innych krajów.

4. Sprawdź, czy w sieci istnieje istotny komponent silnie spójny. A czy istnieje komponent słabo spójny?

5. Znajdź wszystkie kraje, w których grają Nigeryjczycy i zapisz je w postaci nowej sieci.

laboratorium-pajek.txt · ostatnio zmienione: 2018/06/12 22:35 przez mmorzy