Identifizieren Sie nutzlose Kanten für den kürzesten Weg

$G$ $M_G$ $G$ $M_G[i, j]$ $i$ $j$ $G$ $+$ $\max$

Ich sage, dass ein Untergraph von (mit derselben Scheitelpunktmenge) sp-äquivalent zu wenn . Mit anderen Worten, das Entfernen von Kanten von nach ändert nicht die Länge der kürzesten Wege; Die entfernten Kanten sind für einen kürzesten Weg nicht erforderlich . $G'$ $G$ $G$ $M_G = M_{G'}$ $G$ $G'$

Im Allgemeinen gibt es keinen einzelnen sp-äquivalenten Teilgraphen von , der für die Aufnahme minimal ist. Wenn beispielsweise ungerichtet ist und alle Kanten das Gewicht , ist jeder Spannbaum von ein minimaler sp-äquivalenter Teilgraph (tatsächlich könnte jede Kante in einem Zyklus entfernt werden, aber das Trennen eines Scheitelpunktpaars ändert offensichtlich den Abstand). Ich kann jedoch Kanten von immer noch als nutzlos bezeichnen, wenn sie sich nicht in einem minimalen sp-äquivalenten Untergraphen befinden. Dies ist erforderlich, wenn sie sich in allen minimalen sp-äquivalenten Untergraphen befinden (dh in ihrem Schnittpunkt), und optional, wenn sie sich in einigen von ihnen befinden (dh in ihrer Vereinigung). $G$ $G$ $0$ $G$ $G$

Meine erste Frage lautet: Haben diese Begriffe einen Standardnamen?

Meine zweite Frage lautet: Wie komplex ist die Klassifizierung der Kanten von auf diese Weise, abhängig davon, ob ungerichtet oder gerichtet ist, und von der Aggregationsfunktion? $G$ $G$

(Zum Beispiel überspannen für ungerichtet und für die minimalen sp-äquivalenten Untergraphen Bäume mit minimalem Gewicht. Zumindest wenn alle Kantengewichte unterschiedlich sind, kann die Klassifizierung leicht berechnet werden, indem der eindeutige minimale Spannbaum berechnet wird, aber im Allgemeinen Ich weiß nicht, wie die Dinge funktionieren.) $G$ $\max$

ds.algorithms reference-request graph-algorithms shortest-path a3nm
quelle

"Wenn beispielsweise G ungerichtet und ungewichtet ist, ist jeder Spannbaum von G ein minimaler sp-äquivalenter Untergraph." Dies scheint nicht wahr zu sein: In alle Abstände , aber kein Spannbaum von hat diese Eigenschaft. Tatsächlich tut dies kein Untergraph. Andernfalls klingt dies wie ein Schraubenschlüssel en.wikipedia.org/wiki/Graph_spanner#Distance

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

Sasho Nikolov

Tatsächlich existiert für jeden ungerichteten ungewichteten Graphen kein sp-äquivalenter Untergraph: Wenn ein Untergraph keine Kante , dann ist .

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

Ich denke, wir können zumindest sagen, dass die Identifizierung so einfach ist wie der kürzeste Weg aller Paare: Wenn es eine Kante aber der kürzeste Weg von nach kürzer als diese Kante ist, dann ist die Kante "nutzlos". (Wir sollten in jedem Szenario immer diesen kürzeren Pfad anstelle dieser Kante verwenden.) Wenn umgekehrt eine Kante "nutzlos" ist, muss es einen kürzeren Pfad als diese Kantenlänge von nach . Iterieren Sie also einfach über Kanten und prüfen Sie, ob es einen kürzeren Pfad als diese Kante gibt. (Das obige ist für den üblichen kürzesten Weg, habe nicht über die Aggregationsregel nachgedacht .)

(u, v)

$(u,v)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

Usul

Vielleicht möchten Sie "Distanzschoner" nachschlagen

Arnab

Sasho Nikolov: Entschuldigung, für ungerichtete und ungewichtete Diagramme habe ich Kanten mit Gewicht 0 und nicht 1 gemeint. Dies in der Frage umformulieren.

A3nm

Wenn Sie nach einer Möglichkeit suchen, diese Kanten, die Sie als "nutzlos" und "notwendig" bezeichnen, zu benennen (oder alternativ zu charakterisieren), können Sie sie als Kanten mit einer Zentralität zwischen den Werten = 0 bzw. = 1 bezeichnen. Jede Kante kann als mit = 0, = 1 oder in (0,1) Zwischenmaß in der Zeit aller Paare-kürzesten Pfade klassifiziert werden.

Dies ist ein gut untersuchtes Maß für Netzwerkkanten, und es gibt schnelle Algorithmen zum Aktualisieren aller Zentralitätswerte der Kanten bei Kantenlöschungen (bei anderen Störungen bin ich mir jedoch nicht sicher).

In fast jeder Netzwerkanalyse, die ich gesehen habe, ist eine Zentralitätsfunktion integriert, und es gibt eine Definition, die auch für gerichtete Diagramme gilt:

(Bearbeiten: Der Link, den ich anfangs gegeben habe, hat nur die Zentralität von Knoten zwischen Gleichheit besprochen, aber hier ist der einzige Wikipedia-Artikel, der die Zentralität von Kanten zwischen Gleichheit beschreibt: http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm Trotzdem ist die Kantenverflechtung ein Standardmaß, das normalerweise in Netzwerkanalysepaketen zu finden ist.)

JimN
quelle

Ich denke, der Unterschied zwischen der Zentralität zwischen Knoten und der Zentralität zwischen Kanten ist unwesentlich, da Sie Kanten immer Zwischenknoten hinzufügen oder Knoten kopieren und eine Kante von einer Kopie zur anderen hinzufügen können, um eine Definition zur anderen zu reduzieren. Dies ist ein nützlicher Hinweis, danke, dass Sie mich darauf aufmerksam gemacht haben!

A3nm

Identifizieren Sie nutzlose Kanten für den kürzesten Weg

Antworten: