procesos de propagaci¶on de informaci¶on en redes...

TESISMAESTRIA EN CIENCIAS FISICAS

Procesos de Propagacion de Informacion

en Redes Complejas

Jean Pierre Chauny

Dr. Damian ZanetteDirector

ETH El. Ing Jean Pierre ChaunyMaestrando

Instituto BalseiroComision Nacional de Energıa Atomica

Universidad Nacional de Cuyo

Diciembre 2005

Resumen

En este trabajo estudiamos procesos de propagacion de informacion en redescomplejas, ası como un mecanismo no supervisado de deteccion y correccion deerrores basado en la estructura de clusters de la red.

Mediante un algoritmo particular de construccion de redes definimos unaclase de redes complejas dirigidas. Una probabilidad, la aleatoriedad de la red,nos permitio interpolar entre redes ordenadas y redes aleatorias. El estudio delas propiedades geometricas se realizo midiendo tres cantidades: el numero desalidas, la distancia media y el grado de clustering. Esto nos llevo a clasificarlas redes en cuatro tipos: red ordenada, red aleatoria, red totalmente conectaday red small world dirigida.

Una dinamica de interaccion sencilla modela el proceso de propagacion de in-formacion. En ese contexto nos interesamos en la evolucion temporal del numerode nodos informados en funcion de los parametros topologicos de la red. Las evi-dencias numericas demuestran que las propiedades dinamicas son fuertementeinfluenciadas por la topologıa de las redes subyacentes. La red totalmente conec-tada nos permitio validar nuestros algoritmos computacionales, ya que concedeun tratamiento analıtico cerrado. Asimismo este tipo de red nos condujo a unaclasificacion fenomenologica de las redes aleatorias y small world dirigidas atraves de un tiempo caracterıstico que describe la velocidad de propagacion. Lared ordenada, por su lado, mostro dos regımenes dinamicos: uno esencialmentelineal cuando la conectividad de la red es mucho menor que el numero de nodosy otro de tipo “logıstico” cuando la conectividad es del orden del numero denodos. El regimen lineal fue descripto por una ecuacion integro diferencial quenos permitio modelar el proceso de propagacion como dos ondas “informativas”desplazandose a traves de la red en direcciones opuestas y con una velocidadconstante proporcional a la conectividad de la red.

Finalmente estudiamos un mecanismo no supervisado de deteccion y correc-cion de errores. Para esto se introdujo ruido en la transmision a traves de unadada probabilidad y una interaccion sencilla, a primeros vecinos entrantes, quepermite a los agentes detectar y corregir errores. Nos interesamos en la fraccionde nodos desinformados en funcion de los parametros que gobiernan el ruidoy el mecanismo de correccion, ası como de la geometrıa de la red subyacente.Las simulaciones numericas demostraron que las redes con alto grado de clus-tering se encuentran en desventaja cuando se introduce ruido en los canales detransmision, pero que son mas eficientes en detectar y corregir errores.

iii

iv

Palabras clave: sistemas complejos, redes complejas, propagacion de infor-macion, red small world dirigida, deteccion de errores, correccion de errores.

Abstract

We study processes of information propagation on complex networks andnon-supervised detection and correction mechanisms based on the clusteringstructure of the underlying networks.

By means of a specific construction algorithm we define a class of directedcomplex networks. The network randomness is a probability that allows us tointerpolate between ordered and random networks. The study of geometricalproperties is made by measuring three quantities: the number of outgoing edges,the mean distance and the clustering coefficient. This leads us to classify thenetworks in four different types: ordered, random, totally connected and directedsmall world networks.

A simple dynamic interaction models the information propagation process.Within that context we are interested in the temporal evolution of the numberof informed nodes related to the topological parameters of the networks. Nu-merical evidences show that the dynamical properties are strongly influenced bythe geometry of the underlying networks. The totally connected network lets usvalidate our computer algorithms because it grants a complete analytical treat-ment. It also leads us to a phenomenological classification of the random anddirected small world networks through a characteristic time which describes thepropagation speed. On the other hand, the ordered network shows two differentdynamical phases: an essentially linear one when the connectivity is much lesserthan the number of nodes and a kind of “logistic” one when the connectivity isof the order of the number of nodes. The linear phase is described by an integraldifferential equation which lets us to model the propagation process as two in-formation waves. These waves move through the network in opposite directionsat a constant speed which is proportional to the connectivity.

Finally we study a non supervised detection and correction mechanism. Forthis purpose we introduce noise in the transmission by a given probability andan elementary interaction process with the first incoming neighbours so thatthe agents are able to detect and correct this errors. We are interested in thefraction of the wrongly informed nodes related to the parameters that controlthe noise and the correction mechanism, as well as to the geometrical propertiesof the underlying networks. The numerical simulations show that the networkswith a high clustering coefficient are more sensitive to the noise in the trans-mission channels but, at the same time, they are more efficient in detecting andcorrecting errors.

v

vi

Keywords: complex systems, complex networks, information propagation,directed small world network, error detection, error correction.

Indice general

1. Introduccion 1

1.1. ¿Que son redes complejas? . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Procesos de propagacion de informacion . . . . . . . . . . . . . . 4

2. Descripcion del modelo 7

2.1. El algoritmo de construccion de las redes . . . . . . . . . . . . . 7

2.2. La dinamica de interaccion . . . . . . . . . . . . . . . . . . . . . 9

3. Propiedades geometricas de la red 13

3.1. El numero de salidas ZS . . . . . . . . . . . . . . . . . . . . . . . 13

3.2. La distancia media L . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3. El grado de clustering C . . . . . . . . . . . . . . . . . . . . . . . 19

4. Clasificacion de las redes 25

4.1. La red totalmente conectada . . . . . . . . . . . . . . . . . . . . 25

4.2. La red small world dirigida . . . . . . . . . . . . . . . . . . . . . 26

5. Propiedades dinamicas 31

5.1. Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.2. La red totalmente conectada . . . . . . . . . . . . . . . . . . . . 33

5.3. La red ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.4. La red aleatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.5. La red small world dirigida . . . . . . . . . . . . . . . . . . . . . 43

6. Mecanismos de deteccion y correccion de errores 45

vii

viii INDICE GENERAL

6.1. Canales ruidosos . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.2. Deteccion y correccion de errores . . . . . . . . . . . . . . . . . . 48

7. Conclusiones 53

Bibliografıa 57

Indice de figuras

1.1. Los sistemas complejos como enlaces entre distintos niveles deabstraccion. Un ejemplo de los sistemas biologicos. . . . . . . . . 2

1.2. Los sistemas complejos permiten modelarse como redes dirigidaso redes bidireccionales. . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1. Cada uno de los vertices cuenta con conexiones dirigidas haciasus 2k primeros vecinos. . . . . . . . . . . . . . . . . . . . . . . . 8

2.2. Ilustracion esquematica de un paso elemental en el proceso dedesordenamiento. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3. Interpolacion entre redes ordenadas y redes aleatorias mediantela aleatoriedad de la red p. Para valores intermedios de p la redpresenta propiedades small world. . . . . . . . . . . . . . . . . . . 9

2.4. Red ordenada dirigida unidimensional de N = 20, k = 2 concondiciones de contorno periodicas . . . . . . . . . . . . . . . . . 10

2.5. Red ordenada dirigida unidimensional de N = 20, k = 3 concondiciones de contorno periodicas . . . . . . . . . . . . . . . . . 11

3.1. Solucion analıtica (ecuacion 3.4) de la distribucion del numero desalidas ZS para distintos valores de la conectividad k. La aleato-riedad de la red es fija, p = 1. . . . . . . . . . . . . . . . . . . . . 14

3.2. Solucion analıtica (ecuacion 3.4) de la distribucion del numero desalidas ZS para distintos valores de la aleatoriedad de la red p.La conectividad de la red es fija, k = 5. . . . . . . . . . . . . . . 15

3.3. Resultados numericos y solucion analıtica de la distribucion delnumero de salidas ZS . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.4. Valor absoluto de la distancia media L en funcion de la aleato-riedad de la red p para distintos valores de la conectividad k(Numero de Nodos N = 100, 1000 realizaciones). . . . . . . . . . 17

ix

x INDICE DE FIGURAS

3.5. Valor relativo de la distancia L(p)L(0) en funcion de la aleatoriedad

de la red p para distintos valores de la conectividad k (Numerode Nodos N = 100, 1000 realizaciones). . . . . . . . . . . . . . . 18

3.6. La distancia media L es una variable aleatoria. Valor medio ydispersion de L en funcion de la aleatoriedad p para N = 100,k = 3 y 10000 realizaciones. . . . . . . . . . . . . . . . . . . . . . 19

3.7. Distribucion de probabilidades P ( L(p) = j ) de la distanciamedia L en funcion de la aleatoriedad p para N = 100, k = 3 y10000 realizaciones. Notese la influencia de p en la dispersion dela distribucion. (Continua en la figura 3.8) . . . . . . . . . . . . . 20

3.8. Distribucion de probabilidades P ( L(p) = j ) de la distanciamedia L en funcion de la aleatoriedad p para N = 100, k = 3 y10000 realizaciones. Notese la influencia de p en la dispersion dela distribucion. (Viene de la figura 3.7) . . . . . . . . . . . . . . . 21

3.9. Si el individuo A es amigo de los individuos B y D, entoncesexiste una probabilidad grande que por su lado B y D tambiensean amigos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.10. El grado de clustering C se basa en el conteo de las relacionestriangulares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.11. El valor medio del grado de clustering C en funcion de la aleato-riedad de la red p para distintos valores de la conectividad k(N = 100, 5000 realizaciones). . . . . . . . . . . . . . . . . . . . . 23

3.12. El valor medio del grado de clustering relativo C(p)C(0) en funcion de

la aleatoriedad de la red p para distintos valores de la conectividadk (N = 100, 5000 realizaciones). . . . . . . . . . . . . . . . . . . . 24

4.1. La red totalmente conectada (N = 20). . . . . . . . . . . . . . . . 26

4.2. La distancia media relativa L(p)L(0) y el grado de clustering relativo

C(p)C(0) en funcion de la aleatoriedad p (N = 1000, k = 5). . . . . . 27

