# data[].attributes.body
El procesamiento paralelo y distribuido permite manejar grandes volúmenes de datos de manera eficiente al distribuir las tareas entre múltiples nodos o procesadores. Este tipo de procesamiento es esencial en la era de los Big Data, donde la cantidad de datos generados y almacenados excede la capacidad de procesamiento de un solo nodo o máquina.

El procesamiento paralelo implica dividir una tarea en subtareas más pequeñas que se ejecutan simultáneamente en diferentes núcleos de un procesador

# data[].attributes.body
Los grafos son estructuras de datos que representan relaciones entre objetos mediante nodos (o vértices) y aristas (o enlaces). Los grafos son fundamentales en diversas áreas como la teoría de redes, informática, biología, sociología, entre otras. Pueden representar redes de comunicación, estructuras de datos, relaciones en redes sociales, modelos biológicos, etc.

# data[].attributes.body
Grafo: conjunto de nodos y aristas.

Nodo: punto en el grafo.

Arista: línea que conecta dos nodos.

Grado de un nodo: número de aristas que conectan un nodo.

Camino: secuencia de nodos conectados por aristas.

Ciclo: camino cerrado que comienza y termina en el mismo nodo.

Grafo conexo: grafo en el que existe al menos un camino entre cualquier par de nodos.

Grafo completo: grafo en el que todos los nodos están conectados entre sí.

# data[].attributes.body
Redes sociales: los grafos se utilizan para representar las conexiones entre usuarios en una red social.

Sistemas de transporte: los grafos se utilizan para representar las conexiones entre ciudades o estaciones de transporte.

Telecomunicaciones: los grafos se utilizan para representar la red de comunicaciones entre dispositivos.

Biología: los grafos se utilizan para representar las interacciones entre proteínas en una célula.

Informática: los grafos se utilizan para representar la estructura de datos en un programa.

# data[].attributes.body
Grafo dirigido

Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada arista se asocia de forma unidireccional a través de una flecha con otro.

Grafo no dirigido

Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a un conjunto de aristas de forma no direccional.

Grafos etiquetados

Esta clasificación es denominada como grafos etiquetados o grafos dirigidos con pesos. Este tipo de grafos concentran aristas que pueden poseer información adicional donde podemos reflejar nombres, costos, valores u otros datos.

# data[].attributes.body
Definición

Es una plataforma de software que ayuda a los científicos de datos a descubrir las conexiones en grandes volúmenes de datos para responder preguntas comerciales críticas y mejorar las predicciones.

Algoritmos distribuidos que permiten manejarlos

PageRank: El algoritmo PageRank mide la importancia de cada nodo dentro del gráfico, en función del número de relaciones entrantes y la importancia de los nodos de origen correspondientes.

La suposición subyacente, a grandes rasgos, es que una página es tan importante como las páginas que enlazan con ella.

Community Detection: Los algoritmos de detección de comunidades se utilizan para evaluar cómo se agrupan o particionan los grupos de nodos, así como su tendencia a fortalecerse o separarse

# data[].attributes.body
Definición

Es un sistema desarrollado por Google para el procesamiento eficiente de grafos a gran escala mediante un modelo de computación distribuida.

Pregel utiliza un modelo de procesamiento basado en vértices, donde cada vértice en el grafo realiza computaciones locales y envía mensajes a otros vértices. El procesamiento se realiza en una serie de superpasos sincrónicos, donde todos los vértices ejecutan la misma función al mismo tiempo.

Algoritmos distribuidos que permiten manejarlos

Weakly Connected Components: dentifica los componentes débilmente conectados en un grafo. Un componente débilmente conectado es un subgrafo en el que cualquier nodo puede ser alcanzado desde cualquier otro nodo, ignorando la direccionalidad de las aristas.

Shortest Path: Encuentra el camino más corto entre dos nodos en un grafo.

# data[].attributes.attachment_link.readable_text
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.

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 profundidad

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.

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ón

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.

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.

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.

