Przejdź do treści
Wróć do wyników wyszukiwania

Analiza sieci dwudzielnych — sieci dwumodowe

Autor metody
Borgatti & Everett (1997) formalised the two-mode network framework
Rok
1997
Typ
Graph-structural / relational analysis

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Analiza sieci dwudzielnych, sformalizowana przez Borgattiego i Everetta w 1997 roku, to metoda grafowo-strukturalna służąca do badania sieci, w których węzły są podzielone na dwa rozłączne zbiory — aktorów i zdarzeń — a krawędzie istnieją tylko między zbiorami, nigdy w ich obrębie.

Jest to naturalna struktura dla danych dotyczących autorów i artykułów, pacjentów i chorób, użytkowników i produktów oraz wszelkich innych danych afiliacyjnych. Rozszerza ona analizę sieci jednomodowych, dostarczając metryk i technik projekcji dostosowanych do struktury dwumodowej.

Intuicja stojąca za metodą

Wyobraźmy sobie arkusz kalkulacyjny, w którym wiersze to osoby, a kolumny to kluby, do których należą. Komórka jest zaznaczona, jeśli osoba A należy do klubu B. Standardowe narzędzia sieciowe zakładają, że wszyscy łączą się bezpośrednio ze wszystkimi innymi, ale tutaj ludzie łączą się tylko z klubami, a nie z innymi ludźmi. Analiza sieci dwudzielnych odczytuje tę dwustronną strukturę taką, jaka jest — mierząc, jak centralna jest każda osoba lub klub w całym wzorcu afiliacji — a następnie może ją zwinąć w sieć składającą się tylko z ludzi, gdzie dwie osoby są połączone, jeśli mają co najmniej jeden wspólny klub, co daje bogatszy obraz niż proste ignorowanie dwumodowej natury danych.

Historia

Formalne opracowanie danych sieci dwumodowych zostało ustanowione przez Borgattiego i Everetta w ich artykule w „Social Networks” z 1997 roku, który rozszerzył standardowe metryki grafowe na przypadek dwudzielny i wprowadził ramy projekcji. Guillaume i Latapy (2006) następnie wykazali, że wiele empirycznych sieci złożonych — od Internetu po systemy biologiczne — wykazuje dwudzielną podstrukturę, wzmacniając ogólność podejścia. Metoda ta stała się od tego czasu standardem w bibliometrii, badaniach systemów rekomendacji i obliczeniowych naukach społecznych.

Kiedy stosować

Stosuj analizę sieci dwudzielnych zawsze, gdy Twoje dane relacyjne naturalnie dzielą się na dwa rozłączne typy węzłów — aktorów i zdarzeń, użytkowników i przedmiotów, pacjentów i diagnoz — i chcesz badać właściwości strukturalne tego wzorca afiliacji. Metoda ma zastosowanie do celów eksploracyjnych, relacyjnych i klasyfikacyjnych oraz obsługuje binarne, ciągłe lub kategoryczne wagi krawędzi. Zaleca się co najmniej 20 węzłów łącznie dla uzyskania znaczących metryk strukturalnych. Podstawowe założenie jest ścisłe: krawędzie istnieją tylko między dwoma zbiorami węzłów, nigdy w obrębie jednego zbioru. Jeśli taka partycja nie istnieje w Twoich danych, bardziej odpowiednia jest standardowa analiza sieci jednomodowych.

