Popularidad local en grafos del tipo Barabási-Albert: implicancias en el modelo multipartito number-in-hand
Professor Advisor
dc.contributor.advisor
Rapaport Zimermann, Iván
Author
dc.contributor.author
Urrutia Espindola, Javiera Francisca
Staff editor
dc.contributor.editor
Facultad de Ciencias Físicas y Matemáticas
Staff editor
dc.contributor.editor
Departamento de Ingeniería Matemática
Associate professor
dc.contributor.other
Remenik Zisis, Daniel
Associate professor
dc.contributor.other
Soto San Martín, José
Admission date
dc.date.accessioned
2013-11-06T17:34:28Z
Available date
dc.date.available
2013-11-06T17:34:28Z
Publication date
dc.date.issued
2013
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/114676
General note
dc.description
Ingeniera Civil Matemático
Abstract
dc.description.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.