Técnicas cuánticas para la evolución de grafos aleatorios

XXX Coloquio V´ıctor Neumann-Lara de Teor´ıa de Gr´aficas, Combinatoria y sus Aplicaciones T´ecnicas cu´anticas para la evoluci´on de grafos aleatorios Enrique F. Borja∗Clara Grima†Alberto M´arquez‡Reyes Zambrano§ Resumen Con la idea de modelar el comportamiento de diversas redes sociales a lo largo del tiempo, mostramos algunos resultados preliminares sobre evoluci´on de grafos aleatorias empleando t´ecnicas inspiradas en la mec´anica cu´antica. Presentaremos el formalismo y veremos como podemos pasar de una descripci´on microsc´opica a una descripci´on macrosc´opica. Por ´ultimo, compararemos nuestro modelo con los bien conocidos grafos de Erd˝os-R´enyi. Palabras Clave. Grafo aleatorio. Hamiltoniano. Operadores de creaci´on y destrucci´on. Erd˝os- R´enyi. 1 Introducci´on La evoluci´on temporal de grafos es un tema de candente actualidad. La aparici´on de las redes sociales, y su importancia comercial y pol´ıtica, nos obliga a mejorar nuestra capacidad de modelado de dichos sistemas. Para ello, introducimos un modelo que nos permite describir la evoluci´on temporal de los valores esperados de las caracter´ısticas de los grafos a dos niveles. Por un lado podemos modelar el comportamiento microsc´opico de las aristas entre nodos tal y como se hace en los trabajos cl´asicos. Por otro lado, podemos acercarnos a las t´ecnicas de las grafos aleatorios exponenciales donde se trabaja con colectivos siguiendo el esp´ıritu de la mec´anica estad´ıstica en f´ısica. Para acometer este objetivo aplicamos las t´ecnicas de la mec´anica estoc´astica de Baez et al. que toman su inspiraci´on en la mec´anica cu´antica. Esto nos permite describir los procesos de creaci´on y destrucci´on de las aristas entre nodos del grafo. Esta idea tiene como ventaja que podemos aplicar las ideas cu´anticas sin tener que enfrentarnos a los problemas derivados de su formulaci´on en espacios de Hilbert complejos y del omnipresente principio de indeterminaci´on de Heisenberg. 2 Breve resumen sobre mec´anica estoc´astica En esta secci´on vamos a introducir los elementos esenciales de la mec´anica estoc´astica [1] que emplearemos a lo largo de este trabajo. Por razones de espacio y para mantener la claridad de la exposici´on omitiremos los detalles t´ecnicos. Queremos describir un sistema (la evoluci´on de un grafo que modela una red din´amica) que est´a definido seg´un el n´umero de constituyentes (nodos) del mismo. El n´umero de constituyentes se representan por n. En este contexto supondremos que dichos elementos constituyentes del sistema se pueden crear y destruir. Profundizaremos en ello en lo que sigue pero ahora tenemos que introducir el concepto de estado. Un estado Ψ en mec´anica estoc´astica se define como una serie de potencias formal en la variable z. Ψ = X n nzn,(1) ∗Universidad de Sevilla (Espa˜na), [email protected] †Universidad de Sevilla (Espa˜na), [email protected] ‡Universidad de Sevilla (Espa˜na), [email protected] §Universidad de Sevilla (Espa˜na), [email protected] 7 Oaxaca, M´exico, 2 - 6 de marzo de 2015 donde los coeficientes de la serie ψnson las probabilidades de que nuestro sistema tenga un n´umero n de constituyentes. Por supuesto, tenemos que asegurar la condici´on ∞ X n=0 ψn= 1.(2) Llegados a este punto tenemos que introducir los operadores de creaci´on y de destrucci´on. Un operador de creacci´on se denota por a†y su actuaci´on sobre un estado es simplemente la multiplicaci´on por z. Si tomamos el estado Ψ = znla actuaci´on del operador a†viene dada por a†zn=zn+1.(3) Por otro lado, el operador de destrucci´on, que denotaremos por a, act´ua como un operador de derivaci´on d/dz. Su actuaci´on sobre el anterior estado da lugar a azn=dzn dz =zn−1.(4) Es interesante calcular el conmutador entre estos dos operadores, a, a†= 1,(5) Este conmutador define completamente el ´algebra de los operadores que vamos a definir y ser´a de gran utilidad en lo que sigue. De hecho, en mec´anica cu´antica esta relaci´on es la que define de forma abstracta los operadores de creaci´on y destrucci´on. Dicho nombre es totalmente apropiado dados los t´erminos en los que hemos definido los estados y la actuaci´on de dichos operadores. Por supuesto, se cumple que [a, a] = a†, a†= 0. Un operador interesante es el operador n´umero, A, que es el que cuenta el n´umero de constituyentes del sistema. Este operador expresa en t´erminos de los operadores aya†del siguiente modo, A=a†a, (6) empleando las relaciones de conmutaci´on entre aya†obtenemos los siguientes conmutadores, [A, A] = 0, A, a†=a†y [A, a] = −aLa evoluci´on temporal de los estados vendr´a definida por la acci´on de un operador lineal, el Hamiltoniano, representado por Hy que definiremos apropiadamente en la siguiente secci´on para el caso que nos ocupa. En este trabajo estamos interesados en el estudio de la evoluci´on temporal de los valores esperados de distintos observables del sistema. Sea Oun operador construido con operadores aya†. Para llegar a los resultados de inter´es introduciremos una notaci´on compacta ´util en los c´alculos. Denotaremos la relaci´on (2) por PΨ. Para que la evoluci´on temporal est´e bien definida se tienen que cumplir las siguientes relaciones: Xa†Ψ = XΨ,(7) y XaΨ = XAΨ.(8) El valor esperado del operador Ose define como hOi=POΨ. Su evoluci´on temporal viene dada por la siguiente expresi´on, d dthOi=XOHΨ.(9) 8 XXX Coloquio V´ıctor Neumann-Lara de Teor´ıa de Gr´aficas, Combinatoria y sus Aplicaciones 3 El Hamiltoniano definido para grafos La herramienta fundamental que har´a modificar nuestro grafo a lo largo del tiempo es el Hamiltoniano. Definiremos nuestro grafo Gde la forma usual dado un conjunto Vde nnodos y un conjunto de aristas E. Los nodos ser´an indexados por letras latinas min´usculas i, j, . . . que tomar´an valores de 1 a n. Las aristas se denotar´an por el par de nodos que unen, as´ı ij denotar´a la arista entre el nodo iy el nodo j. Seg´un la imagen que estamos construyendo podremos construir aristas entre dos nodos aplicando un operador de creaci´on entre los nodos implicados, por lo tanto, a† ij crear´a una arista entre los nodos i yj. Los operadores de destrucci´on actu´an de forma an´aloga. Por ahora nos centraremos en grafos no dirigidos y sin autolazos. En este caso tenemos que extender las relaciones de conmutaci´on para este caso de la siguiente forma hakl, a† iji=δkl,ij,(10) donde la δkl,ij es una delta de Kronecker generalizada, que tal y como definiremos las sumas sobre v´ertices y teniendo en cuenta las caracter´ısticas de los grafos en las que estamos trabajando, toma el valor 1 cuando los operadores act´uan sobre las misma arista y toma el valor 0 cuando act´uan sobre aristas diferentes. Podemos definir el operador que cuenta las aristas entre un par de nodos Aij =a† ijaij,(11) no es dif´ıcil notar que este operador es la representaci´on en nuestro modelo del elemento ij de la matriz de adyacencia. Por tanto, nuestro modelo tiene que tener los ingredientes necesarios para asegurar que dichos operadores solo pueden tener autovalores 0 o 1. Este es un punto sutil que est´a relacionado con el car´acter fermi´onico de las aristas de la gr´afica. Dicho de otro modo, las multiaristas entre un par de nodos no est´an permitidas. Las relaciones de conmutaci´on que involucran a los operadores Aij que utilizaremos en los c´alculos que siguen son: [Akl, Aij ] = 0, [Akl, aij] = −aklδkl,ij, hAkl, a† iji=a† klδkl,ij. 3.1 El Hamiltoniano Con las herramientas que hemos definido en anteriormente estamos en disposici´on de construir nuestro Hamiltoniano. Este operador contendr´a diversas partes teniendo cada una de ellas un significado en la evoluci´on del grafo. En estas l´ıneas que siguen definiremos cada una de las contribuciones del Hamiltoniano. Hamiltoniano libre El Hamiltoniano libre simplemente da cuenta del n´umero de aristas presentes en el grafo. H0=γ0X iX j<i Aij,(12) donde γ0es un par´ametro real que tiene que ser fijado dependiendo de las propiedades del grafo. Hamiltoniano aleatorio En esta parte del Hamiltoniano se tiene en cuenta la posibilidad de que dos nodos cualesquiera del grafo se interact´uen entre s´ı creando o destruyendo una arista entre ellos. HR=αX iX j>i (a† ij −1)(1 −Aij) + βX iX j>i (aij −Aij),(13) 9 Oaxaca, M´exico, 2 - 6 de marzo de 2015 donde αyβson par´ametros reales que cumplen α+β= 1. El Hamiltoniano total ser´a por tanto H=H0+HR Como veremos en la pr´oxima secci´on la ´unica parte de Hamiltoniano que genera evoluci´on temporal es el HRdado que H0conmuta con todos los observables que vamos a estudiar al estar estos construidos como composici´on de operadores del tipo Aij. 4 Erd˝os-R´enyi En esta secci´on exponemos c´omo nuestro modelo puede recuperar el comportamiento de un grafo aleatorio de Erd˝os-R´enyi,[2], en t´erminos de los valores promedio de cantidades medibles en el grafo. El modelo nos da la evoluci´on temporal de estos valores promedio y se recuperan los resultados conocidos en el l´ımite de tiempos de evoluci´on grandes. N´umero total de Aristas El n´umero total de aristas de nuestro grafo como E=PkPl>k Akl. La evoluci´on temporal del valor promedio de este observable viene dado por: d dthEi=XEHRΨ.(14) El resultado, para un estado inicial Ψ0= 1, el grafo sin aristas, tiene la forma hE(t)i=αn(n−1) 2−αn(n−1) 2e−t.(15) Se puede calcular cualquier otra magnitud relevante del grafo como el grado promedio de un nodo, el n´umero de caminos de longitud 2, el n´umero de 2-estrellas, etc. Todos los resultados son id´enticos asint´oticamente con los resultados conocidos de este tipo de grafos. Empleando estos resultados podemos acometer el estudio estad´ıstico de un colectivo de grafos aleatorios [3]. Para ello utilizamos la funci´on de partici´on del sistema suponiendo que el promedio del n´umero total de aristas est´a fijado. La funci´on de partici´on est´a definida por Z=X G ehH0i= (1 + eγ0)(n 2),(16) donde Ges el colectivo de todos los grafos posibles considerando que son todas equiprobables e imponiendo un valor esperado del n´umero de aristas. A partir de este resultado es trivial recuperar la distribuci´on de probabilidad de Erd˝os-R´enyi para obtener un grafo concreto dentro del colectivo. P(G) = eγ0 1 + eγ0hEi1 1 + eγ0(n 2)−hEi(17) Referencias [1] Baez, J. C., Biamonde, J.: A Course on Quantum Techniques for Stochastic Mechanics, arXiv:1209.3632v1 [quant-ph] , 2012. [2] Albert, R´eka., Barabasi, Albert-Lazlo.: Statistical Mechanics of complex networks, Reviews of modern physics 74 2002, 47 – 97. [3] Fronczak, Agata.: Exponential random graph models, Chapter in Encyclopedia of Social Network Analysis and Mining, R. Alhajj, J. Rokne (Eds.) Springer-Verlag 2014. 10