Ograniczenia i uwagi

  • Projekcja na sieci jednomodowe powoduje utratę informacji: dwóch aktorów może mieć tę samą wagę krawędzi w projekcji, pomimo bardzo różnych wzorców współuczestnictwa.
  • Standardowe metryki centralności zaprojektowane dla grafów jednomodowych muszą być adaptowane lub reinterpretowane; naiwne zastosowanie prowadzi do mylących rankingów.
  • Bardzo rzadkie grafy dwudzielne (niewiele połączeń na węzeł) dają nierzetelne oszacowania centralności.
  • Metoda opisuje strukturę, ale nie modeluje mechanizmów przyczynowych; wnioskowanie o tym, dlaczego aktorzy się afiliują, wymaga metod uzupełniających.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Respektuje inherentną dwustronną strukturę danych afiliacyjnych, zamiast wymuszać na niej reprezentację jednomodową, która odrzuca informacje.
  • Projekcja na sieci jednomodowe umożliwia dalszą analizę za pomocą pełnego zestawu standardowych metod sieciowych.
  • Ma zastosowanie w różnych dziedzinach — bibliometrii, systemach rekomendacji, epidemiologii, ekologii i handlu — wszędzie tam, gdzie pojawiają się dane aktor–zdarzenie.
  • Statystyczne porównanie z modelem zerowym BiRG pozwala na testowanie istotności obserwowanych wzorców strukturalnych.

Zastosowania

  • Bibliometria: mapowanie sieci afiliacyjnych autor–artykuł w celu identyfikacji wpływowych badaczy i społeczności współpracujących.
  • Systemy rekomendacji: analiza grafów interakcji użytkownik–przedmiot w celu wykrycia wzorców współzakupów lub współoglądania.
  • Epidemiologia: badanie sieci pacjent–choroba lub gospodarz–patogen w celu wykrycia skupisk współchorobowości.
  • Ekologia: modelowanie dwudzielnych sieci troficznych roślina–zapylacz lub ofiara–drapieżnik.
  • Badania organizacji: badanie sieci pracownik–projekt lub członek zarządu–firma w celu analizy dzielenia się zasobami i pośrednictwa.

Jak to działa

Jak to działa

1

Surowe dane afiliacyjne są gromadzone w grafie dwudzielnym B z dwoma rozłącznymi partycjami węzłów — konwencjonalnie nazywanymi zbiorem górnym (aktorzy) i zbiorem dolnym (zdarzenia) — a krawędzie są rysowane tylko przez granicę partycji. Dane wejściowe to zazwyczaj macierz incydencji lub lista krawędzi dwukolumnowa; żadna krawędź nie jest dozwolona w obrębie pojedynczej partycji, co jest definiującym ograniczeniem strukturalnym grafu dwudzielnego.

2

Przed obliczeniem metryk weryfikuje się właściwość dwumodową: każdy węzeł musi należeć do dokładnie jednej partycji i nie mogą istnieć krawędzie wewnątrzpartycyjne. Na tym etapie można wygenerować losowy dwumodowy model zerowy — dwudzielny graf losowy (Bipartite Random Graph, BiRG), który zachowuje sekwencje stopni — aby służył jako statystyczny punkt odniesienia do późniejszych porównań.

3

Metryki centralności i klasteryzacji, które są dostosowane do struktury dwudzielnej, są obliczane na pełnym grafie dwumodowym. Standardowe jednomodowe miary pośrednictwa (betweenness) lub bliskości (closeness) mogą być obliczane, ale muszą być interpretowane ze świadomością, że ścieżki zawsze naprzemiennie przechodzą między partycjami. Preferowane są dwudzielne współczynniki klasteryzacji (takie jak współczynnik redundancji), ponieważ respektują one ograniczenie strukturalne, zgodnie z którym aktorzy nigdy nie łączą się bezpośrednio ze sobą.

4

Graf dwumodowy jest opcjonalnie zwijany do jednej lub obu projekcji jednomodowych. W projekcji aktorów dwóch aktorów jest połączonych, jeśli mają co najmniej jedno wspólne zdarzenie; wagi krawędzi zazwyczaj kodują liczbę wspólnych zdarzeń lub ważony wynik współuczestnictwa. Projekcja odrzuca informacje, dlatego zaleca się ważone projekcje i porównanie z modelem zerowym BiRG, aby ocenić, które współuczestnictwa są statystycznie nieoczekiwane.

5