4.3. El indicar κ nos permite seleccionar de manera cualitativa la redsmall world mas reprentativa. (N = 1000, k = 5, psmallworld ≈10−2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.4. Indicador κ(p) en funcion de la aleatoriedad p para distintos va-lores de k. El intervalo de psmallworld es pequeno (N = 100). . . . 28

4.5. Indicador κ(p) en funcion de la aleatoriedad p para distintos va-lores de k. El intervalo de psmallworld es pequeno (N = 1000). . . 29

5.1. El numero de nodos informados en funcion del tiempo I(t) esun proceso estocastico. (3 realizaciones para N = 1000, k = 5 yp = 10−2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

INDICE DE FIGURAS xi

5.2. Para cada valor fijo t0 del tiempo, I(t0) es una variable aleatoriacon una distribucion de probabilidades asociada. . . . . . . . . . 32

5.3. Ilustracion de ayuda para la derivacion analıtica de la probabili-dad de informar Πtc(I) de la red totalmente conectada. . . . . . 35

5.4. La ecuacion diferencial que describe la dinamica de la red total-mente conectada graficada en el espacio de las fases. Se puedenapreciar dos puntos fijos, uno inestable para I = 0 y otro establepara I = N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.5. Simulacion numerica y solucion analıtica de Itc(t). Se graficandos soluciones analıticas para Itc(0) = 1 y Itc(0) = 0,5 respecti-vamente de acuerdo a la expresion de la ecuacion 5.14. . . . . . . 36

5.6. I(t) de redes ordenadas para distintos valores de la conectividadk (k ¿ N). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.7. I(t) de redes ordenadas para distintos valores de la conectividadk. (k ≈ O[N ]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.8. El perfil espacial n(ξ) de la onda informativa en funcion de laconectividad k cuando se propaga en redes ordenadas en el regi-men lineal (k ¿ N). . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.9. Velocidad de propagacion vf del frente de onda informativa enfuncion de k y fe. Comparacion entre resultados numericos de lasolucion analıtica de la ecuacion integro diferencial y medicionesde vf en las simulaciones de propagacion de informacion en redesordenadas (N = 1000, p = 0, 1000 realizaciones). . . . . . . . . . 39

5.10. La evolucion temporal del numero de nodos informados I(t) paradistintos valores de la conectividad k y p = 1 (N = 1000, 1000realizaciones). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.11. La evolucion temporal del numero de nodos informados I(t) paradistintos valores de p > psmallworld y k = 5 (N = 1000, 1000realizaciones). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.12. La calidad de la descripcion fenomenologica va disminuyendo con-forme p decrece en direccion de psmallworld. . . . . . . . . . . . . 42

5.13. El tiempo caracterıstico τ(p) en funcion de la aleatoriedad p paradistintos valores de la conectividad k (N = 1000, 1000 realiza-ciones). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.14. La red small world dirigida no permite ser descripta fenomenologi-camente por la ecuacion 5.23. . . . . . . . . . . . . . . . . . . . . 43

5.15. El tiempo caracterıstico τ(p) en funcion de la aleatoriedad p paradistintos valores de la conectividad k (N = 1000, 1000 realiza-ciones). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

xii INDICE DE FIGURAS

6.1. La fraccion de nodos desinformados i− en funcion de la proba-bilidad de informar erroneamente pE para distintos valores de laaleatoriedad de la red p, (N = 1000, k = 5, 2500 realizaciones). . 46

6.2. La fraccion de nodos desinformados i− en funcion de la proba-bilidad de informar erroneamente pE para distintos valores de laaleatoriedad de la red p, (N = 1000, k = 10, 1000 realizaciones). 47

6.3. La fraccion de nodos desinformados i− en funcion de la conec-tividad k para distintos valores de p y para una probabilidad deerror fija pE = 10−2 (N = 1000, 3000 realizaciones). . . . . . . . 47

6.4. La fraccion de nodos desinformados i− en funcion de la conec-tividad k para distintos valores de p y para una probabilidad deerror fija pE = 10−3 (N = 1000, 7000 realizaciones). . . . . . . . 48

6.5. La fraccion de nodos desinformados i− en funcion de la proba-bilidad de correccion pC para un valor fijo de pE = 10−2, unvalor fijo de la conectividad k = 5 para distintos valores de laaleatoriedad de la red p (N = 1000, 5000 realizaciones). . . . . . 49

6.6. La fraccion de nodos desinformados i− en funcion de la proba-bilidad de correccion pC para un valor fijo de pE = 10−3, unvalor fijo de la conectividad k = 5 para distintos valores de laaleatoriedad de la red p (N = 1000, 10000 realizaciones). . . . . 50

6.7. La fraccion relativa de nodos desinformados i−(pC)i−(0) en funcion de

la probabilidad de correccion pC para un valor fijo de pE = 10−2,un valor fijo de la conectividad k = 5 para distintos valores de laaleatoriedad de la red p (N = 1000, 5000 realizaciones). . . . . . 50

6.8. La fraccion relativa de nodos desinformados i−(pC)i−(0) en funcion de

la probabilidad de correccion pC para un valor fijo de pE = 10−3,un valor fijo de la conectividad k = 5 para distintos valores de laaleatoriedad de la red p (N = 1000, 10000 realizaciones). . . . . 51

Capıtulo 1

Introduccion

1.1. ¿Que son redes complejas?

Cientıficos, ingenieros y otros profesionales, pertenecientes a las mas diver-sas disciplinas, se han visto confrontados a lo largo de la historia, con el reto deentender y describir las propiedades de una clase de sistemas que se caracterizanpor estar compuestos de un gran numero de elementos o agentes interactuantes.A traves de interacciones de mayor o menor alcance estos agentes cambian suspropiedades individuales adoptando estados pertenecientes a un espacio de esta-dos accesibles. De esta interaccion microscopica emergen propiedades colectivasno triviales. Esto quiere decir que el sistema total adquiere propiedades que suselementos constituyentes no poseen.

Por ejemplo, una neurona no tiene inteligencia. Pero un gran numero deneuronas interactuando entre sı pueden producir algo que llamamos mente.Podemos decir que la mente emerge de estas interacciones. En el campo dela inteligencia artificial se busca simular una mente emergente, a partir de com-ponentes mas simples los cuales no se consideran inteligentes. Otro ejemplo esla celula, la cual esta compuesta de moleculas que interactuan a traves de re-acciones quımicas [11]. El metabolismo celular, propiedad de los seres vivos,emerge de estas interacciones quımicas. Por otro lado es bien conocido que elmagnetismo de la materia se manifiesta como resultado del comportamientocolectivo de un gran numero de espines elementales. Estos son solo algunosejemplos de la inmensa variedad de sistemas de estas caracterısticas [2] [3].A estos sistemas se los conoce como sistemas complejos. El deseo de deducircaracterısticas macroscopicas emergentes del entendimiento de las interaccionesmicroscopicas es un reto importante para los cientıficos y una necesidad paralos profesionales involucrados con el universo de aplicaciones relacionadas conestos sistemas.

No existe una definicion precisa del grado de complejidad de un sistemacomplejo, pero podemos decir que un sistema es mas complejo mientras maselementos tenga, mas abundantes sean las interacciones entre ellos, y mayor seala diversidad de los elementos y de las interacciones. La dimension del espacio

1

2 CAPITULO 1. INTRODUCCION

Moleculas

Células

Orgánulos

Tejidos

Organos

Organismos

Ecosistemas

SociedadesN

ive

les d

eA

bstr

acció

n

Nivel de Abstracción n+1

Nivel de Abstracción n

Sistemas Complejos

Figura 1.1: Los sistemas complejos como enlaces entre distintos niveles de abs-traccion. Un ejemplo de los sistemas biologicos.

de estados accesibles contribuye de manera significativa a la complejidad de unsistema de este tipo. Es de interes la evolucion de la complejidad de un sistemaen funcion del numero de agentes interactuantes. Para este analisis nuestro pun-to de partida es un sistema compuesto unicamente de un agente. Este elementototalmente aislado no es capaz de producir propiedades emergentes colectivas yaque estas son la consecuencia de las interacciones microscopicas. A este sistemalo podemos clasificar como un sistema simple. A continuacion agregamos demanera progresiva agentes a este sistema, permitiendoles la interaccion. A me-dida que el numero de elementos aumenta, el analisis y la descripcion del sistemase hacen cada vez mas dificultosos. A este fenomeno se le conoce como comple-jidad emergente. Si continuamos agregando agentes, la complejidad no crece demanera ilimitada. Las propiedades colectivas emergentes permiten describir alsistema en cuestion como un todo. Es posible separar mentalmente las cuali-dades de este objeto global emergente de sus constituyentes microscopicos paraconsiderarlo como una nueva e individual entidad de estudio. Nos abstraemosde los componentes interactuantes de este nuevo objeto para razonar acercade sus cualidades que son determinadas por las propiedades colectivas emer-gentes. Esto quiere decir que, en este nuevo nivel de abstraccion, ya no tenemosun numero grande de agentes interactuantes, sino mas bien un solo objeto connuevas propiedades. Esto es el resultado de una simplicidad emergente. Si iden-tificamos este objeto como nuestro agente aislado del inicio, podemos repetirel proceso de agregar sucesivamente objetos similares y permitir su interaccion.Esto dara lugar nuevamente a una complejidad emergente y el ciclo descritose repetira escalando diferentes niveles de abstraccion. Uno de los objetivos dela ciencia es el tratar de cerrar las brechas entre estos distintos niveles de en-capsulamiento de complejidad. Esto quiere decir que los cientıficos pretendenexplicar, basandose en el conocimiento de las interacciones microscopicas de loselementos, de que manera emergen las propiedades macroscopicas de los obje-tos pertenecientes al nivel de abstraccion inmediato superior. Para este fin elestudio de los sistemas complejos es fundamental, ya que estos representan elenlace entre los distintos niveles de abstraccion (ver la figura 1.1 a manera deejemplo ilustrativo).

Uno de los elementos fundamentales en el modelado de sistemas complejos

1.1. ¿QUE SON REDES COMPLEJAS? 3

Red bidireccionalRedRed dirigida

Figura 1.2: Los sistemas complejos permiten modelarse como redes dirigidas oredes bidireccionales.

son las llamadas redes complejas, estructuras abstractas compuestas de nodoso vertices, ası como de conexiones entre estos elementos. Los nodos representanlos agentes interactuantes y las conexiones modelan la topologıa de estas inter-acciones. Estas conexiones pueden ser bidireccionales o dirigidas (figura 1.2).

El modelo matematico de cualquier red, en particular de una red comple-ja, es un grafo. Estas estructuras han sido estudiadas por la teorıa de grafos,una disciplina de la matematica que nace en el ano 1736 con el famoso tra-bajo de Leonhard Euler sobre los puentes de Konigsberg. La teorıa de grafosse aboco en sus inicios primordialmente al estudio de las redes ordenadas. Si-glos mas tarde el interes se centro en redes que, aparentemente, no presentabanningun tipo de regularidad, las llamadas redes aleatorias. En el ano 1950 losmatematicos hungaros Paul Erdos y Alfred Renyi [7] [8] [9] dan a conocer unalgoritmo de construccion de redes aleatorias, en el cual, partiendo de N no-dos desconectados, se procede a la interconexion con probabilidad p de cada

uno de los(

N2

)posibles pares. El objetivo principal del estudio de las redes

aleatorias es el determinar en que momento del proceso de construccion ante-riormente mencionado aparece alguna propiedad en particular, por ejemplo laconexion total de la red, ası como el calcular el comportamiento asintotico de lasprobabilidades relacionadas cuando el numero de Nodos N tiende hacia infinito.Las redes aleatorias han sido estudiadas exhaustivamente (ver por ejemplo libroclasico de B. Bollobas [5] ) y estas dominaron el modelado de las redes en lascuales no se lograba percibir alguna regularidad en sus topologıas.

El advenimiento de la era informatica impulso de manera significativa elavance del estudio de las redes complejas. El mejor acceso a capacidades com-putacionales importantes permitio, a traves de simulaciones, la exploracionnumerica de muchos fenomenos naturales con patrones de interaccion no tri-viales. Los sistemas de almacenamiento masivos contribuyeron a acceder a unacantidad enorme de datos, entre ellos datos acerca de las topologıas de redescomplejas, tales como redes de colaboracion cientıficas, redes de transmisiony distribucion de energıa electrica, entre otros sistemas de interes. A traves


de la caracterizacion geometrica de estas redes se detectaron propiedades quelas diferenciaban de redes aleatorias en la distribucion de su conectividad y enel agrupamiento de sus nodos en “comunidades” o clusters. Estas discrepan-cias motivaron la busqueda de algoritmos de construccion que reprodujeran lascaracterısticas de las redes reales dando lugar a las redes small world y a las lla-madas redes libres de escala con distribucion de conexiones con ley de potencias.Estos modelos han permitido entender mejor el papel que juega la topologıa dela red en la dinamica colectiva de los sistemas complejos [1].

Habiendo sido detallada la topologıa de la red compleja, otro de los elemen-tos necesarios para el modelado de un sistema complejo es la descripcion delproceso de interaccion. Siendo las interacciones de ındole microscopica, es deesperarse que las condiciones que determinan las transiciones de estados de unagente en particular, esten dadas por los estados de sus elementos vecinos y porla topologıa de sus interacciones. Por lo general, la dinamica de interaccion escomplicada y altamente no lineal, de tal forma que pocas veces es posible descri-birla mediante expresiones matematicas. Por otro lado, en el caso de tratarsede una dinamica sencilla, la posible complejidad topologica de las interaccioneshace fracasar una deduccion analıtica de las propiedades emergentes. Es jus-tamente la complejidad emergente, esta propiedad intrınseca de los sistemascomplejos, la que dificulta las descripciones analıticas. Asimismo, la diversidadde tipos de interaccion es inmensa, dificultando tremendamente su clasificacion.Por lo expuesto anteriormente es indispensable utilizar simulaciones numericaspara el estudio de los sistemas complejos. Algorıtmicamente es posible imple-mentar cualquier tipo de interaccion. Las capacidades computacionales de losordenadores modernos permiten implementar modelos con decenas de miles deagentes y la medicion tanto de propiedades geometricas como de propiedadesdinamicas se logran con mucha facilidad. Ademas la capacidad de visualizacionde cantidades inmensas de datos permite una exploracion numerica eficiente eintuitiva. A traves de estos avances tecnologicos ha sido posible progresar demanera importante en el estudio de los sistemas complejos. Los cientıficos cuen-tan gracias a ello con resultados experimentales importantes que esperan serentendidos y descritos en el futuro por una teorıa unificada y general de estossistemas.

La universalidad de los sistemas complejos exige el siguiente cuestionamientofilosofico: ¿Los sistemas complejos describen sistemas reales con los cuales loscientıficos, ingenieros u otros profesionales se topan esporadicamente en la sendade la busqueda del conocimiento o en realidad se trata de un mecanismo mentala traves del cual el intelecto humano encapsula complejidad para poder describirel universo fascinante y altamente complejo que lo circunda? Invitamos al lectora meditar al respecto.

1.2. Procesos de propagacion de informacion

Una amplia clase de sistemas complejos han evolucionado naturalmente ohan sido creados artificialmente con la finalidad principal de transmitir infor-macion. Pensemos en la divulgacion de un rumor o en procesos de intercambiocultural en redes sociales, en la transmision de una conversacion telefonica en

1.2. PROCESOS DE PROPAGACION DE INFORMACION 5

sistemas de telecomunicaciones, en el sistema neurologico de organismos vivoso en las redes de computo. Con el fin de cumplir de manera eficiente y economi-ca con esta funcionalidad, estos sistemas requieren optimizar las velocidadesde transmision ası como desarrollar mecanismos o topologıas que minimicenlos errores ocasionados por canales ruidosos de transmision. Por ejemplo, en elarea de tecnologıas de la informacion, el diseno optimo de redes interconectadasse ha convertido en uno de los problemas fundamentales. La optimizacion delas topologıas, tanto de los sistemas de computo basados en multiprocesadorescomo de los sistemas distribuidos y de telecomunicacion presentan un reto in-teresante para la comunidad ingenieril. Una parte basica de la arquitectura detales sistemas la constituye el mecanismo que permite la comunicacion entre loselementos procesadores y entre estos y los elementos de memoria del sistema.La eficacia y rendimiento del sistema depende, en buena medida, de la eleccionque se haga de dicha red de interconexion. Ademas, el costo economico de lared constituye una parte importante del costo total del sistema, por lo que laoptimizacion del sistema requiere la optimizacion de la red.

En este trabajo nos proponemos estudiar procesos de propagacion de in-formacion en redes complejas dirigidas de diversas geometrıas. El algoritmo deconstruccion de la clase de redes estudiadas, ası como el proceso de interaccionmodelado entre los agentes es descrito en el capıtulo 2. En particular, estamosinteresados en determinar el papel de la geometrıa de la red en la velocidad detransmision y en la difusion de errores ocasionados por canales de transmisionruidosos. Estas propiedades geometricas son estudiadas en el capıtulo 3. Los re-sultados numericos y analıticos de la evolucion en el tiempo del numero de nodosinformados I(t) son el tema principal del capıtulo 5. Finalmente estudiaremosen el capıtulo 6 tanto la influencia de canales ruidosos en la fraccion de nodoserroneamente informados, ası como mecanismos no supervisados de correccionde errores basados en esquemas que aprovechan la estructura de clusters de lared.

Capıtulo 2

Descripcion del modelo

El modelo implementado para el estudio de procesos de propagacion en re-des complejas consta de un escenario de interaccion, representado por un grafodirigido compuesto de nodos y de conexiones entre estos nodos, ası como de ladescripcion de una dinamica especıfica de interaccion que gobierna el fenomenode propagacion en la red. Los nodos representan agentes interactuantes, loscuales pueden encontrarse en distintos estados y las conexiones dirigidas deter-minan la geometrıa de sus relaciones.

2.1. El algoritmo de construccion de las redes

La clase de redes estudiadas en este trabajo se construye mediante un algo-ritmo particular cuyo punto de partida es una red ordenada, dirigida y unidi-mensional de N Nodos con condiciones de contorno periodicas. Cada uno de losvertices cuenta con conexiones dirigidas hacia sus 2k primeros vecinos (ver figu-ra 2.1). Al parametro k lo denominaremos conectividad de la red. Invitamos allector a observar las figuras 2.4 y 2.5 que ilustran esquematicamente estas redesordenadas. La periodicidad de las condiciones de contorno tiene como conse-cuencia que tanto el numero de salidas ZS como el numero de entradas ZE delos N nodos sean iguales a 2k :

ZS = ZE = 2k. (2.1)

Esta red ordenada es transformada mediante un algoritmo de desordenamien-to caracterizado por una probabilidad p, la aleatoriedad de la red. En este pro-ceso todos los nodos son visitados uno por uno y cada uno de los 2k orıgenes desus respectivas entradas son reconectados con probabilidad p a otro nodo elegi-do al azar entre la totalidad de nodos, con excepcion de sı mismo y del nodode origen de la conexion en cuestion (ver figura 2.2). De esta manera el numerode entradas ZE se mantiene constante e igual a 2k y el numero de salidas ZS

adquiere un caracter de variable aleatoria cuya distribucion de probabilidades

7

8 CAPITULO 2. DESCRIPCION DEL MODELO

... ...

k ... 2 1 1 2 ... k

Figura 2.1: Cada uno de los vertices cuenta con conexiones dirigidas hacia sus2k primeros vecinos.

N=10

k=1

Proceso de Desorden

Figura 2.2: Ilustracion esquematica de un paso elemental en el proceso de des-ordenamiento.

2.2. LA DINAMICA DE INTERACCION 9

Red Ordenada

N=20

k=2

Zs=Ze=4

Small World Red Aleatoria

p=0 p=1

Figura 2.3: Interpolacion entre redes ordenadas y redes aleatorias mediantela aleatoriedad de la red p. Para valores intermedios de p la red presentapropiedades small world.

sera estudiada en el marco de la descripcion de las propiedades geometricas dela red en el capıtulo 3.1. A traves de este proceso de desorden se introducenconexiones dirigidas de largo alcance. Es evidente que para p = 0 recobramosla red ordenada inicial y que para p = 1 tenemos el caso de una red aleatoria.Entre estos dos casos lımites, para un rango determinado de la aleatoriedadp, la red adquiere propiedades small world. Esto quiere decir que, a pesar deposeer un alto grado de clustering C, la distancia media L de la red es ordenesde magnitud menor que el tamano del sistema. Estas cantidades se estudiarandetalladamente en el capıtulo 3.

La representacion matematica de una red es un grafo. Un grafo G consistede un conjunto no vacıo de elementos, llamados vertices o nodos, y una lista depares ordenados de estos elementos (en el caso de una red dirigida), llamadosconexiones. Al conjunto de vertices lo denotamos como V (G) y a la lista deconexiones como E(G). Asimismo es posible representar un grafo a traves de lamatriz de adyacencia

M = (ai,j), (2.2)

cuyos elementos ai,j son iguales a 1 si existe una conexion dirigida desde el nodoi hacia el nodo j, o es igual a cero en caso contrario. M es una matriz cuadraticade dimension N , donde N es el numero de vertices. Es evidente que la matrizde adyacencia M de una red no dirigida es simetrica. Esto quiere decir que

M = MT ⇐⇒ ai,j = aj,i (2.3)

donde MT es la matriz transpuesta de M . En el capıtulo 3.2 veremos que estamatriz juega un papel fundamental en el calculo de la distancia media L.

2.2. La dinamica de interaccion

Una vez definida la topologıa de la red es necesario describir la dinamicade interaccion, es decir, precisar el mecanismo microscopico a traves del cual la


Figura 2.4: Red ordenada dirigida unidimensional de N = 20, k = 2 con condi-ciones de contorno periodicas

informacion se propaga en la red. Para esto especificamos dos posibles estados,en los cuales se pueden encontrar los agentes ubicados en los N nodos de la red:informados o no informados. Al inicio de la dinamica se encuentran todos noinformados con excepcion de uno, quien sera el desencadenante de la propagacionhacia toda la red. En cada unidad de tiempo todos los nodos informados eligenuna de sus salidas al azar e intentan informar al vecino correspondiente. Si elvecino se encuentra en el estado no informado su estado cambia a informado. Siel vecino se encuentra en el estado informado su estado se mantiene invarianteante esta interaccion. El proceso finaliza cuando los N nodos alcanzan el estadode informados, es decir que la informacion ha sido transmitida a toda la red.Nos interesa la evolucion en el tiempo del numero de nodos informados I(t).Es evidente que I(t) es un proceso estocastico, ya que tanto en el proceso deconstruccion de las redes, como en la dinamica de interaccion, los elementosprobabilısticos son predominantes. Las propiedades dinamicas del proceso depropagacion seran estudiadas en el capıtulo 5.

2.2. LA DINAMICA DE INTERACCION 11

Figura 2.5: Red ordenada dirigida unidimensional de N = 20, k = 3 con condi-ciones de contorno periodicas

Capıtulo 3

Propiedades geometricas dela red

Toda red compleja presenta caracterısticas topologicas particulares que des-criben la geometrıa de las interacciones y que influencian de manera importantelos procesos dinamicos que se desarrollan en ellas. Es por eso que el analisis, laclasificacion y la sıntesis de redes complejas se basa en magnitudes medibles ca-paces de expresar las propiedades geometricas mas relevantes. Dependiendo deltipo de red y de los procesos dinamicos que se quieren estudiar es fundamentalhacer una cuidadosa seleccion de estas magnitudes. Un resumen interesante demagnitudes geometricas se encuentra en [6].

En este trabajo se seleccionaron el numero de salidas ZS , la distancia mediaL y el grado de clustering C para describir la topologıa de las redes estudiadas.Estas propiedades geometricas influyen de manera significativa, tanto en losprocesos de propagacion de informacion como en los mecanismos de detecciony correccion de errores que fueron simulados sobre redes small world dirigidas.El algoritmo de construccion de estas redes ha sido descrito en el capıtulo 2. Acontinuacion presentamos resultados numericos, ası como algunos derivacionesanalıticas de estas magnitudes geometricas.

3.1. El numero de salidas ZS

La distribucion de probabilidades del numero de salidas ZS es una cantidadcrucial, ya que sin el conocimiento de ella no es posible derivar propiedadesdinamicas [4]. Del procedimiento de reconexion aleatoria de la red ordenadainicial se deduce que ZS esta determinada por las conexiones originales nd quesobrevivieron a este proceso de desorden y por aquellas conexiones adicionalesng ganadas en el:

ZS = nd + ng. (3.1)

De ZE = 2k se verifica que el valor medio del numero de salidas 〈ZS〉 = 2k (“to-da entrada es al mismo tiempo una salida”). La variable aleatoria nd esta regida

13

14 CAPITULO 3. PROPIEDADES GEOMETRICAS DE LA RED

Figura 3.1: Solucion analıtica (ecuacion 3.4) de la distribucion del numero desalidas ZS para distintos valores de la conectividad k. La aleatoriedad de la redes fija, p = 1.

por una densidad de probabilidades binomial:

Pnd(nd = j) =

(2kj

)(1− p)j

p2k−j j ∈ [0, 2k] (3.2)

cuyo valor medio es 〈nd〉 = 2k(1− p). Para la variable aleatoria ng proponemosuna densidad de probabilidades de Poisson Png (ng = j) = (λ)j

j ! exp(−λ), j ∈ N0,valida cuando k ¿ N y determinamos el parametro λ = 2kp de la condicion〈ZS〉 = 2k, resultando finalmente

Png (ng = j) =(2kp)j

j !exp(−2kp) j ∈ N0 (3.3)

Debido a que ZS = nd + ng, a la distribucion PZS (ZS = c) la obtenemos de laconvolucion de Pnd

(nd = j) y Png (ng = j):

PZS(ZS = c) =

min(c,2k)∑

j=0

(2kj

)(1− p)j

p2k−j (2kp)(c−j)

(c− j) !exp(−2kp) c ∈ N0.

(3.4)La varianza de esta distribucion aumenta para incrementos de la aleatoriedadde la red p (ver Figura 3.2). La solucion analıtica coincide satisfactoriamentecon los resultados numericos, como se puede apreciar en la figura 3.3 .

3.1. EL NUMERO DE SALIDAS ZS 15

Figura 3.2: Solucion analıtica (ecuacion 3.4) de la distribucion del numero desalidas ZS para distintos valores de la aleatoriedad de la red p. La conectividadde la red es fija, k = 5.

Figura 3.3: Resultados numericos y solucion analıtica de la distribucion delnumero de salidas ZS .


3.2. La distancia media L

Por lo general dos nodos de una red compleja no son adyacentes. De hechola mayorıa de las redes de interes son diluidas. Esto quiere decir que, en una

red de N nodos, solo una fraccion pequena de las posibles(

N2

)= N(N−1)

2

conexiones estan presentes. En el caso de las redes no dirigidas la distanciad(i, j) entre los nodos i y j se define como el recorrido mas corto que los conectay la distancia media de la red L es el promedio de d(i, j) sobre todos los posiblespares de nodos:

L =1

N(N − 1)

∑

j 6=i

d(i, j). (3.5)

Una de las condiciones que tiene que reunir una distancia, en el sentidomatematico estricto, es la propiedad de simetrıa, esto quiere decir :

d(i, j) = d(j, i), (3.6)

propiedad que no se cumple en el caso de una red dirigida. En ese sentido,siendo la distancia media L una magnitud que utilizamos para caracterizaruna propiedad global de la red, se justifica transformar nuestra red dirigidaen una red no dirigida, antes de calcular la distancia media segun 3.5. Estatransformacion la realizamos simetrizando la matriz de adyacencia M = (ai,j) dela red en cuestion. Otro de los inconvenientes de esta definicion es la divergenciade la distancia media L en el caso de una red desconexa, es decir cuando noexiste algun recorrido que conecte un par de nodos especıficos. Este caso no esde nuestro interes, por lo que realizaciones que den como resultado redes de estetipo, son descartadas. La dificultad principal del calculo de la distancia mediaL utilizando la ecuacion 3.5 reside en la busqueda del camino mas corto entredos nodos i y j. Se puede demostrar [10] que la n-esima potencia de la matrizde adyacencia contiene esta valiosa informacion:

Mn = (ai,j) . (3.7)

El elemento ai,j representa el numero de caminos de longitud n que conectan elnodo i con el nodo j. La ecuacion 3.7 es muy elegante, pero al mismo tiempomuy costosa desde el punto de vista computacional. El calculo de Mn requierede nN3 multiplicaciones, ası como de nN2 operaciones de suma. Si contempla-mos que el numero de nodos N representa el numero de agentes interactuantesde un sistema complejo y que una de las propiedades fundamentales de estees que justamente aquel numero es grande, llegamos a la conclusion que estaexplosion polinomica de la cantidad de operaciones aritmeticas es una limitacionimportante de este algoritmo de busqueda. Esta situacion se agrava aun mascuando recordamos el caracter probabilıstico del metodo de construccion delas redes contempladas, que nos obliga a realizar una cantidad importante derealizaciones con el fin de poseer informacion estadısticamente representativa.Por lo anteriormente expuesto nos vimos en la obligacion de utilizar redes desolo 100 nodos para el calculo de la distancia media L, con el fin de explorar la

3.2. LA DISTANCIA MEDIA L 17

Figura 3.4: Valor absoluto de la distancia media L en funcion de la aleatoriedadde la red p para distintos valores de la conectividad k (Numero de Nodos N =100, 1000 realizaciones).

relacion de esta magnitud con los parametros k y p. Los resultados numericos sepresentan en las figuras 3.4 y 3.5. El proceso de desorden de la red introduce unaserie de conexiones que hacen las veces de atajos en la red, de tal manera que ladistancia media se reduce de manera importante a medida que la aleatoriedad dela red p aumenta. Por otro lado esta caıda se encuentra fuertemente influenciadapor la conectividad k.

Las redes small world dirigidas, despues que sus respectivas matrices deadyacencia M han sido simetrizadas , coinciden con las redes small world pro-puestas en el ano 1998 por Watts y Strogatz [13] [12] [14] . Se puede demostrarque la distancia media L de las redes ordenadas, es decir para p = 0, dependede la siguiente manera de los parametros k y N :

Lordenada(p = 0) ∝ N

4k. (3.8)

Para las redes aleatorias, es decir para p = 1, la expresion correspondiente es

Laleatoria(p = 1) ∝ ln N

ln 2k. (3.9)

Ambas expresiones 3.8 y 3.9 son validas en el regimen

N À k À ln N À 1. (3.10)


Figura 3.5: Valor relativo de la distancia L(p)L(0) en funcion de la aleatoriedad de

la red p para distintos valores de la conectividad k (Numero de Nodos N = 100,1000 realizaciones).

Este regimen describe redes con un numero grande de nodos N y altamentediluidas en lo que concierne a la fraccion presente de posibles conexiones. Lacondicion k À ln N asegura, en el caso de las redes aleatorias, que el grafo seaconexo. Esto significa que la distancia media L nunca diverge hacia infinito.

Siendo el proceso de construccion de las redes dominado por elementos pro-babilısticos, la distancia media L es una variable aleatoria con una distribucionde probabilidades asociada. Los histogramas respectivos, resultados de las si-mulaciones numericas, presentan distribuciones no triviales. En las figuras 3.7y 3.8 se puede apreciar la influencia de la aleatoriedad p en la dispersion de ladistribucion de L para una eleccion particular de N y k.

3.3. EL GRADO DE CLUSTERING C 19

Figura 3.6: La distancia media L es una variable aleatoria. Valor medio y dis-persion de L en funcion de la aleatoriedad p para N = 100, k = 3 y 10000realizaciones.

3.3. El grado de clustering C

Mientras que la distancia media L es una caracterizacion global de la red, elgrado de clustering C es una magnitud que describe una propiedad local. Estase encuentra inspirada en redes sociales y describe la estructura promedio del“vecindario” de cada vertice. En las redes sociales, en lo referente por ejemploa las amistades, se da el caso que si el individuo A es amigo de los individuos By D, entonces existe una probabilidad grande que por su lado B y D tambiencuenten con lazos de amistad que los unan (figura 3.9). La cantidad de relacionestriangulares de este tipo en una red son las que definen C. Una clase importantede propiedades emergentes de sistemas complejos particulares estan fuertementeinfluenciadas por el grado de clustering C, por ejemplo aquellas que caracterizanrobustez a influencias externas. En el capıtulo 6 veremos que esta propiedadgeometrica cumple un papel fundamental en la deteccion y correccion de erroresen procesos de propagacion de informacion a traves de canales ruidosos.

Se pueden encontrar en la literatura varias definiciones de grado de clus-tering para redes no dirigidas [6]. En este trabajo utilizamos una basada en elconteo de las relaciones triangulares. Antes de abocarnos a la explicacion de ellarecordemos que las redes small world contempladas en este trabajo son dirigi-das. Es por eso que es necesario simetrizar la matriz de adyacencia M antes deaplicar esta definicion. 1

1En el capıtulo 6 veremos que, a pesar de no ser estrictamente aplicable a nuestras redes


Figura 3.7: Distribucion de probabilidades P ( L(p) = j ) de la distancia mediaL en funcion de la aleatoriedad p para N = 100, k = 3 y 10000 realizaciones.Notese la influencia de p en la dispersion de la distribucion. (Continua en lafigura 3.8)


Figura 3.8: Distribucion de probabilidades P ( L(p) = j ) de la distancia mediaL en funcion de la aleatoriedad p para N = 100, k = 3 y 10000 realizaciones.Notese la influencia de p en la dispersion de la distribucion. (Viene de la figura3.7)


A

B D

Figura 3.9: Si el individuo A es amigo de los individuos B y D, entonces existeuna probabilidad grande que por su lado B y D tambien sean amigos.

Calculemos el grado de clustering Ci del nodo i. Para esto definimos elconjunto de vertices V (i) = {v1, v2, . . . , vj} que contiene los j vecinos del no-do i. Asimismo precisamos la magnitud KV (i) como el numero de conexionespresentes entre los nodos vecinos de i. Este numero representa el numero detriangulos que conectan el nodo i con dos de sus vecinos (figura 3.10). El numero

maximo de posibles triangulos de este tipo es el combinatorio(

j2

)= j(j−1)

2 .

Si relacionamos esto con el numero de triangulos presentes llegamos finalmenteal grado de clustering Ci del nodo i:

Ci =2 KV (i)j(j − 1)

(3.11)

El grado de clustering C de la red es el valor medio de los Ci promediados sobrelos N nodos:

C =1N

N∑

i=1

Ci , C ∈ [0, 1]. (3.12)

Los resultados numericos del calculo del grado de clustering C se presentanen las figuras 3.11 y 3.12. Las redes ordenadas (p = 0) son altamente clusteri-zadas, mientras que las redes aleatorias p = 1) no lo son.

Como vimos en la seccion 3.2 las redes small world dirigidas, despues quesus respectivas matrices de adyacencia M han sido simetrizadas, coinciden conlas redes small world propuestas por Watts y Strogatz [14]. Se puede demostrarque el grado de clustering C de las redes ordenadas, es decir para p = 0, esconstante:

Cordenada(p = 0) ∝ 34. (3.13)

small world dirigidas, el grado de clustering C basado en el conteo de las relaciones triangularescaracteriza de manera correcta la robusteza de las redes al ruido de los canales de transmision.


i

V1

V2

V3

Vj

V4

...

Figura 3.10: El grado de clustering C se basa en el conteo de las relacionestriangulares.

Figura 3.11: El valor medio del grado de clustering C en funcion de la aleato-riedad de la red p para distintos valores de la conectividad k (N = 100, 5000realizaciones).


Figura 3.12: El valor medio del grado de clustering relativo C(p)C(0) en funcion de

la aleatoriedad de la red p para distintos valores de la conectividad k (N = 100,5000 realizaciones).

Para las redes aleatorias, es decir para p = 1, la dependencia funcional de C conN y k es:

Caleatoria(p = 1) ∝ 2k

ln N. (3.14)

Ambas expresiones 3.13 y 3.14 son validas en el regimen

N À k À ln N À 1. (3.15)

descrito en la seccion 3.2.

Capıtulo 4

Clasificacion de las redes

En esta seccion nos proponemos clasificar las redes que resultan del algo-ritmo de construccion descrito en el capıtulo 2 en funcion de los parametrosgeometricos distancia media L y grado de clustering C.

4.1. La red totalmente conectada

Veamos el caso lımite de una red totalmente conectada (figura 4.1), es de-cir una red donde la totalidad de las posibles conexiones entre los N nodosse encuentran presentes (“todos conectados con todos”). Esta red se describemediante la siguiente expresion:

ktc =N

2, (Npar). (4.1)

Es evidente que en este caso la aleatoriedad de la red p no tiene ningun efectoen el algoritmo de construccion. Si nos imaginamos que la presencia de unaconexion entre nodos requiere de cierta energıa o costo, entonces concluimos quelas redes totalmente conectadas son en ese sentido del todo derrochadoras. Elnumero total de conexiones en estas redes crece como el cuadrado del numero denodos N . Es por eso que esta topologıa es poco frecuente en sistemas naturales yartificiales. A pesar de estos argumentos, las redes totalmente conectadas son deutilidad como medio de validacion del correcto funcionamiento de los algoritmoscomputacionales implementados en este trabajo debido al tratamiento analıticosencillo que permiten. Asimismo veremos que juegan un papel fundamental enla descripcion fenomenologica de los procesos de propagacion de informacionque seran estudiados en el capıtulo 5. Las redes totalmente conectadas tienen ladistancia media mınima posible Ltc = 1 y el grado de clustering maximo posibleCtc = 1.

25

26 CAPITULO 4. CLASIFICACION DE LAS REDES

Figura 4.1: La red totalmente conectada (N = 20).

4.2. La red small world dirigida

Las expresiones analıticas 3.8, 3.9, 3.13 y 3.14 de las distancias media L yde los grados de clustering C de las redes ordenadas y aleatorias nos permitenafirmar que las redes ordenadas son escenarios con distancias medias grandes yaltamente clusterizados, mientras que las redes aleatorias son escenarios con dis-tancias medias pequenas con un grado de clustering reducido. La aleatoriedadp nos permite interpolar entre estos casos lımites. Nos interesa encontrar unregimen intermedio, es decir una red con distancia media pequena y al mismotiempo altamente clusterizada. Invitamos al lector a observar la figura 4.2 en lacual graficamos la distancia media relativa L(p)

L(0) y el grado de clustering relativoC(p)C(0) en funcion de la aleatoriedad p para una eleccion particular de N y k.Ambas magnitudes decaen fuertemente en funcion de valores crecientes de p,pero a distintos ritmos, dando la posibilidad de la existencia del regimen inter-medio buscado. Este regimen es el correspondiente a las redes small world. Latransicion de las redes ordenadas a las redes aleatorias es suave, de tal maneraque no tiene sentido definir una expresion matematica para el intervalo de pque describa el regimen small world. Sin embargo podrıamos precisar un indicarsencillo que nos permita visualizar de manera cualitativa esta transicion:

κ =C(p)C(0)

− L(p)L(0)

(4.2)

y afirmar que la red small world mas representativa es aquella que maximizaκ en funcion de p (ver figura 4.3). Si graficamos este indicador para distintosvalores de k, podemos apreciar que los valores de psmallworld se encuentran muy

4.2. LA RED SMALL WORLD DIRIGIDA 27

Figura 4.2: La distancia media relativa L(p)L(0) y el grado de clustering relativo

C(p)C(0) en funcion de la aleatoriedad p (N = 1000, k = 5).

cercanos (ver figuras 4.4 y 4.5).

Las propiedades dinamicas del proceso de propagacion de informacion seranpresentadas en el capıtulo 5. Aquel capıtulo se encuentra organizado de acuerdoa los distintos tipos de redes resultantes de la presente clasificacion. A conti-nuacion enumeramos los distintos tipos:

1. Red totalmente conectada

2. Red ordenada

3. Red aleatoria

4. Red small world dirigida


Figura 4.3: El indicar κ nos permite seleccionar de manera cualitativa la redsmall world mas reprentativa. (N = 1000, k = 5, psmallworld ≈ 10−2).

Figura 4.4: Indicador κ(p) en funcion de la aleatoriedad p para distintos valoresde k. El intervalo de psmallworld es pequeno (N = 100).


Figura 4.5: Indicador κ(p) en funcion de la aleatoriedad p para distintos valoresde k. El intervalo de psmallworld es pequeno (N = 1000).

Capıtulo 5

Propiedades dinamicas

Es de esperarse que las propiedades dinamicas de los procesos de propa-gacion de informacion dependan fuertemente de la topologıa del escenario deinteraccion. En nuestro modelo el escenario de interaccion es representado poruna clase de redes que son construidas mediante un algoritmo particular des-crito en el capıtulo 2 y cuyas propiedades geometricas fueron presentadas en elcapıtulo 3. Estas propiedades geometricas nos permitieron clasificar esta clasede redes en 4 tipos: red totalmente conectada, red ordenada, red aleatoria yred small world dirigida. El presente capıtulo inicia con una exposicion gene-ral acerca de la caracterizacion de las propiedades dinamicas de los procesosde propagacion de informacion en esta clase de redes. Luego se presentan losresultados numericos y analıticos organizados de acuerdo a los tipos de redesmencionados anteriormente.

5.1. Generalidades

Tanto en el algoritmo de construccion de las redes (seccion 2.1) como en ladinamica de interaccion modelada (seccion 2.2), los elementos probabilısticosson predominantes. Es de nuestro interes describir la evolucion temporal delnumero de nodos informados I(t). Es evidente que I(t) es un proceso estocastico,ya que cada realizacion γ de nuestro experimento numerico da como resultadouna funcion Iγ(t) (figura 5.1). Asimismo, para cada valor fijo t0 del tiempo,I(t0) es una variable aleatoria con una distribucion de probabilidades asociada(figura 5.2). Estas distribuciones no seran analizadas. Nos enfocaremos en elvalor medio del numero de nodos informados para cada tiempo t. Este promediola denotaremos de manera abreviada como I(t).

A continuacion derivamos una ecuacion diferencial para I(t). Para esto defi-nimos Π(s) como la probabilidad de que un nodo sea informado en el paso desimulacion s. Es decir

P{I(s + 1) = I(s) + 1} = Π(s) (5.1)P{I(s + 1) = I(s)} = 1−Π(s). (5.2)

31

32 CAPITULO 5. PROPIEDADES DINAMICAS

Figura 5.1: El numero de nodos informados en funcion del tiempo I(t) es unproceso estocastico. (3 realizaciones para N = 1000, k = 5 y p = 10−2).

Figura 5.2: Para cada valor fijo t0 del tiempo, I(t0) es una variable aleatoriacon una distribucion de probabilidades asociada.

5.2. LA RED TOTALMENTE CONECTADA 33

El valor medio I(s + 1) es entonces

I(s + 1) = (I(s) + 1) Π(s) + I(s)(1−Π(s))= I(s) + Π(s). (5.3)

Agrupamos terminos de la ecuacion 5.3, la dividimos entre ∆t(s) e identificamosI(s + 1)− I(s) como ∆I(s)

I(s + 1)− I(s) = Π(s)I(s + 1)− I(s)

∆t(s)=

Π(s)∆t(s)

∆I(s)∆t(s)

=Π(s)∆t(s)

(5.4)

Si recordamos que todos los nodos informados intentan de manera simultaneainformar a sus vecinos derivamos que

∆t(s) =1

I(s). (5.5)

De las ecuaciones 5.4 y 5.5 resulta

∆I(s)∆t(s)

= Π(s) I(s) (5.6)

y haciendo tender ∆t hacia cero obtenemos la ecuacion diferencial que buscabamos:

dI

dt= Π(I) I, (5.7)

en la cual denotamos de manera explıcita la dependencia de la probabilidad deinformar Π del numero de nodos informados I.

5.2. La red totalmente conectada

Como mencionamos anteriormente, la red totalmente conectada es una es-tructura poco frecuente en sistemas naturales y artificiales. Esto se debe algran numero de conexiones presentes que, si son asociadas con una energıa deconexion o un costo, las hacen del todo anti economicas. Nuestro interes en elestudio de este tipo de redes se encontro inicialmente motivado en la validacionde nuestros algoritmos de simulacion, ya que permiten un tratamiento analıticocerrado. Como veremos en la seccion 5.4, estas expresiones analıticas sirvieronposteriormente como base de la descripcion fenomenologica de las propiedadesdinamicas de las redes aleatorias. Recordemos que la distancia media Ltc de lared totalmente conectada es igual a 1; es por eso que la informacion se propagaa la maxima velocidad posible. En ese sentido estas redes son las “mas veloces”.

Nos interesa calcular la probabilidad de informar Πtc(I) de la red totalmenteconectada. Para esto invitamos al lector a observar la figura 5.3. De acuerdo a la


dinamica de interaccion, el primer paso consiste en elegir un nodo al azar (conprobabilidad uniforme) del conjunto de nodos informados. La probabilidad deque el nodo informado j haya sido elegido para informar es

P{nodo j es elegido} =1I. (5.8)

El segundo paso es seleccionar, tambien con probabilidad uniforme, una de lassalidas del nodo j. La probabilidad de que la salida seleccionada apunte haciaun nodo no informado es

P{salida seleccionada apunte hacia nodo no informado} =N − I

N − 1. (5.9)

Es decir que la probabilidad que el nodo j informe es

Pj = {nodo j informe} =1I

N − I

N − 1. (5.10)

De la simetrıa de la red deducimos que cualquiera de los I nodos informadosposeen la misma probabilidad de lograr informar, entonces

Πtc(I) =I∑

j=1

Pj =I∑

j=1

1I

N − I

N − 1=

N − I

N − 1. (5.11)

La ecuacion 5.11 se simplifica levemente si consideramos que N À 1

Πtc(I) ≈ N − I

N(5.12)

Insertamos la expresion derivada para Πtc(I) en la ecuacion 5.7 para en-contrar finalmente la ecuacion diferencial que describe la dinamica de la redtotalmente conectada

dItc

dt= Πtc(Itc) Itc

=1N

Itc (N − Itc) . (5.13)

Esta ecuacion es la conocida ecuacion logıstica. Si graficamos esta ecuacion difer-encial en el espacio de las fases (figura 5.4) se puede apreciar que este sistemadinamico poses dos puntos fijos, uno inestable para IPF1 = 0 y otro estable paraIPF2 = N .

La ecuacion 5.13 se puede resolver utilizando el metodo de separacion devariables. El resultado es:

Itc(t) =NItc(0) exp (t)

Itc(0) exp (t) + N − Itc(0). (5.14)

5.2. LA RED TOTALMENTE CONECTADA 35

Nodos informados

Nodos no informados

NI

Nodos en total

Nodos informados

...

1

2

3

4

I - 1

...

1

2

3

4

N - I

j

Figura 5.3: Ilustracion de ayuda para la derivacion analıtica de la probabilidadde informar Πtc(I) de la red totalmente conectada.

N0 N/2

N/4

dI/dt

I

Figura 5.4: La ecuacion diferencial que describe la dinamica de la red totalmenteconectada graficada en el espacio de las fases. Se pueden apreciar dos puntosfijos, uno inestable para I = 0 y otro estable para I = N .


Figura 5.5: Simulacion numerica y solucion analıtica de Itc(t). Se grafican dossoluciones analıticas para Itc(0) = 1 y Itc(0) = 0,5 respectivamente de acuerdoa la expresion de la ecuacion 5.14.

En la figura 5.5 se comparan la simulacion numerica con soluciones analıticas(ecuacion 5.14 ) para dos condiciones iniciales distintas. La solucion numericano coincide con la solucion analıtica para Itc(0) = 1. Esto se debe a que al iniciodel proceso de propagacion de informacion ∆I es del orden de 1, hecho quese encuentra en desacuerdo con nuestra derivacion de la ecuacion 5.7 en la queidentificamos ∆I

∆t con el diferencial dIdt . Por otro lado si ajustamos las condiciones

iniciales a Itc(0) = 0,5 la simulacion numerica coincide satisfactoriamente conla solucion analıtica descrita por la ecuacion 5.14. Estas discrepancias se debena la distorsion originada por describir una simulacion con variables discretasmediante una ecuacion diferencial, que es una descripcion en el continuo de lasvariables I y t.

5.3. La red ordenada

El punto de partida del algoritmo de construccion es una red ordenada.Cuando la aleatoriedad de la red p = 0, el proceso de desordenamiento notiene efecto alguno en la topologıa, de tal manera que el tipo de red resultantesigue siendo una red ordenada. Las soluciones numericas de I(t) de estas redes,presentadas en las figuras 5.6 y 5.7, evidencian la existencia de dos regımenesdinamicos distintos. Uno esencialmente lineal, valido para k ¿ N , y otro de tipo“logıstico” cuando la conectividad k es del orden del numero de nodos N y quetiene como caso lımite la red totalmente conectada estudiada en la seccion 5.2.

5.3. LA RED ORDENADA 37

Figura 5.6: I(t) de redes ordenadas para distintos valores de la conectividad k(k ¿ N).

Se observan excepciones en la linealidad para valores iniciales de t y al finalizarel proceso cuando I(t) satura el valor N . Estas excepciones se pueden atribuirrespectivamente al proceso inicial de la formacion de los frentes de ondas y a lacolision de estos frentes cuando la informacion alcanza toda la red.

Nos interesa derivar una expresion analıtica que describa el regimen lineal,el cual puede ser explicado como la propagacion de dos ondas informativas,las cuales avanzan en direcciones opuestas y a velocidades constantes vf . Lanaturaleza de este fenomeno nos lleva a un tratamiento analıtico en forma deuna ecuacion integro diferencial. Estamos interesados en la dependencia de vf

de k, ası como en el perfil espacial del frente de onda. Proponemos la siguienteecuacion para la densidad lineal de sitios informados n(x, t):

∂n(x, t)∂t

= fe(1− n(x, t))12k

x+k∫

x−k

n(x′, t) dx′ (5.15)

con condiciones de contorno:

lımx→∞

n(x, t) = 0 (5.16)

lımx→−∞

n(x, t) = 1. (5.17)

Con la ecuacion integro diferencial 5.15 postulamos que la velocidad de propa-gacion de la densidad de nodos informados ∂n(x,t)

∂t en el punto del espacio xesta determinada por un producto de dos factores. El primer factor es propor-cional a la densidad de nodos no informados en ese punto del espacio x y el


Figura 5.7: I(t) de redes ordenadas para distintos valores de la conectividad k.(k ≈ O[N ])

segundo es proporcional a la densidad de nodos informados que pueden alcan-zar a traves de sus conexiones el punto del espacio en cuestion. La frecuencia fe

es aquella con la cual los agentes informados intentan transmitir.

La transformacion ξ = x− vf t nos lleva a las siguientes ecuaciones:

∂n(ξ)∂ξ

=fe

vf(n(ξ)− 1)

12k

ξ+k∫

ξ−k

n(ξ′)dξ′ (5.18)

lımξ→∞

n(ξ) = 0 (5.19)

lımξ→−∞

n(ξ) = 1 (5.20)

que describen el perfil espacial del frente de onda n(ξ). Las soluciones numericasde esta ecuacion se presentan en la figura 5.8. El ancho del frente es aproximada-mente igual a 4k. La velocidad del frente vf en funcion de k y de fe se describemediante la siguiente ecuacion:

vf = c k fe (5.21)c = 0,565029 . . . (5.22)

La constante c es adimensional. Las velocidades vf medidas en las simula-ciones numericas del proceso de propagacion de informacion en las redes orde-nadas coinciden en una buena aproximacion con la ecuacion 5.21 (ver figura5.9).

5.3. LA RED ORDENADA 39

−20 −15 −10 −5 0 5 10 15 20

0

0.5

1

ξ

n(ξ)

k=1k=2k=3k=4k=5k=6k=7k=8k=9k=10

k

k

Figura 5.8: El perfil espacial n(ξ) de la onda informativa en funcion de la conec-tividad k cuando se propaga en redes ordenadas en el regimen lineal (k ¿ N).

0 1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8

9

10

k

vf

fe = 1: ecuación integro diferencial

fe = 2: ecuación integro diferencial

fe = 1: Mediciones de v

f en simulaciones

vf (k) = k f

e c

c = 0.565029...

N = 1000 nodos realizaciones = 1000

Figura 5.9: Velocidad de propagacion vf del frente de onda informativa en fun-cion de k y fe. Comparacion entre resultados numericos de la solucion analıticade la ecuacion integro diferencial y mediciones de vf en las simulaciones depropagacion de informacion en redes ordenadas (N = 1000, p = 0, 1000 realiza-ciones).


5.4. La red aleatoria

El proceso de desorden, descrito por el parametro p, introduce atajos enla red ordenada inicial. Estos atajos reducen la distancia media L de la redtal como se vio en la seccion 3.2. De esto se puede deducir que los procesosde propagacion de informacion deberıan culminar en un tiempo menor cuandoocurren en escenarios de interaccion con topologıas correspondientes a redesaleatorias. Invitamos al lector a observar las figuras 5.10 y 5.11, en las cuales semuestran los resultados numericos de las simulaciones. Las curvas de I(t) paradistintos valores de k ¿ N y para valores de la aleatoriedad p > psmallworld

muestran cualitativamente evoluciones temporales de tipo “logıstico”. Esto nosconduce a una descripcion fenomenologica de este regimen mediante la siguienteecuacion, derivada de las propiedades dinamicas de la red totalmente conectada:

Iτ (t) =NIτ (0) exp ( t

τ )Iτ (0) exp ( t

τ ) + N − Iτ (0). (5.23)

El parametro τ es un tiempo caracterıstico que describe satisfactoriamente laevolucion temporal del proceso de propagacion de informacion en redes aleato-rias. Para demostrar esto realizamos el fiteo de las curvas resultantes de lassimulaciones numericas utilizando la ecuacion 5.23 y calculamos el tiempo ca-racterıstico τ que mejor las describa. La calidad de este fiteo fue medida conel indicador Rsquare. 1 Los resultados se presentan en la figura 5.13. Paraτ = 1 se recupera el caso de la red totalmente conectada. Todos los valoresde Rsquare ≈ 0,99. Esta descripcion fenomenologica va perdiendo calidad con-forme p va disminuyendo en direccion de psmallworld (ver figura 5.12).

1Si definimos y como el vector de datos con n componentes y y como el vector resultantedel proceso de fiteo, entonces el indicador Rsquare queda precisado a traves de las siguientescantidades:

SSE =

n∑i=1

(yi − yi)2 (5.24)

SST =

n∑i=1

(yi − y)2 (5.25)

Rsquare = 1− SSE

SST(5.26)

5.4. LA RED ALEATORIA 41

Figura 5.10: La evolucion temporal del numero de nodos informados I(t) paradistintos valores de la conectividad k y p = 1 (N = 1000, 1000 realizaciones).

Figura 5.11: La evolucion temporal del numero de nodos informados I(t) paradistintos valores de p > psmallworld y k = 5 (N = 1000, 1000 realizaciones).


Figura 5.12: La calidad de la descripcion fenomenologica va disminuyendo con-forme p decrece en direccion de psmallworld.

Figura 5.13: El tiempo caracterıstico τ(p) en funcion de la aleatoriedad p paradistintos valores de la conectividad k (N = 1000, 1000 realizaciones).


Figura 5.14: La red small world dirigida no permite ser descripta fenomenologi-camente por la ecuacion 5.23.

5.5. La red small world dirigida

Las propiedades dinamicas de la red small world dirigida no permiten serdescriptas por la ecuacion 5.23. Invitamos al lector a observar la figura 5.14 enla cual se compara un caso particular de una red de este tipo con el correspon-diente fiteo mediante la ecuacion 5.23. La red small world dirigida es mas velozal inicio de la evolucion temporal, pero es alcanzada por la correspondiente redaleatoria. Las dos redes concluyen el proceso de propagacion aproximadamenteal mismo tiempo. Esta evidencia permite utilizar el tiempo caracterıstico τ co-mo un indicador global acerca de la velocidad de propagacion en redes smallworld dirigidas. Esto quiere decir que τ no describe detalladamente la evoluciontemporal del numero de nodos informados I(t) pero sı es un indicador adecuadopara caracterizar la velocidad “promedio” del proceso. Dicho esto nos permiti-mos extender el grafico de la figura 5.13 hasta valores de p en el corazon delintervalo small world (ver figura 5.15).


Figura 5.15: El tiempo caracterıstico τ(p) en funcion de la aleatoriedad p paradistintos valores de la conectividad k (N = 1000, 1000 realizaciones).

Capıtulo 6

Mecanismos de deteccion ycorreccion de errores

Por lo general los canales de transmision de informacion no son perfectos.Podemos pensar en el ruido electromagnetico siempre presente en canales detransmision de sistemas artificiales de comunicacion como, por ejemplo, la redtelefonica, ası como en la mala interpretacion de una de las partes en unaconversacion verbal, ocasionada por una manera incorrecta de expresarse delcorrespondiente interlocutor. Estos son solo dos ejemplos dentro de una ampliagama de situaciones, en las cuales se comprueba que los canales de transmisionestan sujetos a ruido. En este capıtulo nos proponemos estudiar la influencia decanales ruidosos en la fraccion de nodos erroneamente informados, ası como enun mecanismo no supervisado de deteccion y correccion de errores basado enun esquema que aprovecha el grado de clustering C de las redes estudiadas eneste trabajo.

6.1. Canales ruidosos

Para poder estudiar la influencia que tiene el ruido en el proceso de propa-gacion de informacion se implemento un modelo sencillo basado en una proba-bilidad pE , la cual definimos como la probabilidad de que un nodo transmita demanera erronea. Para esto es necesario ampliar el espacio de estados posibles delos agentes interactuantes. Los estados posibles son tres: no informado, infor-mado correctamente e informado incorrectamente. La dinamica de interaccion,que modela la propagacion de informacion es la misma explicada en la seccion2.2 con la excepcion de que con probabilidad pE el nodo receptor de informa-cion es informado de manera incorrecta. A su vez, este nodo mal informado, seconvierte en una fuente de “desinformacion”. Es decir que el nodo en cuestionno es consciente de que se encuentra mal informado e intenta transmitir la in-formacion incorrecta que posee a sus nodos vecinos. Una vez que todos los Nnodos fueron informados, correcta o incorrectamente, al menos una vez, el pro-ceso concluye. Nos interesa la fraccion i− de nodos desinformados al culminar

45

46CAPITULO 6. MECANISMOS DE DETECCION Y CORRECCION DE ERRORES

Figura 6.1: La fraccion de nodos desinformados i− en funcion de la probabilidadde informar erroneamente pE para distintos valores de la aleatoriedad de la redp, (N = 1000, k = 5, 2500 realizaciones).

la propagacion de informacion. En las figuras 6.1 y 6.2 se presentan algunosresultados numericos. Es evidente que cuando pE = 1 la mitad de los nodos seencuentran desinformados. La topologıa de la red no tiene influencia sobre estehecho, es decir:

i−(pE = 1) =12

, ∀ N, k, p. (6.1)

Dado un valor fijo de la conectividad k, tanto la fraccion de nodos desinformadosi− como el grado de clustering C decrecen a medida que la red se desordena.Las evidencias numericas demuestran que las redes con un elevado C son menosrobustas contra ruido en los canales de transmision. Esta desventaja se conver-tira en una ventaja cuando se introduzcan mecanismos de deteccion y correccionde errores en la proxima seccion.

En las figuras 6.3 y 6.4 se aprecia la influencia de la conectividad de la redk sobre la fraccion de nodos desinformados i− para un valor fijo de pE y paradistintos valores de p. La red es mas robusta a la difusion de errores a medidaque el desorden p y la conectividad k aumentan.

6.1. CANALES RUIDOSOS 47

Figura 6.2: La fraccion de nodos desinformados i− en funcion de la probabilidadde informar erroneamente pE para distintos valores de la aleatoriedad de la redp, (N = 1000, k = 10, 1000 realizaciones).

Figura 6.3: La fraccion de nodos desinformados i− en funcion de la conectividadk para distintos valores de p y para una probabilidad de error fija pE = 10−2

(N = 1000, 3000 realizaciones).


Figura 6.4: La fraccion de nodos desinformados i− en funcion de la conectividadk para distintos valores de p y para una probabilidad de error fija pE = 10−3

(N = 1000, 7000 realizaciones).

6.2. Deteccion y correccion de errores

Dado que la presencia de ruido en los canales de transmision es una propiedadinherente a todo proceso de propagacion de informacion, tanto los sistemas ar-tificiales como los que han evolucionado de manera natural cuentan con mecan-ismos que les permiten detectar y corregir errores. Por lo tanto un estudio dedifusion de informacion, como el presente trabajo, tiene necesariamente que abo-carse al analisis de la influencia que poseen estos procesos en la divulgacion deerrores. Este mecanismo particular se basa en una interaccion adicional senci-lla, la cual describimos a continuacion: cada agente, antes de informar, consultael estado actual de sus 2k vecinos entrantes. 1 Estas consultas se realizan atraves de canales libres de ruido. El nodo en cuestion, a traves del criterio dela mayorıa, corrige su estado. Este proceso se realiza con una probabilidad pC

antes de cada intento de informar. El uso de estos canales libres de ruido lodebemos asociar con un costo o una energıa elevada. De no ser ası, el sistemapodrıa utilizar siempre estos canales perfectos y no habrıa lugar a propagacionde errores. Por lo tanto un valor realista de la probabilidad pC deberıa ser unvalor pequeno. Nos interesa la influencia de la probabilidad pC sobre la frac-cion de nodos desinformados i−. Los resultados de las simulaciones se presentanen las figuras 6.5 y 6.6. La introduccion de este mecanismo favorece levementea las redes con mayor grado de clustering. Esto se puede observar, al margen

1Recordemos que el algoritmo de desorden implica que el numero de entradas de cada nodosea igual a 2k.

6.2. DETECCION Y CORRECCION DE ERRORES 49

Figura 6.5: La fraccion de nodos desinformados i− en funcion de la probabilidadde correccion pC para un valor fijo de pE = 10−2, un valor fijo de la conectividadk = 5 para distintos valores de la aleatoriedad de la red p (N = 1000, 5000realizaciones).

de las fluctuaciones estadısticas, cuando se grafica la fraccion relativa de nodosdesinformados i−(pC)

i−(0) en funcion de la probabilidad de correccion pC (ver figuras6.8 y 6.7). Las redes con mayor grado de clustering C consiguen reducir masla propagacion de errores. Asimismo una red menos desordenada puede reducirestos errores mas que una red desordenada cuando los agentes tienen la posi-bilidad de corregirlos. Esta cualidad constituye un ejemplo de una propiedademergente: la red adquiere mayor robustez contra el ruido de los canales detransmision, propiedad a la cual no puede aspirar un agente interactuante aisla-do. Una vez mas se comprueba que estos atributos macroscopicos son atribuiblesa las interacciones microscopicas y que dependen fuertemente del escenario deinteraccion representado por la topologıa de la red compleja.


Figura 6.6: La fraccion de nodos desinformados i− en funcion de la probabilidadde correccion pC para un valor fijo de pE = 10−3, un valor fijo de la conectividadk = 5 para distintos valores de la aleatoriedad de la red p (N = 1000, 10000realizaciones).

Figura 6.7: La fraccion relativa de nodos desinformados i−(pC)i−(0) en funcion de

la probabilidad de correccion pC para un valor fijo de pE = 10−2, un valor fijode la conectividad k = 5 para distintos valores de la aleatoriedad de la red p(N = 1000, 5000 realizaciones).

6.2. DETECCION Y CORRECCION DE ERRORES 51

Figura 6.8: La fraccion relativa de nodos desinformados i−(pC)i−(0) en funcion de

la probabilidad de correccion pC para un valor fijo de pE = 10−3, un valor fijode la conectividad k = 5 para distintos valores de la aleatoriedad de la red p(N = 1000, 10000 realizaciones).

Capıtulo 7

Conclusiones

Pocas palabras son necesarias para dar por concluido este estudio acerca delos procesos de propagacion de informacion en redes complejas. Sin embargo,sera util volver atras sobre el camino recorrido para obtener una vista panorami-ca de los resultados obtenidos.

Los sistemas complejos son sistemas compuestos por una gran cantidad deagentes interactuantes. Las interacciones microscopicas dan lugar a propiedadescolectivas emergentes, propiedades que no poseen los elementos constituyentessino que solo pueden ser atribuidas al sistema en su totalidad. Estos sistemaspermiten ser modelados mediante un escenario y una dinamica de interaccion.Este escenario es representado por un grafo, cuya topologıa modela la geometrıade las relaciones entre agentes.

Mediante un algoritmo particular de construccion de redes dirigidas que nospermitio interpolar, a traves de un parametro p, entre redes ordenadas y redesaleatorias, definimos una clase de redes complejas. El estudio de sus propiedadesgeometricas nos llevo a una clasificacion, que dio como resultado cuatro tipos:red ordenada, red aleatoria, red totalmente conectada y red small world dirigida.Las propiedades geometricas se midieron a traves de tres cantidades elegidascuidadosamente: el numero de salidas ZS , la distancia media L y el grado declustering C.

Una vez precisado el escenario nos abocamos a definir una dinamica mi-croscopica de interaccion sencilla con la cual modelamos el proceso de propa-gacion de informacion. En ese contexto nos interesamos en la evolucion temporaldel numero de nodos informados I(t), la cual fue estudiada en el marco de laclasificacion obtenida del analisis de las propiedades geometricas de las redes.Las evidencias numericas mostraron que las propiedades dinamicas son fuerte-mente influenciadas por la topologıa de las redes subyacentes. La red totalmenteconectada, derrochadora en lo referente al numero de conexiones presentes en-tre sus nodos, nos permitio validar nuestros algoritmos computacionales, ya quees la unica que concede un tratamiento analıtico cerrado. Asimismo este tipode red nos permitio una clasificacion fenomenologica de las redes aleatorias ysmall world dirigidas a traves del tiempo caracterıstico τ , magnitud que per-

53

54 CAPITULO 7. CONCLUSIONES

mite caracterizar la velocidad de estos dos tipos de redes. La red ordenadamostro dos regımenes dinamicos: uno esencialmente lineal para k ¿ N y otrode tipo “logıstico” cuando k ≈ O[N ]. El regimen lineal fue descripto por unaecuacion integro diferencial que nos permitio modelar el proceso de propagacioncomo dos ondas “informativas” desplazandose a traves de la red en direccionesopuestas y con una velocidad constante vf proporcional a la conectividad de lared k.

La presencia de ruido en toda transmision de informacion motivo el estudiode un mecanismo no supervisado de deteccion y correccion de errores basadoen la estructura de clusters de las redes. Para esto se introdujo ruido en latransmision a traves de la probabilidad pE , ası como un proceso de deteccion ycorreccion gobernado por la probabilidad pC . La probabilidad pE es la proba-bilidad que el nodo receptor reciba de manera incorrecta la informacion y laprobabilidad pC es la probabilidad que los nodos detecten y corrijan, a travesde una interaccion particular a primeros vecinos entrantes, sus estados antes deinformar. La fraccion de nodos desinformados i− fue la cantidad central estu-diada en ese contexto. Las simulaciones numericas demostraron que las redescon alto grado de clustering se encuentran en desventaja cuando se introduceruido en los canales de tranmision, pero que son mas eficientes en detectar ycorregir errores.

Despues de este resumen y antes de finalizar, quisieramos mencionar algunosaspectos y problemas dignos de ser estudiados con mayor tiempo y nivel dedetalle.

El algoritmo utilizado para medir la distancia media L es muy elegante, peroal mismo tiempo muy costoso desde el punto de vista computacional. El caracterprobabilıstico de esta magnitud hace necesario su medicion en un numero grandede realizaciones, es por eso que es importante implementar un algoritmo maseficiente que permita en un tiempo razonable llevar a cabo mas experimentosnumericos. Implementado esto se podrıa estudiar mas detalladamente la dis-tribucion de probabilidades de L que mostro distribuciones con comportamien-tos no triviales. Este estudio deberıa realizarse para redes con un mayor numerode nodos N . Algoritmos que podrıan ayudar en ese sentido se encuentran en lareferencia [10].

Antes de calcular tanto la distancia media L como el grado de clustering Cde las redes, las correspondientes matrices de adyacencia M fueron simetrizadas.Es decir que no fueron contempladas las direcciones de las redes dirigidas. Serıade interes definir nuevas magnitudes que permitan caracterizar estas cantidadespara redes dirigidas “puras”. Por ejemplo, en el caso del grado de clustering, po-drıan contarse las relaciones triangulares contemplando el sentido de giro de lostriangulos correspondientes. 1. O en el caso de la distancia media L, se podrıanencontrar condiciones analıticas que cumplan los parametros de construccion N ,k y p, de tal manera que la distancia media “dirigida” no diverja. Relacionadocon este ultimo punto existen conceptos interesantes, aplicados en ingenierıahidraulica, que describen los posibles “flujos” en redes que transportan lıquidos.Si es posible encontrar un flujo que conecte el nodo j con el nodo i, entonces la

1“Si el nodo A puede informar al nodo B y al nodo C, entonces el nodo B puede informaral nodo C y el nodo C puede informar al nodo B.”

55

distancia media “dirigida” entre estos dos vertices no podrıa tender a infinito.De esta manera podrıa definirse un algoritmo de construccion de redes smallworld dirigidas que garantice la conexion dirigida de todos sus vertices.

Las topologıas de las redes complejas no son estaticas. Pensemos en las redesneuronales, cuya topologıa evoluciona a lo largo del tiempo. En este trabajo su-pusimos que las velocidades que caracterizan los procesos de propagacion de in-formacion eran ordenes de magnitud mayores que las velocidades que caracteri-zan la evolucion temporal de los cambios topologicos en las redes subyacentes.Esta condicion podrıa relajarse, permitiendo cambios topologicos que ocurrande manera simultanea al proceso de propagacion de informacion y estudiar suinfluencia tanto en el numero de nodos informados I(t) como en la fraccion denodos desinformados i−.

Queda pendiente la caracterizacion analıtica de las propiedades dinamicasdel proceso de propagacion para todo el espacio de los parametros constructivosN , k y p. Conocida la distribucion de probabilidades del numero de salidas ZS

podrıa encararse este problema, tal vez utilizando las matrices de transicion enel marco de la teorıa de las cadenas de Markov, con el fin de encontrar unaecuacion diferencial maestra. Esto elevarıa el entendimiento de la dinamica depropagacion en redes small world dirigidas.

56 CAPITULO 7. CONCLUSIONES

Bibliografıa

[1] R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks.Reviews of Modern Physics, 74(47), 2002.

[2] A. L. Barabasi and R. Albert. Emergence of scaling in random networks.Science, 286:509–512, 1997.

[3] A. L. Barabasi, R. Albert, and H. Jeong. Diameter of the world wide web.Nature, 401:130–131, 1999.

[4] A. Barrat and M. Weigt. On the properties of small-world network models.The European Physical Journal B, 13:547–560, 2000.

[5] B. Bollobas. Random graphs. Cambridge University Press, 2001.

[6] L. da F. Costa, F. Rodrigues, G. Travieso, and P. Villas Boas. Cha-racterization of complex networks: a survey of measurements. arXiv:cond-mat/0505185, 2005.

[7] P. Erdos and A. Renyi. On random graphs. Publicationes Mathematicae,6:290–297, 1959.

[8] P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math.Inst. Hungar. Acad. Sci, 5:17–61, 1960.

[9] P. Erdos and A. Renyi. On the strenght of connectedness of a randomgraph. Acta Mathematica Scientia Hungary, 12:261–267, 1961.

[10] J. Gross and J. Yellen. Graph theory and its applications. CRC Press, 1999.

[11] H. Jeong, B. Tombor, R. Albert, Z. Oltvai, and A.-L. Barabasi. The large-scale organization of metabolic networks. Nature, 407:651–654, 2000.

[12] D. J. Watts. Small worlds: the dynamics of networks between order andrandomness. Princeton University Press, 1998.

[13] D. J. Watts. Six degrees: the science of connected age. Norton, 2003.

[14] D. J. Watts and S. H. Strogatz. Collective dynamics of small-world net-works. Nature, 393(6684):440–442, 1998.

57

procesos de propagaci¶on de informaci¶on en redes...

Documents