1 Análisis de Redes (Sociales) Caminos y Conectividad v.03

2 Conceptos Básicos Un grafo (G) es un conjunto de vértices (V={v i }) conectados mediante enlaces (E={e j }) Grafo de 4 nodos y 4 enlaces V={A,B,C,D} E={AB,CB,BD,DC} relaciones simétricas V={A,B,C,D} E={AB,BA,BC,DB,CD} enlaces: pares ordenados de vértices relaciones asimétricas Grafo dirigido de 4 nodos y 4 enlaces

3 Caminos y ciclos camino: secuencia de vertices tales que vértices consecutivos están conectados c1={A,B,C}, c2={A,B,D,B,C} camino simple: es un camino que no repite vértices c1 es simple, c2 no lo es ciclo: camino de más de dos vértices que no repite elementos, salvo el primero y último c3={B,C,D,B} es un ciclo. c1c1 c2c2

4 Ciclos  Arpanet (Internet 1970) - Red de comunicaciones que vinculaba 13 universidades  Por diseño cada enlace pertenecía a un ciclo (robustez vía redundancia)  Nota: En redes sociales suelen aparecer ciclos todo el tiempo: conoces a tal, que conoce a tal?

5 Conectividad: componentes de un grafo grafo conexo: Un grafo G es conexo si existe un camino entre cualquier par de vértices del mismo. componente: subconjunto de vértices de un grafo que: I. definen un (sub)grafo conexo II.no estan incluidos en ningún otra estructura conexa componente gigante: componente más grande de un grafo No siempre es posible establecer un camino entre cualquier par de nodos

6 Componente gigante

7  En general, si existe, la componente gigante es única  Si hubiera más de una, la existencia de al menos un enlace entre objetos de componentes distintas tiende a aparecer con probabilidad ~ 1 Merging de componentes gigantes puede tener consecuencias nefastas

8 Estructura de amor adolescente Red del amor.  Enlaces corresponden a relación romántica (acumuladas) entre jovenes de una escuela secundaria (durante 18 meses)  Estructura relevante para analizar riesgos de enfermedades de transmisión sexual [ Bearman et al 2004 “Chains of affection: The structure of adolescent romantic and sexual networks”, Am. Jour. Soc.] “…These structures reflect relationships that may be long over, and they link individuals together in chains far too long to be the subject of even the most intense gossip and scrutiny. Nevertheless, they are real: like social facts, they are invisible yet consequential macrostructures that arise as the product of individual agency."

9 Longitud y Distancia longitud de un camino C: número de pasos que contiene desde su comienzo hasta su final. distancia entre un par de vértices de un grafo: longitud del camino más corto que los une. d(UCLA, UTAH)=2 d(CARN,UCSB) =5

10 Que tan lejos? Búsqueda en anchura (Breadth-first search) Manera eficiente y sistemática de estimar distancias a un nodo I.A vecinos directos de MIT, N(MIT), le corresponde d=1 II.A vecinos directos de vecinos directos de MIT, N(N(MIT)) aun no etiquetados le corresponde d=2 III.d( MIT, N(N(N(MIT))) ) = 3 IV.etc..

11 BFS Búsqueda en anchura (Breadth-first search)

12 Mundo Pequeño Redes sociales (A conoce a B) – presentan una componente gigante (existen caminos) – suelen existir caminos inesperadamente cortos (!) d ( ) = 3

