Identificar bordes inútiles para el camino más corto

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

Digo que una subgrafía de (con el mismo conjunto de vértices) es sp-equivalente a si . En otras palabras, quitar bordes para ir de a no cambia la longitud de los caminos más cortos; los bordes eliminados no son necesarios para ninguna ruta más corta. $G'$ $G$ $G$ $M_G = M_{G'}$ $G$ $G'$

En general, no hay un único subgrafo sp-equivalente de que sea mínimo para su inclusión. Por ejemplo, si no está dirigido y todos los bordes tienen un peso , cualquier árbol de expansión de es un subgrafo mínimo equivalente en sp (de hecho, cualquier borde en un ciclo podría eliminarse, pero desconectar un par de vértices obviamente cambia la distancia). Sin embargo, todavía puedo llamar inútiles los bordes de si no están en un subgrafo equivalente mínimo sp, necesario si están en todos los subgrafos mínimos equivalentes sp (es decir, en su intersección), y opcional si están en algunos de ellos (es decir , en su unión). $G$ $G$ $0$ $G$ $G$

Mi primera pregunta es: ¿Estas nociones tienen un nombre estándar?

Mi segunda pregunta es: ¿Cuál es la complejidad de clasificar los bordes de de esta manera, dependiendo de si no está dirigido o dirigido, y de la función de agregación? $G$ $G$

(Por ejemplo, para no dirigido y para , las subgrafías mínimas equivalentes a sp abarcan árboles de peso mínimo, por lo que al menos si todos los pesos de los bordes son diferentes, la clasificación se calcula fácilmente calculando el árbol de expansión mínimo único, pero en general No sé cómo funcionan las cosas.) $G$ $\max$

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

"Por ejemplo, si G no está dirigido y no está ponderado, cualquier árbol de expansión de G es un subgráfico mínimo equivalente en sp". Esto no parece ser cierto: en todas las distancias son , pero ningún árbol de expansión de tiene esta propiedad. De hecho, ningún subgrafo lo hace. De lo contrario, esto suena como una llave inglesa en.wikipedia.org/wiki/Graph_spanner#Distance

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

Sasho Nikolov

De hecho, para cualquier gráfico no ponderado no dirigido , no existe un subgrafo equivalente sp: si un subgrafo no incluye el borde , entonces .

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

Creo que al menos podemos decir que la identificación es tan fácil como la ruta más corta de todos los pares: si hay un borde pero el camino más corto de a es más corto que ese borde, entonces el borde es "inútil" (siempre debemos utilizar esa ruta más corta en lugar de este borde, en cualquier escenario); por el contrario, si un borde es "inútil", entonces debe haber una ruta más corta que esa longitud del borde de a . Así que solo itera sobre los bordes y verifica si hay una ruta más corta que ese borde. (Lo anterior es para la ruta más corta habitual, no he pensado en la regla de agregación .)

(u, v)

$(u,v)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

usul

Es posible que desee buscar "preservadores de distancia"

arnab

Sasho Nikolov: Lo siento, para gráficos no dirigidos y no ponderados, quise decir bordes de peso 0, no 1. Reformulando esto en la pregunta.

a3nm

Si está buscando una forma de nombrar (o caracterizar alternativamente) estos bordes que llama "inútiles" y "necesarios", podría referirse a ellos como los bordes con centralidad de intermediación = 0 y = 1, respectivamente. Cada borde puede clasificarse como teniendo = 0, = 1 o en (0,1) medida de intermediación en el tiempo de todos los pares de caminos más cortos.

Esta es una medida bien estudiada de los bordes de la red, y existen algoritmos rápidos para actualizar todos los puntajes de centralidad de los bordes al eliminar los bordes (pero no estoy seguro acerca de otras perturbaciones).

La función de centralidad está integrada en la mayoría de los análisis de red que he visto, y también hay una definición que se aplica a los gráficos dirigidos:

(editar: el enlace que proporcioné inicialmente solo discutía la centralidad de intermediación de nodos, pero aquí está el único artículo de Wikipedia que puedo encontrar que analiza la centralidad de intermediación de bordes: http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm Aún así, la intermediación es una medida estándar que generalmente se puede encontrar en los paquetes de análisis de red).

JimN
fuente

Creo que la diferencia entre la centralidad de intermediación de nodos y la centralidad de intermediación de bordes no es esencial porque siempre se pueden agregar nodos intermedios a los bordes, o copiar nodos y agregar un borde de una copia a la otra, para reducir una definición a la otra. Este es un puntero útil, ¡gracias por informarme de esto!

a3nm 01 de

Identificar bordes inútiles para el camino más corto

Respuestas: