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

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 ). $G$ $M_G$ $G$ $M_G[i, j]$ $i$ $j$ $G$ $+$ $\max$

Powiedzieć, że subgraph $G'$ z $G$ (z tego samego zestawu Vertex) jest sp równoważne do $G$ jeśli $M_G = M_{G'}$ . 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 równoważnego sp, który byłby $G$ minimalny 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? $G$ $G$

(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.) $G$ $\max$

ds.algorithms reference-request graph-algorithms shortest-path a3nm
źródło

„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

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

Sasho Nikolov

W rzeczywistości, dla żadnego niekierowanego nieważonego wykresu , nie istnieje podgrupa ekwiwalentu sp: jeśli podgrupa nie zawiera krawędzi , to .

G

$G$

G^{'}

$G'$

(u, v)

$(u, v)$

1 = M_{G} [u, v] < M_{G^{'}} [u, v]

$1 = M_G[u, v] < M_{G'}[u, v]$

Sasho Nikolov,

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)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

usul

Możesz poszukać „konserwatorów odległości”

arnab

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

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

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

Odpowiedzi: