Grafos

por Ira Manzano


El término Knowledge Graph, hace referencia al almacenamiento del conocimiento en una estructura de grafo. Entre el conocimiento almacenado en el mismo, se incluye información semántica, es decir el significado de las entidades como palabras de un lenguaje. Esta información incluye tanto información semántica de la propia entidad (Ejemplo: la entidad ‘persona’ tiene un atributo ‘edad’), como información semántica relativa a las relaciones semánticas entre dos entidades (Ejemplo: la entidad ‘gato’ tiene una relación ‘es un’ con la entidad ‘animal’).

Grafos
Grafos

Básicamente un grafo es una estructura compuesta por un conjunto de nodos y aristas, en la que los nodos serían las entidades y las aristas las relaciones entre las distintas entidades. Se puede almacenar información tanto en los nodos como en las relaciones.

Por establecer una similitud gráfica, la estructura de los grafos es muy similar a la que nuestro cerebro utiliza para estructurar el conocimiento.

Aunque el concepto Knowledge Graph es relativamente nuevo, el estudio y aplicación de grafos es un tema muy antiguo. El primer artículo científico sobre grafos fue escrito en el año 1736 por el matemático Euler.

La relevancia que ha adquirido el término en los últimos años se debe, principalmente, al hecho de que gran parte de la información que manejamos hoy en día es relativa a las relaciones existentes entre entidades, más que a las propias entidades en sí mismas.

Actualmente los sistemas no trabajan con individuos aislados, para determinar su funcionamiento y respuesta, sino que tienen en cuenta las relaciones de un individuo con el resto de individuos incluidos en el sistema.

Estas relaciones entre entidades pueden ser explícitas, una entidad se relaciona directamente con otra, o implícitas, dos entidades no están directamente relacionadas pero existe una relación indirecta entre ambas. Los grafos de conocimiento facilitan el descubrimiento de las relaciones implícitas entre entidades.

Ventajas de aplicar la tecnología Knowledge Graph

  • Alta escalabilidad a grandes conjuntos de datos ya que no requieren de costosas operaciones de combinación.
  • Mayor capacidad y rapidez de procesamiento de consultas que impliquen la exploración de un gran número de relaciones. La velocidad de ejecución de consultas del tipo ‘Quiero saber que amigos de mis amigos conocen a María’, que implican la búsqueda de relaciones de profundidad tres o más, es mayor que con por ejemplo con una base de datos SQL. Está diferencia aumenta cuanto mayor es el conjunto de entidades y relaciones con las que se trabaja.
  • El esquema regular e independiente del dominio que utilizan las bases de datos orientadas a grafos permite la implementación de funcionalidad estándar que se abstraer del área de conocimiento sobre el que se aplica, de manera que sería aplicable a información perteneciente a cualquier dominio de conocimiento.
  • El esquema flexible facilita la incorporación de conocimiento, mejorando así la capacidad de aprendizaje del sistema correspondiente.
  • Gracias a la incorporación de información semántica, mejoran notablemente las capacidades relacionadas con el procesamiento del lenguaje natural, tales como la desambiguación de términos, ya que facilitan la contextualización de un término para así comprender a qué concepto se está haciendo referencia en un momento dado.
  • Facilita la capacidad de inferencia del sistema, ya que se puede descubrir nuevo conocimiento en el grafo, gracias al análisis de las relaciones entre las entidades.

Aplicaciones principales de Knowledge Graph

En base a las características y ventajas que presentan los grafos de conocimiento, analizamos algunas de las aplicaciones principales de este sistema:

  • Sistemas de recomendación: el funcionamiento de los algoritmos de recomendación se basa en las relaciones entre las entidades relevantes para el dominio en el que se desee llevar a cabo la recomendación: normalmente personas y cosas.
  • Redes sociales: se puede predecir el comportamiento de un individuo, sin apenas tener información del mismo, en base a cómo se relaciona con otros individuos.
  • Aplicaciones sobre redes: red de metro, red carreteras… Para dar solución a problemas como el camino más corto entre dos puntos de una red de carreteras o como recorrer todos las estaciones de metro sin pasar dos veces por ninguno de los puntos.

En nuestro entorno, podemos ver algunos ejemplos de aplicaciones reales de esta tecnología:

Google Knowledge Graph

Como se ha comentado anteriormente, una de las principales características de los grafos de conocimiento es la mejora de tareas de procesamiento de lenguaje natural, gracias a la incorporación de información semántica. Esta característica hace que este tipo de estructuras sean idóneas para la construcción de buscadores en lenguaje natural.

Desde hace algo más de dos años Google, el buscador más importante del mundo online, ha incorporado un Knowledge Graph a su algoritmo de búsqueda que es capaz de desambiguar la búsqueda y contextualizarla, mejorando de manera notable el funcionamiento del mismo para la ejecución de búsquedas semánticas.

Gracias a ello, el buscador es capaz de responder con información concreta y detallada que da respuesta de manera directa a nuestra consulta sin la necesidad de tener que acceder a ninguna de las páginas web que nos muestra también como resultado de la búsqueda.

Fuente: https://medium.com/@ira.manzano/knowledge-graph-una-nueva-fuente-de-conocimiento-ca645a77fd68

Graph Databases

El mundo de hoy puede ser representado en grafos para entenderlo casi a plenitud. Los modelos de grafos para gestión de bases de datos son extremadamente potentes y nos permiten conocer información que está escondida a simple vista.

Vamos a profundizar el mundo de los grafos para que descubramos juntos sus potencialidades, tipos, orden y algunas herramientas de visualización que puedes utilizar para tus proyectos.

¿Qué son grafos?

Los grafos son una composición interesante de conjuntos de objetos que denominamos nodos. En ellos se almacena diferentes tipos de elementos o datos que podemos utilizar para procesar o conocer con fines específicos.

Adicionalmente estos nodos, suelen estar unidos o conectados a otros nodos a través de elementos que denominamos aristas.

Los nodos pertenecientes a un grafo pueden contener datos estructurada o no estructurada y al interrelacionarse con otros nodos producen relaciones interesantes que podemos analizar con diferentes finalidades.

Estos elementos son reconocidos por su capacidad de manejar altos volúmenes de datos y ser fácilmente procesados por motores de búsqueda o gestores de bases de datos orientados a grafos.

Potencialidades de los grafos

Estos elementos matemáticos que conocemos como grafos son muy utilizados en el estudio de ciencias naturales y otras áreas del conocimiento.

En el ámbito empresarial y tecnológico se han empezado a explotar sus potencialidades.

Su alcance con fines empresariales recorren desde la posibilidad de estudiar las relaciones de los clientes con los productos que ofrecemos, hasta la posibilidad de entender a profundidad todos y cada uno de los procesos relacionales que se desarrollan dentro de una organización y que son imperceptibles a simple vista.

Los grafos inclusive son útiles para combatir el crimen. Recientemente se han aprovechado sus ventajas inigualables para estudiar patrones sospechosos de fraude electrónico y bancario.

La lucha contra el blanqueo de capitales en un sistema financiero incrementa en gran medida su eficiencia con la incorporación de estas herramientas tecnológicas.

Conozcamos un poco más acerca de la teoría que le da nacimiento a estos impresionantes elementos.

Teoría de grafos

La Teoría de grafos es una mezcla impresionante de cultura, historia, soluciones matemáticas y retos que llevaron un buen tiempo para ser resueltos con fórmulas matemáticas.

La teoría de grafos nació con la finalidad de representar de forma visual conjuntos abstractos de datos que se encuentran en el mundo real para ser útiles en soluciones de problemas de complejidad.

Orígenes

Los primeros desarrollos cercanos a la teoría de grafos pueden encontrarse en el año 1736 con la irrupción de un estudio matemático desarrollado por Leonhard Euler.

Al intentar demostrar la posibilidad de recorrer todos los puentes de Konisberg con una ruta donde no se repitiera recorrido nació el interés científico del mundo por esta materia.

Posteriormente primeros aportes formales a esta teoría nacieron  los circuitos estudiados por Kirchhoff y la teoría de los mapas coloreados de Guthrie que representó un reto titánico casi imposible de resolver.

El reto de la coloración de más resuelto por Appel y Haken dio el nacimiento formal a la teoría de grafos. De ella se desprenden conceptos como los que ya fueron abordados líneas arriba como los de nodos y aristas. El surgimiento de esta teoría ha permitido darle una interpretación diferente a los datos.

Los postulados de esta teoría dan nacimiento a los grafos tal cual los conocemos en la actualidad. Ha contribuido inclusive a la creación de una nueva forma de ver el mundo. Ahora podemos comprender el mundo de los datos con imágenes.

Imágenes de grafos

