´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 1 of 36

Go Back

Full Screen

Close

Quit

REDES SMALL WORLD

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios

1.

Introducci´on

Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 2 of 36

Go Back

Full Screen

Close

Quit

Las estructuras complejas de red describen una gran variedad de sistemas de alta importancia tecnol´ogica e intelectual: ➊ la c´elula se describe mejor como una compleja red de sustancias conectadas por reacciones qu´ımicas, ➋ Internet es una compleja red de enrutadores y computadores conectados por varios enlaces f´ısicos o inal´ambricos, ➌ aficiones e ideas se dispersan por la red social cuyos nodos son seres humanos y los enlaces representan relaciones sociales, ➍ la World-Wide Web es una enorme red virtual de p´aginas web conectadas por hiperv´ınculos.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

Existe un gran n´umero de atributos caracter´ısticos de una red. No obstante, se han definido tres propiedades fundamentales, cuyo comportamiento permite diferenciar a qu´e paradigma de modelado obedece una red. Estas propiedades son:

JJ

II

• la longitud de camino promedio,

J

I

• el coeficiente de agrupamiento,

Page 3 of 36

Go Back

Full Screen

Close

Quit

• y la distribuci´on del n´umero de correlaci´on.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos

1.1.

Longitud de camino promedio

Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 4 of 36

Go Back

Full Screen

Close

Quit

El concepto de small world en t´erminos sencillos describe el hecho de que, no obstante su frecuente gran tama˜no, en la mayor´ıa de las redes hay un camino relativamente corto entre cualquier par de nodos. La distancia entre dos nodos se define como el n´umero de enlaces a lo largo del camino m´as corto que los conecta. La propiedad de small world se cuantifica con la longitud de camino promedio, l, y aparece para caracterizar la mayor´ıa de redes complejas.

1.2.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 5 of 36

Go Back

Full Screen

Close

Quit

Agrupamiento

Una propiedad com´un de las redes sociales es la formaci´on de corrillos, que representan c´ırculos de amigos o conocidos en los cuales cada miembro conoce a todos los otros. Esta tendencia inherente al agrupamiento se cuantifica con el coeficiente de agrupamiento. Se centra la atenci´on sobre un nodo i seleccionado en la red, el cual tiene ki enlaces que lo conectan a otros ki nodos. Si los primeros vecinos del nodo original son parte de un corrillo, deber´ıa haber ki (ki − 1)/2 enlaces entre ellos. La raz´on entre el n´umero Ei de enlaces que realmente existen entre estos ki nodos y el n´umero total ki(ki − 1)/2 da el valor del coeficiente de agrupamiento del nodo i,

Ci = 2Ei/ki(ki − 1) .

(1)

El coeficiente de agrupamiento de toda la red, C , es el promedio de todos los Ci individuales.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

1.3.

´ Distribuci´on del numero de correlaci´on

Home Page

Title Page

JJ

II

J

I

Page 6 of 36

Go Back

Full Screen

Close

Quit

No todos los nodos en una red tienen el mismo n´umero de enlaces. La dispersi´on en el n´umero de enlaces que tiene un nodo, o n´umero de correlaci´on del nodo, se caracteriza con una funci´on de distribuci´on P (k), la cual da la probabilidad de que un nodo seleccionado aleatoriamente tenga exactamente k enlaces.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

La b´usqueda de modelos que se aproximen m´as a las redes reales ha provocado un renacimiento del modelado de redes, dando como resultado la introducci´on y estudio de tres clases principales de paradigmas de modelado [1]: 1. Grafos aleatorios, los cuales son variantes del modelo de Erd´os-R´enyi. 2. Una clase de modelos colectivamente llamados modelos de small world.

Page 7 of 36

3. Modelos libres de escala (SF). Go Back

Full Screen

Close

Quit

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . .

2.

La topolog´ıa de las redes reales: resultados emp´ıricos

El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Red Tama˜no l lrand C Crand γ −5 MC 70975 9.5 8.2 0.59 5.4 ∗ 10 2.5 I-DL 3015-6209 3.7-3.76 6.18-6.36 0.18-0.3 0.001

Title Page

JJ

II

J

I

• MC (Math coautorship):

Grafo de colaboraci´on de matem´aticos en publicaciones entre 1991 y 1998. Los nodos son los matem´aticos y dos nodos estan conectados si los dos matem´aticos han escrito un art´ıculo juntos.

Page 8 of 36

• I-DL (Internet, domain level): Cada dominio, compuesto de Go Back