# data[].attributes.attachment_link.title
Grafos | Qué son, tipos, orden y herramientas de visualización

# data[].attributes.attachment_link.description
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.

# data[].attributes.body
Definición

Hadoop, con su sistema de archivos Hadoop Distributed File System (HDFS), es una herramienta fundamental para el procesamiento distribuido de datos, incluyendo grafos. Hadoop está diseñado para escalar de un solo servidor a miles de máquinas, cada una ofreciendo almacenamiento y computación local.

Su arquitectura se basa en el concepto de dividir grandes volúmenes de datos en bloques más pequeños que se distribuyen entre los nodos del clúster para su procesamiento paralelo y eficiente.

Algoritmos distribuidos que permiten manejarlos

MapReduce: Es el modelo de programación fundamental de Hadoop que posibilita el procesamiento distribuido de grandes volúmenes de datos, este modelo separa la tarea en dos fases principales: Map y Reduce. En la fase de Map, los datos de entrada se dividen en bloques y se procesan de manera paralela, generando pares intermedios de clave-valor. En la fase de Reduce, estos pares intermedios se agrupan y se combinan para producir el resultado final.

Giraph: es una extensión de Hadoop diseñada específicamente para el procesamiento de grafos a gran escala, además de que permite la ejecución de algoritmos de grafos en paralelo utilizando un modelo basado en vértices. Cada vértice puede enviar mensajes a otros vértices y actualizar su estado basado en los mensajes recibidos.

# data[].attributes.body
Definición

Es una herramienta de procesamiento paralelo que permite gestionar grandes volúmenes de datos, incluidos grafos, de manera eficiente. Spark proporciona un motor de procesamiento rápido y versátil para datos a gran escala, ofreciendo interfaces de alto nivel en Java, Scala, Python y R, además de un motor optimizado que soporta la ejecución general de gráficos DAG (Grafos Acíclicos Dirigidos).

Algoritmos distribuidos que permiten manejarlos

Connected Components: Este algoritmo identifica todos los componentes conectados dentro de un grafo. Un componente conectado es un subgrafo en el que existe un camino entre cualquier par de vértices. El algoritmo asigna una etiqueta a cada nodo y propaga estas etiquetas a través de las conexiones del grafo hasta que todos los nodos de un componente conectado compartan la misma etiqueta.

PageRank: El algoritmo PageRank mide la importancia de cada nodo dentro del gráfico, en función del número de relaciones entrantes y la importancia de los nodos de origen correspondientes.

La suposición subyacente, a grandes rasgos, es que una página es tan importante como las páginas que enlazan con ella.

# data[].attributes.body
El algoritmo PageRank mide la importancia de cada nodo dentro del gráfico, en función del número de relaciones entrantes y la importancia de los nodos de origen correspondientes.

Utilizado principalmente en motores de búsqueda para clasificar páginas web. Asigna una puntuación a cada nodo basada en la importancia de los nodos que apuntan hacia él.

# data[].attributes.body
Es un algoritmo que calcula las rutas más cortas desde un único vértice de origen hasta todos los demás vértices en un dígrafo ponderado. Es más lento que el algoritmo de Dijkstra para el mismo problema, pero más versátil, ya que es capaz de manejar gráficos en los que algunos de los pesos de los bordes son números negativos.

Su versión distribuida se usa para procesar grandes grafos de manera eficiente.

# data[].attributes.body
Este algoritmo se utiliza para identificar todos los componentes conectados dentro de un grafo. Un componente conectado es un subgrafo en el que existe un camino entre cualquier par de nodos. El algoritmo asigna una etiqueta a cada nodo y propaga estas etiquetas a través de las conexiones del grafo hasta que todos los nodos en un componente conectado tengan la misma etiqueta.

# data[].attributes.body
Es un subconjunto de las aristas de un grafo que conectan a todos los vértices usando el menor peso posible.

Encuentra el árbol de expansión mínima en un grafo ponderado. Su versión distribuida permite el procesamiento paralelo para grandes grafos.

