sábado, 29 de octubre de 2011

Network Motifs

Se le llama motifs a los subgrafos que aparecen con una frecuencia mayor que la observada en los grafos construidos de forma aleatoria. Por ejemplo, el lado izquierdo de la imagen muestra una red real, mientras que el lado derecho muestra cuatro redes construidas de forma aleatoria. En la red real el patrón triangular aparece 5 veces. En las redes aleatorias esta forma sólo aparece en 2 oportunidades. Esa mayor frecuencia podría estar indicando una característica intrínseca de la red real.

Para descubrir estos patrones se desarrollan algoritmos que comparan las frecuencias en las que aparecen los motifs en redes reales versus en redes construidas de forma aleatoria. En primer lugar se escanea el grafo original para obtener todos los subgrafos de n-nodos que existen en él y la cantidad de veces que aparecen. Luego se comparan la frecuencia en la que efectivamente aparecen con la frecuencia en la que aparecerían si el grafo se construyera de forma aleatoria. Aquellos subgrafos que aparecen en mayor frecuencia se entiende que son característicos de la red.

Para que la comparación entre la red real y aleatoria sea equivalente se construyen redes aleatorias respetando la cantidad de links entrantes y salientes que tiene cada nodo en la red real. Además, la red aleatoria está construida con la misma cantidad de nodos y enlaces que tiene la red real:

“For a stringent comparison, we used ramdomized networks that have the same single-node characteristics as does the real network: each node in the randomized networks has the same number of incoming and outgoing edges as the corresponding node has in the real network”.(1)

En general se establece una probabilidad menor o igual a 0.01 para indicar si el patrón es estadísticamente significativo. Así, por ejemplo, se dice que es un motif si la probabilidad de que aparezca ese patrón en una red construida de forma aleatoria es menor o igual a 0.01.

Detección de Network Motifs

En el trabajo Network Motifs: Simple Building Blocks of Complex Networks, Milo et al aplicaron el algoritmo desarrollado por ellos a varias redes. Las redes que analizaron eran genéticas, de neuronas, de la cadena alimenticia, de circuitos electrónicos y de Internet. La tabla de abajo muestra los resultados de sus investigaciones.

Por ejemplo, las redes Food webs en donde cada nodo representa grupos de especies y los enlaces indican qué nodo es predador de otro nodo revelaron dos tipos de motifs, el Three chain y el Bi-parallel. El Three chain quiere decir que los X´s se comen a los Y´s y los Y´s a los Z´s. El motif Bi-Parallel revela que si un predador tiene a dos especies como presas, es probable que esas dos especies compartan su presa.
Un aspecto interesante de la investigación es que los motifs que surgieron son diferentes según la red se trate de neuronas, circuitos electrónicos, páginas webs o genes. Esto podría indicar que es posible distinguir entre redes según los patrones dominantes.

Otra característica de las redes reales es que a medida que la red se van aumentando su tamaño, la concentración de motifs se mantiene constante. En cambio, en las redes creadas de forma aleatoria los patrones se van perdiendo. El gráfico de arriba muestra la concentración del motif Feedfoward loop en la red de Escherichia coli (círculos negros) y en las redes aleatorias semejantes (círculos blancos). En el caso de la red real la concentración se mantiene relativamente estable a medida que aumenta el tamaño de la red, mientras que en la red aleatoria la concentración decae.

Detección de motifs en las redes del Subte y de Aerolíneas Argentinas

En general las redes que trabajaron Milo et al tienen una gran cantidad de nodos y enlaces. La red más grande que analizaron, la de páginas webs, tiene 325.729 nodos y 1,4 mlls de links. También analizaron redes más pequeñas, como las de presa-predador. Pero en esos casos tuvieron la posibilidad de analizar varias redes pequeñas.

La detección de motifs requiere que el análisis sea extenso. Lo que sigue es sólo un acotado ejercicio para observar qué resultados se obtienen al analizar la red del subte de la Ciudad de Buenos Aires y la red aérea de Aerolíneas Argentinas.

La detección de motifs la realicé con el algoritmo desarrollado por Wernicke. En la red del subte de Buenos Aires el motif que se encuentra es este:
Aparece con una frecuencia de 6,6 veces en la red real mientras que en las redes aleatorias aparece con una frecuencia aproximada de 0,062 y una desviación estándar de 0,003.

 En la tabla se muestran los resultados que obtuve para el análisis de la red del subte y de Aerolíneas Argentinas para la detección de motifs de 3 y 4 nodos. En ambos casos los resultados generan motifs en donde uno de los nodos recibe más links que el resto.


Notas y Links:
(1) Network Motifs; Simple Building Blocks of Complex Networks. Milo et al Science 2002

Algoritmo desarrollado por Wernicke: Link

A excepción de la última tabla, el resto pertenece al trabajo de Milo.

No hay comentarios: