Medida para el cambio de red después de agregar un borde

Question

Tengo un grafo de la red. Quiero tener una medida que me dice cuánto la adición de una cierta borde de los cambios de la red.

Por favor, eche un vistazo a este ejemplo:

Aquí, los bordes negros representan la red original. Es evidente que mediante la adición de la frontera verde, la estructura de la red no va a cambiar mucho. Sin embargo, si puedo añadir el borde rojo, los cambios en la red de manera significativa.

Hay métodos conocidos para el estudio de estos cambios?

Yo estaba pensando en una medida $m(N_{orig},N_{new})$ (donde $N_{orig}$ $N_{new}$ representa el original y el modificado de la red, respectivly) que toma en cuenta la distancia $d$ entre todos los vértices:

$$ m(N_{orig},N_{nuevo})=\sum_{\forall (V_i,V_j)} \left(d_{orig}(V_i,V_j) - d_{nuevo}(V_i,V_j) \right) $$

donde $V_i$ son los vértices de la red. En la red de ejemplo de arriba, $m(N_{orig},N_{black})=2$$m(N_{orig},N_{red})=90$. Es similar a la diferencia de la media de la longitud de la ruta, como se indica por DavidV en los comentarios.

Esto sería ideal, pero la distancia de red es caro para calcular para redes grandes (aproximadamente el $\mathcal{O}(V^2\cdot\log(V)+V\cdot E)$ para el Johnson, el algoritmo de o $\mathcal{O}(V^3)$ para el algoritmo Floyd–Warshall). Mi red tiene V~=5.000 y E~=900.000. Como quiero calcular muchas aristas, esta medida parece ser demasiado caro para mí.

Estoy feliz por todas las sugerencias! Gracias

Answer 1

Han considerado que el vértice de la conectividad de un grafo?

Es igual el número mínimo de vértices a eliminar antes de que usted puede esperar de desconectar el gráfico en componentes separados. Por ejemplo, para los árboles, el vértice de la conectividad es igual a $1$, debido a la eliminación de cualquier nodo se desconecta necesariamente el gráfico.

Es el polinomio de tiempo computable, que es interesante.

En tu ejemplo, si se elimina el medio de nodo, desconecte el gráfico, por lo que tiene el vértice de la conectividad $1$. La adición de la verde orilla claramente no afecta a la conectividad, pero la adición de la roja que uno hace, como la eliminación de la mitad de nodo ya no se desconecta el grafo con esta ventaja extra. Por lo tanto, esta podría ser una medida pertinente para su problema.

Arista-conectividad se define de la misma manera y puede ser utilizado también.

Answer 2

Una manera simple de medir cuán diferente es la red después de la adición de un borde es encontrar la longitud original de la ruta más corta tomó para llegar desde uno de los vértices para que el borde está conectado a los otros vértices.

En tu ejemplo, el camino más corto entre dos vértices conectados por la verde orilla antes de agregar la verde orilla era de dos bordes largos. Antes de agregar el borde rojo, el camino más corto entre dos nodos de siete de los bordes largos. Después de agregar el borde, el camino más corto para cualquier par de vértices se convierte en uno.

La idea básica aquí es que cuanto mayor sea el camino entre dos vértices, más el gráfico cambiará cuando un borde añadido.

Todo lo que realmente necesita es un algoritmo, por lo que esta medida no debería ser demasiado lento.

