Contar Triángulos en Scala – Spark

14 Jul, 2023 Programación 0

Estoy tratando de ingresar al análisis de datos utilizando Spark con Scala. Mi pregunta es cómo obtener los triángulos en un grafo. Y me refiero no al recuento de triángulos que viene con graphx, sino a los nodos reales que forman el triángulo.

Supongamos que tenemos un archivo de grafo, pude calcular los triángulos en Scala, pero la misma técnica no se aplica en Spark ya que tengo que usar operaciones RDD.

Los datos que le doy a la función son una lista compleja que consta del origen y la lista de los destinos de ese origen; por ejemplo, Adj(5, List(1,2,3)), Adj(4, List(9,8,7)), …

Mi versión en Scala es esta:

(Paths: List[Adj])

Paths.flatMap(i => Paths.map(j => Paths.map(k => {
if(i.src != j.src && i.src!= k.src && j.src!=k.src){
if(i.dst.contains(j.src) && j.dst.contains(k.src) && k.dst.contains(i.src)){
println(i.src,j.src,k.src) //3 nodos que forman un triángulo
}
else{
()
}
}
})))

Y la salida sería algo como:

(1,2,3)
(4,5,6)
(2,5,6)

En conclusión, quiero obtener la misma salida pero en un entorno de ejecución de Spark. Además, estoy buscando una forma más eficiente de mantener la información sobre las adyacencias, como el mapeo de clave y luego la reducción por clave o algo similar. Dado que el entorno de Spark requiere un enfoque bastante diferente para cada problema (operaciones en big data), estaría agradecido si pudiera explicar la forma de pensar y darme un breve resumen sobre las funciones que utilizó.

Gracias.

davy.ai

July 14, 2023 at 3:36 am

Para obtener los triángulos en un gráfico utilizando Spark con Scala, podemos seguir los siguientes pasos:

Cargar los datos del gráfico en un RDD de pares (src, List[dst])
Realizar una operación de unión en el RDD para obtener todos los pares de vértices que tienen un vecino común
Mapear los pares resultantes en 3-tuplas que representen triángulos (es decir, (v1, v2, v3) donde v1, v2 y v3 son todos vecinos entre sí)

Aquí tienes un ejemplo de implementación:

// Cargar los datos del gráfico en un RDD de pares (src, List[dst])
val graph: RDD[(Int, List[Int])] = ...

// Realizar una auto-unión para obtener todos los pares de vértices con un vecino común
val joined: RDD[((Int, Int), List[Int])] = graph.flatMap{
  case (src, neighbors) => neighbors.map(n => (src, n) -> neighbors)
}
.reduceByKey(_ ++ _)
.filter{case (_, neighbors) => neighbors.length > 1}

// Mapear los pares en 3-tuplas que representan triángulos
val triangles: RDD[(Int, Int, Int)] = joined.flatMap{
  case ((v1, v2), neighbors) =>
    for {
      v3 <- neighbors if v3 > v2
      if neighbors.contains(v1)
    } yield (v1, v2, v3)
}

En la implementación anterior, comenzamos cargando los datos del gráfico en un RDD de pares (src, List[dst]) (asumiendo que los datos están en ese formato). Luego, realizamos una auto-unión en el RDD para obtener todos los pares de vértices que tienen un vecino común, utilizando flatMap para generar un registro de salida para cada posible par de vértices. Utilizamos reduceByKey seguido de filter para eliminar los pares redundantes donde dos vértices tienen múltiples vecinos comunes.

Finalmente, mapeamos los pares resultantes en 3-tuplas que representan triángulos, comprobando que cada triángulo sea válido asegurándonos de que cada par de vértices tenga un vecino común. El RDD resultante contiene 3-tuplas que representan todos los triángulos en el gráfico.

Esta implementación debería ser más eficiente que la original que utiliza maps anidados porque utiliza el procesamiento distribuido de Spark para realizar la operación de unión de forma distribuida. También utilizamos flatMap en lugar de maps anidados para evitar crear colecciones intermedias innecesarias, lo que puede ahorrar memoria en un contexto de big data.

Espero que esto te ayude. Avísame si tienes alguna otra pregunta o si algo no está claro.

Answer

davy.ai

July 14, 2023 at 3:36 am
Para obtener los triángulos en un gráfico utilizando Spark con Scala, podemos seguir los siguientes pasos:
1. Cargar los datos del gráfico en un RDD de pares (src, List[dst])
2. Realizar una operación de unión en el RDD para obtener todos los pares de vértices que tienen un vecino común
3. Mapear los pares resultantes en 3-tuplas que representen triángulos (es decir, (v1, v2, v3) donde v1, v2 y v3 son todos vecinos entre sí)
Aquí tienes un ejemplo de implementación:
```
// Cargar los datos del gráfico en un RDD de pares (src, List[dst])
val graph: RDD[(Int, List[Int])] = ...

// Realizar una auto-unión para obtener todos los pares de vértices con un vecino común
val joined: RDD[((Int, Int), List[Int])] = graph.flatMap{
  case (src, neighbors) => neighbors.map(n => (src, n) -> neighbors)
}
.reduceByKey(_ ++ _)
.filter{case (_, neighbors) => neighbors.length > 1}

// Mapear los pares en 3-tuplas que representan triángulos
val triangles: RDD[(Int, Int, Int)] = joined.flatMap{
  case ((v1, v2), neighbors) =>
    for {
      v3 <- neighbors if v3 > v2
      if neighbors.contains(v1)
    } yield (v1, v2, v3)
}
```
En la implementación anterior, comenzamos cargando los datos del gráfico en un RDD de pares (src, List[dst]) (asumiendo que los datos están en ese formato). Luego, realizamos una auto-unión en el RDD para obtener todos los pares de vértices que tienen un vecino común, utilizando flatMap para generar un registro de salida para cada posible par de vértices. Utilizamos reduceByKey seguido de filter para eliminar los pares redundantes donde dos vértices tienen múltiples vecinos comunes.

Finalmente, mapeamos los pares resultantes en 3-tuplas que representan triángulos, comprobando que cada triángulo sea válido asegurándonos de que cada par de vértices tenga un vecino común. El RDD resultante contiene 3-tuplas que representan todos los triángulos en el gráfico.

Esta implementación debería ser más eficiente que la original que utiliza maps anidados porque utiliza el procesamiento distribuido de Spark para realizar la operación de unión de forma distribuida. También utilizamos flatMap en lugar de maps anidados para evitar crear colecciones intermedias innecesarias, lo que puede ahorrar memoria en un contexto de big data.

Espero que esto te ayude. Avísame si tienes alguna otra pregunta o si algo no está claro.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Contar Triángulos en Scala – Spark

Answer

davy.ai