big data , teoria de grafos

Métricas de redes .
Cada métrica de red da respuesta a las siguientes preguntas:

pregunta: ¿Quién es más central?
1) METRICA DE RED: centralidad
a)Centralidad de grado (degree centrality).
1) Indegree o grado de entrada
2) Outdegree o grado de salida
b) Centralidad de cercanía (closeness centrality).
c) Centralidad de intermediación (Betweenness centrality).
pregunta: ¿Todo está conectado?
2) METRICA DE RED: los componentes conectados
- Componentes fuertemente conectados:
-Componentes Débilmente conectados:
3) METRICA DE RED: tamaño de componente gigante(giant component)
4) METRICA DE RED: modelo de corbata de moño de la web

pregunta: ¿A qué distancia están las cosas?
5) METRICA DE RED: rutas más cortas

pregunta: ¿Cómo densa son?
6) METRICA DE RED: densidad grafo
redes de modelado: pequeños mundos
Pequeños mundos:
un amigo de un amigo es también con frecuencia un amigo
pero sólo seis saltos separan dos personas en el mundo.









Arnold S. - thomashawk, Flickr;
http://creativecommons.org/licenses/by-nc/2.0/deed.en
CONTENIDO
El mundo es un pañuelo
 
La teoría de los Seis Grados de Separación

Según esta teoría sólo seis niveles nos separan de cualquier persona del planeta. Sólo Seis pasos. Seis grados.
redes de modelado: pequeños mundos
CONTENIDO
¿Qué son las redes y qué utilidad tiene para su estudio?
Investigación sobre redes sociales
El fenómeno del mundo pequeño es la hipótesis sobre que la cadena de conocidos sociales necesaria para conectar a una persona arbitraria con otra persona arbitraria en cualquier parte del mundo, es generalmente corta. El concepto dio lugar a la famosa frase de seis grados de separación a partir de los resultados del «experimento de un mundo pequeño» hecho en 1967 por el psicólogo Stanley Milgram.
En el experimento de Milgram, a una muestra de individuos EE.UU. se le pidió que hiciera llegar un mensaje a una persona objetivo en particular, pasándolo a lo largo de una cadena de conocidos.
La duración media de las cadenas exitosas resultó ser de unos cinco intermediarios, o seis pasos de separación (la mayoría de las cadenas en este estudio ya no están completas). Los métodos (y la ética también) del experimento de Milgram fueron cuestionados más tarde por un estudioso norteamericano, y algunas otras investigaciones para replicar los hallazgos de Milgram habrían encontrado que los grados de conexión necesarios podrían ser mayores.
redes de modelado: pequeños mundos
CONTENIDO
¿Qué son las redes y qué utilidad tiene para su estudio?
Investigación sobre redes sociales
El sociólogo estadounidense Stanley Milgram, quien ideó una manera de probar la teoría, que él llamó "el problema del pequeño mundo". Al azar seleccionó varias personas del medio oeste estadounidense para que enviaran tarjetas postales a un extraño situado en Massachusetts.
Se les indicó que enviaran el paquete a una persona que ellos conocieran directamente y que pensaran que fuera la que más probabilidades tendría, de todos sus amigos, de conocer directamente al destinatario.
Esta persona tendría que hacer lo mismo y así sucesivamente hasta que el paquete fuera entregado personalmente a su destinatario final. Aunque los participantes esperaban que la cadena incluyera al menos cientos de intermediarios, la entrega de cada paquete solamente llevó, como promedio, entre cinco y siete intermediarios.

redes de modelado: pequeños mundos
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/

Red completamente
Conectada.
no se pueden añadir
más enlaces o bordes
o conexiones.
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/
Erdos-Renyi grafos aleatorios
¿Qué pasa con el tamaño del componente gigante (giant component ) como la densidad de la red aumenta?
PAGINA WEB: http://ccl.northwestern.edu/netlogo/models/run.cgi?GiantComponent.884.534
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/
Erdos-Renyi grafos aleatorios.
componente gigante (giant component )
PAGINA DE DESCARGA SOFTWARE NETLOGO: http://ccl.northwestern.edu/netlogo/
CONTENIDO
¿Qué son las redes y qué utilidad tiene para su estudio?
Facebook acorta los "seis grados de separación"
un estudio realizado por Facebook en conjunto con la Universidad de Milán, en Italia, afirma que el número de grados de separación entre dos personas es menor.