Uno de las necesidades más interesantes que han cubierto los grafos es la posibilidad de darle visibilidad a los datos más allá de los registros. Las imágenes de grafos nos permiten conocer a detalle la estructura en la que está contenido el conjunto de datos a analizar y todas sus relaciones.

Utilidades de las imágenes de grafos

Los grafos en imágenes nos permiten entender la profundidad de las relaciones que existen entre los datos. Gracias a estas propiedades de análisis los analistas comerciales de las empresas pueden comprender mejores los segmentos de mercado y optimizar las propuestas de productos y servicios para sus clientes.

Uno de los sectores que más puede sacarle provecho a las propiedades de las imágenes de grafos es el sector financiero y bancario. Los análisis de grafos que arrojan estás imágenes son extremadamente útiles para la prevención de delitos financieros como el blanqueo de capitales o el fraude electrónico.Imagen de grafo

Visual de un grafo

Los sistemas financieros pueden construir estructuras gráficas similares a la de la imagen anterior para representar a sus clientes en nodos.

Con las aristas que conectan los nodos podemos conocer las relaciones que se generan entre ellos y según la configuración de patrones de riesgo podemos detectar actividad inusual e ir a profundidadimagén grafo

Visualización de un grafo en la prevención de blanqueo de capitales

Al detectar un patrón de riesgo o actividad sospechosa de actividad delictivos podemos obtener imágenes específicas dentro del grafo para analizar las operaciones realizadas de forma eficiente y rápida para evitar operaciones fraudulentas.

Tipos de grafos

Como podéis observar, los grafos ofrecen un amplio esquema de posibilidades. Esto es en parte gracias a sus versátiles formas de composición. Existen múltiples tipos de grafos que cuentan con características especiales.

Los grafos simples son los que se generan cuando un conjunto no vacío de vértices o nodos está unido a otro a través de una o más aristas. De acá en adelante empieza a incrementar el grado de complejidad de los grafos y también aumentan sus ventajas.

Adicionalmente tenemos el multigrafo que es una versión ligeramente más compleja en la que los nodos que conforman el grafo se conectan con otros nodos a través de aristas múltiples o paralelas.

Grafos dirigidos, completos, conexos y etiquetados.

Dentro de los principales tipos de grafos que podemos estudiar están los grafos dirigidos.

Éstos son una especie de grafo que cuentan con elementos clásicos de un grafo simple pero con la particularidad de que sus aristas que conectan los nodos tienen una direccionalidad clara. Adicionalmente a los grafos dirigidos tenemos los que conocemos como grafos completos.

Un grafo completo de forma similar cumple con los requisitos de un grafo simple o dirigido. La diferencia que se presenta en este tipo de grafos es que cada par de nodos debe estar interconectado entre sí con diferentes conjuntos de aristas que conforman un camino.

Por su parte los grafos conexos son aquellos que cumplen con una condición especial. Para que un grafo se considere conexo entre los nodos que lo integran deben existir “caminos simples”. De esta estructuración de nodos nace lo que conocemos como árboles de grafos.

Sumado a esta clasificación tenemos los grafos etiquetados. A diferencia de los tipos de grafos anteriores, los grafos etiquetados incorporan datos en las aristas que le proporcionan peso a un grafo y estos son los más comunes en el mundo informático en el que vivimos.

Orden de un grafo

Una de las características de gran importancia dentro del mundo de los grafos es el orden. Este es el que se define por el número o cantidad de vértices que posee un grafo.

Esto nos dice que la forma y la direccionalidad de los vértices comprometen la composición del grafo de forma significativa.  Este puede ser de forma cíclica o alineada a otros grafos. Para esto existen fórmulas especiales con las cuales podemos calcular el ´orden de un grafo.

que son los grafos

Cómo calcular el orden de un grafo

Para calcular el orden de un grafo debemos ejecutar una fórmula relativamente simple en la cual tomamos n(n-1)/2. Se selecciona el primer vértice del grafo nombrandolo como a y se suma hasta b. pudiendo seleccionar a y b en diferentes formas (ab o ba).

Al tomar otro vértice entonces tenemos que tener presente que es n-1 vértices para no incurrir en una doble sumatoria ya que ab o ba implican una misma conexión.

Tipos de orden de grafos

El orden de un grafo es de alguna manera una de las operaciones de mayor relevancia que debemos realizar, porque con esto logramos obtener información de utilidad para entender las relaciones que existen entre los datos.

