{"id":25211,"date":"2026-10-06T07:03:14","date_gmt":"2026-10-06T05:03:14","guid":{"rendered":"https:\/\/www.rasc.es\/blogacademia\/?p=25211"},"modified":"2026-10-09T11:46:55","modified_gmt":"2026-10-09T09:46:55","slug":"conectemos-a-pepito-perez-en-mairena-con-oliver-jones-en-melbourne-ii","status":"publish","type":"post","link":"https:\/\/www.rasc.es\/blogacademia\/?p=25211","title":{"rendered":"Conectemos a Pepito P\u00e9rez, en Mairena, con Oliver Jones, en Melbourne (II)"},"content":{"rendered":"

De d\u00f3nde viene todo esto …<\/h4>\n

El escritor h\u00fangaro \u00a0Frigyes Karinthy public\u00f3 en 1929 un volumen de relatos cortos con el t\u00edtulo \u00abEverything is Different\u00bb, entre los cuales se encuentra uno titulado \u00abEslabones\u00bb. En \u00e9l, uno de los personajes, alentado por la idea de que, debido a la rapidez de las comunicaciones de la \u00e9poca, el mundo se ha vuelto m\u00e1s peque\u00f1o, propone a los dem\u00e1s participar en un juego: les pide que elijan aleatoriamente un individuo del mill\u00f3n y medio de millones de habitantes de la Tierra y apuesta a que, usando no m\u00e1s de cinco personas intermedias, ser\u00e1 capaz de contactar con \u00e9l.<\/p>\n

\"\"
Fig. 1 – F. Karinthy, 1887-1938.<\/figcaption><\/figure>\n

Posiblemente fue esta idea la que dio origen al concepto moderno de los seis grados de separaci\u00f3n y, por extension, a los estudios sobre redes sociales.<\/p>\n

Por otro lado, como vimos en la anterior entrada, los grafos constituyen una herramienta \u00fatil para el an\u00e1lisis de esta cuesti\u00f3n, v\u00e9ase [1]. El punto de partida de la teor\u00eda de grafos se sit\u00faa en 1736, cuando Leonard Euler resolvi\u00f3 el problema de los puentes de K\u00f6nigsberg.<\/em><\/p>\n

El problema era el siguiente:<\/p>\n

\u201cTeniendo en cuenta la disposici\u00f3n de los siete puentes de la ciudad, \u00bfes posible un recorrido que pase por todas las orillas, empiece y acabe en el mismo punto\u00a0 y atraviese cada puente una y s\u00f3lo una vez?\u201d<\/p>\n

Con un razonamiento impecable, Euler demostr\u00f3 que no; v\u00e9ase [2] o Los puentes de Koenigsberg<\/em><\/a>.<\/p>\n

\"\"
Fig. 2 – S. Strogatz, n. en 1959.<\/figcaption><\/figure>\n

M\u00e1s tarde, en 1847, Gustav Kirchhoff introdujo y utiliz\u00f3 grafos para el an\u00e1lisis de redes el\u00e9ctricas, deduciendo las leyes de c\u00e1lculo de diferencia de potencial y corriente que llevan su nombre. En 1857, Arthur Cayley recurri\u00f3 a los grafos para la representaci\u00f3n y clasificaci\u00f3n molecular de los is\u00f3meros y, a mediados del siglo XX, ya eran utilizados para el an\u00e1lisis de las redes sociales.<\/p>\n

La teor\u00eda fue fundamentada y formalizada en los a\u00f1os 70 del siglo pasado. La motivaci\u00f3n principal fue el intento de dar respuesta al problema de los cuatro colores,<\/em> cuyo enunciado es el siguiente:<\/p>\n

\u201cSiempre es posible colorear un mapa con cuatro colores de modo que dos pa\u00edses vecinos nunca tengan el mismo color.\u201d<\/p>\n

El problema hab\u00eda sido formulado en 1852 por Francis Guthrie, pero no fue resuelto hasta 1976 por Kenneth Apple y Wolfgang Haken.<\/p>\n

\"\"El agrupamiento<\/h4>\n

En los modelos de grafos generados para describir conexiones dentro de una poblaci\u00f3n, cobra importancia no s\u00f3lo el di\u00e1metro y la distancia media, sino tambi\u00e9n el agrupamiento.<\/em><\/p>\n

Para determinar el agrupamiento subyacente en un grafo, podemos recurrir a la f\u00f3rmula \u00a0 \\[C := \\frac{3 \\times \\text{n\u00famero de ternas tringulares}}{\\text{n\u00famero de ternas conectadas}} \\,.\\]<\/p>\n

Aqu\u00ed, se dice que una terna de v\u00e9rtices \\(\\{ a, b, c \\}\\) est\u00e1 conectada si al menos uno de los v\u00e9rtices es adyacente a los otros dos; se dice que una terna conectada es triangular si los tres v\u00e9rtices son adyacentes a los otros dos. Claramente, podemos interpretar que, cuanto m\u00e1s cerca est\u00e9 \\(C\\) de \\(1\\), m\u00e1s intenso es el agrupamiento de v\u00e9rtices en el grafo.<\/p>\n

Watts, Strogatz y las redes de contactos<\/strong><\/h4>\n
\"\"
Fig. 4 – Esquema comparativo de los distintos modelos.<\/figcaption><\/figure>\n

El modelo de Erdos y Renyi expuesto en la anterior entrada ha sido modificado y mejorado en \u00e9pocas m\u00e1s recientes por Watts y Strogatz y posteriormente por Kleinberg (v\u00e9anse [3] y [4]), dando lugar a los llamados grafos de mundo peque\u00f1o. Se trata de modelos que ocupan un lugar intermedio entre el grafo regular \\(G_0(n)\\) y el grafo aleatorio \\(G(n)\\); v\u00e9anse las Fig. 4 y 5.<\/p>\n

Duncan Watts es actualmente profesor de Sociolog\u00eda en la Universidad de Columbia, autor del libro [5]. A lo largo de su carrera, se ha interesado por varios temas: la ciencia de las redes, la din\u00e1mica social y el comportamiento colectivo y el estudio de la desinformaci\u00f3n y la desconfianza en los medios digitales.<\/p>\n

Steven Strogatz es un matem\u00e1tico aplicado que trabaja en las \u00e1reas de la din\u00e1mica no lineal y sistemas complejos, a menudo sobre temas inspirados por curiosidades de la vida cotidiana: \u00bfPor qu\u00e9 es dif\u00edcil dormir varias horas antes de la hora habitual? \u00bfQu\u00e9 informaci\u00f3n sobre nuestro ADN guarda un objeto cuando los tocamos? O incluso \u00bfpor qu\u00e9 es tan corriente conocer a alguien en un viaje y descubrir conocidos comunes?<\/p>\n

En una reciente entrevista, no pudo contener la emoci\u00f3n al hablar sobre los recientes avance de la IA y exclamo: \u201cYa no podremos aspirar a escalar las monta\u00f1as m\u00e1s altas, porque las m\u00e1quinas siempre llegar\u00e1n primero. Perderemos siempre\u201d.\u00a0<\/p>\n

\"\"
Fig. 5 – Un modelo de mundo peque\u00f1o generado con el algoritmo de Watts-Strogatz.<\/figcaption><\/figure>\n

En 1998, Duncan J. Watts y Steven Strogatz, por aquel entonces ambos en el Departamento de Mec\u00e1nica Te\u00f3rica y Aplicada de la Universidad de Cornell, publicaron el primer modelo de una red de conexiones [3]. Su objetivo era probar que las redes del mundo natural y las del mundo construido por el hombre poseen la llamada propiedad del mundo peque\u00f1o.<\/em> M\u00e1s precisamente, postularon que, partiendo de una estructura regular, la adici\u00f3n de un peque\u00f1o n\u00famero de v\u00ednculos al azar reduce el di\u00e1metro de la red de un valor grande a otro mucho menor. La investigaci\u00f3n estuvo originalmente inspirada por los esfuerzos de Watts por entender la sincronizaci\u00f3n de los sonidos emitidos por los grillos, ya que \u00e9stos muestran un alto grado de coordinaci\u00f3n, como si fuesen conducidos por un gu\u00eda invisible.<\/p>\n

El modelo matem\u00e1tico desarrollado por Watts y Strogatz para explicar este fen\u00f3meno ha sido aplicado desde entonces con relativo \u00e9xito en un amplio rango de \u00e1reas diferentes.<\/p>\n

Obs\u00e9rvese que en una red social no es aceptable suponer que la probabilidad de que dos personas del mismo vecindario se conozcan sea la misma que la probabilidad de que se conozcan Pepito P\u00e9rez (de Mairena) y Oliver Jones (de Melbourne). Por tanto, parece adecuado buscar un punto intermedio entre grafos regulares (que se asemejan al mundo real en lo que se refiere al agrupamiento) y grafos aleatorios (que comparten con el mundo real la propiedad de peque\u00f1a distancia media).<\/p>\n

\"\"
Fig. 6 – Comportamiento de los distintos modelos.<\/figcaption><\/figure>\n

La idea desarrollada por Watts y Strogatz tiene en cuenta que, si bien la mayor\u00eda de contactos de una persona suelen estar entre los que desde un punto de vista geogr\u00e1fico, social o laboral son sus \u201cvecinos\u201d, es muy frecuente que exista un n\u00famero reducido de contactos \u201clejanos\u201d. Y \u00e9stos juegan el papel de puentes sociales que reducen la distancia de separaci\u00f3n considerablemente.<\/p>\n

Bas\u00e1ndose en esta premisa, dise\u00f1aron el siguiente algoritmo:<\/p>\n

ALG 1:<\/strong><\/p>\n

    \n
  1. Inicializaci\u00f3n – Comenzamos considerando un grao regular de \\(n\\) nodos, cada uno de los cuales es adyacente a los \\(s\\) v\u00e9rtices m\u00e1s cercanos.<\/li>\n
  2. Aleatorizaci\u00f3n – Dado un v\u00e9rtice, cada segmento que le afecta es \u201credirigido\u201d de manera aleatoria con probabilidad \\(p\\) a otro v\u00e9rtice (no adyacente) aleatoriamente elegido, evitando bucles y aristas duplicadas.<\/li>\n<\/ol>\n

    Obs\u00e9rvese que el procedimiento no cambia el n\u00famero de v\u00e9rtices ni de segmentos.<\/p>\n

    Con multitud de simulaciones y argumentos anal\u00edticos, Watts and Strogatz mostraron que este algoritmo permite generar una gran familia de grafos intermedios para los cuales el agrupamiento est\u00e1 bien presente y, al mismo tiempo, la distancia media entre nodos decrece: \\(C_p\\) se mantiene positivo y la distancia media \\(L_p\\) decrece r\u00e1pidamente cuando \\(p\\) crece a \\(1\\); v\u00e9ase la Fig. 6, donde se han representado las cantidades normalizadas respecto de los valores correspondientes al grafo regular, i.e. para \\(p = 0\\).<\/span><\/p>\n

    Kleinberg<\/strong><\/h4>\n

    Jon Kleinberg (Boston, octubre de 1971) es un Profesor de Ingenier\u00eda Inform\u00e1tica de la Universidad de Cornell. Es conocido sobre todo por inventar el algoritmo HITS, una alternativa al algoritmo del PageRank de Google y por haber escrito, junto a \u00c9va Tardos, el libro [6]. Fue galardonado con el Premio Rolf Nevanlinna en 2006 durante el Congreso Internacional de Matem\u00e1ticos celebrado en Madrid. La Uni\u00f3n Matem\u00e1tica Internacional (IMU) le otorg\u00f3 este reconocimiento por \u00absus profundas y creativas contribuciones matem\u00e1ticas al an\u00e1lisis del entorno de la informaci\u00f3n global\u00bb.<\/p>\n

    \"\"
    Fig. 7 – J. Kleinberg, n. en 1971.<\/figcaption><\/figure>\n

    Kleinberg fue m\u00e1s all\u00e1 que Watts y Strogart. Propuso la siguiente variante de ALG 1:<\/p>\n

    ALG 1\u2019:<\/strong><\/p>\n

      \n
    1. Inicializaci\u00f3n \u2013 Como en ALG 1.<\/li>\n
    2. Aleatorizaci\u00f3n – Dado un v\u00e9rtice \\(u\\), a\u00f1adir un arista de extremos \\(u\\) y \\(v\\) de manera aleatoria con probabilidad proporcional a \\(d(u,v)^{-2}\\), de nuevo evitando bucles y aristas duplicadas.<\/li>\n<\/ol>\n

      La idea es, evidentemente, conectar los v\u00e9rtices con nodos lejanos de forma ocasional, de manera que el agrupamiento no se vea seriamente afectado y, al mismo tiempo, la distancia media disminuya satisfactoriamente.<\/span><\/p>\n

      El resultado siguiente muestra la utilidad de ALG 1\u2019:<\/p>\n

      Teorema:<\/strong> Aplicado el algoritmo ALG 1\u2019 a una malla inicial regular <\/em>\\(n \\times n\\), se tiene que la distancia media verifica <\/em>\\(L \\leq K (\\log n)^2\\), donde <\/em>\\(K\\) es independiente de <\/em>\\(n\\).<\/em><\/p>\n

      Para terminar, indiquemos que existe todav\u00eda la posibilidad de mejorar a\u00fan m\u00e1s el modelo. En efecto, muchas redes reales presentan con frecuencia agrupaciones relevantes que nada o poco tienen que ver con la distancia entre individuos; v\u00e9ase por ejemplo el modelo de Barab\u00e1si-Albert en [7], en donde el mecanismo principal es la llamada conexi\u00f3n preferencial.<\/em><\/p>\n

      Referencias:<\/strong><\/h4>\n
        \n
      1. S. Leonesi, The mystery of the six degrees of separation, parts I and II: from order to random, Lett Mat Int (2015) 3:121\u2013127; \u00a0The mystery of the six degrees of separation, part II: navigability and small worlds, Lett Mat Int (2015) 3:215\u2013220.<\/li>\n
      2. L. Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Acad. Sci. U. Petrop 8, 128-40 (1736), <\/span>Reimpreso en Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.<\/span><\/li>\n
      3. D.J. <\/span>Watts, S.H. Strogatz, Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998).<\/span><\/li>\n
      4. J. Kleinberg, The small-world phenomenon: an algorithmic perspective. In: Proceedings 32nd ACM Symposium on Theory of Computing (2000) (also in Cornell Computer Science Technical Report, 99\u20131776, 1999).<\/span><\/li>\n
      5. D.J. Watts, Seis grados de separaci\u00f3n: la Ciencia de las redes en la era del acceso, Ed. Paid\u00f3s, 2006.<\/span><\/li>\n
      6. J. Kleinberg, E. Tardos, Algorithm design,\u00a0<\/span>Pearson, 2005.<\/li>\n
      7. L. Barab\u00e1si, R. Albert, Emergence of scaling in random networks, Science, Vol. <\/span>286, 5439 (1999).<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

        De d\u00f3nde viene todo esto … El escritor h\u00fangaro \u00a0Frigyes Karinthy public\u00f3 en 1929 un volumen de relatos cortos con el t\u00edtulo \u00abEverything is Different\u00bb, entre los cuales se encuentra uno titulado \u00abEslabones\u00bb. En \u00e9l, uno de los personajes, alentado por la idea de que, debido a la rapidez de las comunicaciones de la \u00e9poca, […]<\/p>\n","protected":false},"author":48,"featured_media":25151,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2802],"tags":[268],"ppma_author":[2823],"class_list":["post-25211","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mathema","tag-grafos"],"jetpack_featured_media_url":"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres.jpg","uagb_featured_image_src":{"full":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres.jpg",1700,948,false],"thumbnail":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-150x150.jpg",150,150,true],"medium":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-300x167.jpg",300,167,true],"medium_large":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-768x428.jpg",768,428,true],"large":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-1024x571.jpg",1024,571,true],"1536x1536":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-1536x857.jpg",1536,857,true],"2048x2048":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres.jpg",1700,948,false],"bdpp-medium":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2026\/06\/mediumres-640x480.jpg",640,480,true]},"uagb_author_info":{"display_name":"Enrique Fern\u00e1ndez-Cara","author_link":"https:\/\/www.rasc.es\/blogacademia\/?author=48"},"uagb_comment_info":0,"uagb_excerpt":"De d\u00f3nde viene todo esto … El escritor h\u00fangaro \u00a0Frigyes Karinthy public\u00f3 en 1929 un volumen de relatos cortos con el t\u00edtulo \u00abEverything is Different\u00bb, entre los cuales se encuentra uno titulado \u00abEslabones\u00bb. En \u00e9l, uno de los personajes, alentado por la idea de que, debido a la rapidez de las comunicaciones de la \u00e9poca,…","jetpack_sharing_enabled":true,"authors":[{"term_id":2823,"user_id":48,"is_guest":0,"slug":"fernandez-cara","display_name":"Enrique Fern\u00e1ndez-Cara","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/57e5d3006ba9033519e68604a442c416f94f2505fd5ff4db36647e336399c282?s=96&d=mm&r=g","0":null,"1":"","2":"","3":"","4":"","5":"","6":"","7":"","8":""}],"_links":{"self":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/25211","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/users\/48"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=25211"}],"version-history":[{"count":12,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/25211\/revisions"}],"predecessor-version":[{"id":25266,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/25211\/revisions\/25266"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/media\/25151"}],"wp:attachment":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=25211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=25211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=25211"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=25211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}