El estudio estima que el 99.6 por ciento de los pares de usuarios están conectados con grados de 5 personas, mientras que el 92 por ciento, por grados de cuatro personas.

este nuevo estudio demuestra que con la llegada de Facebook y las redes sociales, la distancia entre las personas se está achicando cada vez más. La estadística demuestra que Facebook está llevando los seis grados a los cuatro grados de separación.
redes de modelado: pequeños mundos
LIBRO: Pequeños Mundos: La dinámica de redes entre el orden y la aleatoriedad (Estudios de Princeton en Complejidad)

Fuente: Watts, DJ, Strogatz, SH (1998) Las dinámicas colectivas de las redes 'small-world'. Nature 393: 440-442.
Fuente: Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442.
Modelos del mundo Pequeñas: Duncan Watts y Steven Strogatz
Fuente: Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442.
Todo el mundo conoce el fenómeno del mundo pequeño: poco después de conocer a un extraño, nos sorprende al descubrir que tenemos un amigo en común, o estamos conectados a través de una corta cadena de conocidos. En su libro, Duncan Watts utiliza este fenómeno intrigante - coloquialmente llamado "seis grados de separación" - como un preludio a una exploración más general: ¿bajo qué condiciones pueden surgir un mundo pequeño en cualquier tipo de red?
Las redes de esta historia están en todas partes: el cerebro es una red de neuronas; organizaciones son redes de personas; la economía mundial es una red de las economías nacionales, que son las redes de los mercados, que son a su vez en las redes de productores y consumidores interactuar. Las redes alimentarias, los ecosistemas y la Internet pueden ser representados como redes, como las estrategias de lata para la solución de un problema, temas en una conversación, e incluso las palabras en un idioma. Muchas de estas redes, según el autor, resultan ser pequeños mundos.
¿Cómo importan esas redes? En pocas palabras, las acciones locales pueden tener consecuencias globales, y la relación entre la dinámica local y global depende fundamentalmente de la estructura de la red. 
Watts ilustra las sutilezas de esta relación usando una variedad de modelos simples --- la propagación de enfermedades infecciosas a través de una población estructurada; la evolución de la cooperación en la teoría de juegos; la capacidad computacional de los autómatas celulares; y la sincronización a de-fase osciladores acoplados.
Enfoque de la novela de Watts es relevante para muchos problemas que tienen que ver con la conectividad de red y el comportamiento de sistemas complejos 'en general: ¿Cómo enfermedades (o rumores) se propagan a través de redes sociales? ¿Cómo evoluciona la cooperación en grupos grandes? ¿Cómo se propagan los fallos en cascada a través de sistemas financieros? 
Modelos del mundo Pequeñas: Duncan Watts y Steven Strogatz
FUENTE: http://www.etoro.com/blog/markets/24122011/efficient-social-configurations-for-collaborative-trading-%E2%80%93-small-world-networks-i/

En esta red de amistad totalmente regular (foto a la izquierda), la gente son amigos con sólo sus cuatro vecinos más cercanos. La red es muy exclusivista, y dos personas son, en promedio, muchos grados de separación. Cómo volver a conectar algunos de los bordes al azar,
una red del mundo pequeño es recibido (foto del medio), donde la gente todavía saben otros cuatro en promedio, pero algunos tienen amigos lejanos. La red es aún altamente cliquish, pero el grado medio de separación es pequeña. Continuar el proceso de recableado al azar por fin tenemos una red aleatoria (imagen de la derecha), donde todo el mundo sabe todavía otros cuatro en promedio, pero los amigos se encuentran dispersos; pocas personas tienen muchos amigos en común, y los pares son, en promedio, sólo unos pocos grados de diferencia.
Ahora que sabemos lo que las redes de pequeño mundo son, y cómo se pueden generar, podemos proceder a discutir lo bien que se pueden utilizar cuando actúa como una infraestructura para el intercambio de información comercial.
LEER Y COLOCAR LA INFORMACION DEL LIBRO EN ESPAÑOL: ScientificCommunicationAsSequentialArt Duncan J. Watts & Steven H. Strogatz.en.es
Modelos del mundo Pequeñas
Revisar esta pagina http://www.papercore.org/summaries/collective-dynamics-of-small-world-networks