# data[].attributes.body
Con el algoritmo de Dijkstra, puedes encontrar la ruta más corta o el camino más corto entre los nodos de un grafo. Específicamente, puedes encontrar el camino más corto desde un nodo (llamado el nodo de origen) a todos los otros nodos del grafo, generando un árbol del camino más corto.

Este algoritmo es usado por los dispositivos GPS para encontrar el camino más corto entre la ubicación actual y el destino del usuario. Tiene amplias aplicaciones en la industria, especialmente en aquellas áreas que requieren modelar redes.

# data[].attributes.attachment_link.title
Neo4j : Base de Datos Basada en Grafos - Breve Introducción 01

# data[].attributes.attachment_link.title
Pregel: The System That Changed Graph Processing - Graph Analytics for Big Data

# data[].attributes.attachment_link.title
Large-scale graphs with Google(TM) Pregel by MICHAEL HACKSTEIN at Big Data Spain 2014

# data[].attributes.attachment_link.readable_text
Pregel: A System for Large-Scale Graph Processing - Malewicz et al. (Google) 2010

"Many practical computing problems concern large graphs."

Yesterday we looked at some of the models for understanding networks and graphs. Today's paper focuses on processing of graphs, especially the efficient processing of large graphs where large can mean billions of vertices and trillions of edges. Pregel is the system at Google that powers PageRank, which makes it a very interesting system to study. It is also the inspiration for Apache Giraph, which Facebook use to analyze their social graph.

There are single machine-sized graph processing problems, and then there are distributed graph processing problems. You probably don't want to be using a distributed graph processing platform to solve a problem that would fit on one machine (See Musketeer), but if you really do have a large graph, then...

Efficient processing of large graphs is challenging. Graph algorithms often exhibit poor locality of memory access, very little work per vertex, and a changing degree of parallelism over the course of execution. Distribution over many machines exacerbates the locality issue, and increases the probability that a machine will fail during computation.

Pregel is Google's scalable and fault-tolerant platform with an API that is sufficiently flexible to express arbitrary graph algorithms. Within Google, even as of 2010:

Dozens of Pregel applications have been deployed, and many more are being designed, implemented, and tuned. The users report that once they switch to the "think like a vertex" mode of programming, the API is intuitive, flexible, and easy to use.

Google already had a distributed computing framework though, based on MapReduce. So why not just use that?

Pregel keeps vertices and edges on the machine that performs computation, and uses network transfers only for messages. MapReduce, however, is essentially functional, so expressing a graph algorithm as a chained MapReduce requires passing the entire state of the graph from one stage to the next - in general requiring much more communication and associated serialization overhead. In addition, the need to coordinate the steps of a chained MapReduce adds programming complexity that is avoided by Pregel's iteration over supersteps.

Let's first take a look at Pregel's programming model, and then we can dive into a few implementation details.

The Pregel Programming Model

The high-level organization of Pregel programs is inspired by Valiant's Bulk Synchronous Parallel model. Pregel computations consist of a sequence of iterations, called supersteps. During a superstep the framework invokes a user-defined function for each vertex, conceptually in parallel. The function specifies behavior at a single vertex V and a single superstep S. It can read messages sent to V in superstep S − 1, send messages to other vertices that will be received at superstep S + 1, and modify the state of V and its outgoing edges. Messages are typically sent along outgoing edges, but a message may be sent to any vertex whose identifier is known.

The synchronicity makes it easier to reason about program semantics, and ensures that Pregel programs are inherently free of deadlocks and data races.

Within each superstep the vertices compute in parallel, each executing the same user-defined function that expresses the logic of a given algorithm. A vertex can modify its state or that of its outgoing edges, receive messages sent to it in the previous superstep, send messages to other vertices (to be received in the next superstep), or even mutate the topology of the graph. Edges are not first-class citizens in this model, having no associated computation.

