Złącze Wienera

W teorii sieci łącznik Wienera jest środkiem maksymalizacji wydajności łączenia określonych „wierzchołków zapytań” w sieci. Mając spójny , nieskierowany graf i zestaw wierzchołków zapytania w grafie, minimalny łącznik Wienera jest indukowanym podgrafem , który łączy wierzchołki zapytania i minimalizuje sumę najkrótszych odległości ścieżek spośród wszystkich par wierzchołków w podgrafie. W optymalizacji kombinatorycznej problem minimalnego łącznika Wienera jest problem znalezienia minimalnego złącza Wienera. Można to traktować jako wersję klasycznego problemu drzewa Steinera (jeden z 21 problemów NP-zupełnych Karpa ), w którym zamiast minimalizować rozmiar drzewa, celem jest minimalizacja odległości w podgrafie.

Minimalny łącznik Wienera został po raz pierwszy przedstawiony przez Ruchansky i in. w 2015 roku

Minimalny łącznik Wienera ma zastosowania w wielu domenach, w których istnieje struktura grafu i zainteresowanie poznaniem powiązań między zbiorami osobników. Na przykład, biorąc pod uwagę zestaw pacjentów zakażonych chorobą wirusową, jakich innych pacjentów należy sprawdzić, aby znaleźć winowajcę? Lub biorąc pod uwagę zestaw białek będących przedmiotem zainteresowania, jakie inne białka uczestniczą z nimi w szlakach?

Złącze Wienera zostało nazwane na cześć chemika Harry'ego Wienera , który jako pierwszy wprowadził Indeks Wienera .

Definicja problemu

Indeks Wienera jest sumą długości najkrótszych ścieżek na (pod)grafie. Używając $,$ oznaczenia najkrótszej ścieżki między i ${\ displaystyle$ , indeksu Wienera (pod) wykresu re ( $S}$ $v ) {\$ $Displaystyle d (u$ , oznaczony jako ${\ Displaystyle W (S)}$

{\ Displaystyle W (S) = \ suma _ {(u, v) \ w S} d (u, v)}

.

Minimalny problem złącza Wienera jest zdefiniowany w następujący sposób. $. displaystyle H\subseteq V}$ $pod$ nieskierowany i nieważony wykres ze zbiorem $zestawem$ $oraz$ wierzchołków , łącznik minimalnego indeksu Wienera. Bardziej formalnie problem polega na obliczeniu

\ Displaystyle \ nazwa operatora {*} {arg \, min} _ {H} W (H \ kubek Q)}

,

to znaczy znajdź złącze , które minimalizuje sumę najkrótszych ścieżek w $}$ $\ displaystyle H$ .

Związek z drzewem Steinera

Optymalne rozwiązania problemu drzewa Steinera i minimalnego łącznika Wienera mogą się różnić. Zdefiniuj zbiór wierzchołków zapytania Q przez Q = { v ₁ , …, v ₁₀ }. Jedynym optymalnym rozwiązaniem problemu drzewa Steinera jest Q , które ma indeks Wienera 165, podczas gdy optymalnym rozwiązaniem problemu minimalnego łącznika Wienera jest Q ∪ { r ₁ , r ₂ }, które ma indeks Wienera 142.

Problem minimalnego złącza Wienera jest powiązany z problemem drzewa Steinera . W pierwszym przypadku funkcją celu w minimalizacji jest indeks Wienera łącznika, natomiast w drugim funkcją celu jest suma wag krawędzi w łączniku. Optymalne rozwiązania tych problemów mogą się różnić, biorąc pod uwagę ten sam graf i zestaw wierzchołków zapytania. W rzeczywistości rozwiązanie problemu drzewa Steinera może być arbitralnie złe dla problemu minimalnego łącznika Wienera; wykres po prawej stronie zawiera przykład.

Złożoność obliczeniowa

Twardość

Problem jest NP-trudny i nie dopuszcza schematu aproksymacji w czasie wielomianowym , chyba że P = NP . Można to udowodnić za pomocą nieaproksymowalności pokrycia wierzchołków w grafach o ograniczonych stopniach. Chociaż nie ma schematu aproksymacji w czasie wielomianowym, istnieje aproksymacja ze stałym współczynnikiem w czasie wielomianowym - algorytm, który znajduje łącznik, którego indeks Wienera mieści się w stałym mnożniku indeksu Wienera optymalnego łącznika. Pod względem klas złożoności minimalny problem ze złączem Wienera występuje w APX , ale nie w PTAS , chyba że P = NP .

Dokładne algorytmy

$,$ daje algorytm, który znajduje optymalne rozwiązanie w to to czas wykładniczy ) na grafach o n wierzchołkach. W szczególnym przypadku, gdy istnieją dokładnie dwa wierzchołki zapytania, optymalnym rozwiązaniem jest najkrótsza ścieżka łącząca te dwa wierzchołki, więc problem można rozwiązać w czasie wielomianowym obliczając najkrótszą drogę. W rzeczywistości dla dowolnej stałej liczby wierzchołków zapytania optymalne rozwiązanie można znaleźć w czasie wielomianowym.

Algorytmy aproksymacyjne

Istnieje algorytm aproksymacji ze stałym współczynnikiem dla problemu minimalnego łącznika Wienera, który działa w czasie ${\ Displaystyle O (q (m \ log n + n \ log ^ {2}n))}$ na grafie o n wierzchołkach, m krawędziach i q wierzchołkach zapytania, mniej więcej tyle samo czasu, ile zajmuje obliczenie odległości najkrótszej ścieżki od wierzchołków zapytania do każdego innego wierzchołka grafu. Centralnym podejściem tego algorytmu jest zredukowanie problemu do problemu drzewa Steinera ważonego wierzchołkami, który dopuszcza przybliżenie ze stałym współczynnikiem w poszczególnych przypadkach związanych z problemem minimalnego łącznika Wienera.

Zachowanie

Minimalny łącznik Wienera zachowuje się jak centralność pośrednia .

Kiedy wierzchołki zapytania należą do tej samej społeczności, wierzchołki niezwiązane z zapytaniem, które tworzą minimalny łącznik Wienera, zwykle należą do tej samej społeczności i mają wysoką centralność w społeczności. Takie wierzchołki prawdopodobnie będą wpływowymi wierzchołkami odgrywającymi role przywódcze w społeczności. W sieci społecznościowej te wpływowe wierzchołki mogą być dobrymi użytkownikami do rozpowszechniania informacji lub celowania w wirusowej kampanii marketingowej.

Kiedy wierzchołki zapytania należą do różnych społeczności, wierzchołki niezwiązane z zapytaniem, które tworzą minimalny łącznik Wienera, zawierają wierzchołki przylegające do krawędzi, które łączą różne społeczności. Te wierzchołki obejmują dziurę strukturalną w grafie i są ważne.

Aplikacje

Minimalny łącznik Wienera jest przydatny w aplikacjach, w których chce się poznać związek między zbiorem wierzchołków grafu. Na przykład,

w biologii zapewnia wgląd w to, w jaki sposób zestaw białek w sieci interakcji białko-białko jest powiązany,
w sieciach społecznościowych (takich jak Twitter ) pokazuje społeczności, do których należy grupa użytkowników i jak te społeczności są ze sobą powiązane,
w sieciach komputerowych może być przydatny do określenia skutecznego sposobu kierowania wiadomości multiemisji do zestawu miejsc docelowych.