Grafy oparte na sile: rysowanie sieci symulacją fizyki

Zamiana wykresu na problem fizyczny

Wykres – węzły i krawędzie łączące je – nie posiada wrodzonej geometrii 2D; ten sam wykres może być narysowany setki razy, zwykle jako nieczytelne splątanie. Rozkład siłowy (force-directed layout) omija kombinatoryczne poszukiwania dobrego rysunku, zamieniając problem na symulację fizyczną: traktuje każdy węzeł jako cząstkę obciążoną, która odpycha wszystkie inne węzły, a każdą krawędź jako sprężynę, która przyciąga jej dwa połączone węzły. Uruchom symulację do przodu i pozwól jej ustabilizować się w konfiguracji o niskiej energii, a wynikowy układ zazwyczaj staje się czytelny niemal przypadkiem – połączone węzły znajdują się blisko siebie, niepołączone węzły rozdzielone, a symetryczne podstruktury w wykresie często dają wizualnie symetryczne układy, wszystko bez tego, aby algorytm był o tym poinformowany.

Fruchterman-Reingold: standardowe sformułowanie

Najszerzej stosowana wersja, opracowana przez Fruchtermana i Reingolda (1991), definiuje dwie siły oparte na jednej charakterystycznej odległości k (w przybliżeniu idealnej długości krawędzi, często ustalanej z powierzchni obszaru podzielonej przez liczbę węzłów):

siła odpychająca (każdy parzysty węzeł): Fr(d) = k^2 / d

siła przyciągająca (tylko pary krawędzi): Fa(d) = d^2 / k

d = odległość między dwoma węzłami

Odpychanie popycha każdą parę węzłów do siebie z siłą rosnącą wraz ze zmniejszeniem się odległości (d w mianowniku), zapobiegając zwarceniu węzłów; przyciąganie spina ze sobą połączone węzły z siłą rosnącą wraz z wydłużeniem się odległości między nimi (d w liczniku), jak sprężyna rozciągana. W odległości charakterystycznej k, obie siły przybliżają równowagę, dlatego też k działa jako docelowa długość krawędzi: zwiększając ją, cała układ się rozprzestrzenia, a zmniejszając – węzły pakują się bardziej gęsto.

repulsive force (every node pair):   Fr(d) = k^2 / d
attractive force (edge pairs only):  Fa(d) = d^2 / k

d = distance between the two nodes

Dlaczego potrzebne jest chłodzenie i dlaczego jest to kosztowne

Pozostawione bez iteracji z pełną siłą w nieskończ czas, węzłami mogą oscylować wokół ich równowagi zamiast ustawać, odbijając się od siebie, gdy dwie siły przeciekają i nadkorygują je. Standardowe rozwiązanie to symulowane wyżarzanie: ogranicz, jak daleko może przesunąć się węzeł w jednym kroku (z ograniczeniem "temperatury") i stopniowo zmniejsz to ograniczenie w trakcie działania, tak że wczesne iteracje dokonają dużych, grubych zmian, a późniejsze iteracje dokonują małych, precyzyjnych korekt – dokładnie ten sam schemat chłodzenia używany w ogólnej optymalizacji symulowanego wyżarzania. Obliczeniowo, odpychanie się między każdą parą węzłów kosztuje O(n^2) na iterację, co jest w porządku dla grafów o kilkuset węzłach, ale staje się wąskim gardłem dla tysięcy; silniki do projektowania produkcji wykorzystują przybliżone podejście przestrzenne w stylu Barnesa-Huta (ta sama sztuczka quadtree używana w symulacjach grawitacyjnych N-ciał) do grupowania odległych klastrów węzłów w jednym przybliżonym źródle odpychania, co obniża koszt do około O(n log n).

Losowe modele grafów wpływają na układ w różny sposób

Charakter wizualny układu siłowego mówi tyle o strukturze grafu, co o algorytmie. Losowy graf Erdosa-Reniego (każde możliwe połączenie między węzłami uwzględniane niezależnie z ustalonym prawdopodobieństwem p) ma tendencję do prezentowania się jako stosunkowo jednolita, nieodróżnialna masa, ponieważ nie posiada preferencyjnej struktury, wokół której mógłby się skupić. Graf Barabasi-Alberta, budowany poprzez przyłączenie preferencyjne, w którym nowe węzły są bardziej skłonne do łączenia się z już popularnymi węzłami, generuje niewielką liczbę węzłów o wysokim stopniu – a te węzły widocznie przyciągają duże ilości węzłów o niskim stopniu do obrotu wokół nich pod wpływem sił sprężynowych, ponieważ węzeł z wieloma krawędziami doświadcza wielu przyciągających wpływów skierowanych na niego. Graf małej sieci Wattsa-Strogata – pierścieniowy układ z losowo przestawionymi krawędziami – układa się jako lokalnie skupiony pierścień z okazjonalnymi długodystansowymi połączeniami, wyraźnie widocznymi na układzie, bezpośrednią wizualną sygnaturą właściwości „małej sieci” (krótka średnia odległość ścieżki pomimo wysokiego lokalnego zwarcia), dla której model został zaprojektowany.

Analiza nieruchomego układu

Po ostudzeniu się symulacji, wiele właściwości strukturalnych staje się widocznie odczytywalne bez dodatkowego wysiłku. Gęsto połączone społeczności przyciągają się do siebie w zwarte, wyraźnie oddzielone skupiska (ze względu na ciągłe wewnętrzne naprężenia, które są minimalnie oddziaływane przez naprężenia skierowane od innych skupisk). Elementy łączące i krawędzie łączące dwa skupiska stają się widocznie naciągane, ponieważ walczą z naprężeniami dwóch oddzielnych skupisk jednocześnie. Stopień połączenia węzła koreluje luźno z jego centralnością, ponieważ wysoko połączony węzeł jest ciągle przyciągany przez wiele innych węzłów i ma tendencję do przesuwania się w kierunku środka masy układu. Żadne z tego nie jest programowane jawnie – jest to efekt uboczny minimalizacji tej samej funkcji energii, która pierwotnie umieściła każdy węzeł.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Force-Directed Graph i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.