Rankingi centralności, współczynniki klasteryzacji i struktura projekcji są interpretowane w kategoriach dziedzinowych — na przykład, identyfikując najbardziej wpływowych autorów w sieci współautorstwa, najczęściej uczęszczane wydarzenia w sieci aktor–zdarzenie lub najsilniejsze pary współzakupów w sieci handlowej. Wyniki powinny być porównywane z modelem zerowym, aby odróżnić znaczące wzorce strukturalne od przypadkowych fluktuacji.

Częste pułapki

  • Traktowanie grafu dwudzielnego jako grafu jednomodowego poprzez ignorowanie przynależności do partycji — narusza to założenie strukturalne i prowadzi do bezsensownych metryk.
  • Używanie nieważonej projekcji, gdy zdarzenia znacznie różnią się wielkością uczestnictwa — współuczestnictwo w dwuosobowych warsztatach nie powinno mieć takiej samej wagi jak współuczestnictwo w konferencji dla tysiąca osób; zamiast tego należy używać ważonych projekcji.
  • Stosowanie jednomodowych współczynników klasteryzacji bez dostosowania — ponieważ aktorzy nigdy nie mają bezpośrednich krawędzi, naiwne współczynniki klasteryzacji sprowadzają się do zera; należy użyć miary klasteryzacji odpowiedniej dla grafów dwudzielnych.
  • Pomijanie porównania z modelem zerowym — bez punktu odniesienia BiRG niemożliwe jest ocenienie, czy obserwowana liczba współuczestnictw jest strukturalnie znacząca, czy po prostu wynika z wysokiego stopnia.

Najczęściej zadawane pytania

Czym sieć dwudzielna różni się od zwykłej (jednomodowej) sieci?

W zwykłej sieci wszystkie węzły mogą potencjalnie łączyć się z dowolnym innym węzłem. W sieci dwudzielnej węzły są podzielone na dwa rozłączne zbiory — aktorów i zdarzeń — a krawędzie są dozwolone tylko przez granicę partycji. To ograniczenie odzwierciedla naturalną strukturę danych afiliacyjnych, gdzie ludzie dołączają do grup, ale grupy nie łączą się bezpośrednio z innymi grupami.

Co robi projekcja i kiedy powinienem jej używać?

Projekcja zwija graf dwumodowy w graf jednomodowy poprzez łączenie aktorów, którzy mają co najmniej jedno wspólne zdarzenie (lub zdarzeń, które mają co najmniej jednego wspólnego aktora). Jest to przydatne, gdy chcesz zastosować standardowe metryki jednomodowe, ale powoduje utratę informacji. Zawsze używaj ważonych projekcji i porównuj z modelem zerowym, aby odróżnić znaczące współuczestnictwo od przypadkowego nakładania się wynikającego z wysokiego stopnia.

Czy mogę używać standardowych miar centralności w grafie dwudzielnym?

Standardowe miary, takie jak stopień, pośrednictwo (betweenness) i bliskość (closeness), mogą być obliczane, ale muszą być interpretowane ostrożnie, ponieważ wszystkie ścieżki naprzemiennie przechodzą między partycjami. Wersje współczynników klasteryzacji dostosowane do grafów dwudzielnych są zdecydowanie preferowane w stosunku do ich jednomodowych odpowiedników, które w grafie dwudzielnym z definicji sprowadzają się do zera.

Jaka jest minimalna wymagana wielkość danych?

Zaleca się minimum 20 węzłów łącznie w obu partycjach, aby metryki strukturalne były znaczące. Bardzo małe grafy dwudzielne dają bardzo niestabilne oszacowania centralności. Jeśli Twoja sieć jest mniejsza, opisowe podsumowania stopnia i liczby współuczestnictw są bardziej informatywne niż globalne metryki strukturalne.

Pokrewne metody

Źródła

  1. Borgatti, S.P. & Everett, M.G. (1997). Network Analysis of 2-Mode Data. Social Networks, 19(3), 243-269.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Guillaume, J.L. & Latapy, M. (2006). Bipartite Structure of All Complex Networks. Information Processing Letters, 90(5), 215-221.

    Otwórz odnośnik do publikacji
    Skopiowano.