A Pregel program terminates when every vertex votes to halt. A vertex starts in the active state. It deactivates itself by voting to halt, after which time the Pregel framework will not execute that vertex in subsequent supersteps unless it receives a message. If reactivated by a message, a vertex must explicitly deactivate itself again. Communication is via message passing:

We chose a pure message passing model, omitting remote reads and other ways of emulating shared memory, for two reasons. First, message passing is sufficiently expressive that there is no need for remote reads. We have not found any graph algorithms for which message passing is insufficient. Second, this choice is better for performance. In a cluster environment, reading a value from a remote machine incurs high latency that can't easily be hidden. Our message passing model allows us to amortize latency by delivering messages asynchronously in batches.

Of course, the second reason does not apply if you are using RDMA. So it would be very interesting to see what a graph processing platform over RDMA might be able to do, similar in spirit to FaRM's key-value store over RDMA.

The sequence below shows the four supersteps needed to complete a maximum value calculation for a graph with four nodes. In each step, each vertex reads any incoming messages and sets its value to the maximum of its current value and those sent to it. It then sends this maximum value out along all of its edges. If the maximum value at a node does not change during a superstep, the node then votes to halt.

Vertices are addressed by (string) ids. If the destination vertex of a message does not exist, a user-defined handler is executed. This can manipulate the graph by e.g. creating the missing vertex, or removing the dangling edge from its source vertex.

Combiners are optional user provided functions that can combine multiple messages intended for a vertex into one - thus reducing the number of messages that must be transmitted and buffered. For the maximum value example, a combiner could collapse multiple messages into a single one containing the maximum for example.

There are no guarantees about which (if any) messages are combined, the groupings presented to the combiner, or the order of combining, so combiners should only be enabled for commutative and associative operations. For some algorithms, such as single-source shortest paths, we have observed more than a fourfold reduction in message traffic by using combiners.

Aggregators enable global information exchange:

Each vertex can provide a value to an aggregator in superstep S, the system combines those values using a reduction operator, and the resulting value is made available to all vertices in superstep S + 1.

Aggregators are quite flexible - for example the output of an aggregator can be used to control conditional branching in vertex compute functions, or a min or max aggregator applied to the vertex id can be used to select a vertex to play a distinguished role in an algorithm.

Finally, a vertex compute function can issue request to add or remove vertices or edges:

Some graph algorithms need to change the graph's topology. A clustering algorithm, for example, might replace each cluster with a single vertex, and a minimum spanning tree algorithm might remove all but the tree edges.

Mutations become effective in the superstep after the request were issued. Mutations are always applied in the following order: edge removal, vertex removal (which implicitly removes all of its out edges), vertex addition, edge addition. Any conflicts are resolved by user-defined handlers.

The Pregel Implementation

Pregel is designed to run on Google's cluster architecture.

The Pregel library divides a graph into partitions, each consisting of a set of vertices and all of those vertices' outgoing edges. Assignment of a vertex to a partition depends solely on the vertex ID, which implies it is possible to know which partition a given vertex belongs to even if the vertex is owned by a different machine, or even if the vertex does not yet exist. The default partitioning function is just hash(ID) mod N, where N is the number of partitions, but users can replace it.

Multiple copies of a user program begin executing on a cluster of machines. One of these as as the master and is responsible for coordinating worker activity. Workers use a name service to discover the master's location and register with it. Then,...

The master determines how many partitions the graph will have, and assigns one or more partitions to each worker machine. The number may be controlled by the user. Having more than one partition per worker allows parallelism among the partitions and better load balancing, and will usually improve performance.

After this point, parallel loading of the input graph occurs, with the master assigning portions of the input to each worker.

The division of inputs is orthogonal to the partitioning of the graph itself, and is typically based on file boundaries. If a worker loads a vertex that be- longs to that worker's section of the graph, the appropriate data structures are immediately updated. Otherwise the worker enqueues a message to the remote peer that owns the vertex. After the input has finished loading, all vertices are marked as active.

The master then instructs each worker to perform a superstep. A worker uses one thread for each partition it is responsible for, looping through the active vertices in each partition. Messages are sent asynchronously, but are delivered before the end of the superstep. The worker then tells the master how many vertices will be active in the next superstep. The master repeats this process so long as any vertices are active, or any messages are in transit.

Fault tolerance is achieved through checkpointing. At the beginning of a superstep, the master instructs the workers to save the state of their partitions to persistent storage, including vertex values, edge values, and incoming messages; the master separately saves the aggregator values.

A simple heartbeating mechanism is used to detect failures.

When one or more workers fail, the current state of the partitions assigned to these workers is lost. The master reassigns graph partitions to the currently available set of workers, and they all reload their partition state from the most recent available checkpoint at the beginning of a superstep S.

The frequency of checkpointing is chosen to balance checkpoint cost against expected recovery cost using a mean time to failure model.

Example Applications

The paper gives examples of PageRank, single-source shortest path, bipartite maching, and semi-clustering algorithms implemented using Pregel's programming model. See the full paper (link at the top of the post as always) for details.

Running shortest paths for a graph with a billion vertices and over 127 billion edges, using 800 worker tasks on 300 multicore machines, took 'a little over 10 minutes.'

# data[].attributes.attachment_link.title
Pregel: A System for Large-Scale Graph Processing

# data[].attributes.attachment_link.description
Pregel: A System for Large-Scale Graph Processing - Malewicz et al. (Google) 2010 "Many practical computing problems concern large graphs." Yesterday we looked at some of the models for understanding networks and graphs. Today's paper focuses on processing of graphs, especially the efficient processing of large graphs where large can mean billions of vertices and trillions of edges.

# data[].attributes.attachment_link.readable_text
Skip to content

Community detection algorithms are used to evaluate how groups of nodes are clustered or partitioned, as well as their tendency to strengthen or break apart. The Neo4j GDS library includes the following community detection algorithms, grouped by quality tier:

# data[].attributes.attachment_link.title
Community detection - Neo4j Graph Data Science

# data[].attributes.attachment_link.description
This chapter provides explanations and examples for each of the community detection algorithms in the Neo4j Graph Data Science library.

# data[].attributes.attachment_link.readable_text
Directed Acyclic Graphs (DAGs) are directed graphs that do not contain cycles. These kind of graphs are commonly used to model dependencies between entities.

The canonical algorithm that goes hand in hand with DAGs is topological sort, for which GDS provides an efficient parallel implementation. Running topological sort is the best way to make sure the graph is a DAG.

Some of the problems that are computationally hard to solve in the general case can be solved efficiently when the scope is limited to DAGs. One of these is the longest path problem, for which GDS provides an efficient algorithm.

The Neo4j GDS library includes the following DAG algorithms:

# data[].attributes.attachment_link.title
DAG algorithms - Neo4j Graph Data Science

# data[].attributes.attachment_link.description
This chapter provides a description of the available DAG algorithms in the Neo4j Graph Data Science library.

# data[].attributes.attachment_link.readable_text
In this article, we will be discussing one of the most commonly known shortest-path algorithms i.e. Dijkstra's Shortest Path Algorithm which was developed by Dutch computer scientist Edsger W. Dijkstra in 1956. Moreover, we will do a complexity analysis for this algorithm and also see how it differs from other shortest-path algorithms.

Dijkstra's algorithm is a popular algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956.

The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts at the source vertex and iteratively selects the unvisited vertex with the smallest tentative distance from the source. It then visits the neighbors of this vertex and updates their tentative distances if a shorter path is found. This process continues until the destination vertex is reached, or all reachable vertices have been visited.

Need for Dijkstra's Algorithm (Purpose and Use-Cases)

The need for Dijkstra's algorithm arises in many applications where finding the shortest path between two points is crucial.

For example, It can be used in the routing protocols for computer networks and also used by map systems to find the shortest path between starting point and the Destination (as explained in How does Google Maps work? )

