Homología persistente de redes complejas

Traballo de Fin de Mestrado Homología persistente de redes complejas Gabriel Penide Calvo 2015-2016 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA MESTRADO UNIVERSITARIO EN MATEMÁTICAS Traballo de Fin de Mestrado Homología persistente de redes complejas Gabriel Penide Calvo 19 de xullo de 2016 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Universidade de Santiago de Compostela Departamento de Xeometría e Topoloxía D. Enrique Macías Virgós, profesor del Departamento de Xeometría e Topoloxía de la Universidade de Santiago de Compostela, certifica que la presente memoria realizada por D. Gabriel Penide Calvo titulada Homología persistente de redes complejas ha sido realizada bajo su dirección y da su conformidad para su presentación y defensa ante un tribunal con el fin de optar a la TITULACIÓN DE MÁSTER UNIVERSITARIO EN MATEMÁTICAS El director: Enrique Macías Virgós El autor: Gabriel Penide Calvo En Santiago de Compostela, a 11 de julio de 2016 May 17, 2011 To Whom it May Inspire, I, like many of you artists out there, constantly shift between two states. The first (and far more preferable of the two) is white-hot, “in the zone” seat-of-the-pants, firing on all cylinders creative mode. This is when you lay your pen down and the ideas pour out like wine from a royal chalice! This happens about 3 % of the time. The other 97 % of the time I am in the frustrated, struggling, office-corner-full-of-crumpled-up-paper mode. The important thing is to slog diligently through this quagmire of discouragement and despair. Put on some audio commentary and listen to the stories of professionals who have been making films for decades going through the same slings and arrows of outrageous production problems. In a word: PERSIST. PERSIST on telling your story. PERSIST on reaching your audience. PERSIST on staying true to your vision. Remember what Peter Jackson said, “Pain is temporary. Film is forever.” And he of all people should know. So next time you hit writer’s block, or your computer crashes and you lose an entire night’s work because you didn’t hit save (always hit save), just remember: you’re never far from that next burst of divine creativity. Work through that 97 % of murky abyssmal mediocrity to get to that 3 % which everyone will remember you for! I guarantee you, the art will be well worth the work! Your friend and mine, Austin Madison “ADVENTURE IS OUT THERE!” Índice general Resumen ix Introducción xi 1. Homología simplicial 1 1.1. Complejos simpliciales . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Complejos simpliciales abstractos . . . . . . . . . . . . . . . . . . 3 1.3. Homología simplicial orientada . . . . . . . . . . . . . . . . . . . 5 1.4. Invariancia homotópica . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5. Computabilidad............................ 10 1.5.1. Forma normal de Smith . . . . . . . . . . . . . . . . . . . 10 1.5.2. Algoritmo para las matrices de incidencia . . . . . . . . . 12 2. Construcción de complejos simpliciales 21 2.1. ComplejodeČech .......................... 21 2.2. Complejo de Vietoris-Rips . . . . . . . . . . . . . . . . . . . . . . 24 2.3. Complejo de Delaunay . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4. Otros complejos simpliciales . . . . . . . . . . . . . . . . . . . . . 28 3. Homología persistente 29 3.1. Filtraciones .............................. 29 3.1.1. Filtraciones con índices naturales . . . . . . . . . . . . . . 30 3.1.2. Filtraciones con índices reales . . . . . . . . . . . . . . . . 31 3.2. Códigosdebarras .......................... 34 3.2.1. Intervalos de persistencia . . . . . . . . . . . . . . . . . . 35 3.2.2. Filtraciones de Čech y Vietoris-Rips . . . . . . . . . . . . 36 3.3. Estructuras algebraicas . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1. Módulos y complejos de persistencia . . . . . . . . . . . . 38 3.3.2. Clasificación sobre cuerpos . . . . . . . . . . . . . . . . . 39 3.3.3. Algoritmo de cálculo sobre cuerpos . . . . . . . . . . . . . 42 3.4. Notashistóricas............................ 51 vii Capítulo 1 Homología simplicial Uno de los problemas fundamentales de la topología es conseguir determinar si dos espacios topológicos son o no homeomorfos o, más generalmente, si son homotópicamente equivalentes. Dar una respuesta satisfactoria a esta pregunta puede resultar muy difícil la mayoría de las veces. Estas dificultades derivaron en el surgimiento de la topología algebraica y en el estudio de propiedades que permaneciesen invariantes para hacer más sencilla la distinción de espacios topológicos. La homología simplicial surgió durante esta búsqueda de invariantes topológicos. La homología simplicial formaliza la idea de encontrar los agujeros de una determinada dimensión que tiene un cierto espacio. Sin embargo, la homología simplicial necesita una estructura poliédrica subyacente, lo que no la hace válida para espacios que no sean suficientemente «buenos». De esta manera, esta teoría dio paso al estudio de la conocida como homología singular, que sí permitía desarrollar la teoría en espacios topológicos arbitrarios. Además, ambas homologías coinciden para aquellos espacios donde la primera se puede calcular. A pesar de esto, la homología singular resulta de muy difícil cálculo en muchos casos. La irrupción y desarrollo de la computación a finales del siglo xx provocó que los complejos simpliciales cobraran de nuevo importancia en la topología algebraica debido a las posibilidades que brindan los ordenadores para su tratamiento. Este hecho y sus aplicaciones en muchos ámbitos cotidianos provocaron el regreso al estudio de la homología simplicial. La exposición del capítulo sigue en gran parte [2], incorporando también elementos de [34]. 1.1. Complejos simpliciales La idea básica para entender el origen de los complejos simpliciales es verlos como una generalización de las triangulaciones de las superficies. Decimos que los n+1 puntos v0, v1, . . . , vnde Rmson afínmente independientes si los vectores 1 2CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL v1−v0, . . . , vn−v0son linealmente independientes. Esta noción de independencia afín garantiza que los puntos no se encuentran contenidos en algún hiperplano de una cierta dimensión y sirve para definir la estructura básica utilizada para construir la homología simplicial. Definición 1.1. Un símplice de orden non-símplice es la envoltura convexa de n+ 1 puntos afínmente independientes. En otras palabras, dados v0, v1, . . . , vn puntos afínmente independientes de Rmse llama n-símplice al conjunto σ=(x= n X i=0 λivi∈Rm: n X i=0 λi= 1, λi≥0para todo i). Los coeficientes λise conocen como coordenadas baricéntricas y los puntos vi son los vértices del símplice, con i= 0, . . . , n. Habitualmente, denotaremos un n-símplice mediante un conjunto de n+ 1 elementos formado por sus vértices, σ={v0, . . . , vn}, o mediante una yuxtaposición de los mismos, σ=v0· · · vn. Definición 1.2. Sean σyτdos símplices. Se dice que τes una cara de σ, y lo denotamos por τ≤σ, si todos los vértices de τson vértices de σ. Si τ6=σy τ≤σ, diremos que τes una cara propia de σy escribiremos τ < σ. Los complejos simpliciales son familias de símplices que cumplen dos propiedades que recuerdan a las que verifican las triangulaciones. Definición 1.3. Un complejo simplicial finito Kes una colección finita de símplices verificando las siguientes condiciones: (i) Si σ1, σ2∈K, entonces la intersección σ1∩σ2es vacía o bien es una cara común a σ1y a σ2. (ii) Si σ∈Kyτ≤σ, entonces τ∈K. Un subcomplejo de Kes una subcolección de símplices de Kque sigue siendo un complejo. La dimensión de Kes el número dim K= m´ax{dim σ:σ∈K}. Observación 1.4.Todo n-símplice σdetermina un complejo simplicial finito de dimensión nformado por él mismo y cada una de sus caras. Sea Kun complejo simplicial en Rm. De considerar todos los puntos de los símplices de Ksurge un subespacio de Rm, que llamaremos poliedro subyacente aKy que podemos expresar como sigue: |K|=[ σ∈K σ. Más adelante dotaremos de una topología al poliedro subyacente y veremos su importancia, pues la homología de un espacio Xdependerá únicamente del tipo de homotopía de |K|, para un complejo simplicial Kasociado a Xadecuado. 1.2. COMPLEJOS SIMPLICIALES ABSTRACTOS 3 1.2. Complejos simpliciales abstractos Pese a su sencillez, la gran rigidez que poseen los complejos simpliciales definidos en la sección anterior obligó a buscar una definición un poco más abstracta que permitiese una mayor facilidad de manipulación. Definición 1.5. Sea Vun conjunto. Un complejo simplicial abstracto Kes una colección no vacía de partes finitas de Vverificando las siguientes condiciones: (i){v}∈Kpara todo v∈V. (ii) Dado σ∈ K, todo subconjunto de σpertenece a K. Los elementos del conjunto Vse llaman vértices de Ky los elementos de K son los símplices de K. Además, cualquier subcolección de Kque siga siendo un complejo se denomina subcomplejo de K. La dimensión de un símplice σ∈ K es el cardinal de σcomo conjunto menos una unidad. La dimensión de un complejo Kse define como el supremo de las dimensiones de sus símplices (puede no ser finita): dim(K) = sup{#σ:σ∈ K} − 1. La noción de complejo simplicial abstracto formaliza las propiedades que cumple el conjunto de símplices de un complejo simplicial. Es claro que a todo complejo simplicial Kse le puede asociar un complejo simplicial abstracto K. En primer lugar, se toman como vértices de Klos vértices de Ketiquetados de alguna forma. Finalmente, los símplices de Kson los subconjuntos formados por aquellas etiquetas que se corresponden con vértices de Kque están situados en un mismo símplice de K. Recíprocamente, todo complejo simplicial abstracto finito Kadmite una realización geométrica como complejo simplicial finito en algún Rm. Para construirla, basta con embeber el conjunto de vértices de Kcomo un subconjunto de puntos afínmente independientes en Rm, para una dimensión msuficientemente grande. Cada símplice de Kse puede identificar entonces con el símplice geométrico en Rmgenerado por los correspondientes vértices embebidos. La realización geométrica de K, que denotaremos por |K|, es la unión de todos estos símplices geométricos. Esta realización geométrica es trivialmente el poliedro subyacente a algún complejo simplicial finito, de ahí la notación. En caso de que el complejo simplicial abstracto Kno sea finito el razonamiento anterior no es válido. Pese a ello, también es posible construir la realización geométrica de K. Los detalles para el caso general pueden encontrarse en [34]. Sin embargo, en lo que sigue únicamente trabajaremos con complejos simpliciales abstractos finitos, por lo que no se hace necesaria esa demostración. Ejemplo 1.6. A continuación se muestra un ejemplo sencillo de un complejo simplicial abstracto que representa una triangulación de la banda de Möbius. 4CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL v0v1v2v3 v3v4v5v0 Figura 1.1: Banda de Möbius junto a una triangulación. La banda está tomada de [28]. En este ejemplo, el conjunto de vértices viene dado por V={v0, v1, v2, v3, v4, v5}, mientras que el complejo simplicial abstracto se puede expresar como K={v0, v1, v2, v3, v4, v5, v0v1, v0v2, v0v3, v0v4, v0v5, v1v2, v1v4, v1v5, v2v3, v2v5, v3v4, v4v5, v0v1v4, v0v2v3, v0v2v5, v0v3v4, v1v2v5, v1v4v5}. Para expresar los elementos de Kse ha dado de alguna forma un «sentido de recorrido». Por ejemplo, el 2-símplice v0v2v3podríamos haberlo expresado como v0v3v2,v2v0v3,v2v3v0o cualquier otra permutación de los vértices. Es claro que todas sirven para expresar el mismo triángulo como figura geométrica. No obstante, esta orientación en los símplices será importante para introducir una estructura de módulo a partir de los elementos de Ky poder hablar de la homología del complejo simplicial abstracto. Este ejemplo también pone de manifiesto la facilidad con la que los ordenadores pueden manipular los complejos simpliciales abstractos: el complejo queda determinado conociendo el conjunto de sus vértices y una lista con las conexiones establecidas entre ellos. En cuanto se define un nuevo concepto matemático dotado de una cierta estructura el siguiente paso es considerar aquellas aplicaciones entre ellos que respeten esta estructura. Definición 1.7. Sean K1yK2dos complejos simpliciales abstractos y sea ϕ:V1→V2una aplicación definida entre sus conjuntos de vértices. Se dice que ϕes una aplicación simplicial si dado un símplice {v0, . . . , vq}∈K1se verifica que los vértices ϕ(v0), . . . , ϕ(vq)forman un símplice de K2. Cometiendo un abuso de notación, escribiremos ϕ:K1→ K2para referirnos a una aplicación simplicial entre los vértices de K1yK2. 1.3. HOMOLOGÍA SIMPLICIAL ORIENTADA 5 También es preciso el concepto de «igualdad» o «equivalencia» de complejos simpliciales abstractos una vez tenemos definidas las aplicaciones entre ellos. Definición 1.8. Dos complejos simpliciales abstractos K1yK2se dicen isomorfos si existe una biyección ϕ:V1→V2entre los conjuntos de vértices de ambos complejos de forma que {v0, . . . , vq} ∈ K1si, y solo si, {ϕ(v0), . . . , ϕ(vq)}∈K2. En lo que sigue, a menudo obviaremos los adjetivos «abstracto» y «finito» y hablaremos simplemente de un «complejo simplicial». 1.3. Homología simplicial orientada Antes de definir la homología simplicial, es necesario introducir una estructura algebraica en los complejos simpliciales. Para ello, daremos una orientación en cada símplice del complejo mediante una relación de equivalencia. Esta relación genera dos clases de equivalencia para cada símplice, lo que permitirá establecer un signo, es decir, lo que conoceremos como una cadena simplicial y su opuesta. Finalmente, una aplicación lineal entre los símplices de una cierta dimensión y los símplices de una dimensión una unidad menor permitirá poner en marcha toda la maquinaria del álgebra homológica. Sea Kun complejo simplicial. Dado un símplice σ={v0, . . . , vq}, con q > 0, se define la siguiente relación de equivalencia sobre el conjunto de las ordenaciones de los vértices de σ: (v0, . . . , vq)∼(vπ(0), . . . , vπ(q)) si πes una permutación par de los índices. Esta es una relación de equivalencia y origina dos clases de equivalencia, cada una llamada orientación de σ. En otras palabras, dos símplices con los mismos vértices poseen la misma orientación si se puede pasar de uno a otro mediante un número par de trasposiciones en el orden de los vértices. Al escoger una de las orientaciones, σse dice un símplice orientado. Cabe decir que los 0-símplices solo tienen una orientación al estar formados por un único vértice. En adelante, escribiremos [v0, . . . , vq]para denotar el símplice {v0, . . . , vq} con la orientación definida por la ordenación de los índices. A continuación, se introducen las estructuras algebraicas que usaremos en el resto del texto. Fijamos un anillo unitario y conmutativo Ry consideramos las dos posibles orientaciones σ1yσ2de un q-símplice σ. Definición 1.9. Se define el R-módulo de q-cadenas simpliciales orientadas, y se denota por Cq(K;R), como el cociente del R-módulo libre generado por todos los q-símplices σde Kpor el submódulo generado por los σ1+σ2. Los elementos de Cq(K;R)se llaman q-cadenas simpliciales orientadas. Resulta que los elementos de Cq(K;R)son combinaciones lineales de qsímplices con coeficientes en el anillo R. Además, Cq(K;R)es un R-módulo libre con una base dada por cada q-símplice σ∈ K tomado con una orientación, identificando la otra orientación con el elemento −σdel R-módulo. 6CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL Por otra parte, como los 0-símplices son los vértices y estos solo tienen una orientación posible, C0(K;R)es el R-módulo libre generado por los vértices de K. También se tiene que estos R-módulos únicamente están definidos para q≥0, pues no existen símplices de dimensión negativa. Asimismo, se entiende que Cq(∅;R)=0para todo qy que Cq(K;R)=0si q > dim(K). Definición 1.10. Llamamos operador borde de orden qal homomorfismo de R-módulos ∂q:Cq(K;R)−→ Cq−1(K;R) dado por la extensión lineal de ∂q([v0, . . . , vq]) = q X i=0 (−1)i[v0,...,ˆvi, . . . , vq], donde [v0,...,ˆvi, . . . , vq]representa el (q−1)-símplice orientado resultante de eliminar en [v0, . . . , vq]el vértice que ocupa la posición i. Antes de proseguir, tenemos que comprobar que ∂qestá bien definido y que ∂q(−σ) = −∂q(σ)para un q-símplice σ. Para ello, basta con ver que el lado derecho de la igualdad en la definición anterior cambia de signo al permutar dos vértices adyacentes en [v0, . . . , vq]. Comparemos, pues, las expresiones de ∂q([v0, . . . , vj, vj+1, . . . , vq]) y∂q([v0, . . . , vj+1, vj, . . . , vq]). Si el índice de la suma i /∈ {j, j +1}, entonces el resto de sumandos de ambas expresiones difieren precisamente en el signo: los términos son iguales, salvo la permutación de los vértices vjyvj+1 que provoca el cambio de signo. Veamos ahora los sumandos cuando el índice de la suma es i=jei=j+ 1. En la primera expresión, se tiene (−1)j[v0, . . . , vj−1, vj+1, vj+2, . . . , vq]+(−1)j+1[v0, . . . , vj−1, vj, vj+2, . . . , vq]. En la segunda expresión, se tiene (−1)j[v0, . . . , vj−1, vj, vj+2, . . . , vq]+(−1)j+1[v0, . . . , vj−1, vj+1, vj+2, . . . , vq]. Efectivamente, estas dos expresiones difieren en un signo. Ejemplo 1.11. Sea Kun complejo simplicial de dimensión 2. Supongamos que C0(K;Z)está generado por el conjunto de vértices {v0, v1, v2, v3}, que C1(K;Z) tiene por base a {[v0, v1],[v1, v2],[v0, v2],[v2, v3]}y que la base de C2(K;Z)es {[v0, v1, v2]}. El operador borde ∂2:C2(K;Z)→C1(K;Z)actúa así: ∂2(8[v0, v1, v2]) = 8([v1, v2]−[v0, v2]+[v0, v1]). Por su parte, el operador borde de orden 1 hace lo siguiente sobre una combinación lineal de elementos de la base de C1(K;Z): ∂1(2[v2, v3] + 5[v0, v1]) = 2(v3−v2) + 5(v1−v0). Finalmente, se tiene que ∂0:C0(K;Z)→C−1(K;Z)es necesariamente el homomorfismo nulo ya que C−1(K;Z) = 0. 1.3. HOMOLOGÍA SIMPLICIAL ORIENTADA 7 Un cálculo rutinario sirve para comprobar el siguiente resultado. Proposición 1.12. El operador borde verifica que ∂q◦∂q+1 = 0 para todo q. Demostración. En efecto, al hacer el cálculo (∂q◦∂q+1)[v0, . . . , vq+1] = ∂q q+1 X i=0 (−1)i[v0,...,ˆvi, . . . , vq+1]! = q+1 X i=0 (−1)i X j<i (−1)j[v0,...,ˆvj,...,ˆvi, . . . , vq+1] +X j>i (−1)j−1[v0,...,ˆvi,...,ˆvj, . . . , vq+1]  los términos de ambas sumas se cancelan por parejas. La proposición anterior es crucial porque convierte a (C•(K;R), ∂•)en un complejo de cadenas. La propiedad ∂q◦∂q+1 = 0 implica que Im(∂q+1)⊂ker(∂q) para todo q. La imagen y el núcleo del operador borde definen dos submódulos de Cq(K;R)que reciben nombre propio debido a su importancia. Definición 1.13. Llamamos q-ésimo R-módulo de ciclos aZq(K;R) = ker(∂q). Llamamos q-ésimo R-módulo de bordes aBq(K;R) = Im(∂q+1). Definición 1.14. Se define el q-ésimo R-módulo de homología simplicial de K como el siguiente cociente: Hq(K;R) = Zq(K;R) Bq(K;R). Se define también el q-ésimo número de Betti de K, denotado por βq, como el rango de Hq(K;R). Proposición 1.15. Sean K1yK2dos complejos simpliciales y ϕ:K1→ K2 una aplicación simplicial. Entonces, para todo q≥0la aplicación ϕinduce un homomorfismo de complejos de cadenas Cq(ϕ): Cq(K1;R)−→ Cq(K2;R) definido por la extensión lineal de Cq(ϕ)[v0, . . . , vq] = ([ϕ(v0), . . . , ϕ(vq)] si no aparecen vértices repetidos, 0en otro caso. En particular, C•(id) = id y si ψ:K2→ K3es otra aplicación simplicial se tiene que C•(ψ◦ϕ) = C•(ψ)◦C•(ϕ). 8CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL Demostración. Es obvio que la definición de C•(ϕ)no depende de la permutación que da la orientación. Para comprobar que define un homomorfismo de complejos de cadenas, tenemos que demostrar que ∂2 q◦Cq(ϕ) = Cq−1(ϕ)◦∂1 q para q > 0(el caso q= 0 es inmediato). Basta comprobarlo en los símplices orientados, ya que estos forman una base. Sea σ= [v0, . . . , vq]∈Cq(K1;R). Si al aplicar ϕno se repite ningún vértice, entonces Cq−1(ϕ)◦∂1 q[v0, . . . , vq] = Cq−1(ϕ) q X i=0 (−1)i[v0,...,ˆvi, . . . , vq]! = q X i=0 (−1)i[ϕ(v0),..., [ ϕ(vi), . . . , ϕ(vq)] =∂2 q◦Cq(ϕ)[v0, . . . , vq]. Si al aplicar ϕse repite algún vértice, pongamos ϕ(vj) = ϕ(vk), se tiene que ∂2 q◦Cq(ϕ)[v0, . . . , vq] = 0 y, por otra parte, Cq−1(ϕ)◦∂1 q[v0, . . . , vq] = Cq−1(ϕ) q X i=0 (−1)i[v0,...,ˆvi, . . . , vq]! = q X i=0 (−1)iCq−1(ϕ)[v0,...,ˆvi, . . . , vq] = 0 pues si i /∈ {j, k}hay un vértice repetido y Cq−1(ϕ)[v0,...,ˆvi, . . . , vq] = 0 y, suponiendo que j < k, se verifica que (−1)j[ϕ(v0),...,\ ϕ(vj), . . . , ϕ(vk), . . . , ϕ(vq)] + (−1)k[ϕ(v0), . . . , ϕ(vj),...,\ ϕ(vk), . . . , ϕ(vq)] =(−1)j(−1)k−j−1+ (−1)k[ϕ(v0),...,\ ϕ(vj), . . . , ϕ(vk), . . . , ϕ(vq)] =(−1)k−1+ (−1)k[ϕ(v0),...,\ ϕ(vj), . . . , ϕ(vk), . . . , ϕ(vq)] = 0 ya que son necesarias k−j−1trasposiciones para pasar de un símplice al otro (contando desde 0, el vértice ϕ(vk)ocupa la posición k−1en el primer símplice). Finalmente, las igualdades C•(id) = id yC•(ψ◦ϕ) = C•(ψ)◦C•(ϕ)resultan inmediatas a partir de la definición del homomorfismo en cada grado. Una vez probada la existencia del homomorfismo anterior, es un resultado general de homología que un homomorfismo de complejos de cadenas induce un homomorfismo en homología. Corolario 1.16. Toda aplicación simplicial ϕ:K1→ K2induce un homomorfismo Hq(ϕ): Hq(K1;R)−→ Hq(K2;R) tal que H•(id) = id yH•(ψ◦ϕ) = H•(ψ)◦H•(ϕ)para ψ:K2→ K3simplicial. 1.4. INVARIANCIA HOMOTÓPICA 9 Este homomorfismo viene dado de la siguiente forma: si [z]∈Hq(K1;R)es la clase de un q-ciclo, entonces Hq(ϕ)([z]) = [Cq(ϕ)(z)]. 1.4. Invariancia homotópica En la sección anterior hemos descrito un proceso para asociar un R-módulo graduado a un complejo simplicial K. La presente sección pretende recoger un resultado de gran importancia que afirma que estos módulos de homología solo dependen del tipo de homotopía del poliedro subyacente |K|. Como los objetivos de este trabajo son otros, no se dará una demostración de este hecho. La prueba puede encontrarse en [2] o en [34], que dedican un capítulo entero cada uno a tratar este asunto. Empezamos dando una topología al poliedro |K|. Para ello, en un primer momento parece natural plantearse dar la topología relativa de Rm, ya que |K| ⊂ Rm. También existe la posibilidad de dar al poliedro la topología débil de los símplices: la mayor topología que hace las inclusiones σ ,→ |K| continuas. Sin más que tener en cuenta que los símplices son subespacios compactos de Rm, es inmediata la siguiente afirmación. Proposición 1.17. La topología relativa y la topología débil de |K| ⊂ Rmcoinciden. Aún más, esta topología hace a |K| compacto. La proposición anterior no es cierta si Kno es finito. En general, la topología débil de |K| es más fina que la topología relativa que hereda de Rm. De esta manera es también inmediato que A⊂ |K| es cerrado (abierto) si, y solo si, A∩σes cerrado (abierto) en σpara todo σ∈ K. Una vez introducida una topología en |K| tiene sentido la siguiente definición. Definición 1.18. Sea Xun espacio topológico. Se dice que Xes triangulable si existen un poliedro |K| y un homeomorfismo h:|K| → X. En ese caso, se dice que el par (K, h)es una estructura simplicial otriangulación de X. Estamos ya en condiciones de enunciar el principal resultado que recogerá esta sección. Teorema 1.19. Si K1yK2son dos complejos simpliciales tales que sus poliedros subyacentes |K1|y|K2|tienen el mismo tipo de homotopía, entonces los módulos de homología Hq(K1;R)yHq(K2;R)son isomorfos para todo q. En particular, los módulos de homología son invariantes topológicos para cualquier poliedro |K|. Esto permite dar la siguiente definición. Definición 1.20. Sea Xun espacio topológico triangulable. Se define el q-ésimo R-módulo de homología de Xcomo Hq(X;R) := Hq(K;R), donde (K, h)es una triangulación de X. Para un espacio triangulable puede probarse que la homología simplicial coincide con su homología singular [34, Capítulo 4, §34], por lo que se trata 16 CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL Gracias a la matriz en forma normal podemos expresar su borde como ∂q(cq) = k X i=1 γiaie0 i. Para demostrar (1), dado que ai6= 0, la q-cadena cqes un ciclo si, y solo si, γi= 0 para i= 1, . . . , k. Como consecuencia de lo anterior, para probar la afirmación (3) basta notar que todo (q−1)-borde ∂q(cq)se encuentra en el módulo generado por el conjunto {a1e0 1, . . . , ake0 k}. Como ai6= 0, los elementos del conjunto anterior son independientes. Por último, veamos (2). Dado que aie0 i=∂q(ei),i= 1, . . . , k, se tiene que e0 1, . . . , e0 k∈Wq−1. Recíprocamente, sea cq−1= m X i=1 ηie0 i una (q−1)-cadena y supongamos que cq−1∈Wq−1. Entonces, cq−1satisface una ecuación de la forma λcq−1=∂q(cp) = k X i=1 γiaie0 i para algún λ∈R, con λ6= 0. Igualando los coeficientes de esta expresión junto con los correspondientes del cq−1arbitrario (multiplicado por λ) deducimos que ληi= 0 para i > k. Luego, ηi= 0 para i > k. Por tanto, {e0 1, . . . , e0 k}es una base de Wq−1. El Lema 1.27 es la pieza final para conseguir toda la información buscada. A continuación se recogen explícitamente sus consecuencias. Corolario 1.28. Con las notaciones anteriores, se verifican los siguientes hechos referentes a la forma normal de Smith de M(∂q): (1’) El rango de Zqson las columnas de ceros. (2’) El rango de Wq−1son las filas no nulas. (3’) Existe un isomorfismo que permite expresar la parte de torsión de Hq−1: Wq−1 Bq−1 ∼ =R (a1)⊕ · · · ⊕ R (ak). Demostración. Los puntos (1’) y (2’) son consecuencias inmediatas de los puntos (1) y (2) del Lema 1.27, respectivamente. Por su parte, el isomorfismo mencionado en el punto (3’) se deduce de los puntos (2) y (3) del Lema 1.27. 1.5. COMPUTABILIDAD 17 De aquí se sigue que la forma normal de M(∂q)proporciona los coeficientes de torsión del módulo de homología de Ken grado q−1: son las entradas no nulas y distintas de 1 de la forma normal. Esta forma normal también permite calcular el rango de Zq. Análogamente, de M(∂q+1)se obtiene el rango de Wq. Esto permite calcular el q-ésimo número de Betti, pues βq= rango(Zq)−rango(Wq). Por tanto, el q-ésimo módulo de homología Hqqueda completamente determinado por las matrices M(∂q)yM(∂q+1), ya que de ellas se extraen βqy los coeficientes de torsión, que conforman un sistema completo de invariantes. En consecuencia, hemos probado el siguiente teorema. Teorema 1.29. Los módulos de homología de un complejo simplicial Ksobre un dominio de ideales principales Rson algoritmicamente computables. La potencia de este resultado se comprueba fácilmente mediante un ejemplo sencillo. En particular, se pone de manifiesto que las únicas herramientas necesarias pertenecen al álgebra lineal. Ejemplo 1.30. Consideremos el complejo simplicial Krepresentado en la Figura 1.2. Tenemos que Kes de dimensión 2. Esto nos dice directamente que Hq(K;R)=0para q≥3. Resta por calcular la homología en grados 0, 1 y 2. En primer lugar, escogemos bases para C0(K;R),C1(K;R)yC2(K;R)orientando los símplices de todas las dimensiones. v0 v1 v2 v3 v4 a b c d e f σ Figura 1.2: El complejo simplicial K. El complejo simplicial Kúnicamente cuenta con el 2-símplice orientado σ= [v0, v1, v2]∈C2(K;R). Por su parte, una base para C1(K;R)está formada por los 6 símplices orientados denotados por a, b, . . . , f. Finalmente, los 5 vértices v0, v1, . . . , v4generan C0(K;R). Trabajaremos con coeficientes en el anillo R=Z. Procedemos a expresar en forma matricial el homomorfismo ∂2:C2(K;Z)→C1(K;Z). Para ello, calculamos ∂2(σ)=[v1, v2]−[v0, v2]+[v0, v1] =−b−c+a. Como {σ}es una base de C2(K;Z)y{a, b, c, d, e, f}es una base de C1(K;Z), representamos matricialmente el homomorfismo como la matriz de la izquierda, 18 CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL mientras que a la derecha está su correspondiente forma normal: σ a b c d e f         1 −1 −1 0 0 0         , σ a−b−c b c d e f         1 0 0 0 0 0         . De aquí deducimos que rango(Z2) = 0 yrango(W1) = 1. Nótese que el algoritmo utilizado para calcular la forma normal de Smith también permite obtener las nuevas bases, incluidas alrededor de la matriz. En el caso de M(∂1), esta matriz viene dada por abcdef v0 v1 v2 v3 v4       −1 0 −1 0 0 0 110100 0−1 1 0 −1 1 000−1 1 0 00000−1       , que en forma normal se expresa como a b f z1z2z3 v1−v0 v1−v2 v2−v4 v4−v3 v4       100000 010000 001000 000100 000000       , donde z1=d−b−f,z2=e+d−byz3=c+b−a. Así, rango(Z1)=2yrango(W0)=4. Finalmente, ∂0= 0 ya que C−1(K;Z) = 0. Esto nos dice que rango(Z0) = rango(C0(K;Z)) = 5. Teniendo en cuenta que W2= 0 al tenerse C3(K;Z)=0, la fórmula para calcular los números de Betti vista anteriormente arroja los siguientes resultados: β2= 0 −0=0, β1= 2 −1=1, β0= 5 −4=1. Y puesto que todas las formas normales tienen unos en las diagonales, esto provoca que no haya coeficientes de torsión y, en consecuencia, que los módulos de homología no tengan parte de torsión. Por tanto: H2(K;Z)=0, H1(K;Z) = Z, H0(K;Z) = Z. 1.5. COMPUTABILIDAD 19 Ejemplo 1.31. Veamos ahora un ejemplo donde los módulos de homología tienen torsión. Consideremos la triangulación del plano proyectivo que se muestra en la Figura 1.3. Hemos dado orientaciones a todos los símplices que aparecen en ella para fijar las bases. Las aristas muestran sus correspondientes orientaciones. Con el fin de no llenar el dibujo con demasiadas notaciones, no se indican ni los nombres ni las orientaciones de todos los 2-símplices. Todos tienen orientación antihoraria y se nombran de abajo a arriba y de izquierda a derecha. v0 v1v2 v3 v4v5 v0 v1 v2 a a b b c c d ef ghij klm n˜n σ5 Figura 1.3: Triangulación de RP2tomada de [1]. Nuevamente, estamos ante un complejo simplicial de dimensión 2, por lo que Hq(RP2;R) = 0 para q≥3. Esta vez, veremos el efecto de trabajar en homología con coeficientes en anillos diferentes cuando aparecen elementos de torsión. En primer lugar, tomamos como antes el anillo R=Z. La matriz asociada a ∂2:C2(RP2;Z)→C1(RP2;Z)y su forma normal vienen dadas, respectivamente, por M(∂2) =              −1 0 0 0 0 0 0 0 0 −1 0 0 0 0 0 −1−1 0 0 0 0−1 0 0 0 0 0 −1 0 0 1−1 0 0 0 0 0 0 0 0 −1 0 1 0 0 0 0 0 0 0 0 1 0 0 −1 0 0 0 0 0 0 0 −1 0 0 1 0 0 0 0 0 0 1 −1 0 0 0 0 0 0 0 0 0 1 −1 0 0 0 0 0 0 0 0 0 1 0 −1 0 0 0 0 0 0 0 0 −1 0 1 0 0 0 0 0 −1 0 0 0 0 1 0 000000100−1 0 0 0 0 0 0 0 −1 1 0 0 0 0 0 0 0 0 0 −1 1              ,           1000000000 0100000000 0 0 10000000 0001000000 0 0 0 0 100000 0000010000 0000001000 000000010 0 0000000010 0000000002 0000000000 0000000000 0000000000 0000000000 0000000000           . La forma normal de M(∂2)consta de una matriz identidad de orden 9 y un elemento de torsión (un 2) que aparecerá reflejado en H1(RP2;Z). Deducimos que rango(Z2) = 0 yrango(W1) = 10. 20 CAPÍTULO 1. HOMOLOGÍA SIMPLICIAL La matriz del operador borde ∂1es M(∂1) =   −1 0 1 −1 0 0 0 0 0 0 0 0 0 −1−1 1−1 0 0 −1 0 −1 0 0 0 0 0 −1 0 0 0 1 −1 0 0 −1 0 0 0 −1−1 0 0 0 0 0 0 0 1 1 1 0 −1−1 0 0 0 0 0 0 00000011001−1 0 1 0 000000001101101  , con forma normal   10 0 0 0 0 0 0 0 0 0 0 0 0 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 00010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  . Concluimos que rango(Z1) = 10 yrango(W0) = 5. Nuevamente, rango(Z0) = rango(C0(RP2;Z)) = 6, ya que ∂0= 0, y W2= 0 al tenerse C3(RP2;Z) = 0. Obtenemos los siguientes números de Betti: β2= 0 −0 = 0, β1= 10 −10 = 0, β0= 6 −5=1. Y, en consecuencia, los siguientes grupos de homología: H2(RP2;Z)=0, H1(RP2;Z)=0⊕Z 2Z=Z2, H0(RP2;Z) = Z. Comparemos ahora estos resultados con los que se obtienen al considerar coeficientes en el cuerpo Z2. Los módulos de homología se convierten en espacios vectoriales, luego carecerán de torsión. En efecto, las matrices son exactamente las mismas, tomando las entradas módulo 2. Tenemos: rango(Z2)=1,rango(W1) = 9; rango(Z1) = 10,rango(W0) = 5. Además, rango(Z0) = 6 yrango(W2)=0. Luego: β2= 1 −0 = 1, β1= 10 −9=1, β0= 6 −5=1. Y, en consecuencia, los siguientes son los Z2-módulos de homología de RP2: H2(RP2;Z2) = Z2, H1(RP2;Z2) = Z2, H0(RP2;Z2) = Z2. En particular, los módulos de homología de grado 2 con coeficientes en Zy en Z2ponen de manifiesto que el plano proyectivo real es Z2-orientable (en general, toda variedad lo es), pese a ser una superficie no orientable. Además, efectivamente desaparece la torsión en grado 1. Trabajar con coeficientes en Z2hace también los cálculos más sencillos, al no tener que preocuparse por los signos. Esto lleva consigo detrás el hecho de olvidarse de la orientación en los símplices. Este último ejemplo también evidencia el problema que acarrea la discretización de espacios. Aunque esto hace posible su manipulación por máquinas, al trabajar en un espacio relativamente sencillo como el plano proyectivo real ya hay que manipular matrices de un tamaño considerable, con los costes computacionales que ello conlleva. Capítulo 2 Construcción de complejos simpliciales La enorme cantidad de datos de todo tipo que se produce cada día hace necesaria la aparición de técnicas de análisis para su posterior tratamiento e interpretación. Los avances tecnológicos han permitido que recabar datos sea una tarea relativamente sencilla en todos los ámbitos de la ciencia moderna. De esta manera, el desarrollo de todos estos métodos de obtención de datos debe traer consigo el nacimiento de nuevas técnicas que sirvan para extraer la información relevante que contengan estos datos. Por ello, este capítulo expone varias formas de asociar un complejo simplicial a una nube de puntos que represente los datos a estudiar. Estas construcciones básicas permiten utilizar las técnicas homológicas presentadas previamente. Además, sirven para desarrollar las nuevas herramientas de análisis topológico de datos que se exponen en el próximo capítulo. La estructura de este capítulo sigue el trabajo [5] de G. Carlsson y las definiciones allí expuestas. También se incluyen algunas explicaciones y observaciones recogidas en [37, 38]. 2.1. Complejo de Čech El primer objetivo planteado es conseguir asociar un complejo simplicial (abstracto) a la nube de puntos de interés que queramos estudiar. Aunque empezaremos considerando espacios topológicos arbitrarios, enseguida nos restringiremos a espacios métricos. Esto es razonable porque la propia naturaleza de los datos hace que lleven consigo alguna métrica detrás. Además, no es una gran restricción puesto que las nubes de datos están habitualmente en espacios que son, de hecho, euclídeos. Para empezar, damos la definición de un tipo especial de recubrimiento que usaremos para construir un primer complejo simplicial más adelante. 21 22 CAPÍTULO 2. CONSTRUCCIÓN DE COMPLEJOS SIMPLICIALES Definición 2.1. Sean Xun espacio topológico y U={Ui}i∈Iun recubrimiento abierto de X. Decimos que Ues un buen recubrimiento abierto o, simplemente, un buen recubrimiento de Xsi todos los abiertos Ui∈ U y todas las intersecciones finitas y no vacías Ui1∩ · · · ∩ Uiqson contráctiles. Figura 2.1: Dos recubrimientos distintos para S1, con los abiertos representados en el espacio ambiente. A la izquierda, un recubrimiento por abiertos cuya intersección tiene dos componentes conexas. A la derecha, un buen recubrimiento. La condición de contractibilidad hace que posiblemente sean necesarios más abiertos para recubrir el espacio. Con esto se gana un estudio local más detallado, con lo que se captura de forma más fiel y precisa la forma del espacio. El complejo de Čech pretende reconstruir un espacio mediante un recubrimiento abierto del mismo, pero de forma que sea computacionalmente más fácil de trabajar con él. Previamente hacemos una construcción más general, válida para cualquier recubrimiento (no necesariamente abierto ni bueno) de un espacio topológico. Definición 2.2. Sean Xun espacio topológico y U={Ui}i∈Iun recubrimiento de X. El nervio de U, denotado por N(U), es el complejo simplicial abstracto cuyo conjunto de vértices es Iy para el que una familia de índices {i0, . . . , iq} ⊂ I forma un q-símplice si, y solo si, Ui0∩ · · · ∩ Uiq6=∅. Es obvio que los conjuntos unitarios pertenecen a N(U)(se entiende que los conjuntos de Uson no vacíos) y que si {i0, . . . , iq} ∈ N (U), entonces todo subconjunto de {i0, . . . , iq}forma también un símplice ya que la intersección de los conjuntos asociados a esos índices es no vacía al haber menos elementos. Por tanto, el nervio de un recubrimiento es efectivamente un complejo simplicial abstracto. El complejo de Čech es un tipo especial de nervio. Definición 2.3. Sean Xun espacio topológico y U={Ui}i∈Iun buen recubrimiento de X. Llamamos complejo de Čech al nervio de U. Aunque resulta evidente que la realización geométrica del complejo de Čech asociado al buen recubrimiento de un espacio no preserva la forma ni el tamaño de ese espacio, sí se tiene que respeta el tipo de homotopía. Como hemos establecido en el Teorema 1.19, esto último es suficiente al trabajar en homología. 2.1. COMPLEJO DE ČECH 23 Figura 2.2: En rojo están los respectivos nervios de los recubrimientos anteriores de S1. Como el recubrimiento de la derecha es bueno, su nervio es un complejo de Čech. Existen varios enunciados del próximo resultado, pero nos interesa el siguiente por su interpretación en el lenguaje de complejos de Čech. Teorema 2.4 (del nervio).Sea Uun buen recubrimiento finito de un espacio topológico X. Entonces, la realización geométrica de su nervio, |N (U)|, tiene el mismo tipo de homotopía que X. La demostración puede encontrarse en [30, Teorema 15.21]. Como anunciábamos, gracias a este teorema podemos afirmar que el complejo de Čech de un buen recubrimiento finito es homotópicamente equivalente a la unión de los abiertos del recubrimiento. Existe un tipo especial de complejo de Čech, que es el que se suele usar cuando el espacio topológico es en realidad un espacio métrico (X, d). Esta es la situación con la que nos encontraremos al tratar con datos: la nube de puntos de interés posiblemente se halla en algún espacio euclídeo Rm. Dado un ε > 0, para cada x∈Xtenemos el conjunto B(x, ε) = {y∈X:d(x, y)< ε}, que es la bola abierta de centro xy radio ε. Entonces, un recubrimiento abierto de Xviene dado por la familia B(X, ε) = {B(x, ε)}x∈Xpara cada ε > 0. Más generalmente, si Y⊂Xes un subconjunto tal que X=Sy∈YB(y, ε), podemos construir el nervio del recubrimiento {B(y, ε)}y∈Y. Denotamos esta construcción por ˇ C(Y, ε)y la llamamos complejo de Čech asociado a Ycon parámetro ε. En general, estos recubrimientos no son necesariamente buenos. Sin embargo, el siguiente resultado establece condiciones para la existencia de un buen recubrimiento por bolas abiertas. La demostración de la primera parte se debe a Jean-Claude Hausmann y puede consultarse en [26], donde se deja abierta la pregunta sobre la veracidad de la segunda afirmación. En [33], Janko Latschev da una respuesta afirmativa probando un resultado más fuerte. Teorema 2.5. Sea Muna variedad riemanniana compacta. Entonces, existe un ε0>0de forma que B(M, ε)es un buen recubrimiento de Myˇ C(M, ε)tiene el mismo tipo de homotopía que Mpara todo ε≤ε0. Además, para cada ε≤ε0 existe un subconjunto finito Y⊂Mtal que el subcomplejo ˇ C(Y, ε)⊂ˇ C(M, ε) también tiene el mismo tipo de homotopía que M. 24 CAPÍTULO 2. CONSTRUCCIÓN DE COMPLEJOS SIMPLICIALES Dicho de otro modo, si el espacio es suficientemente bueno, existe un conjunto finito de puntos que tiene asociado un recubrimiento (también finito) cuyo complejo de Čech captura toda la información relevante sobre la estructura topológica del espacio original, para parámetros pequeños. Este conjunto finito de puntos es el que interesa en la práctica para que el complejo de Čech sea finito. 2.2. Complejo de Vietoris-Rips No obstante, pese a sus buenas propiedades teóricas, en la práctica ocurre que el complejo de Čech es computacionalmente inmanejable. Por ejemplo, puede ocurrir que haya muchas redundancias en el recubrimiento. Dicho de otro modo, es posible que varios elementos del recubrimiento se solapen, creando símplices innecesarios de distintas dimensiones y que realmente no aportan nada, más allá de gasto en almacenamiento. Figura 2.3: En el dibujo está representado un pequeño trozo de algún espacio métrico sin agujeros. A la izquierda, las bolas forman parte de un recubrimiento abierto del espacio. El elevado número de intersecciones provocará que el complejo de Čech tenga un gran número de símplices de distintas dimensiones. A la derecha, sin embargo, un único abierto recubre exactamente el mismo pedazo de espacio que las bolas. En ese caso, el abierto solo aporta un 0-símplice al complejo de Čech. La solución que se propone a este problema es poder recuperar el complejo al completo únicamente por medio de la información sobre la distancia entre vértices. Esto hace que no sea necesario comprobar si existen intersecciones no vacías en todas las subcolecciones de B(X, ε), donde (X, d)es el espacio métrico en el que estamos trabajando. El complejo de Vietoris-Rips es una variante del complejo de Čech que implementa esta solución. Definición 2.6. Sea (X, d)un espacio métrico. Dado un ε > 0, llamamos complejo de Vietoris-Rips asociado a Xcon parámetro ε, y lo denotamos por V R(X, ε), al complejo simplicial cuyos vértices son los puntos de Xy en el que los puntos {x0, . . . , xq}forman un q-símplice si, y solo si, d(xi, xj)≤εpara todo 0≤i, j ≤q. Como en el caso del complejo de Čech, es obvio que el complejo de VietorisRips es un complejo simplicial abstracto, pues d(x, x)=0≤εpara todo x∈X y la distancia entre dos puntos de cualquier subconjunto de {x0, . . . , xq}sigue siendo εo menos. 2.2. COMPLEJO DE VIETORIS-RIPS 25 La primera observación que debe hacerse es que los conjuntos de vértices para ambos complejos son idénticos. Las diferencias empiezan a aflorar al considerar distintos valores del parámetro ε. Por ejemplo, la Figura 2.4 muestra cinco puntos, cada uno con una bola de radio un determinado εcentrada en él. Figura 2.4: A la izquierda, una nube de cinco puntos con bolas abiertas del mismo radio centradas en ellos. En el centro, el complejo de Čech para el parámetro elegido. A la derecha, el complejo de Vietoris-Rips para el parámetro elegido. En este caso, el complejo de Čech estaría formado por cinco 0-símplices y tres 1-símplices. Para el complejo de Vietoris-Rips solo dos puntos están lo suficientemente cerca entre sí como para que aparezca un 1-símplice, luego tenemos cinco 0-símplices y un único 1-símplice. Consideremos de nuevo los cinco puntos anteriores, pero incrementemos el parámetro εun poco para ver cómo afecta a los complejos. La nueva situación está reflejada en la Figura 2.5. Figura 2.5: A la izquierda, el complejo de Čech con el nuevo parámetro. A la derecha, el complejo de Vietoris-Rips con el nuevo parámetro. Con el nuevo parámetro, el complejo de Čech es mucho más grande: cinco 0-símplices, ocho 1-símplices, cinco 2-símplices y un 3-símplice. Por su parte, el complejo de Vietoris-Rips tan solo añade un 1-símplice más con respecto a la situación anterior, pues los puntos no están lo suficientemente cerca como para que se generen más símplices. Estas consideraciones deberían poner aún más de manifiesto la distinta naturaleza de los dos complejos para un mismo parámetro. El complejo de Čech 32 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE Denotemos por R=R∪ {−∞,+∞} el conjunto totalmente ordenado que denominamos recta real ampliada. Definición 3.5. Llamamos R-filtración ascendente de un complejo de cadenas (C•, ∂•)a una colección de complejos de cadenas {(FrC•, ∂•)}r∈Rtal que: (i)(FrC•, ∂•)es un subcomplejo de cadenas de (C•, ∂•)para todo r∈R. (ii)(FrC•, ∂•)⊂(Fr0C•, ∂•)para r≤r0, con r, r0∈R. (iii)Tr∈R(FrC•, ∂•) = ∅. (iv)Sr∈R(FrC•, ∂•)=(C•, ∂•). Un complejo de cadenas junto con una R-filtración se denomina complejo de cadenas R-filtrado. De forma equivalente, las propiedades (iii)y(iv) de la definición se reescriben, respectivamente, como (F−∞C•, ∂•) = ∅y(F+∞C•, ∂•)=(C•, ∂•). Nótese que estamos denotando por ∂qla diferencial en grado qde los subcomplejos de cadenas de la filtración, que se corresponden con las respectivas restricciones del operador borde del complejo de cadenas. Esto significa que la diferencial conserva la filtración, en el sentido de que ∂q(FrCq)⊂ FrCq−1. Resulta evidente que en la definición de R-filtración se puede sustituir R por cualquier otro conjunto totalmente ordenado en el que todo subconjunto tenga supremo e ínfimo. En este caso, la recta real ampliada es conveniente para trabajar con las filtraciones que proporcionan los complejos de Čech y de Vietoris-Rips, cuyos parámetros toman valores reales positivos. Lema 3.6. Sea (C•, ∂•)un complejo de cadenas R-filtrado. Para toda q-cadena α∈Cqexiste un r0∈Rtal que sup{r0:α /∈ Fr0Cq}=r0= ´ınf{r00 :α∈ Fr00 Cq}. Demostración. Es consecuencia de las propiedades que cumple una R-filtración por definición y del orden de R. En primer lugar, tenemos garantizada la existencia de supremos e ínfimos en R. Llamando r0= sup{r0:α /∈ Fr0Cq}ys0= ´ınf{r00 :α∈ Fr00 Cq}, es claro que r0≤s0, pues una vez aparece α∈Cqen la filtración no puede desaparecer por la propiedad (ii) de la definición. Finalmente, por ser supremo del conjunto, r0+ε≥s0para todo ε > 0; luego r0≥s0. Por tanto, r0=s0. 3.1. FILTRACIONES 33 Usemos nuevamente la notación condensada Cr •,Zr •,Br •yHr •para representar los módulos de cadenas, ciclos, bordes y homología para el r-ésimo elemento de una R-filtración. En analogía con los complejos simpliciales filtrados por índices naturales, un complejo de cadenas R-filtrado también proporciona inclusiones FrC•,→ Fr+lC•para cada l≥0, que inducen los homomorfismos en homología ηr,l •:Hr •−→ Hr+l •. Definición 3.7. Se define el q-ésimo módulo de l-persistencia de FrCqcomo la imagen del homomorfismo inducido por la inclusión: Hr,l q:= Im ηr,l q. La definición de los números de Betti persistentes es completamente análoga, así como la reinterpretación dada por la Proposición 3.3 en términos de Zr qy Br+l q. En este sentido, Hr,l qcaracteriza aquellos q-ciclos de FrCqque no son borde de ninguna (q+ 1)-cadena del complejo Fr+lCq, que es más grande. De esta forma, recordemos que si α∈Zr q, entonces αrepresenta una clase de homología [α]∈Hr q. Como Zr q⊂Zr0 qpara r0≥r,αtambién representa una clase de homología en Hr0 q(que seguimos denotando por [α]). Pero puede ocurrir que [α]6= 0 en Hr qy que [α]=0en Hr0 q. Veamos cómo se comportan los índices de una R-filtración con el nacimiento y muerte de clases de homología. Lema 3.8. Sea (C•, ∂•)un complejo de cadenas R-filtrado. Para todo q-ciclo α∈Zq, el conjunto Iα:= {r∈R: 0 6= [α]∈Hr q} o bien es vacío o bien es un intervalo. Demostración. Sean α∈Zqun ciclo y r1el valor dado por el Lema 3.6. Tenemos dos posibilidades: que el ciclo αsea también un borde o que no lo sea. Si α∈Bq, entonces existe un β∈Cq+1 tal que ∂q+1(β) = α. Sea r2el correspondiente valor dado por el Lema 3.6 para β. Como β∈ FrCq+1, para algún r≥r2, esto implica que ∂q+1(β) = α∈ FrCq. Por tanto, necesariamente debe ocurrir que r2≥r1. De esta forma, αrepresenta una clase no nula de homología exactamente en el intervalo (posiblemente vacío) que empieza en r1y termina en r2. Este intervalo contiene el extremo inicial r1si, y solo si, α∈ Fr1Cq, y contiene el extremo final r2si, y solo si, β /∈ Fr2Cq+1. Si αno es un q-borde proveniente de una (q+ 1)-cadena, entonces αrepresenta una clase no trivial de homología en FrCqexactamente cuando restá en el intervalo {s:s≥r1}o el intervalo {s:s > r1}, que empieza en r1y termina en el infinito. Como antes, r1pertenece al intervalo si, y solo si, α∈ Fr1Cq. Ejemplo 3.9 (Filtración asociada al complejo de Čech).Supongamos que el conjunto X={x1, . . . , xn}es un muestreo de puntos de algún espacio métrico (M, d). Sea K=ˇ C(X, +∞)el mayor complejo simplicial que se puede elaborar con el conjunto de vértices X. 34 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE La colección de complejos de Čech {ˇ C(X, ε)}ε≥0con distintos valores no negativos del parámetro proporciona una R-filtración, que pasamos a describir. Cada uno de los elementos de la familia anterior es un complejo simplicial, que por brevedad denotaremos por Kε. Fijado un anillo R, para cada uno de estos complejos simpliciales, basta tomar el correspondiente complejo de cadenas (C•(Kε;R), ∂ε •)para obtener la filtración. En efecto, (C•(Kε;R), ∂ε •)es un subcomplejo de cadenas de (C•(K;R), ∂•), puesto que Kεes un subcomplejo simplicial de Kpara todo ε≥0, y (C•(Kε;R), ∂ε •)⊂(C•(Kε0;R), ∂ε0 •) para ε≤ε0, ya que ˇ C(X, ε)⊂ˇ C(X, ε0). Además, Kε=∅para todo ε≤0y, si δes el diámetro del conjunto X, entonces Kε=Kpara ε > δ 2. De esta manera, la colección {(C•(Kε;R), ∂ε •)}ε≥0 es una R-filtración del complejo de cadenas (C•(K;R), ∂•). Ejemplo 3.10 (Filtración asociada al complejo de Vietoris-Rips).Supongamos que X={x1, . . . , xn}es de nuevo un muestreo de puntos de algún espacio métrico (M, d). La colección de complejos de Vietoris-Rips {V R(X, ε)}ε≥0con distintos valores no negativos del parámetro proporciona otra R-filtración. Nuevamente, por simplicidad, denotamos por Kεcada uno de los complejos simpliciales de la familia anterior y tomamos K=V R(X, +∞), el mayor complejo simplicial que se puede elaborar con el conjunto de vértices X. Para un anillo Rfijado, construimos el complejo de cadenas asociado a cada complejo simplicial, (C•(Kε;R), ∂ε •), y conseguimos así una nueva R-filtración del complejo de cadenas (C•(K;R), ∂•), que esta vez vendrá dada de la siguiente forma: {(C•(Kε;R), ∂ε •)}ε≥0. Las comprobaciones de que verifica la definición son inmediatas y análogas a las del complejo de Čech (en este caso, Kε=Kpara ε > δ, siendo δel diámetro del conjunto X). 3.2. Códigos de barras Para visualizar fácilmente la homología persistente se usan los llamados códigos de barras. Estas representaciones en el plano incluyen los índices ascendentes de la filtración en el eje horizontal y los distintos módulos de homología en el eje vertical. La homología persistente se codifica mediante ciertos intervalos horizontales, que son representantes arbitrarios de cada clase. Los extremos de estos intervalos indican los momentos de la filtración en los que nace y muere cada clase de homología. Siguiendo el artículo de P. Bubenik y P. T. Kim [4], damos una definición más formal de un código de barras y un resultado sobre los códigos de barras asociados a las filtraciones de Čech y Vietoris-Rips. 3.2. CÓDIGOS DE BARRAS 35 3.2.1. Intervalos de persistencia Los códigos de barras están formados por los intervalos durante los que persisten o viven las clases no triviales de homología a través de una filtración. Definición 3.11. Sean (C•, ∂•)un complejo de cadenas R-filtrado y α∈Zqun ciclo. Se define el intervalo de persistencia representado por αcomo el intervalo Iαdado por el Lema 3.8. Obviamente, de la definición de Iαse sigue que si α0=α+∂q+1(β)para algún β∈Cq+1, entonces Iα0=Iαya que [α0]=[α]y estas serán clases no nulas para los mismos parámetros de la R-filtración. Recíprocamente, puede ocurrir que [α]6= [α0]y, sin embargo, Iα=Iα0. Por tanto, tiene sentido la siguiente definición. Definición 3.12. Para un complejo de cadenas R-filtrado (C•, ∂•)se define su código de barras asociado como el multiconjunto {Jα}α∈S, donde S⊂Z•es un cierto subconjunto de ciclos, tal que: (i)Jαes un subintervalo de Iα. (ii) Para todo r∈R, el conjunto {[α]∈Hr •:α∈S, r ∈Jα}está formado por los generadores de Hr •. La definición anterior es bastante oscura en una primera lectura. Para desentrañarla, vamos a detenernos un momento a analizar su significado. En primer lugar, el subconjunto Sde los ciclos tiene como función evitar los intervalos de persistencia redundantes que habría para ciclos homólogos, tal y como indica el comentario previo a la definición. En este sentido, el hecho de que un código de barras se defina como un multiconjunto es porque pueden nacer y morir simultáneamente clases de homología distintas que generen el mismo intervalo, provocando que este deba aparecer con multiplicidad mayor que uno. Por otra parte, la selección de los subintervalos Jα⊂Iαse hace necesaria porque al avanzar en la filtración se ganan nuevas clases de homología y se pierden otras al volverse triviales o fusionarse con una clase de homología más antigua. Por ejemplo, supongamos que las clases de homología [σ]y[τ]nacen, respectivamente, en FrCqyFr0Cq, con r≤r0. Ambas clases se fusionan si existen l, l0≥0tales que ηr,l q([σ]) = ηr0,l0 q([τ]). En ese caso, como la clase [σ] es más antigua, el código de barras refleja únicamente un subintervalo Jτ⊂ Iτ(desde que [τ]nace hasta que se fusiona con [σ]) en vez del intervalo de persistencia Iτal completo; en otras palabras, mientras es un generador de la homología. Por tanto, los intervalos de persistencia que aparecen íntegros en el código de barras son aquellos correspondientes a las clases de homología primigenias, que son las que no se fusionan con otras. Ejemplo 3.13. La Figura 3.2 muestra el código de barras asociado a la filtración de la Figura 3.1. Los generadores de H0reflejan las componentes conexas del complejo simplicial. Las dos barras superiores del código de barras representan las componentes conexas asociadas a los dos 0-símplices que aparecen en la 36 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE H2 H1 H0 K0K1K2K3K4K5K6K7 Figura 3.2: Código de barras correspondiente a la filtración de la Figura 3.1. filtración antes de K1. Antes de K3aparece un 1-símplice que une estos vértices, así que las dos clases de homología se fusionan y permanece la primera que apareció en la filtración. De forma similar, otras tres clases aparecen en distintos puntos de la filtración y acaban fusionándose con la primera, que es la que perdura a lo largo del tiempo. Para H1, un primer generador nace cuando antes de K4se cierra un 1-ciclo, creando un agujero. Más adelante, aparece una nueva arista y este agujero se divide en dos. En este caso, el nuevo generador se vuelve trivial cuando se rellena la cara con un 2-símplice. En vista del código de barras, podemos constatar que existen dos características topológicas persistentes en la filtración. El resto es ruido topológico. 3.2.2. Filtraciones de Čech y Vietoris-Rips En un primer momento, tal y como se establece en la demostración del Lema 3.8, el intervalo de persistencia de un ciclo puede contener sus dos extremos, solo uno de ellos o ninguno. Sin embargo, las construcciones específicas de las filtraciones de Čech y Vietoris-Rips permiten concretar los tipos de intervalos de persistencia asociados a sus ciclos. El siguiente resultado proporciona el valor exacto del número r0∈Rdel Lema 3.6 para las filtraciones de Čech y Vietoris-Rips. Lema 3.14. Sean (M, d)un espacio métrico y X={x1, . . . , xn}un muestreo de puntos de M. Sea {(FrC•, ∂•)}r∈Runa filtración de Čech o de Vietoris-Rips y sea α=Pm i=0 αiσiuna q-cadena, donde σi= [xi0, . . . , xiq]es un q-símplice. (1) Para la filtración de Čech sea r0= m´ax 0≤i≤m´ınf{εi:existe un x∈Mtal que xi0, . . . , xiq∈B(x, εi)}. Entonces, α /∈ Fr0Cqpara todo r0≤r0yα∈ Fr00 Cqpara todo r00 > r0. 3.3. ESTRUCTURAS ALGEBRAICAS 37 (2) Para la filtración de Vietoris-Rips sea r0= m´ax 0≤i≤mm´ax 0≤j,k≤qd(xij, xik). Entonces, α /∈ Fr0Cqpara todo r0< r0yα∈ Fr00 Cqpara todo r00 ≥r0. Demostración. El Lema 3.6 proporciona la existencia de un r0∈Rque verifica la tesis. Veamos que, en efecto, este valor es el que se indica en el enunciado para cada filtración. En primer lugar, nótese que para construir la q-cadena α=Pm i=0 αiσien un complejo de la filtración es necesario y suficiente que todos los elementos de la familia compuesta por los msímplices orientados de dimensión qdada por [xi0, . . . , xiq]0≤i≤mestén presentes en el complejo Fr0Cqde la filtración. Para la filtración de Čech, los puntos xi0, . . . , xiqforman un q-símplice si las correspondientes bolas de radio r0centradas en los puntos tienen intersección común no vacía. Si tomamos un punto x∈Men esa intersección, B(x, r0) deberá contener también los vértices del símplice. Es claro que debemos tomar el radio más pequeño posible para cada grupo de qpuntos (es un ínfimo por ser las bolas abiertas) y después tomar el máximo de todos ellos, pues tiene que ser el más grande posible entre los mismos (en otro caso, algún grupo de qvértices no formaría un símplice). Para la filtración de Vietoris-Rips, los puntos xi0, . . . , xiqdeben estar todos a distancia r0o menos de los demás para formar símplice. Tomando el primer máximo nos aseguramos de que los puntos definan un símplice. Finalmente, el segundo máximo es necesario para que todos los grupos de qvértices formen un símplice. Proposición 3.15. Sea {(FrC•, ∂•)}r∈Runa filtración de Čech o de VietorisRips. Dado un q-ciclo α∈Zq, el intervalo de persistencia de αo bien es vacío o bien es de la forma (1) (r1, r2)o(r1,+∞]para la filtración de Čech. (2) [r1, r2)o[r1,+∞]para la filtración de Vietoris-Rips. Demostración. La misma demostración vale en ambos casos. Para determinar si un extremo pertenece o no al intervalo de persistencia, tenemos en cuenta las observaciones hechas en la demostración del Lema 3.8. Si α∈Zqes un q-ciclo, por el Lema 3.6 existe un intervalo de persistencia (posiblemente vacío) para α. Si αno es un borde, basta aplicar el Lema 3.14 aα. Si α∈Bqes un borde, existe un β∈Cq+1 tal que ∂q+1(β) = α; basta entonces aplicar el Lema 3.14 a β. 3.3. Estructuras algebraicas Los módulos de homología persistente se pueden englobar en los conocidos como módulos de persistencia. Además, veremos que los módulos de persistencia están relacionados con otra estructura que llamaremos complejo de persistencia. 38 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE El estudio de la homología persistente desde este punto de vista permite dar algunos resultados interesantes que se relacionarán con los códigos de barras. Este hecho es importante, pues ya hemos visto que los códigos de barras recogen la información relevante de la homología persistente. Como ocurría en la homología simplicial, el teorema de estructura vuelve a ser clave para relacionar conceptos y establecer resultados. 3.3.1. Módulos y complejos de persistencia Las siguientes definiciones son generalizaciones de las presentadas en [41], donde se trabaja directamente con filtraciones con índices naturales. En la presente sección, empezamos desarrollando la teoría para conjuntos de índices arbitrarios con una relación de orden total y, posteriormente, nos restringiremos aN. Como en capítulos previos, Res un anillo conmutativo y unitario. Definición 3.16. Sea (I, ≤)un conjunto totalmente ordenado. Un R-módulo de persistencia parametrizado por Ies una familia de R-módulos {Mi}i∈Ijunto con homomorfismos de R-módulos {ϕi→j:Mi→Mj}i≤jtales que: (i)ϕi→i= idMipara todo i∈I. (ii)ϕj→k◦ϕi→j=ϕi→kpara todo i≤j≤k. Una definición completamente análoga a la anterior permite establecer lo que es un complejo de persistencia. Definición 3.17. Sea (I, ≤)un conjunto totalmente ordenado. Un complejo de persistencia parametrizado por Ies una familia de complejos de cadenas {(Ci •, ∂i •)}i∈Isobre Rjunto con aplicaciones de cadenas {fi→j •:Ci •→Cj •}i≤j tales que: (i)fi→i •= idCi •para todo i∈I. (ii)fj→k •◦fi→j •=fi→k •para todo i≤j≤k. Notación 3.18.Anteriormente, hemos usado otra notación para los superíndices de las aplicaciones cuando el conjunto de índices era NoR. En esos casos particulares, como hay definida una operación suma y existe un elemento neutro para la misma, los superíndices separados por comas indicaban el índice filtrante de inicio y el número de pasos que se avanza en la filtración. Para conjuntos de índices arbitrarios, al carecer en general de una operación suma, la notación mediante las flechas indica los índices filtrantes de inicio y final. El siguiente diagrama muestra cómo podría ser un pequeño trozo de un complejo de persistencia, fijados los grados filtrantes. Cada columna es un complejo de cadenas, mientras que las aplicaciones de cadenas conectan por filas las etapas fijadas de la filtración. 3.3. ESTRUCTURAS ALGEBRAICAS 39 . . . ∂i q+1  . . . ∂j q+1  · · · f·→i q //Ci q fi→j q // ∂i q  Cj q ∂j q  fj→· q //· · · · · · f·→i q−1 //Ci q−1 fi→j q−1 // ∂i q−1  Cj q−1 fj→· q−1 // ∂j q−1  · · · . . .. . . Ejemplo 3.19. Un complejo simplicial I-filtrado junto con las inclusiones de símplices forman un complejo de persistencia parametrizado por I. Por su parte, la homología de un complejo de persistencia da lugar a un módulo de persistencia parametrizado por I, siendo las aplicaciones ηi→j •definidas previamente los homomorfismos requeridos en cada grado homológico. 3.3.2. Clasificación sobre cuerpos El siguiente paso es clasificar, salvo isomorfismo, los módulos de persistencia sobre cuerpos. Los resultados de este apartado, de gran importancia, se deben a la extensión que A. Zomorodian y G. Carlsson [41] hicieron de un algoritmo para calcular la persistencia. El algoritmo original estaba definido únicamente para complejos simpliciales tridimensionales y coeficientes en Z2. La extensión de este algoritmo se hace viendo un sistema inductivo de espacios vectoriales como una única entidad: un módulo de persistencia. Esto permite generalizar la clasificación de sistemas inductivos de espacios vectoriales tridimensionales sobre Z2a dimensiones arbitrarias y cualquier cuerpo. Además, veremos que no existe una clasificación así de simple para sistemas inductivos de módulos sobre un anillo arbitrario. Estos teoremas de clasificación exigen una condición de finitud en las estructuras que manejamos. Definición 3.20. Un módulo de persistencia M={Mi, ϕi→j}i≤jparametrizado por Isobre un anillo Rse dice de tipo finito si cada R-módulo Mies finitamente generado como R-módulo y si existe un n∈Ital que para todo j≥nlas aplicaciones ϕn→json isomorfismos. Definición 3.21. Un un complejo de persistencia C={Ci •, fi→j •}i≤jparametrizado por Isobre un anillo Rse dice de tipo finito si cada complejo de cadenas Ci qes finitamente generado como R-módulo y si existe un n∈Ital que para todo j≥nlas aplicaciones fn→j •son isomorfismos. 40 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE Nota 3.22.Como los complejos simpliciales considerados en este trabajo son finitos, cualquier filtración genera un complejo de persistencia de tipo finito cuya homología es un módulo de persistencia de tipo finito. En lo que sigue, nos centraremos en módulos y complejos de persistencia parametrizados por Ny, más adelante, comentaremos los parametrizados por R, pues son los casos de interés que estamos manejando. En primer lugar, damos una estructura de R[t]-módulo a los módulos de persistencia parametrizados por N. Para ello, equipamos R[t]de una estructura de anillo graduado tomando la descomposición R[t] = M i∈N ti·R, donde ti·R={rti:r∈R}. El producto de polinomios cumple la condición de graduación: (ti·R)(tj·R)⊂ti+j·R. Esto permite dotar de una estructura de módulo graduado sobre el anillo de polinomios R[t]a cualquier módulo de persistencia M={Mi, ϕi,j}parametrizado por Ncomo M=M i∈N Mi, donde la acción de tsobre Mviene dada por la extensión lineal de t·mi=ϕi,1(mi) para todo mi∈Mi. Así, (ti·R)Mj⊂Mi+j. En otras palabras, la acción de taumenta el grado en una unidad. En el caso de un complejo de persistencia que derive de la filtración de un complejo simplicial, la acción del anillo de polinomios conecta la homología a través de los distintos complejos de la filtración. Es por ello que las propiedades algebraicas de este objeto contienen la información de los módulos de homología persistente de la filtración. Para poder aplicar el Teorema 1.22, consideraremos que el anillo de coeficientes Res un cuerpo F. De esta forma, los R-módulos se vuelven F-espacios vectoriales y el anillo de polinomios F[t]es un dominio de ideales principales. Teorema 3.23. Sea M={Mi, ϕi,j}un módulo de persistencia de tipo finito parametrizado por Nsobre F[t]. Entonces M∼ = n M i=1 tai·F[t]!⊕  m M j=1 tbj·F[t] (tcj) , donde n, m ≥1yai,bjycjson potencias enteras no negativas de t. 3.3. ESTRUCTURAS ALGEBRAICAS 41 Demostración. El módulo M=⊕iMies un F[t]-módulo finitamente generado por ser Mun módulo de persistencia de tipo finito. Puesto que Fes un cuerpo, el anillo de polinomios F[t]es un dominio de ideales principales. Por tanto, M=⊕iMies un módulo graduado finitamente generado sobre un dominio de ideales principales graduado y el Teorema 1.22 permite descomponerlo en suma directa de su parte libre y su parte de torsión. La componente libre está formada entonces por una suma directa de un cierto número de copias del anillo graduado F[t]. La parte de torsión será una suma directa de un cierto número de cocientes del anillo graduado F[t]por ideales de este anillo, que son todos homogéneos de la forma (ts). Por último, el cambio en la graduación tanto en la parte libre como en la parte de torsión se debe a que el módulo Mes graduado y, entonces, el isomorfismo de módulos graduados debe ser un isomorfismo de grado 0. Así, si zes un generador homogéneo de grado α > 0de la parte libre de M, entonces se hace necesario aumentar en αel grado de F[t](mediante la acción de tα) para que el isomorfismo sea de grado 0. Lo mismo ocurre con la parte de torsión de M. Por tanto, el Teorema 1.22 adopta la forma del enunciado en este contexto. En particular, la homología persistente en un grado fijado qde un complejo simplicial N-filtrado con coeficientes en un cuerpo Fes un módulo de persistencia de tipo finito parametrizado por Nsobre F[t], luego admite una descomposición como la anterior. Este resultado tiene una interpretación inmediata en términos de los códigos de barras. Las potencias de la variable tcapturan la aparición y desaparición de características topológicas a lo largo de la filtración. En primer lugar, la parte libre se encuentra en correspondencia biyectiva con los generadores de la homología que nacen en el grado filtrante aiy que sobreviven hasta el final de la filtración. Por su parte, los elementos de torsión se corresponden con los generadores de la homología que surgen en el grado filtrante bjy que se vuelven triviales al alcanzar el grado filtrante bj+cj. Nota 3.24.Mediante la teoría de Artin-Rees de álgebra conmutativa se puede probar [41] que existe una correspondencia biyectiva entre la categoría de módulos de persistencia de tipo finito parametrizados por Nsobre Ry la categoría de módulos graduados (con graduación no negativa) finitamente generados sobre R[t]. Esto también indica que una clasificación simple no es posible si el anillo de coeficientes considerado no es un cuerpo. Por ejemplo, la clasificación de módulos sobre Z[t]es muy complicada, aunque se pueden asignar invariantes de interés a los Z[t]-módulos. Anteriormente hemos trabajado con filtraciones con índices en R, pues son las que surgen de modo natural al considerar las filtraciones dadas por los complejos de Čech y Vietoris-Rips, por ejemplo. También es posible hacer una clasificación de los módulos de persistencia de tipo finito como F[t]-módulos cuando están parametrizados por R. 48 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE Equivalentemente, obtenemos un intervalo con extremos deg(e0 i)ydeg(e0 i)+s o un intervalo no acotado con extremo inferior deg(e0 i), respectivamente, en el código de barras asociado a Hq−1. Por otra parte, lo que resta de la prueba del teorema se sigue de que ∂q◦∂q+1 = 0 y, por tanto, M(∂q)·M(∂q+1)=0. Esta relación no cambia mediante operaciones elementales, que únicamente generan matrices intermedias de cambio de base. Además, como el dominio de ∂qes el codominio de ∂q+1, las operaciones elementales hechas por columnas en M(∂q)para conseguir la forma escalonada por columnas ˜ M(∂q)se corresponden con operaciones hechas por filas en M(∂q+1). Estas operaciones por filas anulan aquellas filas de M(∂q+1)que se corresponden con columnas pivote no nulas de ˜ M(∂q)y proporcionan el cambio de base que da la representación de ∂q+1 que buscábamos para completar la inducción. M(∂q) M(∂q+1) = 0 i j i j Figura 3.4: La relación M(∂q)·M(∂q+1)=0queda inalterada por operaciones elementales. Al reducir M(∂q)a su forma escalonada por columnas ˜ M(∂q), las respectivas operaciones por filas en M(∂q+1)anulan las filas que se corresponden con columnas pivote de ˜ M(∂q). Lema 3.33. Sea Cun complejo de persistencia de tipo finito parametrizado por Nsobre un cuerpo F. Para representar el homomorfismo ∂q+1 con respecto a la base estándar de Cq+1 y la base calculada en el Teorema 3.30 para Zqbasta con eliminar las filas de M(∂q+1)que se corresponden con columnas pivote de ˜ M(∂q). Demostración. Únicamente hemos usado operaciones elementales de tipos (1) y (3). De ellas, las de tipo (3) son las únicas que cambian valores en la matriz. Supongamos que en M(∂q)sustituimos la j-ésima columna por (columna j)+λ(columna i), con λ∈F[t]homogéneo, para eliminar un elemento en la fila pivote i. Esta operación cambia el elemento de la base de las columnas ejpor ej+λeien M(∂q). Para conseguir el mismo cambio de base en las filas de M(∂q+1)debemos sustituir la i-ésima fila por (fila i)−λ(fila j). 3.3. ESTRUCTURAS ALGEBRAICAS 49 Pero las sucesivas operaciones elementales por columnas que convierten la iésima columna de ˜ M(∂q)en columna pivote acaban provocando que la i-ésima fila de ˜ M(∂q+1)sea nula y, por otra parte, la j-ésima fila no sufre cambios por estas operaciones en ningún momento. Por tanto, no necesitamos realizar operaciones por filas. Es suficiente con eliminar las filas correspondientes a columnas pivote de una dimensión inferior para obtener la representación de ∂q+1 en términos de la base estándar de Cq+1 y la base homogénea de Zq. La validez del algoritmo queda probada con el último resultado, que completa la inducción del Teorema 3.30. Terminamos la sección con un ejemplo de cálculo. Ejemplo 3.34. Calculemos la homología persistente de la N-filtración de la Figura 3.1 mediante el algoritmo que acabamos de describir. Usaremos coeficientes sobre el cuerpo R, luego el módulo de persistencia será un R[t]-módulo. Los símplices de la filtración tienen los siguientes grados: v0v2v1v3v4v0v2v0v1v3v1v2v3v4v2v2v1v0v1v2 1 1 2 2 2 3 4 4 4 5 6 7 La representación matricial del operador borde ∂1:C1→C0, con la base de C0en orden decreciente de grados, viene dada por M(∂1) =         v0v2v0v1v3v1v2v3v4v2v2v1 v40 0 0 0 t30 v30 0 t2t20 0 v10t2t20 0 t4 v2t20 0 t3t4t5 v0t2t30 0 0 0         , mientras que su forma escalonada por columnas adopta la forma ˜ M(∂1) =            v4v2v3v1v0v1v0v2z1z2 v4t30 0 0 0 0 v30t20 0 0 0 v10t2t20 0 0 v2t40 0 t20 0 v00 0 t3t20 0            , donde z1=v2v3−v3v1+v0v1−t·v0v2 y z2=v2v1−t2·v0v1−t3·v0v2 forman una base homogénea de Z1. 50 CAPÍTULO 3. HOMOLOGÍA PERSISTENTE Con esta información, el Corolario 3.32 permite concluir que el código de barras correspondiente a H0incluye los siguientes intervalos: [deg(v4),deg(v4) + 3) = [2,5), [deg(v3),deg(v3) + 2) = [2,4), [deg(v1),deg(v1) + 2) = [2,4), [deg(v2),deg(v2) + 2) = [1,3), [deg(v0),+∞) = [1,+∞). Por su parte, la matriz asociada a ∂2:C2→C1y su forma escalonada por columnas vienen ambas dadas por M(∂2) =           v0v1v2 v2v1t v4v20 v2v30 v3v10 v0v1t3 v0v2t4           . Para obtener la representación en términos de la base estándar de C2y la base ordenada {z1, z2}de Z1que obtuvimos previamente, basta con eliminar la segunda y las tres últimas filas, que son las asociadas a los pivotes de ˜ M(∂1). Luego tenemos ˜ M(∂2) =   v0v1v2 z2t z10 , donde también hemos sustituido los elementos v2v3yv2v1de la base por z1=v2v3−v3v1+v0v1−t·v0v2 y z2=v2v1−t2·v0v1−t3·v0v2. De esta forma, obtenemos los dos siguientes intervalos de persistencia para el código de barras asociado a H1: [deg(z2),deg(z2) + 1) = [6,7), [deg(z1),+∞) = [4,+∞). Los cálculos de los intervalos de persistencia anteriores confirman que el código de barras que mostramos intuitivamente en la Figura 3.2 para la filtración de la Figura 3.1 es correcto. 3.4. NOTAS HISTÓRICAS 51 3.4. Notas históricas Como cuentan H. Edelsbrunner y J. Harer en [18], la homología persistente, como muchos otros conceptos matemáticos, surgió de forma independiente en tres trabajos distintos. Los primeros descubrimientos fueron de forma casi simultánea en los últimos años del siglo xx. En primer lugar, algunos trabajos de P. Frosini y M. Ferri contienen la persistencia de la homología en grado cero. Por otra parte, la tesis doctoral de V. Robins incluye una definición de homología persistente para estudiar conjuntos fractales con formas alfa. Por último, H. Edelsbrunner introdujo, entre otras, una de las herramientas básicas en la teoría de persistencia: las filtraciones en complejos simpliciales. La corta existencia del concepto de homología persistente provoca que la definición aquí presentada no se corresponda con las iniciales. Por ello, es fácil encontrar literatura sobre homología persistente en la que los conceptos no coinciden exactamente debido al escaso desarrollo de la teoría y las necesidades de refinarla. En cuanto a los métodos de cálculo, existe un algoritmo primigenio de emparejamiento persistente de símplices. A. Zomorodian y G. Carlsson son los primeros en dar el algoritmo de cálculo efectivo de intervalos de persistencia descrito anteriormente, e incluso consiguen un algoritmo que no usa las matrices. Ello se debe a observaciones hechas a partir de los dos lemas probados en la sección precedente y la no necesidad de realizar operaciones por filas para el cálculo inductivo de las matrices. De esta manera, el algoritmo se ejecuta directamente sobre el cuerpo Fy se obtiene directamente el código de barras sin calcular explícitamente el F[t]-módulo de persistencia. Capítulo 4 Análisis de redes complejas Un gran número de sistemas en ciencias naturales y sociales se modela gracias a redes. La complejidad de estas redes se pone de manifiesto tanto en su estructura y características topológicas como en su dinámica evolutiva. La visión clásica de las redes se hacía a través de la teoría de grafos. No obstante, este punto de vista tiene limitaciones en cuanto a sus aplicaciones en modelos reales. La aparición de nuevos sistemas de redes, más allá de los grafos regulares y aleatorios, ha propiciado, junto a algunos métodos estadísticos, la utilización de técnicas novedosas como la homología persistente. Siguiendo algunos ejemplos dados en el artículo [27] de Danijela Horak, Slobodan Maletić y Milan Rajković y el principal ejemplo del artículo [9] de C. J. Carstens y K. J. Horadam, el presente capítulo muestra algunas aplicaciones prácticas de la homología persistente. Centraremos el estudio en el análisis de redes complejas, así que el capítulo comienza con unos preliminares básicos que introducen la terminología de teoría de grafos que utilizaremos. Posteriormente se explica el uso que se hace de la homología persistente para examinar distintos tipos de redes. Con el fin de estudiar en profundidad una red es habitual observar su dinámica evolutiva para conocer el comportamiento que muestra a lo largo del tiempo. Esto motiva la búsqueda de aquellas características topológicas persistentes en la red. Uno de los objetivos primordiales es identificar las propiedades que hacen a las redes menos vulnerables frente a los ataques y distinguirlas de las propiedades que debilitan la red. En este sentido, los análisis mediante homología persistente de redes complejas con distintas distribuciones de grado reflejan la robustez de la red. 4.1. Teoría de grafos En esta sección revisamos los conceptos básicos de teoría de grafos que necesitaremos en el resto del capítulo. En primer lugar, se repasan rápidamente las definiciones elementales. A continuación, se introducen algunos fundamen53 54 CAPÍTULO 4. ANÁLISIS DE REDES COMPLEJAS tos de las distribuciones de grado, donde se combina la teoría de grafos con la de probabilidades. Ello es necesario para el posterior estudio que realizaremos mediante homología persistente. Las definiciones están tomadas en su mayoría de [20]. 4.1.1. Conceptos básicos Informalmente, un grafo es un conjunto de puntos unidos de cierta forma mediante líneas entre ellos que crean conexiones. A continuación, detallamos una definición más formal. Definición 4.1. Un grafo simple Ges un par ordenado (V, E), donde Ves un conjunto no vacío y numerable y E⊂ {{u, v}:u, v ∈V}. Vse denomina conjunto de vértices onodos yEse llama conjunto de aristas, conexiones oenlaces. Una arista se representa como un par no ordenado {u, v} de vértices, con u, v ∈V. En ese caso, los vértices se dicen vecinos oadyacentes y la arista se dice incidente con los vértices. Más adelante, usaremos a menudo el término red para denominar los grafos simples. También obviaremos el adjetivo «simple», ya que no trataremos el caso de grafos con aristas múltiples. Definición 4.2. Un grafo con pesos es un grafo G= (V, E)junto con una función ω:E→Rque asigna un valor real a cada arista. Definición 4.3. Sea G= (V, E)un grafo. Se dice que G0= (V0, E0)es un subgrafo de Gsi se verifica: (i)V0⊂V. (ii)E0⊂ {{u, v}:u, v ∈V0} ∩ E. Definición 4.4. Para cada n≥1, llamamos grafo completo a un grafo Kn formado por nvértices y en el que dos nodos distintos siempre están unidos por una arista. Para trabajar cómodamente con grafos cuyos vértices no están etiquetados, resulta útil asignar unas etiquetas genéricas. Por ejemplo, un grafo con n vértices podemos etiquetarlo asignando a cada nodo un elemento del conjunto {1,2, . . . , n}. Mediante este etiquetado, es posible recoger fácilmente la información básica de un grafo en una matriz. Definición 4.5. Sea G= (V, E)un grafo simple, con V={1,2, . . . , n}. Definimos la matriz de adyacencia de Gcomo la matriz cuadrada A= (aij ), donde para 1≤i, j ≤nhacemos aij =(1,{i, j} ∈ E 0,{i, j}/∈E. 4.1. TEORÍA DE GRAFOS 55 Definición 4.6. Sea G= (V, E)un grafo. Un camino es una sucesión finita de aristas (no necesariamente distintas) {u1, v1},{u2, v2},...,{uk, vk} para las que vi=ui+1, con i= 1, . . . , k−1. Si vk=u1, el camino se dice cerrado o un lazo. Se llama longitud del camino al número de aristas k. Si los vértices de un camino son distintos dos a dos, se dice que el camino es simple. Si las aristas de un camino son distintas dos a dos, el camino se llama recorrido. Un recorrido cerrado es un circuito. Los caminos permiten establecer el concepto de conexión en un grafo. Definición 4.7. Sea G= (V, E)un grafo. Decimos que Ges conexo si cada par de vértices de Gse puede unir mediante un camino de aristas. La conectividad está relacionada con la robustez o tolerancia del grafo a mantener intactas sus propiedades topológicas ante la adición o eliminación de vértices. 4.1.2. Complejo clique El siguiente paso es asociar un complejo simplicial al grafo para poder estudiar su homología persistente a través de una filtración. Aunque podríamos considerar los grafos como complejos simpliciales de dimensión uno y trabajar directamente con una filtración del grafo, esto solo proporcionaría números de Betti no triviales de dimensiones cero y uno. Gracias a los complejos simpliciales podemos codificar información topológica de los grafos en otras dimensiones; en nuestro caso, utilizaremos una construcción que se denomina complejo clique. Definición 4.8. Sea G= (V, E)un grafo. Un q-clique es un subgrafo completo de Gcon qvértices. Definición 4.9. Sea G= (V, E)un grafo. El complejo clique asociado a Gse construye introduciendo un q-símplice en el complejo si q+ 1 vértices forman un (q+ 1)-clique. Así, un 3-clique se convierte en un triángulo o 2-símplice y un 4-clique en un tetraedro sólido o 3-símplice, por ejemplo. Pero el complejo clique asociado a un grafo no es nada nuevo, ya que resulta ser un cierto complejo de Vietoris-Rips de parámetro ε= 1. Por concretar, los puntos del espacio métrico son los vértices del grafo y la función distancia está dada por la longitud del camino más corto entre cada par de vértices. Una propiedad del complejo clique es que los cliques se corresponden con agrupamientos de nodos altamente conectados que representan comunidades. Por ejemplo, el primer número de Betti del complejo clique representa la cantidad de ciclos del complejo. En el grafo original, cada triángulo es un ciclo que aumenta β1en una unidad. Sin embargo, en el complejo clique los triángulos se rellenan y el ciclo deja de existir. Esto se traduce en que los agujeros detectados 56 CAPÍTULO 4. ANÁLISIS DE REDES COMPLEJAS en el complejo clique tienen cuatro o más vértices. Así, el ciclo más simple que se puede crear en el complejo clique consiste en cuatro nodos conectados como un cuadrado sin las conexiones diagonales. 4.1.3. Distribuciones de grado El estudio de la distribución de grado sirve para conocer el comportamiento de las redes complejas. En primer lugar, establecemos lo que entendemos por el grado de un vértice. Definición 4.10. Sea G= (V, E)un grafo. El grado de un nodo v∈V, escrito deg(v), se define como el número de aristas que son incidentes con v. La idea es ver cómo se distribuyen los grados de los nodos a lo largo de la red. Basta con inspeccionar la matriz de adyacencia para comprobar las diferencias existentes entre los grados de los distintos nodos de la red. Definición 4.11. Sea G= (V, E)un grafo de nvértices. Supongamos que n(k) es el número de nodos de grado kque tiene G. Se define la distribución de grado de la red Gcomo P(k) := n(k) n. Así, para cada k, el número P(k)representa la probabilidad de que un vértice seleccionado al azar tenga grado k. Y si vemos P(k)como una función de k estamos ante una distribución de probabilidades sobre el grafo. 4.2. Herramientas de computación Existe bastante software que permite calcular la homología persistente. El paquete javaPlex [40], escrito en Java y preparado para usarse con la interfaz de MATLAB, cuenta con una amplia documentación que incluye numerosos ejemplos. Fue desarrollado por el grupo de topología computacional de la Universidad de Stanford, está basado en la librería Plex y sustituye al antiguo paquete jPlex. Además, es capaz de trabajar en los cuerpos finitos Zp(e incluso en Q) y producir imágenes con los códigos de barras. El artículo [36] detalla los pormenores de estos y otros softwares disponibles, comparando las funciones de cada uno e indicando sus distintos objetivos o especializaciones. Estas diferencias están provocadas en parte por uno de los problemas fundamentales que deben afrontar estos programas: las representaciones fieles de los espacios en forma de complejos simpliciales tienden a ser muy costosas computacionalmente. En el artículo [27] que seguiremos se hace uso de la librería Plex en MATLAB para los cálculos relacionados con el análisis de conjuntos de datos convertidos en complejos simpliciales y del paquete (no oficial) Simplicial Homology [16] del software de álgebra discreta computacional GAP [21] para trabajar con la homología simplicial. Por su parte, en el otro artículo de referencia [9] se utiliza el software Gephi [3] para manipular y dibujar los grafos, código en Java para tratar los datos y javaPlex para el cálculo de los intervalos de persistencia. 4.3. REDES ALEATORIAS DE ERDŐS-RÉNYI 57 En nuestro caso, los intentos de reproducir algunos de los ejemplos expuestos en [27] se han realizado gracias al paquete igraph [12] del software estadístico R para generar los grafos, junto con el paquete javaPlex ejecutado en MATLAB para el cálculo de la homología persistente y la obtención de los correspondientes códigos de barras. Todo el código utilizado para generar los ejemplos propios puede consultarse en el Apéndice A de la memoria. 4.3. Redes aleatorias de Erdős-Rényi El primer ejemplo que se estudia en el artículo [27] es el de redes aleatorias. Existen varias formas de construir un grafo aleatorio, pero todas parten de la idea de describirlos mediante una distribución de probabilidades que genere la red. Aunque no es el único, el artículo utiliza el modelo de Erdős-Rényi, uno de los más conocidos, para crear la red aleatoria de estudio. Definición 4.12. Para construir una red aleatoria de Erdős-Rényi, denotada por G(n, p), se considera un número fijo nde vértices aislados y entre cada par de nodos se incluye una arista con probabilidad 0<p<1. En la práctica, según [20], se fija un parámetro ppara construir la red. De esta forma, para cada par de nodos se genera uniformemente un número aleatorio ren el intervalo (0,1) y se incluye una arista entre los nodos seleccionados si p>r. En este caso, la construcción de la red G(n, p)hace que sea claro que la existencia de cada posible arista siga una distribución de Bernoulli con probabilidad p. Por tanto, la distribución de grado para un vértice vtomado al azar toma la forma de una binomial de parámetros n−1yp(pues vse puede conectar con n−1nodos con probabilidad p), luego P(k) = n−1 kpk(1 −p)n−1−k. Un resultado clásico de estadística [10] establece que cuando nva aumentando y el producto (n−1)p=λse mantiene constante, la distribución binomial converge hacia una distribución de Poisson de parámetro λ. Esto es, P(k)→λke−λ k!. La primera red aleatoria estudiada en [27] se generó a partir de 2000 nodos, con una probabilidad de enlace entre ellos de p= 0,005. Mediante el software estadístico R generamos un grafo aleatorio con los parámetros del artículo. A continuación, utilizamos MATLAB para construir el complejo clique del grafo, filtrarlo y calcular su homología persistente. Para obtener la N-filtración, tomamos como i-ésimo complejo el i-esqueleto del complejo clique, es decir, el conjunto de símplices de dimensión menor o igual que i. Debido a la dispersión de la red, truncamos la construcción del complejo clique en el 3-esqueleto. 64 CAPÍTULO 4. ANÁLISIS DE REDES COMPLEJAS gráficas son similares, durante las etapas intermedias de la filtración surgen comportamientos diferenciadores. Por otra parte, los autores afirman que también compararon los correspondientes códigos de barras mediante la distancia de cuello de botella (definida, por ejemplo, en [18]) y sus cálculos arrojaron diferencias suficientemente significativas para permitir discernir las topologías de la red de colaboración y las redes aleatorias. Figura 4.6: En azul, la evolución de β0para la red científica; en rojo, superpuestas, las evoluciones de β0para diez redes aleatorias. La imagen está tomada de [9]. Finalmente, el artículo analiza el primer número de Betti del complejo clique asociado a la red. La Figura 4.7 muestra el código de barras correspondiente a H1en las etapas finales de la filtración. Los colores sirven para identificar los ciclos del complejo que se ven reflejados mediante barras en el diagrama inferior. Los autores notan que los ciclos con más aristas se crean para los pesos umbrales más pequeños, aunque muchas de esas conexiones tienen pesos grandes. Nuevamente, tratan de usar la información dada por β1para distinguir esta red de otras aleatorias. Como antes, generan 1000 redes aleatorias y calculan una media de 520,65 intervalos (con una desviación típica de 4,39) para el código de barras de H1, cuando la red científica tiene 9 intervalos como se observa en la Figura 4.7. Este comportamiento ya había quedado patente cuando analizamos nuestras redes aleatorias: las redes de Erdős-Rényi no tienen tendencia a formar agrupaciones, sino que los 1-ciclos dominan la red. Por tanto, β1es suficiente para comparar y distinguir redes aleatorias de otras más estructuradas. Esto les sugiere que un análisis más profundo de la homología persistente a lo largo de toda la filtración permita detectar diferencias más sutiles en la topología de otras redes que posean una estructura mucho más parecida. Para acabar, un detalle menor que comentan es que todos los ciclos de H1 que nacen viven hasta el final. Esto no sería así si, por ejemplo, los cuatro autores del ciclo rojo que aparece en ω∗= 1 hubieran colaborado en un artículo. En ese supuesto, aparecería una arista diagonal en ω∗= 0,33 que mataría el ciclo. 4.6. CONCLUSIONES 65 Figura 4.7: Código de barras para H1correspondiente a cinco etapas finales de la filtración. En la parte superior se señalan los ciclos generadores en distintos colores para identificarlos fácilmente en el diagrama inferior. En la etapa correspondiente a ω∗= 0,5hay dos triángulos sombreados para indicar que ahí no hay ningún ciclo. La imagen está tomada de [9]. 4.6. Conclusiones Los análisis de redes complejas mediante homología persistente permiten establecer una nueva medida de la robustez de una red. La aparición de generadores persistentes en los módulos de homología de dimensión superior guarda relación con la resistencia de la red frente a ataques que añadan o eliminen nodos. En particular, la red de correos electrónicos con distribución exponencial muestra características persistentes en H2, al contrario que las redes aleatorias o la red de colaboración, que serán más débiles en este sentido. Como segunda aplicación interesante, la homología persistente, incluso en las dimensiones más pequeñas, es una herramienta para distinguir la red de colaboración científica estudiada de redes aleatorias creadas con características muy parecidas. Apéndice A Código para implementar los ejemplos El presente apéndice recoge los códigos en R y MATLAB desarrollados para crear el primer grafo aleatorio estudiado en el capítulo anterior y analizar su homología persistente. Pequeñas modificaciones de los mismos permiten recrear el segundo ejemplo. Se ha optado por definir una métrica sobre el grafo y, mediante esta, calcular los cliques que conforman el complejo clique, sabiendo que el paquete igraph tiene una función que devuelve directamente los cliques de un grafo (y que, posiblemente, haría la implementación del código más eficiente). A.1. Código en R El siguiente código en R crea un grafo aleatorio G(2000,0,005) y guarda en sendos ficheros de texto la información sobre los vértices conectados y sobre el número de nodos y aristas. library(igraph) n <- 2000 p <- 0.005 g <- sample_gnp(n, p, directed = FALSE) v <- get.data.frame(g, ’vertices’) e <- get.data.frame(g, ’edges’) num_aristas <- nrow(e) write.table(e, "grafo_aleatorio.txt", sep="\t", ... col.names = FALSE, row.names = FALSE) write(n, "variables.txt", sep="\n", append = FALSE) write(num_aristas, "variables.txt", sep="\n", append = TRUE) 67 68 APÉNDICE A. CÓDIGO PARA IMPLEMENTAR LOS EJEMPLOS A.2. Código en MATLAB El siguiente código en MATLAB lee la información sobre el grafo creado previamente en R, crea el complejo clique de dimensión 3 asociado al grafo y lo filtra mediante sus sucesivos esqueletos. Después, calcula la homología persistente del grafo para esa filtración y dibuja el código de barras asociado. Finalmente, imprime por pantalla los números de Betti persistentes. % En primer lugar, situados en el directorio donde esté % descargado javaPlex hay que ejecutar el comando % load_javaplex % para cargar el paquete y poder trabajar con el código inferior. % Incorporamos las variables que necesitamos del script de R. fileID = fopen(’variables.txt’, ’r’); variables = fscanf(fileID, ’%d’); fclose(fileID); n = variables(1); num_aristas = variables(2); % Leemos los datos sobre las aristas % conectadas del archivo creado con R. fileID = fopen(’grafo_aleatorio.txt’, ’r’); aleatorio = fscanf(fileID, ’%d %d’, [2, num_aristas]); aleatorio = aleatorio’; fclose(fileID); % Definimos un espacio métrico sobre G(n,p) % dotando a cada arista de la métrica que la % haga isométrica al intervalo [0,1]. distancias = zeros(n); for i = 1:num_aristas distancias(aleatorio(i,1),aleatorio(i,2)) = 1; distancias(aleatorio(i,2),aleatorio(i,1)) = 1; end % Inicializamos el complejo simplicial. complejo = api.Plex4.createExplicitSimplexStream(); % Añadimos los vértices en la etapa 0 de la filtración. for i = 1:n complejo.addVertex(i, 0); end A.2. CÓDIGO EN MATLAB 69 % Añadimos las aristas en la etapa 1 de la filtración. for i = 1:num_aristas complejo.addElement([aleatorio(i,1), aleatorio(i,2)], 1); end % Añadimos los 2-símplices en la etapa 2 de la filtración. for i = 1:n-2 for j = i+1:n-1 if (distancias(i,j) == 1) for k = j+1:n if (distancias(i,k) == 1 && distancias(j,k) == 1) complejo.addElement([i, j, k], 2); end end end end end % Añadimos los 3-símplices en la etapa 3 de la filtración. for i = 1:n-3 for j = i+1:n-2 if (distancias(i,j) == 1) for k = j+1:n-1 if (distancias(i,k) == 1 && distancias(j,k) == 1) for l = k+1:n if (distancias(i,l) == 1 && distancias(j,l) == 1 ... && distancias(k,l) == 1) complejo.addElement([i, j, k, l], 3); end end end end end end end % Finalizamos el complejo. complejo.finalizeStream(); % Comprobamos que el código anterior crea, % efectivamente, un complejo simplicial. complejo.validateVerbose(); % Calculamos la homología persistente del complejo hasta la % de dimensión 2 (calculamos H_0, H_1 y H_2) sobre el cuerpo Q. persistencia = api.Plex4.getRationalSimplicialAlgorithm(3); 70 APÉNDICE A. CÓDIGO PARA IMPLEMENTAR LOS EJEMPLOS % Dibujamos el código de barras. dibujar_intervalos = persistencia.computeIntervals(complejo); % Guardamos el código de barras en un archivo, indicando el % número de etapas de la filtración que se debe considerar % y la dimensión homológica máxima a mostrar. options.filename = ’codigo_de_barras’; options.max_filtration_value = 3; options.max_dimension = 2; plot_barcodes(dibujar_intervalos, options); % Imprimimos por pantalla los números de Betti % persistentes, correspondientes a los intervalos % no acotados del código de barras. intervalos = persistencia.computeAnnotatedIntervals(complejo); intervalos_infinitos = intervalos.getInfiniteIntervals(); intervalos_infinitos.getBettiNumbers() Bibliografía [1] Aaronson, S., Scoville, N. A. Lusternik–Schnirelmann category for simplicial complexes. Illinois J. Math.,57(3):743–753, 2013. [2] Ayala, R., Domínguez, E., Quintero, A. Elementos de la teoría de homología clásica,65. Universidad de Sevilla, 2002. [3] Bastian, M., Heymann, S., Jacomy, M. Gephi: An open source software for exploring and manipulating networks, 2009. Software disponible en http://www.gephi.org. [4] Bubenik, P., Kim, P. T. A statistical approach to persistent homology. Homology, Homotopy Appl.,9(2):337–362, 2007. [5] Carlsson, G. Topology and data. Bull. Am. Math. Soc.,46(2):255–308, 2009. [6] Carlsson, G., Ishkhanov, T., De Silva, V., Zomorodian, A. On the local behavior of spaces of natural images. IJCV,76(1):1–12, 2008. [7] Carlsson, G., Singh, G., Zomorodian, A. Computing multidimensional persistence. En Algorithms and computation, 730–739. Springer, 2009. [8] Carlsson, G., Zomorodian, A., Collins, A., Guibas, L. J. Persistence barcodes for shapes. Int. J. Shaping Model.,11(02):149–187, 2005. [9] Carstens, C. J., Horadam, K. J. Persistent homology of collaboration networks. Math. Probl. Eng.,2013, 2013. [10] Casella, G., Berger, R. L. Statistical inference. Duxbury Pacific Grove, 2002. [11] Collins, A., Zomorodian, A., Carlsson, G., Guibas, L. J. A barcode shape descriptor for curve point cloud data. Computers & Graphics,28(6):881– 894, 2004. [12] Csardi, G., Nepusz, T. The igraph software package for complex network research. InterJournal, Complex Systems 1695, 2006. http://igraph.org. 71 72 BIBLIOGRAFÍA [13] De Silva, V., Carlsson, G. Topological estimation using witness complexes. Proc. Sympos. Point-Based Graphics, 157–166, 2004. [14] De Silva, V., Ghrist, R. Coverage in sensor networks via persistent homology. Algebr. Geom. Topol.,7(1):339–358, 2007. [15] De Silva, V., Ghrist, R., Muhammad, A. Blind swarms for coverage in 2-D. En Robotics: Science and Systems, 335–342, 2005. [16] Dumas, J.-G., Heckenbach, F., Saunders, B. D., V., W. Simplicial Homology, a (proposed) GAP share package. http://ljk.imag.fr/membres/ Jean-Guillaume.Dumas/Homology/. [17] Edelsbrunner, H. The union of balls and its dual shape. En Proceedings of the ninth annual symposium on Computational geometry, 218–231. ACM, 1993. [18] Edelsbrunner, H., Harer, J. Persistent homology – a survey. Contemporary mathematics,453:257–282, 2008. [19] Edelsbrunner, H., Harer, J. Computational topology: an introduction. American Mathematical Society, 2010. [20] Estrada, E., Knight, P. A first course in network theory. Oxford University Press, 2015. [21] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.4.10, 2007. http://www.gap-system.org. [22] Ghrist, R. Barcodes: the persistent topology of data. Bull. Am. Math. Soc., 45(1):61–75, 2008. [23] Guimerà, R., Danon, L., Díaz-Guilera, A., Giralt, F., Arenas, A. Selfsimilar community structure in a network of human interactions. Phys. Rev. E Stat. Nonlin. Soft. Matter Phys.,68(6):065103, 2003. [24] Gyulassy, A., Natarajan, V. Topology-based simplification for feature extraction from 3D scalar fields. En Visualization, 2005. VIS 05. IEEE, 535–542. IEEE, 2005. [25] Hartley, B., Hawkes, T. O. Rings, modules and linear algebra. Chapman & Hall/CRC, 1970. [26] Hausmann, J.-C. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. Ann. Math. Studies,138:175–188, 1995. [27] Horak, D., Maletić, S., Rajković, M. Persistent homology of complex networks. J. Stat. Mech. Theor. Exp.,2009(03):P03034, 2009. BIBLIOGRAFÍA 73 [28] Jake (http://tex.stackexchange.com/users/2552/jake). Moebius strip using TikZ. Stack Exchange, 10 de junio de 2013. http://tex. stackexchange.com/questions/118563/moebius-strip-using-tikz, visitado el 3 de marzo de 2016. [29] Kahle, M. Topology of random clique complexes. Discrete Math., 309(6):1658–1671, 2009. [30] Kozlov, D. Combinatorial algebraic topology. Springer Science & Business Media, 2007. [31] Lamar León, J., García Reyes, E. B., González Díaz, R. Human gait identification using persistent homology. En Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, 244–251. Springer, 2012. [32] Lang, S. Algebra. Addison-Wesley, 1993. [33] Latschev, J. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Arch. Math. (Basel),77(6):522–528, 2001. [34] Munkres, J. R. Elements of algebraic topology. Addison-Wesley Reading, 1984. [35] Newman, M. E. J., 2006. Phys. Rev. E 74, 036104. [36] Otter, N., Porter, M. A., Tillmann, U., Grindrod, P., Harrington, H. A. A roadmap for the computation of persistent homology. arXiv preprint arXiv:1506.08903, 2015. [37] Salvatore, J. Applying Topology to Data, Part 1: A Brief Introduction to Abstract Simplicial and Čech Complexes. DyingLoveGrape. http://www.dyinglovegrape.com/math/topology_data_1.php, visitado el 11 de marzo de 2016. [38] Salvatore, J. Applying Topology to Data, Part 2: More Čech Complexes, the Vietoris-Rips Complexes, and Clustering. DyingLoveGrape. http://www.dyinglovegrape.com/math/topology_data_2.php, visitado el 11 de marzo de 2016. [39] Singh, G., Memoli, F., Ishkhanov, T., Sapiro, G., Carlsson, G., Ringach, D. L. Topological analysis of population activity in visual cortex. J. Vis., 8(8):1–18, 2008. [40] Tausz, A., Vejdemo-Johansson, M., Adams, H. JavaPlex: A research software package for persistent (co)homology. En Proceedings of ICMS 2014, Lecture Notes in Computer Science 8592, 129–136, 2014. Software disponible en http://appliedtopology.github.io/javaplex/. [41] Zomorodian, A., Carlsson, G. Computing persistent homology. Discrete Comput. Geom.,33(2):249–274, 2005.