Edit: Como NicoDean señalado, esto por sí solo no tomar los vértices vecinos en cuenta. Creo que tengo una forma de evitar esto. Esto va a ser bastante duro para medir el cambio, pero usted debería ser capaz de modificarlo para que funcione. Voy a utilizar su gráfico como un ejemplo, y voy a etiquetar todos los nodos de izquierda a derecha en orden alfabético, por lo que la línea roja se conecta nodos $A$$J$, y la línea verde se conecta nodos $H$$L$. Cuando se conectan dos nodos que están indirectamente conectado, se forma un ciclo, en el que la longitud de ruta de acceso desde cualquier nodo en el ciclo a otro nodo, ya sea siendo el mismo, o sea independientemente de la duración de la ruta original entre los dos nodos conectados fue de menos la longitud de la ruta entre el nodo a uno de los nodos conectados más uno. En tu ejemplo, la adición de la línea roja, se crea el ciclo de $\{A, E, D, F, G, I, H, J\}$. Antes de agregar la línea roja, el camino más corto de$E$$J$$6$, ahora es $7-6+1=2$. A continuación, puede calcular la diferencia entre estos dos valores para encontrar la mejora. Hacer esto para cada punto en el ciclo y agregar a algunos ejecución total. Que se ocupa de los ciclos, y todo lo que realmente necesita es la longitud del ciclo. En el gráfico, el borde rojo afectados de todo, así que lío de mí porque todo lo que usted necesita para medir el cambio de la longitud de la línea. La segunda cosa a tener en cuenta es que la adición de una línea sólo afecta a las rutas que utilizan la línea. Por ejemplo, el camino más corto de $K$ $H$incluiría $IH$, pero la adición de la red de borde no tiene ningún efecto sobre la longitud de la trayectoria.

La última cosa que usted necesita considerar es que los nodos del ciclo de los nodos exteriores están conectados. Desde allí, usted debe encontrar la longitud de todos los caminos más cortos desde que el exterior nodo a cualquier punto en el ciclo antes y después de agregar el borde. Este algoritmo debe comenzar con los nodos que están conectados directamente a un nodo en el ciclo. Por ejemplo, si consideras $B$, es conectado a $A$$D$. El camino más corto longitudes de $A$ $D$ a cualquier nodo en el ciclo después de insertar el borde rojo se enumeran a continuación. $$(A, E) = 1; (D, E) = 1$$ $$(A, F) = 3; (D, F) = 1$$ $$(A, G) = 4; (D, G) = 2$$ $$(A, I) = 3; (D, I) = 3$$ $$(A, H) = 2; (D, H) = 4$$ $$(A, J) = 1; (D, J) = 3$$ El camino más corto de $B$ a cualquiera de los nodos en el ciclo es el mínimo de los dos números de hasta más de uno, así: $$(B, E) = 2$$ $$(B, F) = 2$$ $$(B, G) = 3$$ $$(B, I) = 3$$ $$(B, H) = 3$$ $$(B, J) = 2$$ Ahora, estas son las longitudes antes de añadir el borde: $$(A, E) = 1; (D, E) = 1$$ $$(A, F) = 3; (D, F) = 1$$ $$(A, G) = 4; (D, G) = 2$$ $$(A, I) = 5; (D, I) = 3$$ $$(A, H) = 6; (D, H) = 4$$ $$(A, J) = 7; (D, J) = 5$$ Después de elegir el menor longitud, esto es lo que tenemos para $B$ antes de añadir el borde: $$(B, E) = 2$$ $$(B, F) = 2$$ $$(B, G) = 3$$ $$(B, I) = 4$$ $$(B, H) = 5$$ $$(B, J) = 6$$ A continuación, podemos medir la mejora restando el antes y el después: $$(B, E) = 0$$ $$(B, F) = 0$$ $$(B, G) = 0$$ $$(B, I) = 1$$ $$(B, H) = 2$$ $$(B, J) = 4$$ El total de mejora para agregar el borde de la longitud de la trayectoria de B es, por tanto,$1+2+4=7$. A continuación, hacer el mismo proceso para todos los nodos que tienen al menos un borde conectado al ciclo y sumar el total de ejecución para la mejora. A continuación, siga el mismo proceso para todos los nodos conectados a las iniciales de los nodos, el cálculo de la mejora, y continuar hasta que se ha calculado el total de mejora. El mayor de la mejora, el más grande es el cambio. Por favor comentar si algo no está claro para usted, o ver cualquier error en mi razonamiento. Este algoritmo tiene la idea básica de abajo, pero usted debería ser capaz de utilizar como base para el algoritmo que se va a utilizar. El único problema que puedo ver con este algoritmo es que si usted tiene un preexistentes ciclo, la adición de una arista entre dos nodos, en este ciclo se divide en dos ciclos. Esta realidad no parece ser un problema.