Can Dijkstra's Algorithm work on both Directed and Undirected graphs?

Yes, Dijkstra's algorithm can work on both directed graphs and undirected graphs as this algorithm is designed to work on any type of graph as long as it meets the requirements of having non-negative edge weights and being connected.

In a directed graph, each edge has a direction, indicating the direction of travel between the vertices connected by the edge. In this case, the algorithm follows the direction of the edges when searching for the shortest path.

In an undirected graph, the edges have no direction, and the algorithm can traverse both forward and backward along the edges when searching for the shortest path.

Algorithm for Dijkstra's Algorithm :

1. Mark the source node with a current distance of 0 and the rest with infinity.

2. Set the non-visited node with the smallest current distance as the current node.

3. For each neighbor, N of the current node adds the current distance of the adjacent node with the weight of the edge connecting 0->1. If it is smaller than the current distance of Node, set it as the new current distance of N.

4. Mark the current node 1 as visited.

5. Go to step 2 if there are any nodes are unvisited.

How does Dijkstra's Algorithm works?

Let's see how Dijkstra's Algorithm works with an example given below:

Dijkstra's Algorithm will generate the shortest path from Node 0 to all other Nodes in the graph.

Consider the below graph:
The algorithm will generate the shortest path from node 0 to all the other nodes in the graph.
For this graph, we will assume that the weight of the edges represents the distance between two nodes.
As, we can see we have the shortest path from,
Node 0 to Node 1, from
Node 0 to Node 2, from
Node 0 to Node 3, from
Node 0 to Node 4, from
Node 0 to Node 6.

Initially we have a set of resources given below :

The Distance from the source node to itself is 0. In this example the source node is 0.

The distance from the source node to all other node is unknown so we mark all of them as infinity.

Example: 0 -> 0, 1-> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.

we'll also have an array of unvisited elements that will keep track of unvisited or unmarked Nodes.

Algorithm will complete when all the nodes marked as visited and the distance between them added to the path. Unvisited Nodes:- 0 1 2 3 4 5 6.

Step 1: Start from Node 0 and mark Node as visited as you can check in below image visited Node is marked red.

Step 2: Check for adjacent Nodes, Now we have to choices (Either choose Node1 with distance 2 or either choose Node 2 with distance 6 ) and choose Node with minimum distance. In this step Node 1 is Minimum distance adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2
Step 3: Then Move Forward and check for adjacent Node which is Node 3, so marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7
Step 4: Again we have two choices for adjacent Nodes (Either we can choose Node 4 with distance 10 or either we can choose Node 5 with distance 15) so choose Node with minimum distance. In this step Node 4 is Minimum distance adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17
Step 5: Again, Move Forward and check for adjacent Node which is Node 6, so marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 = 19 So, the Shortest Distance from the Source Vertex is 19 which is optimal one

Pseudo Code for Dijkstra's Algorithm

function Dijkstra(Graph, source):
// Initialize distances to all nodes as infinity, and to the source node as 0.

distances = map(all nodes -> infinity)

distances = 0

// Initialize an empty set of visited nodes and a priority queue to keep track of the nodes to visit.
visited = empty set
queue = new PriorityQueue()
queue.enqueue(source, 0)

// Loop until all nodes have been visited.
while queue is not empty:
// Dequeue the node with the smallest distance from the priority queue.
current = queue.dequeue()

// Check all neighboring nodes to see if their distances need to be updated.
for neighbor in Graph.neighbors(current):
// Calculate the tentative distance to the neighbor through the current node.
tentative_distance = distances[current] + Graph.distance(current, neighbor)

// If the tentative distance is smaller than the current distance to the neighbor, update the distance.
if tentative_distance < distances[neighbor]:
distances[neighbor] = tentative_distance

// Enqueue the neighbor with its new distance to be considered for visitation in the future.
queue.enqueue(neighbor, distances[neighbor])

// Return the calculated distances from the source to all other nodes in the graph.
return distances

