Projekcja sieci dwustronnej
Projekcja sieci dwudzielnej jest szeroko stosowaną metodą kompresji informacji o sieciach dwudzielnych . Ponieważ projekcja jednomodowa jest zawsze mniej informacyjna niż oryginalny wykres dwudzielny, często wymagana jest odpowiednia metoda ważenia połączeń sieciowych. Optymalne metody ważenia odzwierciedlają charakter konkretnej sieci, są zgodne z założeniami projektanta i mają na celu minimalizację utraty informacji.
Tło
Sieci dwudzielne są szczególną klasą sieci złożonych , których węzły są podzielone na dwa zbiory X i Y, a dozwolone są tylko połączenia między dwoma węzłami w różnych zbiorach. Dla wygody bezpośredniego pokazania struktury relacji między określonym zestawem węzłów, sieci dwudzielne są zwykle kompresowane przez projekcję jednomodową. Oznacza to, że powstająca sieć zawiera węzły tylko jednego z dwóch zestawów, a dwa węzły X (lub alternatywnie Y) są połączone tylko wtedy, gdy mają co najmniej jeden wspólny sąsiedni węzeł Y (lub alternatywnie X).
Najprostsza metoda polega na odwzorowaniu sieci dwudzielnej na sieć nieważoną, bez uwzględnienia topologii sieci czy częstotliwości współdzielenia połączenia z elementami przeciwstawnego zbioru. Ponieważ sieci dwuczęściowe o bardzo różnych strukturach mogą mieć w tym przypadku dokładnie taką samą reprezentację jednomodową, klarowna ilustracja oryginalnej topologii sieci zwykle wymaga zastosowania jakiejś metody ważenia.
Możliwe metody ważenia
W zależności od potrzeb projektanta i właściwości topologicznych danej sieci zaproponowano kilka różnych metod ważenia. Ponieważ stwierdzono, że redystrybucja wag ma silny wpływ na strukturę społeczności (zwłaszcza w gęstych sieciach), należy ostrożnie dokonywać wyboru metodologicznego.
- Proste ważenie. Proste ważenie oznacza, że krawędzie są ważone bezpośrednio przez liczbę powtórzeń wspólnego skojarzenia. (Jest to metoda zastosowana na załączonym wykresie po prawej stronie.) To podejście sprawdza się w szerokim zakresie ustawień, takich jak kuchnia molekularna lub większość sieci społecznościowych. Może to jednak wprowadzać w błąd, jeśli krańcowy wpływ jednego dodatkowego powiązania nie jest ustalony, ale zależy od pewnych cech sieci (np. od pierwotnej wagi między odpowiednimi węzłami). Może tak być na przykład we współpracy naukowej, jak zauważyli Fan i in. .
- Ważenie hiperboliczne. W typowym przypadku malejącego krańcowego udziału dodatkowych łączy w węźle, użycie prostego ważenia może nie być zbyt pouczające. Na przykład w sieciach współpracy naukowej oczekuje się, że dwóch naukowców, których nazwiska pojawiają się w artykule wraz z wieloma innymi współautorami, zna się mniej niż dwóch, którzy byli jedynymi autorami artykułu. Aby uwzględnić ten tak zwany efekt nasycenia, zaproponowano odwrotne ważenie krawędzi zgodnie z liczbą wspólnych przynależności w sąsiednim zbiorze. Najłatwiej to osiągnąć, wprowadzając współczynnik skalowania 1/( n - 1) do prostej liczby, co osłabia powiązanie między węzłami z bardziej popularnymi wspólnymi dopasowaniami.
- Ważenie oparte na alokacji zasobów. Przy ważeniu prostym i hiperbolicznym rzutowana macierz sąsiedztwa jest zawsze ustawiona jako symetryczna, co oznacza, że połączenie między dwoma rzutowanymi węzłami ma taką samą wagę dla obu wierzchołków. Ponadto informacje zawarte w krawędziach, których „docelowe” węzły mają stopień 1 w oryginalnej sieci, zostaną utracone w projekcji, co może mieć poważne konsekwencje w niektórych rzeczywistych sieciach z wieloma niezależnymi zestawami krawędzi . Aby przezwyciężyć te niedociągnięcia, Zhou i in. zaproponował metodę ważenia opartą na założeniu, że pewna ilość zasobów jest powiązana z każdym węzłem w projekcji, a waga kierunkowa w_ij reprezentuje proporcję zasobów, które węzeł j chciałby rozdysponować do węzła i . Alokacja zasobów opiera się na grafie dwudzielnym, obejmuje równą dystrybucję między sąsiadami i składa się z dwóch kroków: najpierw ze zbioru rzutowanego do zbioru nieprojektowanego, a następnie z powrotem. Symulacje numeryczne wskazują, że ta metoda projekcji może działać znacznie lepiej niż niektóre powszechnie stosowane metody (takie jak filtrowanie oparte na współpracy ) do celów osobistych rekomendacji .
Niektóre godne uwagi aplikacje
- Sieć smakowa i zasady parowania potraw
- Sieć współpracy naukowej
- Korporacyjna elitarna sieć
- Sieć chorób ludzkich