Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.
-
Upload
patricia-duarte-murillo -
Category
Documents
-
view
226 -
download
0
Transcript of Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.
![Page 1: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/1.jpg)
Modelos de Conectividad
Grafos aleatorios
Carlos Aguirre MaesoEscuela Politécnica superior
![Page 2: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/2.jpg)
El modelo de Erdos y Renyi
● Se estudia en los años 50-60
● Cada rama del grafo existe con una probabilidad p
● P suele seguir una distribución uniforme.
![Page 3: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/3.jpg)
El modelo de Erdos y Renyi
![Page 4: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/4.jpg)
Comparación con grafos aleatorios
![Page 5: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/5.jpg)
El modelo de Erdos y Renyi
● Otra forma de definir los grafos aleatorios es
seleccionar parejas de nodos aleatoriamente.
● Se seleccionan exactamente p*N*(N-1)/2 parejas.
● Ambos tipos de grafos aleatorios son equivalentes.
![Page 6: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/6.jpg)
Propiedades.
● El estudio de grafos aleatorios se centra sobre todo
en averiguar para que probabilidad p aparece
cierta propiedad Q.
– Cuando el grafo es conexo
– Cuando la distancia media es menor que cierto numero.
– Cuando el indice de clusterizacion es mayor que cierto
numero
![Page 7: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/7.jpg)
Propiedades.
● Erdos y Renyi descubrieron que las propiedades Q
aparecian de forma repentina según crecia p.
● Para muchas propiedades Q se verifica que existe
una probabilidad crítica pc(N) tal que
– con probabilidad 0 el grafo no tiene Q si p(N) < pc(N)
– con probabilidad 1 el grafo tiene Q si p(N) > pc(N)
![Page 8: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/8.jpg)
Subgrafos
● La primera propiedad que estudiaron Erdos y
Renyo fue la aparicion de subgrafos
– Por ejemplo, a que probabilidad crítica p casi todo
grafo G contiene un arbol de orden 3.
![Page 9: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/9.jpg)
Subgrafos
● Se puede demostrar que el número medio de
subgrafos con k nodos y l ramas de un grafo
aleatorio con N nodos y probabilidad p es:
● Donde a es el numero de grafos isomorfos entre si
![Page 10: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/10.jpg)
Subgrafos
● Se puede demostrar que el número medio de
subgrafos con k nodos y l ramas de un grafo
aleatorio con N nodos y probabilidad p es:
● Donde a es el numero de grafos isomorfos entre si
![Page 11: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/11.jpg)
Subgrafos
● La probabilidad crítica pc(N) de encontrar algunos
subgrafos es:
![Page 12: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/12.jpg)
Clusters
● Un subgrafo aislado y conexo es un cluster.
● Erdos y Renyi demostraron que la estructura de
clusters de un grafo cambia abruptamente cuando
<k> se acerca a 1.
![Page 13: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/13.jpg)
Clusters.
● Si 0< <k> < 1 casi todos los clusters son arboles
(en su mayor parte) o clusters que contienen un
solo ciclo.
● El numero de clusters es de orden N-n donde n es
el numero de ramas.
● El mayor cluster es un arbol de tamaño
proporcional a N
![Page 14: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/14.jpg)
Clusters.
● Si <k> > 1 la estructura anterior cambia
completamente
● Aparece un cluster gigante con [1-f(<k>)]N nodos
donde f es una función que decae
exponencialmente de 1 a 0 cuando x va a infinito.
● Los demas clusters pertenecen a arboles con
Nf(<k>) nodos.
![Page 15: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/15.jpg)
Clusters.
● Si pc = 1/N la mayoria de los nodos pasan a formar
parte del cluster gigante.
● En esta region El tamaño del cluster gigante es
proporcional a la distancia de la probabilidad
critica y la probabilidad
![Page 16: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/16.jpg)
Distribución de grado
● El grado de cada nodo sigue una distribución
binomial
![Page 17: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/17.jpg)
Distribución de grado
● La distribución del grado de los nodos sigue una
distribucion de poisson.
![Page 18: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/18.jpg)
Distribución de grado
![Page 19: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/19.jpg)
Conexidad y diametro.
● El diametro de un grafo es la máxima distancia
entre cualquier par de nodos.
● Si p no es demasiado pequeño los grafos aleatorios
tienden a tener poco diametro.
● Casi todos los grafos aleatorios tienen el mismo
diametro (mas o menos) para la mayor parte de los
valores de p
![Page 20: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/20.jpg)
Conexidad y diametro.
● Para la mayor parte de grafos aleatorios su
diametro toma el siguiente valor
![Page 21: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/21.jpg)
Conexidad y diametro.
● En general se tiene:
– Si <k> < 1 el grafo tiene arboles aislados.
– Si <k> > 1 (aparece el cluster gigante) el diametro del
grafo es el del cluster gigante. Para <k> > 3.5 el
diametro es proporcional a ln(N)/ln(<k>)
– Si <k> ln(N) el grafo es conexo y su diametro es
proximo a ln(N)/ln(<k>)
![Page 22: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/22.jpg)
Camino caracteristico.
● El camino caracteristico se comporta de forma
similar al diametro. En particular:
![Page 23: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/23.jpg)
Camino caracteristico.
![Page 24: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/24.jpg)
Indice de clusterización
● En un grafo aleatorio la probabilidad de que dos
vecinos esten conectados es igual a la que dos
nodos elegidos al azar esten conectados.
● El indice de clusterizacion de un grafo aleatorio es
Crand = p = <k>/N
![Page 25: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/25.jpg)
Indice de clusterización
![Page 26: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/26.jpg)
![Page 27: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/27.jpg)
Espectro del grafo.
● Un grafo puede ser visto como una matriz NxN.
● Dicha matriz tendra un conjunto de autovalores.
● Se define su densidad espectral como
![Page 28: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/28.jpg)
Espectro del grafo.
![Page 29: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/29.jpg)
Grafos aleatorios generalizados.
● Son grafos cuya distribucion del grado de los
nodos esta prefijada.
● Se aleatorizan otros aspectos del grafo.
![Page 30: Modelos de Conectividad Grafos aleatorios Carlos Aguirre Maeso Escuela Politécnica superior.](https://reader035.fdocumento.com/reader035/viewer/2022062222/5665b4831a28abb57c921dc1/html5/thumbnails/30.jpg)
Grafos aleatorios generalizados.
● Las ramas conectan nodos al azar, pero tienen la
restriccion que la distribución del grado es
prefijada (usualmente libre de escala).
● La distribución libre de escala viene determinada
por un unico parametro g (la pendiente de la
recta).