Un método para ordenar un grafo es desde el cálculo de su distancia o los saltos que este grafo posea. La distancia en un grafo no se refiere a la longitud de las aristas, sino en el número de nodos que deben recorrerse para reunir la información que buscamos.

El orden de grafos mediante este método funciona bastante bien para grafos en árbol y grafos lineales, ya que utilizan un solo nodo como punto de partida.

Orden cíclico y con otro grafo

Dentro de los órdenes que podemos establecer sobre los grafos destaca el orden cíclico y el orden con otro grafo. Para el caso del orden cíclico existe un método directo en el que podemos establecer el orden del grafo.

Se parte de un vértice dado en cero y los demás vértices se deben organizar en el sentido de las agujas del reloj.

En cuanto a ordenar un grafo con otro, debemos conectar dos nodos enteros con otro nodo, devolviéndonos un subgrafo.

Grafos en Java

Los grafos como ya hemos destacado pueden ser representado de forma visual, lo que nos permite entender el conjunto de relaciones que integran sus datos.

Ahora bien, las formas de representar un grafo son diversas gracias a las múltiples y avanzadas herramientas de visualización de la que te comentaremos más adelante.

Es posible construir un gráfico en Java, con la particularidad de que su representación es estática. Nos permite obtener un corte directo del conjunto de datos como el que se presenta en la imagen a continuaciónjava graph

Ejemplo de visualización de un grafo en Java

En ella se puede identificar con facilidad las aristas y múltiples conexiones de cada vértice. Estas imágenes son útiles para analizar sectores específicos de datos.

Knowledge Graph

Un grafo de conocimiento es un modelo muy interesante creado con la ayuda de algoritmos que progresivamente van incorporando el contenido que de alguna manera aprenden.

Este tipo de grafo proporciona una estructura e interfaz común para los datos, lo que permite la creación de relaciones inteligentes a través de los conjuntos de datos que la componen.

Este tipo de grafos se han estado haciendo presentes con mayor frecuencia en nuestra interacción digital.

Estos han sido incorporados en estructura de búsqueda como google o en plataformas sociales como Facebook para ofrecer búsquedas de información más específica y compleja a los usuarios.

Herramientas de visualización de grafos

Vamos a un asunto serio. Como habéis podido observar, somos fanáticos de los grafos gracias a las múltiples propiedades que hemos destacado.

En parte nuestro entusiasmo se debe a lo que vamos a abordar a continuación, las herramientas de visualización de grafos. Las herramientas de visualización de grafos son softwares de extrema utilidad en la era del Big data.

Los grafos son elementos complejos compuestos de nodos y aristas donde podemos alojar un gran conjunto de datos, características y elementos de los cuales podemos analizar y estudiar su comportamiento.

La visualización de grafos es la representación de un conjunto completo donde podemos observar la posición de los vértices y la orientación de las aristas que dan forma al grafo.

Con esto se busca darle una imagen mental al conjunto de datos y su incorrecta representación puede afectar la comprensión, usabilidad y costo de la información.

Mejores herramientas de visualización de grafos

Existe una buena variedad de herramientas para visualizar grafos. Analicemos algunas de las mejores marcas a continuación

Gephi

Es un software open source que goza de una buena reputación en el ámbito científico y en el análisis de redes sociales. Cuenta con un motor de renderización y herramientas de  manipulación de datos de alto desempeño para descubrir patrones de comportamiento en los datos de forma intuitiva.

Graphviz

Esta es una herramienta de visualización de grafos que contiene un gran conjunto de aplicaciones orientadas al diseño visual de grafos. Posee un conjunto de interfaces interactivas que complementan sus actividades con herramientas auxiliares y bibliotecas. Este software es ejecutable en cualquier sistema operativo.

Sigma

La herramienta de visualización de grafos Sigma es una biblioteca construida en JavaScript muy interesante. Permite la elaboración de dibujos de redes de grandes conjuntos de datos y su fácil integración a aplicaciones web en tiempo real. Esta herramienta ofrece una gran cantidad de prestaciones integradas como los renderizadores Canvas y WebGl. También nos ofrece la posibilidad de realizar los dibujos en pantallas táctiles.

JUNG

JUNG (Java Universal Network Graph Framework) es una biblioteca de software que permite el modelado, análisis y visualización de gafos. Está construida en JAVA lo que ofrece una gran ventaja debido a que pueden aprovecharse múltiples aplicaciones y características desde la API, así como existe también la facilidad de vincularse otras bibliotecas de Java.