Edit: Otro pequeño problema que me di cuenta es que si usted tiene dos vértices conectados entre sí que están a la misma distancia desde el ciclo, la mejora puede tener una dependencia circular. Esto puede ser solucionado por no considerar que el borde hasta que todos los otros bordes de los dos nodos han sido consideradas. A continuación, puede ejecutar la mejora del algoritmo en ambos bordes, asegúrese de agregar uno a todos los demás nodos del borde de longitudes.

Optimización: Cualquier nodo que no ve ninguna mejoría puede no deben ser considerados cuando se trata con los nodos conectados a él.

Este debe tener un tiempo de ejecución de algo como $O(E+V)$ por el simple búsqueda en anchura $O((E-L)*L^2)$ donde $E$ es el número total de aristas y $L$ es la longitud del ciclo, como la que usted necesita para encontrar la ruta más corta longitud para cada nodo en el ciclo, que es donde se obtiene el $L^2$, para cada uno de los borde fuera del ciclo, que es donde se obtiene el $E-L$. Se parece a $L$ debe ser relativamente baja, debido a la relación del número de bordes para el número de aristas que tendría que tener un grafo completo es bastante alto.

Reales de funcionamiento del Algoritmo Voy a usar mi algoritmo para calcular lo que yo llamo la "mejora" en la gráfica tanto de la línea roja y la línea verde. Voy a hacer la línea roja de la primera, ya que constituye un singular ciclo, mientras que la línea verde formularios de tres nuevos ciclos.

Lo primero que tenemos que hacer es encontrar el camino más corto entre dos nodos y calcular su longitud ($7$). Esto le llevará $O(V+E)$ del tiempo. Lo siguiente que tenemos que hacer es calcular la longitud de la ruta para cada nodo que va a ser en el ciclo antes de que el borde se agrega. Ese paso es muy simple, ya que sólo es necesario considerar los bordes en el ciclo. Lo siguiente que debemos hacer es calcular la ruta más corta longitud de todos los nodos en el ciclo no dentro de los límites de la mitad de la longitud ($\lceil{\frac7 2}\rceil=4$) de los dos nodos conectados después de agregar el borde. Sabemos que sólo tenemos que considerar estos nodos, porque sólo estos nodos va a experimentar un cambio en la ruta más corta. En este ejemplo, voy a utilizar la notación $(X,Y)=k$ para denotar la longitud de la ruta más corta entre el$X$$Y$.

Antes de $$(A,I)=5;*(E,I)=4;*(D,I)=3$$ $$(A,H)=6;(E,H)=5;*(D,H)=4$$ $$(A,J)=7;(E,J)=6;(D,J)=5$$

Después de $$(A,I)=3;*(E,I)=4;*(D,I)=3$$ $$(A,H)=2;(E,H)=3;*(D,H)=4$$ $$(A,J)=1;(E,J)=2;(D,J)=3$$

