Popularidad local en grafos del tipo Barabási-Albert: implicancias en el modelo multipartito number-in-hand

Abstract

La presente memoria tiene como objetivo el estudio del problema de reconstrucción de redes en sistemas distribuidos que utilizan mensajes pequeños. Esto resulta de gran interés en la actualidad debido a la existencia de redes de gran tamaño, tales como la World Wide Web y las redes sociales, que no necesariamente se encuentran almacenadas en su totalidad en un solo lugar. Debido a esto surge el interés de estudiar aspectos particulares de la topología de las redes de este tipo, coloquialmente denominadas Small World Networks. En primer lugar se elabora un protocolo donde todos los nodos o procesadores, utili- zando su información local, colaboran para reconstruir el grafo completo intercambiando información en rounds. Este protocolo es capaz de reconstruir cualquier grafo en 2 rounds. En particular, funcionará utilizando una cantidad pequeña de información local para cla- ses de grafos que exhiben una topología especial, que se denominará Popularidad Local (se dice que un grafo es k-Localmente-Popular si para todo nodo en la red, éste tiene a lo más k vecinos con grado mayor o igual a él). Posteriormente, se expone el modelo desarrollado por Barabási y Albert, quienes mo- tivados por simular de mejor forma la topología de redes que surgen en la actualidad, proponen un modelo que evoluciona en etapas discretas. Partiendo con un grafo pequeño, en cada etapa se agrega un nuevo nodo que se conecta con m nodos existentes en el grafo utilizando la regla Preferential Attachment, en la cual la probabilidad de conectarse con un nodo depende de su grado. Luego se introduce la noción de Popularidad-Local-Débil para grafos aleatorios. Se analiza la topología de los árboles del tipo Small World utilizando el modelo de Bara-bási y Albert con parámetro m = 1 y se demuestra que esta clase de grafos es 9-Débil- 4 Localmente-Popular. Por lo tanto, estos grafos se pueden reconstruir en 2 rounds utilizando información local de tamaño logarítmico. Finalmente se estudia experimentalmente la topología de los grafos generales de Ba- rabási y Albert y se conjetura que estos grafos son k-Débil-Localmente-Populares donde k sólo depende de m y no depende del tamaño del grafo. Ésto podría constituir un gran avance dado que permitiría reconstruir eficientemente las grandes redes de la actualidad.