ARS 101: Intermediación de enlace

Cálculo del índice de intermediación de enlace

Este material suplementario pretende explicar brevemente el cálculo de intermediación de enlace ilustrando los pasos clave. La red de ejemplo que se muestra a continuación se ha tomado de una ilustración en la página 596 (Figura 24.6) de (Cormenet al.2001).



En primer lugar, las rutas más cortas entre cada par de vértices se calculan (Brandes 2001). Hay dos entradas requeridas: una matriz de adyacencia (Adj) y una matriz de pesos de enlaces (W). Ambos son matrices cuadradas de dimensión n, donde n es el número de vértices en el grafo original. En estas matrices, los índices de fila y columna especifican los números de vértices. Por ejemplo, el elemento de la fila 1 y la columna 2 de Adj representa un enlace dirigido desde el vértice 1 a 2. Del mismo modo, Adj (1,4) representa un enlace dirigido desde el vértice 1 a 4.





En el paso 1 del algoritmo, estas dos matrices de entrada se utilizan para calcular los tres siguientes matrices n × n: una matriz menor número de caminos (Ssigma = [ωij], que indica el número de rutas más cortas de i a j), una matriz predecesor (Ppred = [πij], donde πij es 0 si bien i = j o no hay camino de i a j, de lo contrario, πij es el predecesor de j en la ruta más corta desde i), y una matriz de distancia más corta (Ddist = [dij], que denota la longitud de la ruta más corta desde i a j). Para el ejemplo anterior, estas matrices son




El siguiente paso es identificar los nodos de la cabeza y de la hoja de cada "red de ruta más corta 'descrito por las tres matrices anteriores para calcular los valores de borde intermediación (Newman y Girvan 2004). Una ruta de acceso se describe mediante una secuencia de nodos predecesores y un conjunto correspondiente de distancias más cortas ponderadas, que se dan por Ppred y Ddist, respectivamente. En el ejemplo actual (véase la parte superior figura en la página 1), las cinco filas de Ppred especifican cinco grafos dirigidos, cada uno con un nodo principal diferente. Las ilustraciones siguientes muestran los grafos y los nodos principales correspondientes (Caso 1 ~ 5). Cada uno de estos gráficos reflejan las cortas distancias de ruta ponderados se muestran en Ddist. Por ejemplo, la fila 1 de Ppred establece que el nodo 4 precede nodo 2 (columna 2), que precede nodo 3 (columna 3). Nodo 1 (nodo de cabeza) precede el nodo 4 (columna 4), que también precede el nodo 5 (columna 5). La fila correspondiente de Ddist muestra que la ruta más corta desde el nodo ponderado 1 a 4 tiene una longitud 5. En el mismo ejemplo, la ruta más corta desde el nodo ponderado 1 a 3 (a través de 4 y 2) tiene una longitud 9.




A partir de los diagramas anteriores, es evidente que un conjunto diferente de nodos hojas (leaf node) se encuentran para cada nodo cabeza (head node).
Para aplicar el algoritmo de análisis de intermediación de enlace, las direcciones de los senderos se invierten de manera que los caminos comienzan en los nodos hojas y terminan en el nodo principal. Los grafos invertidos de la red de ejemplo se muestran a continuación.




Los pasos de análisis de intermediación de enlaces se ilustran a continuación para el caso 1. Estos cálculos corresponden al paso 2 del algoritmo descrito en el texto de la nota de aplicación. Las entradas de fila de los tres cortos matrices de información ruta son:
Ssigma (1, :) = [1 1 1 1 1]; % de Entradas del vector son el número de rutas más cortas desde el
nodo principal (en este caso, el vértice 1) a los otros vértices.
Ppred (1, :) = [0 4 2 1 4]; % de Entradas vector especificar el nodo predecesor por cada una de las
vértices.
Ddist (1, :) = [0 8 9 5 7]; % de Entradas del vector son las distancias más cortas entre ponderados
el nodo principal (en este caso, el vértice 1) y los otros vértices

Tenga en cuenta que los índices de columna se especifica el número de vértices.




Los valores del índice de canto intermediación se recogen en una matriz 'edgeBC' a través de los siguientes pasos:

1. Inicialice el 'Anew "y las matrices 'edgeBC '. Por ejemplo, edgeBC (:,:, 1) y Anew (:,:, 1) se refieren a la oración de 1;



2. Calcular los ponderadores de los enlaces como describe (Newman y Girvan 2004).
Para encontrar (un) nodo (s) hoja, sustituir el elemento (ind, Ppred (1, :)) de Anew (:,:, 1) con 1 si hay un predecesor;




// Las columnas cero indican que los vértices correspondientes son nodos hoja, que son los nodos 3 y 5 para el caso 1.

3. Construir la matriz del 'edgeBC';

En primer lugar, identificar el nodo de distancia máxima desde el nodo principal (un nodo hoja). Para el caso 1, este es el nodo 3 (ind = 3). En segundo lugar, identificar el predecesor de este nodo hoja, que en este caso es el nodo 2 (col = 2):





Sustituya el elemento en edgeBC (:,:, 1) que especifica (ind, col) con la puntuación de la intermediación de enlace calculada;




El valor de canto intermediación es ωcol / ωind (de Ssigma = [ωij]), si ind es un nodo hoja; de lo contrario el valor está dado por [(puntuaciones borde intermediación de los bordes vecinos directamente debajo del nodo) 1 + Σ] · ωcol / ωind [3].

4. Repita los pasos 1 - 3 para todos los nodos de cabeza // para s = 1: n

5. Suma todo el edgeBC (s) y la transposición de la resumió matriz para recuperar las direcciones de ruta originales.

edgeBetCen = suma (edgeBC, 3);
// El resultado es el edgeBCof la red dirigida de Caso 1
edgeBetCen = edgeBetCen ';

Tenga en cuenta que cuando hay más de una ruta más corta entre el mismo par de vértices, Ssigma (= [ωij]) contendrá entradas no unitarias. En este caso, una matriz Ppred separada tiene que ser calculado para cada camino más corto diferente. Los efectos de la multiplicidad de caminos más cortos en la centralidad general borde de intermediación dependerán de los valores numéricos de los elementos de Ssigma y Ddist. Independientemente de la multiplicidad, los valores de borde intermediación de los bordes conectados a un nodo de cabecera deben sumar el número total de otros vértices que son accesibles desde este vértice de referencia. Para el caso 1, este número es 4.

Referencias 

• Brandes, U. (2001) A faster algorithm for betweenness centrality. J Math Soci, 25, 163-177.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2001) Introduction to algorithms, 2nd edn. The MIT press, Cambridge, Massachusetts.
• Newman, M.E. and Girvan, M. (2004) Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys, 69, 026113.

Bioinformatics



Los enlaces de cada micelio son coloreados de acuerdo a su normalizada centralidad de 'intermediación de enlace', en rojo oscuro = 1 y azul oscuro= 0. De esta manera es fácil de ver eventos de fusión puntuales que ocurren entre dos micelios independientes. El entorno ambiental está mostrando la concentración de la sustancia autoreguladora (también normalizado, lo que provoca el parpadeo si algunos punta de fusión capaz activado emite grandes cantidades de la señal). En este caso, el medio ambiente de los recursos (que no se muestra en este video) consta de rectángulos de dimensiones 60x80 cada uno presenta como un tablero de ajedrez, en el que la mitad de ellos contiene 100% de alimentos y la otra mitad el 75% de los que están separados por zanjas estrechas donde no hay comida en general. Las 12 pequeñas colonias de micelio iniciales en última instancia, se fusionan para formar 7 redes independientes, inconexas.