Archivo de la etiqueta: grafos

Bases de Datos NoSQL de grafos: mejor rendimiento para grandes volúmenes de datos

Como saben, la semana pasada, organizamos un evento titulado “Las tecnologías Big Data al servicio de la sociedad“.  Un evento en el que a través del famoso caso de los Papeles de Panamá, tratábamos de divulgar la utilidad que tiene este nuevo paradigma del Big Data -sus métodos y tecnologías- también para beneficio de toda la sociedad.

Iremos, a lo largo de los próximos días difundiendo los contenidos y materiales generados para esa sesión. Empezamos la serie hablando de la intervención de Mario Iñiguez, Co-founder de Adamantas Analytics, que nos explicó cómo poner en valor las tecnologías de Big Data con las Bases de Datos NoSQL de grafos.

Las Bases de Datos NoSQL aparecen a la par de la explosión de la web 2.0. En ese momento, se produce un crecimiento espectacular del volumen de datos. Además, generado por el propio usuario, con información volátil, variada, no estructurada y extensa. Las relaciones se multiplican, no existe una estructuración previa. En este contexto, el paradigma de Bases de Datos Relacional que venimos usando desde los años 70, nos limitaba mucho. Un modelo de datos estático y con dificultad de adaptación a cambios, que dispone de relaciones explícitas entre tablas, es un paradigma que no casa bien con esta explosión de datos no estructurados.

Ahí es cuando empezamos a hablar de la necesidad de disponer de un nuevo paradigma. Lo bautizamos como NoSQL, manifestando claramente su desvinculación de este paradigma relacional que había venido siendo imperante hasta entonces.  Y, aparecen, cuatro nuevos tipos de bases de datos:

  • Clave valor: el más popular, además de ser la más sencilla en cuanto a funcionalidad. Cassandra, BigTable o HBase son ejemplos de este tipo. Son bastante eficientes tanto en lectura como en escritura. En nuestro programa vemos Cassandra.
  • Columnares: las bases de datos, en lugar de estar estructuradas por filas, están estructuradas por columnas. Al tratarse de una sola dimensión, hace más eficiente la recuperación de la información. En nuestro programa, trabajamos con Vertica.
  • Documentos: almacena la información como un documento, permitiendo realizar consultas bastante avanzadas sobre el mismo. Por ello, suele considerarse como el más versátil. MongoDB o CouchDB son ejemplos de ello. Nosotros en nuestro Programa de Big Data hacemos alguna sesión práctica con MongoDB.
  • Grafos: los datos son representados como nodos y aristas que modelizan la relación entre esos nodos. De esta manera, podemos emplear la teoría de grafos -de lo que ya hemos hablado en el pasado– para recorrer y navegar por su contenido. Su principal ventaja es que permite una navegación más eficiente entre relaciones que en un modelo relacional. Neo4J -la empleada en el caso de los Papeles de Panamá- o Virtuoso son ejemplos de ello, siendo Neo4J la que vemos en nuestro programa y sobre la que sacaremos un programa específico el próximo Otoño (dada la relevancia que va adquiriendo, por lo que ya informaremos de ellol).

Este último tipo, el de grafos, fue el que nos introdujo Mario y sobre el que nos contó sus bondades. Uno de los elementos que destacó Mario es cómo esta forma de representar la información se aproxima bastante al pensamiento humano (cómo representamos la información en nuestro cerebro). A través de varios ejemplos (éste de Open Corporates de Goldman Sachs o éste de la complejidad económica del MIT), vimos las principales ventajas de representar la información en grafos. Que, básicamente, se resumen en un tiempo de ejecución bastante menor que una base de datos relacional (en la transparencia 7 de la siguiente presentación podéis ver la comparativa empírica que hizo Mario).

Para concluir, Mario nos resumió las principales utilidades de este nuevo tipo de bases de datos NOSQL de grafos:

  • Disponer de más información con agilidad y eficiencia (lugares más visitados, análisis de sentimiento, rutas y medios, quejas y reclamaciones, círculos de influencia, etc.)
  • Y, desencadenar acciones (mejora de infraestructuras, mejora de servicios, mejora de la oferta turística, oportunidades de negocio, promoción comercio local)

Además, os dejamos un vídeo donde le preguntaba por los principales puntos que trató durante su intervención y que provocó varias preguntas de la audiencia. Como concluíamos, el modelo relacional podría tener sus días contados si las tecnologías de BBDD NoSQL siguen mejorando el rendimiento y resultados de procesar grandes cantidades de datos. Será interesante ver la evolución.

Análisis de redes sociales: el poder de la teoría de grafos

Cuando hablamos de procesamiento de datos, automáticamente a muchos de nosotros nos vienen muchos números a la cabeza, muchas técnicas estadísticas, conclusiones cuantitativas, etc. Esto es así, pero es que hay mundo más allá de los números. Dos de las explotaciones de datos que más popularidad están ganando en los últimos tiempos, especialmente derivado de que se estima (más arriba, más abajo) que aproximadamente el 80% de los datos son desestructurados, son el análisis de textos y el análisis de redes sociales.

El análisis de textos o Text Mining hace  referencia al análisis de textos o contenidos escritos sin ningún tipo de estructura. Se calcula que el 80% de la información de una empresa está almacenada en forma de documentos. Sin duda, este campo de estudio es muy amplio, por lo que técnicas como la categorización de texto, el procesamiento de lenguaje natural, la extracción y recuperación de la información o el aprendizaje automática, entre otras, apoyan el text mining (o minería de texto).

El segundo campo en el que veremos gran recorrido (ya lo estamos viendo) es el análisis de redes sociales o estructuras de grafos. Ya hablamos de ello en un artículo anterior. No es solo análisis de las redes sociales entendidas como análisis de contenido de Social Media. Es un estudio numérico, algebraico, de una representación de conocimiento en formato de grafo. Un campo que mezcla la sociología y las matemáticas (el álgebra de grafos) en el que hay actores o entidades que interactúan, pudiendo representar estas acciones a partir de un grafo.

Un grafo o representación de la interacción entre entidades o actores a través del álgebra de grafos (Fuente: http://www.adictosaltrabajo.com/tutoriales/web-htmlcomo-grafo/)
Un grafo o representación de la interacción entre entidades o actores a través del álgebra de grafos (Fuente: http://www.adictosaltrabajo.com/tutoriales/web-htmlcomo-grafo/)

El interés por estudiar los patrones y estructura que esconden esta representación de nodos y aristas ha crecido en los últimos años a medida que ha aumentado la relación entre agentes. Es decir, a medida que han crecido las redes sociales (¿cómo se relacionan mis clientes en facebook?), ha crecido la influencia de una persona en otra para comprar (los millenials confían más en la reputación de sus amigos que en la publicidad de las marcas), las redes de proveedores y clientes han aumentado sustancialmente (por la globalización de la economía y la interconexión internacional), etc., crece el interés por estudiar qué patrones pueden descubrirse para incrementar la inteligencia del negocio.

¿Y por qué esto de interés ahora? En la medida en que un problema dado (acordaros, primer paso de un proyecto Big Data), puede ser modelado mediante un grafo y resuelto mediante algoritmos específicos de la teoría de grafos, la información que podemos obtener es muy relevante. Esto es algo que los topógrafos (cómo enlazar las estaciones del metro de Nueva York de la manera más eficiente para todas las variables a optimizar -distancia, coste, satisfacción usuario, etc.-) o los antropólogos (cómo se han relacionado las especies y los efectos producidos unos en otros) llevan muchos años ya explotando. Ahora, da el salto al mundo del consumo, la sanidad, la educación, etc.

¿Qué nos puede aportar un grafo, una red social, y su análisis a nuestros interes? Las redes sociales pueden definirse como un conjunto bien delimitado de actores como pueden ser individuos, grupos, organizaciones, comunidades, sociedades globales, entre otros. Están vinculados unos a otros a través de una relación o un conjunto de relaciones sociales. El análisis de estos vínculos puede ser empleado para interpretar comportamientos sociales de los implicados. Esto es lo que ha venido a denominarse el Análisis de Redes Sociales o ARS (Social Network Analysis, o SNA).

Dentro del ARS, uno de los conceptos clave es la Sociometría. Su fundador, Jacob Levy Moreno, la describió como:

“La sociometría tiene por objeto el estudio matemático de las propiedades psicológicas de las poblaciones; con este fin utiliza una técnica experimental fundada sobre los métodos cuantitativos y expone los resultados obtenidos por la aplicación de estos métodos. Persigue así una encuesta metódica sobre la evolución y la organización de los grupos y sobre la posición de los individuos en los grupos”.

Usando una herramienta interactiva como Gephi,  se puede visualizar, explorar y analizar toda clase de redes y sistemas complejos, grafos jerárquicos y dinámicos. Es decir, hacer sociometría. Una herramienta de este tipo nos permitirá obtener diferentes métricas, que podemos clasificar en tres niveles:

  1. Nivel global de un grafo
    • Coeficiente de agrupamiento: nivel de agrupamiento de los nodos, para saber cómo de cohesionados o integrados están los agentes/actores.
    • Camino característico: mide el grado de separación de los nodos, para determinar lo contrario al punto anterior: cómo de separados o alejados están, y poder buscar así medidas para juntar más la relación entre agentes/actores.
    • Densidad: un grafo puede ser denso (cuando tiene muchas aristas) o disperso (muy pocas aristas). En este sentido, se puede interpretar como que hay mucha o poca conexión.
    • Diámetro: es el máximo de las distancias entre cualesquiera par de nodos. De esta manera, sabemos cómo de “alejados” o “próximos” están en agregado a la hora de comparar varios grafos.
    • Grado medio: número de vecinos (conexiones a otros nodos) medio que tiene un grado. Indicará cuál es la media de conexiones que tiene un nodo, de manera que se puede saber su popularidad..
    • Centralidad: permite realizar un análisis para indicar aquellos nodos que poseen una mayor cantidad de relaciones y por ende, los influyentes dentro del grupo. De esta manera, sabemos su “popularidad”, lo que nos puede dar mucha información para saber la importancia de un nodo dentro del total.
  2. Nivel comunidad (grupos de nodos dentro de un grafo)
    • Comunidades: instrumento para conocerse a sí mismo, para conocer a los otros, al grupo concreto que vive su momento, y en general a los grupos que viven procesos similares. De esta manera, podemos agrupar a los nodos por patrones de similtud.
    • Puentes entre comunidades: ¿cómo se conectan estas comunidades? ¿cómo de comunicables son esas comunidades? Para trazar planes de actuación o de marketing.
    • Centros locales vs. periferia: para saber, dentro de las comunidades, los nodos que son más centrales o críticos, frente a los que no lo son.
  3. Nivel nodo (propiedades de un influenciador dado)
    • Centralidad: es una métrica de poder. El valor 0.522 para la centralidad de un nodo indica que si para cada par de influenciadores buscamos el camino más corto en el grafo, el 52.2% de estos caminos pasa por ese influenciador. Mide su popularidad, y el algoritmo de Google, por ejemplo, funcionó durante mucho tiempo así, siendo cada nodo, una página web o recurso en Internet.

      Métricas de un nodo en una red (Fuente: http://historiapolitica.com/redhistoria/imagenes/ndos/larrosa4.jpg)
      Métricas de un nodo en una red (Fuente: http://historiapolitica.com/redhistoria/imagenes/ndos/larrosa4.jpg)
    • Modularidad: la modularidad es una medida de la estructura de las redes o grafos. Fue diseñado para medir la fuerza de la división de una red en módulos (también llamados grupos, agrupamientos o comunidades). Las redes con alta modularidad tienen conexiones sólidas entre los nodos dentro de los módulos, pero escasas conexiones entre nodos en diferentes módulos.
    • Intermediación: se puede enfocar como la capacidad que inviste el nodo en ocupar una posición intermediaria en las comunicaciones entre el resto de los influenciadores. Aquellos, con mayor intermediación tienen un gran liderazgo, debido a que controlan los flujos de comunicación. Y esto, de nuevo, da mucha inteligencia a un negocio.
    • Pagerank: algoritmo que permite dar un valor numérico ( ranking ) a cada nodo de un grafo que mide de alguna forma su conectividad. Es el famoso pagerank que utilizó Google (de hecho, el algoritmo fue diseñado por los creadores de Google, que es de donde viene su pasado matemático).
    • Closeness: cuán fácil es llegar a los otros vértices. Indicará, por lo tanto, cómo de cerca queda ese influenciador para llegar a contactar con otros. Esto, permite saber cuán importante es ese nodo dentro de la red de influencia para eventuales comunicaciones o relaciones con otros nodos.

Todo esto ya se está empleando en campos tan diversos como el marketing digital (para la detección de influenciadores entre los seguidores, de especial importancia en la economía colaborativa, donde la reputación online es clave de consumo), el fútbol (para la detección que Xavi y Xabi Alonso fueron la clave en el campeonato de Sudáfrica para que España ganase, en lugar de Iniesta, autor del gol), optimización de rutas de distribución (por ejemplo, la de un taxi, en tiempo real, para evitar congestiones en ciudades como Pekín o New York), conocer los tipos de conversaciones que se mantienen con tu audiencia/comunidad (muy usado en televisión y Twitter), saber cuáles son los drivers de compra que más afectan a las decisiones de consumo de tus clientes, etc.

Y tú, ¿a qué esperas para que el análisis de grafos puedan aportarte inteligencia a tu representación en forma de red social? De nuevo, las matemáticas, además de la sociología, a disposición de la inteligencia de un negocio. Bienvenidos al análisis de redes sociales.

Evitando el fraude a través de la presentación de la información en grafos

En nuestro workshop del pasado 27 de Octubre, también estuvo como ponente Jesús Barrasa, Field Engineer de Neo Technology. Básicamente, el  objetivo de su ponencia fue contarnos cómo poder prevenir el fraude a través de la modelización de la información en grafos. Este formalización matemática, que ha ganado bastante popularidad en los últimos años, permite una expresividad de información tan alta, que para muchas aplicaciones donde el descubrimiento de la información es crítica (como es el evitar el fraude), puede ser vital.

Pero, empecemos por lo básico. Jesús, nos describió lo que es un grafo. Un conjunto de vértices (o nodos), que están unidos por arcos o aristas. De este modo, tenemos una información representada a través de relaciones binarias entre el conjunto de elementos. Fue Leonhard Euler, matemático suizo, el inventor de la teoría de grafos en 1736. Por lo tanto, no estamos hablando de un instrumento matemático nuevo.

Un grafo, como conjunto de vértices y arcos (Fuente: https://www.flickr.com/photos/thefangmonster/352461415/in/photolist-x9suX-fDVc6-88T8hQ-7X9u8d-afsXkh-i6KLs-6PpBb6-836Ttv-85z1hy-rA46-rjfq-5RTzeU-bDcg8x-f5s1g3-a1Jv37-bsDVCK-7i62o-5WbpbF-i6LKS-aRBH8x-5RPjSa-h1Xkr2-4d5ypn-DifCQ-7SGo1D-9C4Y3c-noNEE9-7noTPo-7dYzTc-7dYzxZ-d672zw-99Z1f9-bz2Y9P-bquhCW-881tVy-4vn6sS-7Zebpn-4t7P4n-bdYG1z-ePUf2-aVcE68-f7Tsq-7JdUAY-bmhmrn-e2KEC6-63bkHm-e8zMaZ-88V6bY-9ZjTax-7SGo6Z)
Un grafo, como conjunto de vértices y arcos (Fuente: https://www.flickr.com/photos/thefangmonster/352461415/in/photolist-x9suX-fDVc6-88T8hQ-7X9u8d-afsXkh-i6KLs-6PpBb6-836Ttv-85z1hy-rA46-rjfq-5RTzeU-bDcg8x-f5s1g3-a1Jv37-bsDVCK-7i62o-5WbpbF-i6LKS-aRBH8x-5RPjSa-h1Xkr2-4d5ypn-DifCQ-7SGo1D-9C4Y3c-noNEE9-7noTPo-7dYzTc-7dYzxZ-d672zw-99Z1f9-bz2Y9P-bquhCW-881tVy-4vn6sS-7Zebpn-4t7P4n-bdYG1z-ePUf2-aVcE68-f7Tsq-7JdUAY-bmhmrn-e2KEC6-63bkHm-e8zMaZ-88V6bY-9ZjTax-7SGo6Z)

Pues bien, este tipo de representación de información (en grafos) es el tipo de bases de datos que más está ganando en popularidad en los últimos años (consultar datos aquí). Su uso en aplicaciones como las redes sociales (y todo lo que tiene que ver con el Análisis de Redes Sociales o Social Network Analysis), el análisis de impacto en redes de telecomunicaciones, sistemas de recomendación (como los de Amazon), logística (y la optimización de los puntos de entrega -vértices- a través de la distancia entre puntos – longitud de las aristas -), etc., son solo algunos ejemplos de la potencia que tiene la representación de la información en grafos.

Jesús nos introdujo un caso concreto que desde Neo Technology han trabajado para la detección y prevención del fraude. Un contexto de aplicación, que además de tener cierta sensibilidad social en los últimos años, no solo es aplicable al ámbito económico, sino también a muchos otros donde el fraude ha sido recurrente y muy difícil de detectar. El problema hasta la fecha es que los límites del modelo relacional de bases de datos (el que ha imperado hasta la fecha) han traído siempre una serie de asuntos que complicaban la detección:

  • Complejidad al modelizar relaciones (por asuntos como la integridad relacional, etc.)
  • Degradación del rendimiento al aumentar el número de asociaciones y con el volumen de datos
  • Complejidad de las consultas
  • La necesidad de rediseñar el esquema de datos cuando se introducen nuevas asociaciones y tipos de datos
  • etc.

Estos puntos (entre otros), hacen que las bases de datos relacionales tradicionales resulten hoy en día inadecuadas cuando las asociaciones entre puntos de datos son útiles y valiosas en tiempo real. Y aquí es donde las bases de datos NoSQL (orientadas a documentos, las columnares, las de grafos, etc.), son bastante útiles para soliviantar este problema.

Introducida esta necesidad por las bases de datos de grafos, Jesús nos contó el caso concreto de los defraudadores. Personas que solicitan líneas de crédito, actúan de manera aparentemente normal, extienden el crédito y de repente desaparecen. De hecho, decenas de miles de millones de dólares son defraudados al año solo a bancos estadounidenses. 25% del total de créditos personales son amortizados como pérdidas. Para prevenir esto, la modelización de los datos como grafos puede ayudar.

¿Qué es lo que se representa como un grafo? ¿Qué datos/información? Lo que Jesús denominó los anillos de fraude (que podéis encontrar en la imagen debajo de estas líneas). Acciones que va realizando un usuario, y que como son representadas a través de relaciones, permite no solo detectar el fraude, sino también minimizar pérdidas y prevenirlo en la medida de lo posible a través de cadenas de conexión sospechosas.

Anillo de fraude (Fuente: Neo Technology)
Anillo de fraude (Fuente: Neo Technology)

Como siempre, os dejamos al final de este artículo las diapositivas empleadas por Jesús. Otro caso más de aplicación del Big Data y de mejora de las sociedades, empresas e instituciones a través de la puesta en valor de los datos. En este caso, los grafos.