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.

Las redes de oficina revelan como se distribuyen el contagio

Redes de oficina revelan qué compañeros de trabajo se deben evitar durante brotes infecciosos  
Algunos de sus compañeros de trabajo son mucho más probable que se propague la enfermedad que otros. Ahora, un nuevo estudio de las redes de oficinas revela cómo detectarlos. 




La enfermedad se propaga a través de la sociedad manera es actualmente objeto de un gran interés, sobre todo debido a los recientes brotes, aterradores del ébola y varias cepas de la gripe aviar. Una esperanza es que una mejor comprensión de este proceso puede conducir a métodos más eficientes y rentables de la vacunación.

La semana pasada, vimos sólo un estudio de los contactos interpersonales dentro de tales escuelas. Esto sugirió que una manera eficaz de prevenir una epidemia sería cerrar una sola clase en lugar de toda la escuela.

Hoy, Mathieu Genois en la Universidad de Toulon en Francia y unos amigos estudiar el patrón de contactos cara a cara en un edificio de oficinas y decir que esto también sugiere una nueva estrategia de vacunación y rentable para la prevención de epidemias.

El equipo estudió las interacciones cara a cara más de dos semanas entre las personas que trabajan en un edificio de oficinas perteneciente al Instituto francés de Vigilancia Sanitaria (InVS), cerca de París. El edificio cuenta con tres departamentos científicos diferentes junto con un fepartment recursos humanos y un departamento de logística.

Los trabajadores dentro del edificio fueron dados sensores portátiles que detectan la proximidad de otros cercanos. Dado que el cuerpo actúa como un escudo en las frecuencias de radio utilizadas por los sensores, los dispositivos sólo detectan contactos cuando las personas se enfrentan entre sí a distancias de menos de 150 centímetros. En total, el equipo distribuyó 100 de estos sensores a las dos terceras partes del personal que aceptaron participar.

El equipo estudió la naturaleza de los contactos mediante la elaboración de una red en la que cada individuo es un nodo y una línea entre ellos representa un contacto al menos una vez durante el período de recolección de datos (véase más arriba).

El aspecto más llamativo de esta red es que los individuos son agrupados generalmente de acuerdo con el departamento en el que trabajan. En otras palabras, la mayoría de la gente tiene la mayoría de los contactos con los colegas de su propio departamento. Lo que es más, tienen contacto con unos 15 otras personas en promedio, una pequeña fracción de la población total de la oficina.

Hay algunas excepciones, sin embargo. Un pequeño número de personas tienen la mayoría de sus contactos en otros departamentos. El equipo de llamar a estas personas 'errantes'. Es fácil imaginar que cuando se trata de la propagación de la enfermedad, vagabundos llegar a ser importante. De hecho, ese no es el caso, porque aunque la mayoría de los vagabundos tienen contactos fuera de su departamento, estos contactos se limitan a grupos limitados de otras personas.

Genois y colegas dicen que hay un grupo mucho más importante de la gente, que ellos llaman 'enlazadores'. Estos se definen como personas que tienen aproximadamente la mitad de sus contactos dentro de su propio departamento y medio fuera de ella. "Enlazadores actúan como puentes en la red", dicen, y por lo tanto tienen más probabilidades de transmitir la enfermedad.

De hecho, Genois y colegas simulan la propagación de la enfermedad usando modelos estándar de la infección y muestran cómo los enlazadores juegan un papel clave.

Eso apunta a una estrategia interesante. En lugar de la vacunación de todo el mundo, o la vacunación de personas al azar, de manera eficiente, de bajo costo de prevenir la propagación de la enfermedad es vacunar sólo a las personas clasificadas como enlazadores. "Una estrategia de vacunación dirigida a los enlazadores eficiente evita grandes brotes", concluyen.

Un problema potencial es la identificación de enlazadores. Esto se puede hacer llevando a cabo el mismo tipo de análisis de red que realizan estos tipos. Sin embargo, esto lleva mucho tiempo y es caro.

Una manera mucho más fácil es identificar engarces de sus descripciones de trabajo. Por ejemplo, la persona que empuja el carro de sándwich o electrónico cesta de un departamento a otro podría ser un objetivo obvio. "Este resultado podría ayudar en el diseño de las estrategias de vacunación, de bajo costo eficiente", dicen.

