Tabla de contenidos
Qué son los grafos
Un grafo es un conjunto de objetos de tipo vértices o nodos, unidos y relacionados entre ellos por medio de aristas, arcos o bordes. Cuando un grafo es representado gráficamente, los vértices son puntos, y las aristas las líneas que los unen.
Los grafos representan grupos de entidades del mundo real que pueden ser de naturaleza muy variada, (documentos, personas) y existen para resolver problemas complejos.
Los vértices son datos o entidades. Las aristas son las relaciones entre estas entidades. Algunos ejemplos de esta representación:
- En una red social, las personas estarían representadas por los vértices, mientras que las relaciones entre las personas serían las aristas.
- Para un motor de búsqueda resulta crucial determinar la cantidad y calidad de hiperenlaces entre las diferentes páginas web. En este contexto, en un grafo las páginas estarán representadas por los vértices, mientras que los links lo estarán por las aristas.
Los grafos son una rama de las matemáticas y de las ciencias de la computación, especialmente en el Procesamiento de datos y Big Data, donde cobran una importancia aún más crucial.
Los grafos permite almacenar y analizar grandes cantidades de datos, estudiar las relaciones que existen entre diferentes tipos de entidades, hecho que no sería posible con otros enfoques, como el de las relaciones jerárquicas.
Para este cometido existen aplicaciones de software especializadas en la visualización, análisis y almacenamiento de grafos, algunas de las cuales se abordan más adelante.
Casos de uso de los grafos
Ejemplos de lo que pueden ser nodos en diferentes situaciones:
- Gestión de conocimiento. Por ejemplo, a través de documentos de texto entrelazados entre sí en función de su temática, a través de hiperenlaces, formando una red. Un ejemplo de esto, representable con grafos, sería la gigantesca red de páginas de Wikipedia (vea una representación gráfica de una parte de la Wikipedia en este grafo en el sitio web de sigma.js). Los vértices o nodos son las páginas, y los hiperenlaces están representados por las aristas.
- Optimización y modelado de rutas. Analizar y encontrar la ruta más corta entre dos puntos de un mapa. Modelar redes de carreteras o líneas de transporte público.
- Descubrimiento de patrones. Distinguir entre cuentas de bots y cuentas reales, detectar el spam, …
- Sistemas de recomendación. Basados en las similitudes entre usuarios, o tendencias de compra.
- Mercado financiero. Detección de estafas y fraude fiscal, transacciones financieras, …
- Química. Representación gráfica de la composición de moléculas.
En el contexto del ejemplo de la Wikipedia, se podría tratar de un sistema de gestión del conocimiento personal, o PKM por sus siglas en inglés.
Para ampliar información sobre la creación de un PKM utilizando una red de ficheros entrelazados, considérese la lectura de los artículos Siguientes:
- Introducción al método Zettelkasten e implementación con software libre. Qué es un Zettlekasten, y herramientas libres para empezar a implementarlo.
- Procesador de textos Zettlr, una guía de inicio rápido. Un procesador de textos optimizado para la productividad, con enlazado de archivos para implementar el método Zettelkasten, visor del grafo de nuestro PKM, estadísticas varias y muchas más funcionalidades.
La teoría de grafos
La teoría de grafos, llamada a veces teoría de gráficas, estudia las propiedades de los grafos.
Definición básica de un grafo
Un grafo G se define como un par ordenado (V,E), donde V es un conjunto de nodos y E es un conjunto de bordes que conectan pares de nodos.
Tipos de grafos
El grado de un nodo. En un grafo no dirigido, el grado es el número de bordes incidentes en un nodo.
La siguiente lista muestra solo algunos tipos de grafos. La elección del grafo a utilizar en cada caso depende el contexto de la situación o problema a resolver:
- Grafo conexo o conectado, y disconexo o inconexo. En un grafo conexo, para cualquier par de vértices existe al menos un camino entre ellos. En otras palabras, todos los vértices están conectados por un camino si el grafo es no dirigido, o por un semicamino si el grafo es dirigido.
- Árbol. Es un tipo especial de grafo conexo y acíclico. En esta estructura, solo existe una ruta entre un punto A y un punto B.
- Grafo Bipartito. Sus vértices se pueden separar en dos conjuntos disjuntos, de forma que las aristas no pueden relacionar vértices de un mismo conjunto. Así pues, cada borde conecta un nodo de un conjunto con un nodo del otro conjunto.
- Grafo Cíclico y Acíclico. El cíclico contiene al menos un ciclo, que es una secuencia de nodos conectados que comienza y termina en el mismo nodo.
- Grafo dirigido y no dirigido. En los grafos dirigidos, las aristas tienen una dirección específica (dirección de entrada/de salida).
- Grafo Ponderado. En este se asigna un peso numérico a cada arista.
- Grafo Regular. Todos los nodos tienen el mismo grado,
- Grafo Completo. En este existe una arista entre cada par de nodos. Es decir, cada nodo está conectado a todos los demás nodos.
Herramientas de visualización de grafos
Existen diferentes formas de representar un grafo y de almacenarlo en una computadora.
- Gephi. Gephi es un software libre de visualización de grafos y análisis de redes, enormemente potente y lleno de funcionalidades. Corre sobre Linux, Windows y MacOS.
- Graphviz. Un software libre consistente en un lenguaje de descripción de grafos llamado DOT, un conjunto de herramientas y librerías
- Sigma.js. Se trata de una biblioteca de JavaScript, por lo que permite una fácil integración de grafos en aplicaciones web.
Bases de datos orientadas a grafos
Una base de datos de grafos (y en general cualquier BBDD noSQL), carece de las limitaciones propias de una BBDD relacional, lo que es lo mismo que decir de una jerarquía.
En una jerarquía, una entidad padre puede relacionarse con una o muchas entidades hijo. Esto, en una base de datos relacional se conoce como «relación de uno a varios». Cuando simultáneamente a esto, el hijo puede tener más de un padre, el tema empieza a complicarse. Cuando no hay una jerarquía clara, y las relaciones entre nodos o registros son complejas, como ocurre en una red neuronal o en el cerebro humano, una BBDD relacional no es viable.
Relacionado:
- Bases de datos no relacionales o noSQL
- El gestor de bases de datos orientado a grafos Neo4j
Las redes neuronales gráficas
Las redes neuronales gráficas (Graph Neural Networks o GNN), son un tipo de redes neuronales artificiales basadas en grafos.
Estas redes resuelven ciertos problemas mejor que las redes neuronales tradicionales. Las redes neuronales gráficas juegan un papel crucial y son más útiles en situaciones en que las relaciones desempeñan un papel importante.
Cuanto más relevante es el papel de las relaciones en el grafo o red neuronal, mayor sentido tiene y más útiles son las redes neuronales gráficas. Esto es así en algunos ámbitos, como en el mercado financiero, o en la química.
Recursos
- [gephi.org] Guía rápida de Gephi
- [neo4j.com] Fun with Beer – and Graphs.
- [linkurious.com] Our first Neo4j meetup: visualizing graphs with Linkurious and Gephi