13 Mundo Pequeño Stanley Milgram (1967) “The small world problem” Psychology Today Hipótesis: estamos conectados globalmente por medio de cadenas cortas de conocidos Experimento: I.Selección aleatoria de 296 personas de la costa oeste. II.Tarea: hacer llegar una carta a una dada persona (corredor de bolsa de direcci{on conocida en Boston) III.Sólo podían entregar la carta a alguien que conocieran, y encomendarle II y III 64/296 cadenas llegaron a destino Mediana de intermediarios: 6 Notas:  Conclusión sobre prop de la red usando estimación via trazadores  6 es mucho o poco? { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_13.jpg", "name": "Mundo Pequeño Stanley Milgram (1967) The small world problem Psychology Today Hipótesis: estamos conectados globalmente por medio de cadenas cortas de conocidos Experimento: I.Selección aleatoria de 296 personas de la costa oeste.", "description": "II.Tarea: hacer llegar una carta a una dada persona (corredor de bolsa de direcci{on conocida en Boston) III.Sólo podían entregar la carta a alguien que conocieran, y encomendarle II y III 64/296 cadenas llegaron a destino Mediana de intermediarios: 6 Notas:  Conclusión sobre prop de la red usando estimación via trazadores  6 es mucho o poco .", "width": "800" } 14 Milgram reloaded Analisis de 240.000.000 de cuentas de Microsoft Instant Messenger activas, durante un mes. Enlaces entre usuarios que intercambian mensajes Leskovec 2007 “Planetary-scale views of instant-messagging network” Sampling: BFS para 1000 usuarios Estimación un poco más global, aunque aún sesgada (personas tecnoalfabetizadas) Existencia de componente gigante que engloba a la mayor parte de la red ~6.6 (!) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_14.jpg", "name": "Milgram reloaded Analisis de 240.000.000 de cuentas de Microsoft Instant Messenger activas, durante un mes.", "description": "Enlaces entre usuarios que intercambian mensajes Leskovec 2007 Planetary-scale views of instant-messagging network Sampling: BFS para 1000 usuarios Estimación un poco más global, aunque aún sesgada (personas tecnoalfabetizadas) Existencia de componente gigante que engloba a la mayor parte de la red ~6.6 (!).", "width": "800" } 15 Mundo Pequeño https://oracleofbacon.org IMDB 2.9 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_15.jpg", "name": "Mundo Pequeño https://oracleofbacon.org IMDB 2.9", "description": "Mundo Pequeño https://oracleofbacon.org IMDB 2.9", "width": "800" } 16 Caminos y conectividad Hasta ahora – Grafo: G(V,E) – camino, camino simple, ciclo – componentes, grafo conexo, componente gigante – longitud de camino, distancia entre nodos – caminos sorpresivamente cortos en redes sociales: mundo pequeño { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_16.jpg", "name": "Caminos y conectividad Hasta ahora – Grafo: G(V,E) – camino, camino simple, ciclo – componentes, grafo conexo, componente gigante – longitud de camino, distancia entre nodos – caminos sorpresivamente cortos en redes sociales: mundo pequeño", "description": "Caminos y conectividad Hasta ahora – Grafo: G(V,E) – camino, camino simple, ciclo – componentes, grafo conexo, componente gigante – longitud de camino, distancia entre nodos – caminos sorpresivamente cortos en redes sociales: mundo pequeño", "width": "800" } 17 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_17.jpg", "name": "", "description": "", "width": "800" } 18 Lazos fuertes / lazos débiles La estructura de conectividad de las redes sociales es altamente no trivial. El entorno de un dado vértice es diferente al de otro. Puedo inferir ciertos tipo de roles a partir del cableado Pero hay información adicional que aún no tuvimos en cuenta: Los vínculos interpersonales pueden ser de distinta intensidad. En un escenario simplificado: puede haber enlaces fuertes y débiles ¿Cómo correlaciona/condiciona esta distinción a la estructura de la red? { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_18.jpg", "name": "Lazos fuertes / lazos débiles La estructura de conectividad de las redes sociales es altamente no trivial.", "description": "El entorno de un dado vértice es diferente al de otro. Puedo inferir ciertos tipo de roles a partir del cableado Pero hay información adicional que aún no tuvimos en cuenta: Los vínculos interpersonales pueden ser de distinta intensidad. En un escenario simplificado: puede haber enlaces fuertes y débiles ¿Cómo correlaciona/condiciona esta distinción a la estructura de la red .", "width": "800" } 19 Buscando Trabajo Mark Grannoveter (1974) “Getting a Job. A study of contacts and careers” Entrevista a personas que recientemente cambiaron empleo: ¿cómo obtuvieron información de la oportunidad laboral? Observación: Las personas reciben información sobre nuevos trabajos vía contactos personales Esos contactos eran mayormente calificados como “conocidos” (weak- ties) y no como “amistades” (strong-ties) ¿Por qué la recomendación de gente que debería conocer más y mejor nuestros intereses no funcionaba mejor?? estructura de la red y vínculos locales mejor (más efectivo) que conocimiento intensivo de la persona { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_19.jpg", "name": "Buscando Trabajo Mark Grannoveter (1974) Getting a Job.", "description": "A study of contacts and careers Entrevista a personas que recientemente cambiaron empleo: ¿cómo obtuvieron información de la oportunidad laboral. Observación: Las personas reciben información sobre nuevos trabajos vía contactos personales Esos contactos eran mayormente calificados como conocidos (weak- ties) y no como amistades (strong-ties) ¿Por qué la recomendación de gente que debería conocer más y mejor nuestros intereses no funcionaba mejor . estructura de la red y vínculos locales mejor (más efectivo) que conocimiento intensivo de la persona.", "width": "800" } 20 Redes sociales que evolucionan Cuales son los mecanismos por los que una red social podría evolucionar? Principio de clausura transitiva: Si dos personas tienen una amistad en común, aumenta la probabilidad de que se vuelvan amigos entre sí tiempo { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_20.jpg", "name": "Redes sociales que evolucionan Cuales son los mecanismos por los que una red social podría evolucionar.", "description": "Principio de clausura transitiva: Si dos personas tienen una amistad en común, aumenta la probabilidad de que se vuelvan amigos entre sí tiempo.", "width": "800" } 21 Clausura transitiva Por qué funcionaría? 1)Si A y B son amigos y A y C son amigos se amplían las probabilidades de que B y C interactuen y se relacionen 2)El hecho de que B y C sean amigos de la misma persona, y ambos lo sepan, genera cierta confianza implicita 3)habla de cierta similaridad implicita en compartir la amistad de una misma persona. 4)Conveniencia de A de generar el lazo de amistad entre B y C (evitar stress) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_21.jpg", "name": "Clausura transitiva Por qué funcionaría.", "description": "1)Si A y B son amigos y A y C son amigos se amplían las probabilidades de que B y C interactuen y se relacionen 2)El hecho de que B y C sean amigos de la misma persona, y ambos lo sepan, genera cierta confianza implicita 3)habla de cierta similaridad implicita en compartir la amistad de una misma persona. 4)Conveniencia de A de generar el lazo de amistad entre B y C (evitar stress).", "width": "800" } 22 Son amigos, mis amigos? { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_22.jpg", "name": "Son amigos, mis amigos", "description": "Son amigos, mis amigos", "width": "800" } 23 Clausura transitiva Bearman 2004 Am. J. Public Health { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.es/41/11317122/slides/slide_23.jpg", "name": "Clausura transitiva Bearman 2004 Am. J. Public Health", "description": "Clausura transitiva Bearman 2004 Am. J. Public Health", "width": "800" } 24 La fortaleza de los lázos débiles De vuelta al trabajo…por qué las mejores recomendaciones vienen de conocidos y no de amigos? A se vincula con cuatro personas: N(A)={C,D,E,B} El enlace e AB es estructuralmente inusual. Formalmente es un: enlace puente: enlace que si es removido provoca que sus vértices queden en componentes diferentes del grafo.

25 Tendiendo puentes Los enlaces puente son raros de encontrar en la práctica en redes sociales reales  puente local: enlace cuyos vértices no comparten primeros vecinos.  alcance de un puente local : distancia a la que quedan sus vértices cuando el mismo es removido Por definición el alcance de un puente local es estríctamente mayor que 2 e AB es un puente local de alcance 4

26 Tendiendo puentes Los enlaces puente son raros de encontrar en la práctica en redes sociales reales  puente local: enlace cuyos vértices no comparten primeros vecinos.  alcance de un puente local : distancia a la que quedan sus vértices cuando el mismo es removido Por definición el alcance de un puente local es estríctamente mayor que 2 e AB acerca el mundo de A, al mundo de B. Facilita el acceso de A a nueva información

27 Clausura Transitiva Fuerte (CTF) I.Distinción de vínculos personales: fuertes, débiles. II.Noción estructural  El nodo A viola la propiedad CTF si A presenta vínculos fuertes con dos de sus vecinos, pero no existe un enlace entre ellos  El nodo A satisface CTF si no la viola. El concepto CTF vincula las dos nociones:

28 Clausura Transitiva Fuerte (CTF) s

29 CTF, puentes locales y lazos débiles Si un nodo A satisface la propiedad de CTF y presenta al menos dos enlaces fuertes, entonces cualquier puente local en el que esté involucrado es necesariamente un enlace débil w e AB no puede ser un enlace fuerte y un puente local w s

30 CTF, puentes locales y lazos débiles En criollo: En concordancia con nuestra hipótesis de trabajo original (sobre como opera la clausura transitiva) un puente local tiene que ser débil porque si no lo fuera aparecerían eventualmente enlaces en la vecindad que harian que dicho puente local deje de serlo w e AB no puede ser un enlace fuerte y un puente local w s

31 Roles topológicos El acceso a enlaces que conectan grupos no suele estar uniformemente distribuido a lo largo de los nodos de la red. enlace de alto embedding #vecinos comunes de sus nodos extremos enlaces de bajo embedding Ronald Burt, "The Social Capital of Structural Holes” 2005

32 Es válida la hipótesis de CT?  Onnela (2007): análisis de comunicaciones de red móvil de 4.6 10 6 usuarios por 18 meses. “Structure and tie strengths in mobile communication networks”, Onnela et al (2007) PNAS

33 Es válida la hipótesis de CT?  Onnela (2007): análisis de comunicaciones de red móvil de 4.6 10 6 usuarios por 18 meses.  2 nodos se conectan si intercambiaron una comunicación en ambos sentidos durante el período.  Estructura de la red: proxy de la red social subyacente  Componente gigante del 84% de la masa de usuarios “Structure and tie strengths in mobile communication networks”, Onnela et al (2007) PNAS

34 Intensidad de enlace estructura local Onnela et al (2007) PNAS Intensidad de un enlace Numero de llamadas intercambiadas Overlap: medida continua de la noción de puente local

35 Intensidad de enlace estructura local Onnela et al (2007) PNAS Overlap: medida continua de la noción de puente local Intensidad de un enlace Numero de llamadas intercambiadas overlap en función de intensidad acumulada control random

36 Desarmando la componente gigante Onnela et al (2007) PNAS Análisis de estabilidad de la CG frente a remoción ordenada de enlaces

37 Desarmando la componente gigante ordenamiento por intensidad ordenamiento por overlap R GC tamaño relativo de la CG f fracción de enlaces removidos orden ascendente orden descendente La CG se contrae:  de manera continua, si se eliminan primero los enlaces más fuertes  de manera abrupta, si se eliminan primero los enlaces más débiles enlaces fuertes conectividad intra grupos / enlaces débiles conectividad inter-grupo

38 Referencias NCM, Easley & Kleinberg Chap 2 “Chains of affection: The structure of adolescent romantic and sexual networks”, Bearman et al (2004) Am. Jour. Soc. “The small world problem”, Stanley Milgram (1967) Psychology Today “Planetary-scale views of instant-messagging network”, Leskovec (2007) https://oracleofbacon.org “Getting a Job. A study of contacts and careers” Mark Grannoveter (1974) “Suicide and Friendships Among American Adolescents”, Bearman & Moody (2004) Am. J. Public Health “Structure and tie strengths in mobile communication networks”, Onnela et al (2007) PNAS