Full Screen

Close

Quit

cientos de routers y computadores, se representa con un nodo, y se dibuja un enlace entre dos dominios si existe al menos una ruta que los conecta.

´ Introduccion La topolog´ıa de las . . .

3.

Grafos aleatorios

Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 9 of 36

Go Back

Full Screen

Close

Quit

• En t´erminos matem´aticos una red se representa con un grafo. Un grafo es un par de conjuntos G = {P, E}, donde P es un conjunto de N nodos P1 , P2 , . . . , PN y E es un conjunto de enlaces que conectan dos elementos de P . • Erd´os y R´enyi definen un grafo aleatorio como N nodos rotulados conectados por n enlaces los cuales son escogidos N (N −1)

aleatoriamente de entre los 2 posibles enlaces. En total hay C Nn (N −1) grafos con N nodos y n enlaces, formando un es2 pacio de probabilidad en el cual cada realizaci´on es equiprobable.

• La teor´ıa de grafos aleatorios estudia las propiedades del espacio de probabilidad asociado con grafos con N nodos cuando N → ∞.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . .

Resultados para los grafos aleatorios:

Algoritmos sobre grafos

−pN (pN )

Resultados obtenidos

P (k) ' e

Home Page

Title Page

JJ

II

J

I

Page 10 of 36

Go Back

Full Screen

Close

Quit

k!

k

k −hki hki

=e

k!

donde

hki = p(N − 1) ' pN . ln(N ) lrand ∼ . ln(hki) hki . Crand = p = N

,

4. ´ Introduccion

Redes small world y el modelo de Watts-Strogatz

La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 11 of 36

Go Back

Full Screen

Close

Quit

Las redes small world se caracterizan por tener un coeficiente de agrupamiento alto y una longitud de camino promedio l peque˜na. El primer intento exitoso de generaci´on de grafos con estas propiedades es debido a Watts y Strogatz [1]. 1. Comenzar con orden: Comenzar con una red en anillo de N nodos, en la cual cada nodo est´a conectado a sus primeros K vecinos (K/2 a cada lado). Para tener una red dispersa pero conectada en todo instante de tiempo, considerar N  K  ln N  1. 2. Aleatoriedad: Redireccionar aleatoriamente cada enlace de la red con probabilidad p, excluyendo auto conexiones y enlaces duplicados. Este proceso introduce en promedio pN K/2 enlaces de largo alcance que conectan nodos que de otro modo har´ıan parte de vecindades diferentes. Variando p, se puede monitorear la transici´on entre orden (p = 0) y aleatoriedad (p = 1).

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 12 of 36

Go Back

Full Screen

Close

Quit

Por ejemplo, en los sistemas sociales la mayor´ıa de la gente tiene como amigos a sus vecinos de barrio o a sus compa˜neros de trabajo; pero por otro lado, todos tienen uno o dos amigos en otros pa´ıses, los cuales est´an representados por los enlaces de largo alcance que se obtienen mediante redireccionamiento en el modelo de Watts-Strogatz.

5.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos

El modelo de Newman y Watts y las propiedades de las redes small world

Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 13 of 36

Existe una variante muy estudiada del modelo de WS, propuesta por Newman y Watts [1], en la cual se adicionan enlaces entre pares de sitios escogidos aleatoriamente, pero no se remueven enlaces de la red regular. Este modelo es m´as f´acil de analizar que el modelo de Watts-Strogatz porque no lleva a la formaci´on de grupos aislados, lo cual s´ı puede suceder en el modelo original. Para p suficientemente peque˜na y N suficientemente grande, este modelo es equivalente al modelo WS.

Go Back

Full Screen

Close

Quit

A continuaci´on se resumen los principales resultados concernientes a las propiedades de los modelos small world, los cuales se encuentran recopilados en [1].

5.1.

Longitud de camino promedio

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

El el modelo WS hay un cambio en el comportamiento de la longitud de camino promedio, l, a medida que se incrementa la fracci´on p de los ejes redireccionados. Para peque˜nas p, l escala linealmente con el tama˜no del sistema, mientras que para grandes p el escalado es logar´ıtmico.

Home Page

Title Page

JJ

II

J

I

Existe una longitud cr´ıtica N ∗ (dependiente de p) tal que l ∝ N si N < N ∗ , y l ∝ ln N si N > N ∗ . Este concepto permiti´o que se conjeturara que la longitud de camino caracter´ıstica escala como  