Implemention of Dijkstra's Algorithm:

There are several ways to Implement Dijkstra's algorithm, but the most common ones are:

1. Priority Queue (Heap-based Implementation):

2. Array-based Implementation:

In this Implementation, we are given a graph and a source vertex in the graph, finding the shortest paths from the source to all vertices in the given graph.
Example:
Below is the algorithm based on the above idea:

Initialize the distance values and priority queue.

Insert the source node into the priority queue with distance 0.

While the priority queue is not empty:

Extract the node with the minimum distance from the priority queue.

Update the distances of its neighbors if a shorter path is found.

Insert updated neighbors into the priority queue.

Below is the C++ Implementation of the above approach:
Final Answer:

Time complexity: O((V + E) log V) , where V is the number of vertices and E is the number of edges.

Auxiliary Space: O(V), where V is the number of vertices and E is the number of edges in the graph.

2. Array-based Implementation of Dijkstra's Algorithm (Naive Approach):

Dijkstra's Algorithm can also be implemented using arrays without using a priority queue. This implementation is straightforward but can be less efficient, especially on large graphs.

The algorithm proceeds as follows:

Initialize an array to store distances from the source to each node.

Mark all nodes as unvisited.

Set the distance to the source node as 0 and infinity for all other nodes.

Repeat until all nodes are visited:

Find the unvisited node with the smallest known distance.

For the current node, update the distances of its unvisited neighbors.

Mark the current node as visited.

Complexity Analysis:

Time Complexity: O(V^2) in the worst case, where V is the number of vertices. This can be improved to O(V^2) with some optimizations.

Auxiliary Space: O(V), where V is the number of vertices and E is the number of edges in the graph.

Dijkstra's algorithm and Bellman-Ford algorithm are both used to find the shortest path in a weighted graph, but they have some key differences. Here are the main differences between Dijkstra's algorithm and Bellman-Ford algorithm:

Dijkstra's algorithm and Floyd-Warshall algorithm are both used to find the shortest path in a weighted graph, but they have some key differences. Here are the main differences between Dijkstra's algorithm and Floyd-Warshall algorithm:

Dijkstra's Algorithm vs A* Algorithm

Dijkstra's algorithm and A* algorithm are both used to find the shortest path in a weighted graph, but they have some key differences. Here are the main differences between Dijkstra's algorithm and A* algorithm:

Practice Problems on Dijkstra's Algorithm:

Conclusion:

Overall, Dijkstra's Algorithm is a simple and efficient way to find the shortest path in a graph with non-negative edge weights. However, it may not work well with graphs that have negative edge weights or cycles. In such cases, more advanced algorithms such as the Bellman-Ford algorithm or the Floyd-Warshall algorithm may be used.

# data[].attributes.attachment_link.title
What is Dijkstra's Algorithm? | Introduction to Dijkstra's Shortest Path Algorithm - GeeksforGeeks

# data[].attributes.attachment_link.description
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

# data[].attributes.attachment_link.description
El Minimum Spanning Tree (MST) o Árbol Recubridor Mínimo es un subconjunto de las aristas de un grafo que conectan a todos los vértices usando el menor peso posible. En este ejemplo podemos ver el grafo completo con las aristas grises y el subgrafo MST marcado en negro que deja a todos los vértices conectados usando la menor suma de los pesos de las aristas posible.

# data[].attributes.attachment_link.readable_text
Last Updated : 11 Apr, 2023

Connected component in an undirected graph refers to a group of vertices that are connected to each other through edges, but not connected to other vertices outside the group.

For example in the graph shown below, {0, 1, 2} form a connected component and {3, 4} form another connected component.

Characteristics of Connected Component:

A connected component is a set of vertices in a graph that are connected to each other.

A graph can have multiple connected components.

Inside a component, each vertex is reachable from every other vertex in that component.

How to identify Connected Component:

There are several algorithms to identify Connected Components in a graph. The most popular ones are:

