harto ocio y otras cosas

Algunas pocas cosas

Maps of random walks on complex networks reveal community structure

05 junio, 2015 | Tésis

Este escrito es un resumen del documento:

Resumen

Los sistemas biológicos y sociales son variados, compuesto por muchas partes, desagregados y dinámicos. Los datos de estos sistemas están ahora disponibles a una escala sin precedentes, a menudo modelada en forma de red. A pesar de lo anterior, las abstracciones de estos sistemas siguen siendo complejos de entender, por lo que resulta útil dividir la gran cantidad de nodos y arcos en modulos que representen la red.

Una buena representanción simplifica y destaca las estructuras subyacentes y las relaciones que ellas representan, son mapas. El mejor mapa transmite mucha información con la cantidad mínima de información: los mejores mapas son también buenas compresiones.

Usamos mapas para describir dinámicas que ocurren a través de arcos y nodos en redes dirigidas con pesos que representan interacciones locales entre subunidades del sistema. Estas interacciones inducen un flujo de información en todo el sistema que caracteriza su comportamiento.

Para entender como la estructura de la red se relaciona con el comportamiento del sistema es necesario entender el flujo de información presente en la red. Según esto se identifican módulos (estructuras) que componen la red a partir de un descriptor eficiente de como la información fluye.

Un grupo de nodos entre los cuales fluyen flujos de información rapida y fácilmente pueden ser agrupados y descritos como un módulo bien conectado. Los arcos entre módulos captura las posibilidades de desplazamiento entre módulos del flujo de información.

Describir sucintamente un flujo de información es un problema de compresión. Por otro lado, la idea clave de la teoríá de codificación es que un conjunto de datos puede ser comprimido con un código que explota regularidades en el proceso que genera los datos.

Nosotros usamos un recorrido aleatorio como un proxy (representante) del flujo de información porque éste usa toda la información de la representación del sisitema (red) y nada más. A partir de lo anterior se desarrolla una codificación eficiente que describe un recorrido aleatorio sobre una red.

Si maximizar la descripción fuera nuestro único objetivo, podríamos codificar la ruta descrita en el recorrido aleatorio cercana al radio entropía del proceso de markov correspondiente. Shannon mostró que uno puede lograr esta rate asignando a cada nodo un código único sobre las transiciones de salida. Pero la compresión no es nuestro único objetivo, queremos que nuestro lenguaje refleje la estructura de la red. Comparandolo con un mapa: los mapas útiles asignan nombrer únicos a estructuras importantes por lo que nuestra codificación debe describir de alguna forma estas estructuras.

 

 

Comentarios

comments powered by Disqus