Identyfikacja bezużytecznych krawędzi dla najkrótszej ścieżki

11

Rozważmy wykres (problem ma sens zarówno dla wykresów skierowanych, jak i niekierowanych). Nazwij macierzą odległości : to najkrótsza odległość ścieżki od wierzchołka do wierzchołka w dla pewnej stałej funkcji agregacji (na przykład lub ).M G G M G [ i , j ] i j G + maxGMGGMG[i,j]ijG+max

Powiedzieć, że subgraph G z G (z tego samego zestawu Vertex) jest sp równoważne do G jeśli MG=MG . Innymi słowy, usunięcie krawędzi, aby przejść z G do G nie zmienia długości najkrótszych ścieżek; usunięte krawędzie nie są wymagane w przypadku najkrótszej ścieżki.

Zasadniczo nie ma pojedynczego podgraphu G równoważnego sp, który byłby Gminimalny do włączenia. Na przykład, jeśli G jest przekierowane, a wszystkie krawędzie mają wagę 0 , każde drzewo rozpinające G jest minimalnym podgraphem równoważnym sp (faktycznie, każda krawędź w cyklu mogłaby zostać usunięta, ale rozłączenie pary wierzchołków oczywiście zmienia odległość). Jednak nadal mogę nazywać krawędzie G bezużytecznymi, jeśli nie są w minimalnym podgrodzie równoważnym sp, konieczne, jeśli znajdują się we wszystkich minimalnych podgraphach równoważnych sp (tj. W ich przecięciu), i opcjonalne, jeśli znajdują się w niektórych z nich (tj. , w ich związku).

Moje pierwsze pytanie brzmi: czy te pojęcia mają standardową nazwę?

Moje drugie pytanie brzmi: jaka jest złożoność klasyfikacji krawędzi w ten sposób, w zależności od tego, czy jest nieukierunkowe czy ukierunkowane, oraz od funkcji agregacji?GGG

(Na przykład dla bezkierunkowego i dla minimalne podgrupy równoważne sp są drzewami o minimalnej wadze, więc przynajmniej jeśli wszystkie wagi krawędzi są różne, klasyfikację można łatwo obliczyć, obliczając unikalne minimalne drzewo opinające, ale ogólnie Nie wiem, jak to działa.)maksGmax

a3nm
źródło
2
„Na przykład, jeśli G jest nieukierowane i nieważone, każde drzewo rozpinające G jest minimalnym podgraphem równoważnym sp.” Nie wydaje się to prawdą: w wszystkie odległości wynoszą , ale żadne drzewo nie ma tej właściwości. W rzeczywistości nie ma podgrupy. W przeciwnym razie brzmi to jak klucz en.wikipedia.org/wiki/Graph_spanner#Distance 1 K nKn1Kn
Sasho Nikolov
5
W rzeczywistości, dla żadnego niekierowanego nieważonego wykresu , nie istnieje podgrupa ekwiwalentu sp: jeśli podgrupa nie zawiera krawędzi , to . G ( u , v ) 1 = M G [ u , v ] < M G [ u , v ]GG(u,v)1=MG[u,v]<MG[u,v]
Sasho Nikolov,
2
Myślę, że możemy przynajmniej powiedzieć, że identyfikacja jest tak łatwa, jak najkrótsza ścieżka wszystkich par: jeśli istnieje krawędź ale najkrótsza ścieżka od do jest krótsza niż ta krawędź, wówczas krawędź jest „bezużyteczna” (w każdym scenariuszu powinniśmy zawsze wykorzystywać tę krótszą ścieżkę zamiast tej krawędzi); i odwrotnie, jeśli krawędź jest „bezużyteczna”, wówczas musi istnieć krótsza ścieżka niż długość krawędzi od do . Więc po prostu iteruj po krawędziach i sprawdź, czy istnieje krótsza ścieżka niż ta krawędź. (Powyższe dotyczy zwykłej najkrótszej ścieżki, nie myślałem o regule agregacji .)u v u v max(u,v)uvuvmax
usul
3
Możesz poszukać „konserwatorów odległości”
arnab
2
Sasho Nikolov: Przepraszam, w przypadku wykresów niekierowanych i nieważonych miałem na myśli krawędzie o wadze 0, a nie 1. Przeformułowanie tego w pytaniu.
a3nm

Odpowiedzi:

3

Jeśli szukasz sposobu nazwania (lub naprzemiennego scharakteryzowania) tych krawędzi, które nazywasz „bezużytecznymi” i „niezbędnymi”, możesz nazywać je odpowiednio krawędziami o centralności pomiędzy = 0 i = 1. Każda krawędź może być sklasyfikowana jako posiadająca = 0, = 1 lub w (0,1) miarę miary odstępowości w czasie wszystkich par najkrótszych ścieżek.

Jest to dobrze zbadana miara krawędzi sieci i istnieją szybkie algorytmy do aktualizacji wszystkich wyników centralności krawędzi po usunięciu krawędzi (ale nie jestem pewien co do innych zaburzeń).

Funkcja centralności jest wbudowana w prawie każdą analizę sieci, jaką widziałem, i istnieje definicja, która dotyczy również grafów ukierunkowanych:

(edytuj: link, który podałem początkowo tylko omawiał centralność między węzłami, ale tutaj jest jedyny artykuł w Wikipedii, który omawia centralność między krawędziami: http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorytm Nadal krawędź jest standardową miarą, którą zwykle można znaleźć w pakietach do analizy sieci.)

JimN
źródło
Uważam, że różnica między centralnością węzłów między centralnością a centralnością zależności między krawędziami jest nieistotna, ponieważ zawsze można dodawać węzły pośrednie do krawędzi lub kopiować węzły i dodawać jedną krawędź z jednej kopii do drugiej, aby zmniejszyć jedną definicję do drugiej. Jest to przydatny wskaźnik, dzięki za poinformowanie mnie o tym!
a3nm