La protagonizó nodos experimentar ningún cambio y son sólo para fines de comparación más tarde en el algoritmo. Hay un montón de patrones en esto que usted debe ser capaz de averiguar observar en el gráfico, que usted probablemente puede utilizar para optimizar. A continuación, se agrega el total de mejora, a continuación, haga doble debido a que la ruta de las mejoras se aplican en ambas direcciones. El total de la mejora hasta el momento es $2*((3*(5-3))+(2*(6-2))+(1*(7-1))=36$. A partir de allí, se debe calcular para los nodos que no son parte del ciclo de tocar, pero el ciclo. Comenzando con $B$, se comparan los caminos más cortos entre todos los nodos a los que se conecta en el ciclo, que se $A$$D$.

Antes de $$(A,I)=5;(D,I)=3\implies(B,I)=4$$ $$(A,H)=6;(D,H)=4\implies(B,H)=5$$ $$(A,J)=7;(D,J)=5\implies(B,J)=6$$

Después de $$(A,I)=3;(D,I)=3\implies(B,I)=4$$ $$(A,H)=2;(D,H)=4\implies(B,H)=3$$ $$(A,J)=1;(D,J)=3\implies(B,J)=2$$

La mejora de $B$ por lo tanto $(4-4)+(5-3)+(6-2)=6$. El total de la mejora es que ahora se $36+6=42$. Ahora consideremos $C$, el cual está conectado a $D$$F$. Porque el único camino que mejoró fue la $(D,J)$, sólo necesitamos considerar el $(C,J)$ camino.

Antes de $$(D,J)=5;(F,J)=4\implies(C,J)=5$$

Después de $$(D,J)=3;(F,J)=4\implies(C,J)=4$$

La mejora de la $C$; el total de la mejora de la es $42+1=43$. El siguiente nodo a considerar es $K$. Esto es donde las cosas se ponen interesantes. En lugar de encontrar a $(K,J)$, podemos empezar a encontrar a $(K,A)$ porque $K$ está conectado a $I$, que no tiene $(I,J)$ camino que tenemos que verificar. También, debemos considerar que $K$ se conecta a $M$, que no es parte del ciclo. Para ello, hemos de ignorar que el borde hasta que calcular la distancia de cambio de ambas $K$$M$, de modo que podemos comparar con ellos. Para $K$, sólo necesitamos considerar el $(A,I)$ ruta de antes y después.

Antes de $$(A,I)=4\implies(K,A)=5$$ Después de $$(A,I)=3\implies(K,A)=4$$

$K$ mejora por uno, así que el total de la mejora de ahora es $44$. Ahora consideremos $M$, lo que también tiene un borde que vamos a ignorar por ahora.

Antes de $$(A,H)=6\implies(M,A)=7$$ $$(E,H)=5\implies(M,E)=6$$ Después de $$(A,H)=2\implies(M,A)=3$$ $$(E,H)=3\implies(M,E)=4$$

El total de la mejora es que ahora se $50$. Ahora podemos comparar las longitudes de ruta para $K$ $M$ a ver si hay una ruta más corta a través de cualquiera de ellos. Usted podría rehacer $K$ considerando los $M$ como parte del ciclo y viceversa. En este caso, no hay ninguna ruta de acceso más corta, pero si $M$ estaba conectado a $J$, usted va a ver una mejoría. Finalmente consideramos $L$, el cual es conectado a $I$$J$.

Antes de $$(A,I)=5;(A,J)=7\implies(L,A)=6$$ $$(E,I)=4;(E,J)=6\implies(L,E)=5$$ $$(D,I)=3;(D,J)=5\implies(L,D)=4$$ Después de $$(A,I)=3;(A,J)=1\implies(L,A)=2$$ $$(E,I)=4;(E,J)=2\implies(L,E)=3$$ $$(D,I)=3;(D,J)=3\implies(L,D)=4$$

Esto nos da un total mejora de las $56$. Por último, debemos considerar el $LM$ de ventaja. Este borde no produce una mejora. Total de nuestra mejora es $56$.

Ahora, para el green edge, debemos considerar los tres ciclos de la forma. Una vez que hacemos eso, tenemos que ver si hay alguna mejora en cualquiera de los ciclos. Vemos que no hay ninguna mejora en cualquier lugar en los ciclos, excepto los nodos $H$$L$, que vea una mejora de $1$ cada uno, dando un total de mejora de $2$. Ya que ninguno de los nodos en el ciclo que toque nodos fuera del ciclo de ver ninguna mejora, podemos detener el algoritmo aquí para un final de mejora de $2$.