El siguiente proceso de recableado al azar se ejecuta para generar un gráfico que permite la interpolación entre regular ( p = 0 ) y (aleatorios p = 1 ) redes:

Generar una red de anillo con n nodos y un (promedio) grado k para cada nodo
Rewire cada borde con probabilidad p , donde se elige un nuevo punto final del borde uniformemente al azar entre todos los vértices. Este borde sólo se añade, si no existe hasta el momento.
Dos observables son considerados para investigar las redes de mundo pequeño. 
El camino característica longitud L ( p ) se define por el número de bordes en el camino más corto entre dos nodos, promediado sobre todos los pares de nodos y es una propiedad global. 
El coeficiente de agrupación C (p ) es una propiedad local y que básicamente se mide la fracción de vecinos conectados de un nodo en el gráfico en comparación con todas las posibles conexiones de los vecinos promediado sobre todos los nodos.
Revisar esta pagina http://adsabs.harvard.edu/abs/1998Natur.393..440W

Redes de sistemas dinámicos acoplados se han utilizado para modelar osciladores biológicos, matrices de unión Josephson ,, medios excitables, redes neuronales, juegos espaciales, redes de control genético y muchos otros sistemas de auto-organización. 
Ordinariamente, la topología de conexión se supone que es ya sea totalmente regular o completamente al azar. 

Pero muchas de las redes biológicas, tecnológicas y sociales se encuentran en algún lugar entre estos dos extremos. Aquí exploramos modelos simples de redes que pueden ser ajustados a través de esta tierra de en medio: redes regulares `Rewired 'para introducir cantidades crecientes de desorden. Se encuentra que estos sistemas pueden ser muy agrupadas, como celosías regulares, sin embargo, tener pequeñas longitudes de trayectoria característicos, como grafos aleatorios. 
Los llamamos `redes de mundo pequeño", por analogía con el fenómeno del mundo pequeño, (popularmente conocido como seis grados de separación). 
La red neuronal del gusano Caenorhabditis elegans, la red eléctrica del oeste de los Estados Unidos, y el gráfico de la colaboración de los actores de cine se demuestra que son las redes de mundo pequeño. Modelos de sistemas dinámicos con pantalla de acoplamiento del mundo pequeño mayor velocidad de propagación de la señal, la potencia de cálculo, y synchronizability. En particular, las enfermedades infecciosas se propagan más fácilmente en las redes de mundo pequeño que en celosías regulares
Modelos del mundo Pequeñas: Duncan Watts y Steven Strogatz
Modelos del mundo Pequeñas: Duncan Watts y Steven Strogatz
Fuente: Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442.
Modelos del mundo Pequeñas: Duncan Watts y Steven Strogatz
Fig. 1 Ilustración de pequeñas propiedades de conectividad de la red mundial, por Watts y Strogatz. 
L = longitudes entre dos nodos arbitrarios
C= altos coeficientes de agrupamiento o clustering 
P= probabilidad recableada
Una red del mundo pequeño exhibe camino medio bajo longitudes entre dos nodos arbitrarios (L en el diagrama) y sin embargo contiene altos coeficientes de agrupamiento o clustering 
(C en el diagrama).Puede ver aquí que se caracteriza por una gran cantidad de conectividad local entre los nodos, así como el enlace ocasionalmente más largos, un acceso directo si se quiere.
 Sólo unos pocos de estos enlaces más largos son necesarios con el fin de inclinar la red, en lo que se conoce como una transición de fase, a partir de un estado global relativamente mal conectada a un estado del mundo pequeño. 
Desde el punto de vista de la red espacial, mundos pequeños significan altos niveles de accesibilidad media de cualquier nodo dado a cualquier otro nodo, una distribución homogénea de los altos niveles de movilidad si se quiere. Vemos propiedades de mundo pequeño principalmente en redes autoorganizadas. Ellos se observaron por primera vez en las redes sociales por parte de Watts y Strogatz.
Fuente :http://www.urbagram.net/v1/show/Microplexes

= probabilidad recableado
Modelos del mundo Pequeñas
Duncan Watts y Steven Strogatz :
algunos enlaces aleatorios de otra manera en un grafo estructurado hacen la red de un pequeño mundo: la ruta más corta media es corta.
regular lattice o enrejado regular: P=0
el amigo de mi amigo es
siempre mi amigo
small world o pequeño mundo:
0