También sugiere mecanismos que las personas pueden utilizar ellos mismos para ayudar a prevenir la infección. Si usted sabe que los conectores están en la oficina, una estrategia para evitar que baja con gripe este invierno sería evitarlos, la llamada estrategia de distanciamiento social.

Es un trabajo interesante que proporciona algunas fascinante visión de la microestructura de los contactos sociales dentro de los edificios de oficinas. En particular, se revela que un factor importante es la organización de las oficinas en departamentos. Eso está en marcado contraste con muchas otras situaciones sociales y, desde luego a la asunción a veces realizados en la simulación de epidemias, que los contactos son homogéneos dentro de los edificios.

Este tipo de trabajo puede parecer académico, pero la verdad es que, con el primer diagnóstico de ébola en suelo estadounidense esta semana, estrategias para evitar infecciones en el trabajo puede llegar a ser una parte necesaria de la vida de oficina.

MIT Technology Review

Detección de comunidades: Algoritmo Girvan-Newman

Algoritmo de Girvan - Newman


El algoritmo de Girvan -Newman (el nombre de Michelle Girvan y Mark Newman ) es un método jerárquico utilizado para detectar las comunidades en sistemas complejos. [1]

Intermediación  de enlaces y estructura de la comunidad 

El algoritmo de Girvan -Newman detecta comunidades eliminando progresivamente los enlaces de la red original. Los componentes conectados de la red que queda son las comunidades. En lugar de tratar de construir una medida que nos indica que los enlaces son los más importantes para las comunidades, el algoritmo de Girvan -Newman se centra en los enlaces que son más probable " entre " comunidades.

La intermediación de vértices se ha estudiado en el pasado como una medida de la centralidad y la influencia de los nodos en las redes. Para cualquier nodo i, intermediación vértice se define como el número de caminos más cortos entre pares de nodos que se ejecutan a través de él. Es una medida de la influencia de un nodo sobre el flujo de información entre otros nodos, especialmente en los casos donde el flujo de información a través de una red sigue principalmente el camino más corto disponible. El algoritmo de Girvan - Newman extiende esta definición para el caso de enlaces, la definición de la " intermediación enlace " de un enlace como el número de caminos más cortos entre pares de nodos que se ejecutan a lo largo de ella. Si hay más de una ruta más corta entre un par de nodos, cada ruta se le asigna el mismo peso tal que el peso total de todos los caminos es igual a la unidad. Si una red contiene las comunidades o grupos que están sólo vagamente conectados por unos enlaces entre grupos, entonces todos los caminos más cortos entre las diferentes comunidades deben pasar por una de estas pocas aristas. Por lo tanto, los enlaces de conexión comunidades tendrán alta intermediación enlace (al menos uno de ellos). Mediante la eliminación de estos enlaces, los grupos están separados uno de otro y por lo que la estructura de la comunidad subyacente de la red se revela.

Los pasos del algoritmo para la detección de la comunidad se resumen a continuación

1. La intermediación de todos los enlaces existentes en la red se calcula primero.
2. Se elimina el enlace con la más alta intermediación.
3. La intermediación de todos los enlaces afectados por la eliminación se vuelve a calcular.
4. Pasos 2 y 3 se repiten hasta que no hay quedan enlaces.

El hecho de que los únicos betweennesses siendo recalculados son sólo los que se ven afectados por la eliminación, puede disminuir el tiempo de ejecución del proceso de simulación ' en las computadoras. Sin embargo, la centralidad de intermediación debe ser recalculado con cada paso, o se producen errores graves. La razón es que la red se adapta a las nuevas condiciones establecidas después de la eliminación enlace. Por ejemplo, si dos comunidades están conectados por más de un enlace, entonces no hay garantía de que todos estos enlaces tendrán alta intermediación. De acuerdo con el método, sabemos que al menos una de ellas tendrá, pero nada más que lo que se sabe. Por recalcular betweennesses después de la eliminación de cada enlace, se asegura que al menos uno de los enlaces restantes entre dos comunidades siempre tendrá un valor alto.

El resultado final del algoritmo de Girvan - Newman es un dendrograma. Cuando se ejecuta el algoritmo de Girvan - Newman, el dendrograma se produce a partir de la parte superior hacia abajo ( es decir, la red se divide en diferentes comunidades con la eliminación sucesiva de enlaces). Las hojas de la dendrograma son nodos individuales.

Referencia

1. Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)

Wikipedia