Applications of Connected Component:

Graph Theory: It is used to find subgraphs or clusters of nodes that are connected to each other.

Computer Networks: It is used to discover clusters of nodes or devices that are linked and have similar qualities, such as bandwidth.

Image Processing: Connected components also have usage in image processing.

What else can you read?

# data[].attributes.attachment_link.title
Connected component definition & meaning in DSA - GeeksforGeeks

# data[].attributes.attachment_link.description
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

# data[].attributes.attachment_link.description
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

# data[].attributes.attachment_link.title
A Detailed Guide to Hadoop Distributed File System (HDFS) - Spiceworks

# data[].attributes.attachment_link.description
The Hadoop Distributed File System (HDFS) handles big data on off-the-shelf hardware and is used to scale Hadoop clusters to numerous nodes.

# data[].attributes.attachment_link.readable_text
La Teoría de Grafos: Conceptos básicos y aplicaciones en redes y sistemas complejos

La teoría de grafos es una rama de las matemáticas que estudia las propiedades de las redes y sistemas complejos. Un grafo es un conjunto de puntos llamados nodos o vértices, que se conectan entre sí mediante líneas llamadas aristas o bordes. La teoría de grafos se aplica en una amplia variedad de áreas, como la informática, la ingeniería, la biología y la física, entre otras.

¿Qué son los grafos?

Los grafos son una representación visual de una red o sistema complejo. Un grafo se compone de nodos y aristas, que se pueden representar de diferentes maneras. En la teoría de grafos, los nodos se representan con puntos y las aristas con líneas que conectan los nodos. Los grafos se utilizan para representar relaciones entre objetos, como por ejemplo en una red social, donde los nodos pueden representar usuarios y las aristas las conexiones entre ellos.

¿Cuáles son los conceptos básicos de la Teoría de Grafos?

Existen varios conceptos básicos en la teoría de grafos, entre ellos:

- Grafo: conjunto de nodos y aristas.
- Nodo: punto en el grafo.
- Arista: línea que conecta dos nodos.
- Grado de un nodo: número de aristas que conectan un nodo.
- Camino: secuencia de nodos conectados por aristas.
- Ciclo: camino cerrado que comienza y termina en el mismo nodo.
- Grafo conexo: grafo en el que existe al menos un camino entre cualquier par de nodos.
- Grafo completo: grafo en el que todos los nodos están conectados entre sí.

¿Cuáles son las aplicaciones de la Teoría de Grafos?

La teoría de grafos tiene múltiples aplicaciones en diferentes áreas. Algunas de las aplicaciones más comunes son:

Redes sociales: los grafos se utilizan para representar las conexiones entre usuarios en una red social.

Sistemas de transporte: los grafos se utilizan para representar las conexiones entre ciudades o estaciones de transporte.

Telecomunicaciones: los grafos se utilizan para representar la red de comunicaciones entre dispositivos.

Biología: los grafos se utilizan para representar las interacciones entre proteínas en una célula.

Informática: los grafos se utilizan para representar la estructura de datos en un programa.

¿Cómo se pueden analizar los grafos?

Existen diferentes técnicas para analizar los grafos, algunas de las más comunes son:

Medidas de centralidad: se utilizan para identificar los nodos más importantes en un grafo. Las medidas de centralidad más comunes son el grado, la cercanía y la intermediación.

Clustering: se utiliza para identificar grupos de nodos altamente conectados entre sí.

Algoritmos de búsqueda: se utilizan para encontrar caminos entre nodos en un grafo.

Algoritmos de optimización: se utilizan para encontrar la mejor solución en un grafo, como por ejemplo encontrar el recorrido más corto entre dos nodos en un grafo de transporte.

# data[].attributes.attachment_link.title
Teoría de grafos: conceptos básicos y aplicaciones en redes y sistemas complejos

# data[].attributes.attachment_link.description
La Teoría de Grafos: Conceptos básicos y aplicaciones en redes y sistemas complejos