JUNG incluye implementaciones de una serie de algoritmos de la teoría de grafos, minería de datos y análisis de redes sociales entre los que destacan las rutinas de agrupamiento, descomposición, cálculo de distancias de red, generación de gráficos aleatorios entre otros.

Linkurious

Linkurious es una plataforma de análisis y visualización de grafos que en los últimos tiempos ha ganado renombre internacional. Brinda un conjunto de características impresionantes que nos permiten analizar múltiples fuentes de datos. Cuenta con un soporte incorporado para las principales bases de datos de grafos. Podemos obtener imágenes completas, eliminando puntos ciegos y reduciendo considerablemente el tiempo de seguimiento de la información.

Logo Linkurious

Esta herramienta posee un sistema de alarmas que ayuda a detectar de forma eficiente amenazas en miles de millones de entidades en tiempo real. Estas alarmas son totalmente configurables con reglas que se adapten a las necesidades de investigación. Su sistema de programación es altamente intuitivo y no requiere un rango de especialización profundo. Esto también ayuda a los analistas a determinar rápidamente las amenazas reales en los esquemas que se planteen.

¿Qué herramienta de visualización debo escoger?

Si debes elegir entre algunas de estas maravillosas opciones, la respuesta la conseguirás solo en tu proyecto. Todos estos softwares ofrecen ventajas interesantes e importantes a considerar, pero la decisión central gira en torno a sus necesidades.

De Bases de datos relacionales a Grafos

Para comprender la importancia actual de los grafos, debemos entender la procedencia o el inicio de la historia de la gestión de datos desde su inicio. Las bases de datos relacionales que implementan un lenguaje declarativo nos permite ejecutar consultas específicas desde el código de la aplicación relacional que estemos usando.

Estas bases de datos siguen representando una solución efectiva a algunos requerimientos que pueden presentarse en nuestros proyectos. Es importante recordar que las bases de datos relacionales siguen gozando de gran aceptación por su facilidad de estructuración y por ofrecer mucha seguridad en el análisis de datos.

También es importante recordar que el lenguaje Cypher que es muy común en herramientas o bases de datos orientadas a grafos se basa en los conceptos bases de SQL pero con funciones adicionales.

De Bases de datos No SQL a Grafos

Es una verdad casi absoluta decir que el Big Data cambio las reglas de juego en el mundo tecnológico.

Las bases de datos No SQL tomaron el protagonismo e impusieron una nueva forma de interpretar el mundo ya que prestan soluciones a problemas más complejos que con una base de datos relacional es difícil o muy costoso de resolver.

También es cierto que las BBDD orientadas a grafos le dieron también una vuelta al tablero.

Las bases de datos No SQL en comparación a las BBDD de grafos orientan su trabajo a agregados de datos con criterios particulares como objetos, documentos o claves valor.

Estos modelos aportan operaciones muy rápidas, pero limitadas en cuanto a la visibilización de los datos. Precisamente este es el punto fuerte de las bases de datos orientadas a grafos.

Podemos analizar grandes conjuntos de agregados de forma visual y manipulable para poder entender sus relaciones garantizando los estándares ACID.

Comparación entre Bases No SQL y Bases de datos orientadas a Grafos

Tomando los principales modelos de bases de datos No SQL podemos encontrar que hay diferencias marcadas y muchas posibilidades de complementar su funcionamiento.

Por ejemplo las bases de datos de clave valor son altamente escalables con facilidad, pero la posibilidad de observar sus datos es de baja profundidad al compararse con los grafos que nos permiten ir totalmente al fondo o la raíz de los datos.

Ahora bien podemos comparar las bases de datos de grafos con los modelos orientados a documentos.

La jerarquía estructurada de un documento ordena gran cantidad de datos sin esquemas. Estos podemos representarlas como un árbol que representa una sola proyección o perspectiva de los datos.

En este caso la desventaja de la base de datos orientada a documentos es que la manipulación o el contexto que brinda son mínimos.

Esperamos que este extenso recorrido por el interesante mundo de los grafos te sea de utilidad para tu proyecto.

Visita más en Grapheverywhere para conocer a profundidad más sobre bases de datos.

Fuente: https://www.grapheverywhere.com/grafos-que-son-tipos-orden-y-herramientas-de-visualizacion/

Deja un comentario