l(N, p) ∝ N ∗F

Page 14 of 36

Go Back

Full Screen

Close

Quit

donde

N N∗

( u si u  1 F (u) = ln(u) si u  1

,

(2)

, .

(3)

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 15 of 36

Go Back

Full Screen

Close

Quit

Simulaciones num´ericas y argumentos anal´ıticos [2] permiten concluir que la longitud cr´ıtica N ∗ escala con p como N ∗ ∝ p−τ , donde τ = 1/d y d es la dimensi´on de la red original a la cual se le adicionan los enlaces aleatorios . As´ı, para el modelo original WS, definido sobre un c´ırculo (d = 1), se tiene τ = 1, y el inicio del comportamiento small world tiene lugar en la probabilidad de redireccionamiento p∗ ∼ 1/N .

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 16 of 36

Go Back

Full Screen

Close

Quit

´ Introduccion La topolog´ıa de las . . .

5.2.

Grafos aleatorios

Coeficiente de agrupamiento

Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Para calcular C 0 (p) para el modelo WS, se comienza con una red regular con un coeficiente de agrupamiento C(0). Para p > 0, dos vecinos de un nodo i que estaban conectados con p = 0 son a´un vecinos de i y est´an a´un conectados por un enlace con probabilidad (1 − p)3 , ya que hay tres enlaces que deben permanecer intactos. Consecuentemente, C 0 (p) w C(0)(1 − p)3 . Se ha verificado que la desviaci´on de C(p) de esta expresi´on es peque˜na y tiende a cero cuando N → ∞. La expresi´on correspondiente para el modelo de Newman-Watts es [1],

Page 17 of 36

Go Back

Full Screen

Close

Quit

C 0(p) =

3K(K − 1) 2K(2K − 1) + 8pK 2 + 4p2K 2

.

(4)

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 18 of 36

Go Back

Full Screen

Close

Quit

5.3.

´ Distribuci´on del numero de correlaci´on

En el modelo WS con p = 0, cada nodo tiene el mismo n´umero de correlaci´on K , de modo que la distribuci´on del n´umero de correlaci´on es una funci´on delta centrada en K . Una p diferente de cero introduce desorden en la red, ensanchando la distribuci´on del n´umero de correlaci´on mientras mantiene el n´umero de correlaci´on promedio igual a K . La forma de la distribuci´on del n´umero de correlaci´on es similar a la de un grafo aleatorio: tiene un pico pronunciado en hki = K y decae exponencialmente para k grande . De este modo, la topolog´ıa de la red es relativamente homog´enea, con todos los nodos teniendo aproximadamente el mismo n´umero de enlaces.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 19 of 36

Go Back

Full Screen

Close

Quit

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . .

6.

Algoritmos sobre grafos

Algoritmos sobre grafos Resultados obtenidos

Home Page

Los grafos son estructuras de datos muy importantes en ciencias de la computaci´on, y los algoritmos para trabajar con ellos son fundamentales para este campo.

Title Page

JJ

II

6.1.

J

I

Existen dos m´etodos est´andar para representar un grafo G = (N, E): como una colecci´on de listas de adyacencia o como una matriz de adyacencia. Los dos m´etodos son aplicables tanto a grafos dirigidos como no dirigidos.

Page 20 of 36

Go Back

Full Screen

Close

Quit

Representaciones de grafos

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 21 of 36

Go Back

Full Screen

Close

Quit

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 22 of 36

Go Back

Full Screen

Close

Quit

6.2.

C´alculo de los caminos m´as cortos entre todas las parejas

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 23 of 36

Go Back

Full Screen

Close

Quit

Los algoritmos de esta secci´on usan una representaci´on en matriz de adyacencia. Por conveniencia, se asume que los nodos est´an numerados 1, 2, . . . , |N |, de modo que la entrada es una matriz W de dimensi´on n x n, la cual representa los pesos de los enlaces de un grafo dirigido de n nodos G = (N, E). Esto es, W = (wij ), donde

  0 si i = j , wij = 1 si i 6= j y (i, j) ∈ E  ∞ si i = 6 j y (i, j) ∈ /E

, .

La salida tabular de los algoritmos para los caminos m´as cortos entre todas las parejas presentados en esta secci´on es una matriz D = (dij ) de dimensi´on n x n, donde la entrada dij contiene el peso del camino m´as corto desde el nodo i hasta el nodo j . Esto es, si δ(i, j) denota el peso del camino m´as corto desde el nodo i hasta el nodo j , entonces dij = δ(i, j) al final.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 24 of 36

Go Back

Full Screen

Close

Quit

E XTEND -S HORTEST-PATHS(L, W ) 1 n ← rows[L] 2 sea L0 = (lij0 ) una matriz n x n 3 for i ← 1 to n 4 do for j ← 1 to n 5 do lij0 ← ∞ 6 for k ← 1 to n 7 do lij0 ← min(lij0 , lik + wkj ) 8 9 10 return L0 FASTER -A LL -PAIRS -S HORTEST-PATHS(W ) 1 n ← rows[W ] 2 L(1) ← W 3 m←1 4 while m < n − 1 5 do L(2m) ← E XTEND -S HORTEST-PATHS(L(m) , L(m) ) 6 m ← 2m 7 return L(m)

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

6.3.

C´alculo del coeficiente de agrupamiento

En esta secci´on se considera el problema de encontrar el coeficiente de agrupamiento de un grafo dirigido y con pesos G = (N, E), con una funci´on peso w : E → R que asigna a cada enlace un peso de valor real, dada por

Home Page

Title Page

JJ

II

J

I

Page 25 of 36

Go Back

Full Screen

Close

Quit

  0 si i = j , wij = 1 si i 6= j y (i, j) ∈ E  ∞ si i = 6 j y (i, j) ∈ /E

, .

El c´alculo del coeficiente de agrupamiento se hace a partir de su definici´on. El coeficiente de agrupamiento se calcula solo para grafos con 100 nodos. El siguiente procedimiento realiza el c´alculo, recibiendo como par´ametro la matriz W con los pesos de los enlaces y retornando el coeficiente de agrupamiento ci.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 26 of 36

Go Back

Full Screen

Close

Quit

C LUSTERING -C OEFFICIENT(W ) 1 n ← rows[W ] 2 ci ← 0 3 for i ← 1 to n 4 do neighbori ← 0 5 for i ← 1 to n 6 do k ← 0 7 for j ← 1 to n 8 do if wij = 1 9 then neighbork ← j 10 k ←k+1 11 12 realedges ← 0 13 for p ← 0 to k − 2 14 do for q ← p + 1 to k − 1 15 do if wneighborp neighborq = 1 16 then realedges ← realedges + 1 17 18 19 totaledges ← k(k − 1)/2 20 ci ← ci + realedges/totaledges 21 ci ← ci/100 22 return ci

6.4. ´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

´ C´alculo de la distribuci´on del numero de correlaci´on

Ahora se considera el problema de encontrar la distribuci´on del n´umero de correlaci´on de un grafo dirigido y con pesos G = (N, E), con una funci´on peso w : E → R que asigna a cada enlace un peso de valor real, dada por

Home Page

Title Page

JJ

II

J

I

Page 27 of 36

Go Back

Full Screen

Close

Quit

  0 si i = j , wij = 1 si i 6= j y (i, j) ∈ E  ∞ si i = 6 j y (i, j) ∈ /E

, .

El c´alculo de la distribuci´on del n´umero de correlaci´on se hace a partir de su definici´on. La distribuci´on del n´umero de correlaci´on se calcula solo para grafos con 100 nodos. El siguiente procedimiento realiza el c´alculo, recibiendo como par´ametro la matriz W con los pesos de los enlaces, y retornando el arreglo DIST con el total de nodos por cada posible n´umero de enlaces.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 28 of 36

Go Back

Full Screen

Close

Quit

D EGREE -D ISTRIBUTION(W ) 1 n ← rows[W ] 2 for i ← 1 to n 3 do disti ← 0 4 for i ← 1 to n 5 do numedges ← 0 6 for j ← 1 to n 7 do if wij = 1 and i 6= j 8 then numedges ← numedges + 1 9 10 distnumedges ← distnumedges + 1 11 for i ← 1 to n 12 do disti ← disti /100 13 return DIST

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos

7.

Resultados obtenidos

Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 29 of 36

Go Back

Full Screen

Close

Quit

Para nuestras investigaciones num´ericas utilizamos redes unidimensionales que inicialmente ten´ıan condiciones de frontera peri´odicas (un anillo de nodos), en las cuales cada nodo estaba conectado a los K = 2 nodos m´as cercanos a e´ l. Posteriormente se adicionaron enlaces entre parejas de nodos escogidas aleatoriamente, sin remover enlaces de la red inicial, de conformidad con el modelo de Newman-Watts. El tama˜no de las redes oscil´o entre un m´ınimo de N = 5 nodos y un m´aximo de N = 100 nodos.

7.1.

Longitud de camino promedio

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos 18

Resultados obtenidos

16

Home Page

p=0.001 p=0.003 p=0.005 p=0.007 p=0.01 p=1

14

12

Title Page

JJ

II

J

I

lprom

10

8

6

4

Page 30 of 36

2

0

Go Back

Full Screen

Close

Quit

0

10

20

30

40

50

60 N

70

80

90

100

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios

La gr´afica de N ∗ en funci´on de la probabilidad p sugiri´o una ley de potencia del tipo

Redes small world y el . . .

N ∗(p) = Cp−τ

El modelo de Newman . . . Algoritmos sobre grafos

,

(5)

Resultados obtenidos

Home Page

Title Page

que comprobamos al realizar una gr´afica log-log y obtener la recta. Un ajuste lineal de m´ınimos cuadrados nos permiti´o establecer los valores de C y τ , dando como resultado

τ = 0.95(6) (F = 1095.635, r = −0.9986337) ,

JJ

II

C = 0.13(4),

J

I

que al ser reeemplazados en la ec. (5), conducen a

Page 31 of 36

N ∗(p) = 0.13(4)p−0.95(6) .

(6)

Go Back

Full Screen

Close

Quit

Por lo tanto, obtuvimos τ ' 1/d = 1/1 = 1, tal como se esperaba.

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . .

10

3

El modelo de Newman . . . R es ultados de la s imulac ión N*(p) = 0.13(4) p exp(0.95(6))

Algoritmos sobre grafos Resultados obtenidos

Home Page

JJ

II 10

J

2

N*(p)

Title Page

10

1

I

Page 32 of 36 0

Go Back

Full Screen

Close

Quit

10 4 10

10

3

10 p

2

10

1

7.2.

Coeficiente de agrupamiento

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos 1

Resultados obtenidos

0.9

Home Page

Fó rmula teó rica R es ultados de la s imulació n C (p) = 0.998(8) p + 0.006(4)

0.8 0.7

Title Page

II

C (p)

JJ

0.6 0.5 0.4

J

I

0.3 0.2

Page 33 of 36

0.1 0

Go Back

Full Screen

Close

Quit

0

0.1

0.2

0.3

0.4

0.5 p

0.6

0.7

0.8

0.9

1

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos Resultados obtenidos

Un ajuste lineal de m´ınimos cuadrados permite establecer que esta curva obedece la ecuaci´on

Home Page

C(p) = 0.998(8)p + 0.006(4)

(7)

Title Page

JJ

II

J

I

Page 34 of 36

Go Back

Full Screen

Close

Quit

(F = 56458.8, r = 0.9999203) . Un an´alisis de los casos extremos triviales p ∼ 0 y p = 1, a la luz de la definici´on del coeficiente de agrupamiento, comprueba la validez de los resultados generados por el software.

´ Distribuci´on del numero de correlaci´on

7.3. ´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . . Algoritmos sobre grafos 10

0

p=0.1 p=0.2 p=0.4 p=0.6 p=0.9 p=1

Resultados obtenidos

Home Page

1

10

P (k)

Title Page

JJ

II

J

I

2

10

3

10

Page 35 of 36 10

4

10

Go Back

Full Screen

Close

Quit

0

10

1

10 k

2

10

3

References

´ Introduccion La topolog´ıa de las . . . Grafos aleatorios Redes small world y el . . . El modelo de Newman . . .

[1] R´eka, A. y Barab´asi, A., Statistical Mechanics of Complex Networks, cond-mat/0106096.

Algoritmos sobre grafos Resultados obtenidos

Home Page

Title Page

JJ

II

J

I

Page 36 of 36

[2] Argollo de Menezes, M., Moukarzel, C.F. y Penna, T.J.P., First Order Transition is Small-World Networks, condmath/9903426. [3] Barrat, A. y Weigt, M., Euro. Phys. Journ. B 13, 547, 2000. [4] Stauffer, D. y Aharony, A., Introduction to Percolation Theory, Taylor & Francis, 1992. [5] Cormen, T., Leiserson, C., Rivest, R. y Stein, C., Introduction to Algorithms, The MIT Press, 2001.

Go Back

Full Screen

Close

Quit

[6] Yates, R. y Goodman, D., Probability and Stochastic Processes: a Friendly Introduction for Electrical and Computer Engineers, John Wiley and Sons, 1998.