Grafos: encontrando sentido en el planeta

El Machine Learning es muy eficiente para resolver tareas específicas y bien definidas, pero no para las ambiguas. ¿Sabías que es posible mejorar su desempeño utilizando la teoría de grafos?

Autor: Rocío B. Ayala Meza

Fuente: [1]⁠

Introducción

El mundo está impulsado por conexiones, desde sistemas de comunicación hasta procesos biológicos [2]⁠. Encontrar un significado detrás de estas relaciones promueve avances como la optimización de rutas para vehículos en el sector logístico y la identificación de redes fraudulentas. 

La teoría de grafos se basa en matemática desarrollada explícitamente para obtener información de estas conexiones. Haciendo posible descubrir el funcionamiento de sistemas y redes complejas a escalas masivas, para cualquier organización [2]⁠. Por ejemplo, los métodos tradicionales de detección de fraude emplean datos discretos como cuentas, dispositivos y direcciones IP privadas. Pero, para evitar ser capturados, los estafadores emplean identidades falsas. Entonces, para detectarlos debe analizarse las conexiones, es decir, los vínculos que conectan a esos puntos de datos individuales.

En este artículo va a describirse la teoría de grafos, y cómo puede usarse para mejorar el desempeño del machine learning (ML).

¿Qué es la teoría de grafos?

Es el estudio de grafos, los cuales son diagramas que involucran líneas (aristas) y puntos (vértices) [3]⁠. Los grafos son utilizados para modelar relaciones de pares; varían en tipo (ver Figura 1), tienen varios atributos y exhiben diferentes clases de algoritmos.

Figura 1. Tipos de grafos [2]⁠.

1. Atributos

Entre algunos atributos tenemos:

• Grafos sin etiqueta versus grafos con etiqueta: cuando hay valores en vértices o aristas. Estos valores representan costo, capacidad, distancia, tiempo o una prioridad específica de un área de dominio [2]⁠. Si se ignoran, habrá diferencias en los resultados. Por ejemplo, en la Figura 2 el camino más corto de A a E, en el grafo con etiqueta, sería una distancia de 50 km cruzando A, C, D, E. Mientras que en el grafo sin etiqueta, sería el número de saltos entre cada vértice (2 saltos atravesando A, D, E).

Figura 2. Grafos sin etiqueta vs Con etiqueta, aplicados en encontrar el camino más corto [2]⁠.

• Grafos no dirigidos versus grafos dirigidos: cuando las aristas definen explícitamente un vértice inicial o final. Las flechas agregan más contexto al grafo para inferir más información [2]⁠. Por ejemplo, si el grafo dirigido en la Figura 3 fuese una red de puntos de entrega, y las aristas "carreteras", entonces entre A y C hay 2 carreteras o sino es   bidireccional.

Figura 3. Grafos no-dirigidos vs Grafos dirigidos [2]⁠.

1. Clases de algoritmos

Hay 3 áreas de análisis: 

• Búsqueda de rutas: en donde la ruta más corta es el camino con menos saltos o etiqueta menor entre dos vértices. Estos algoritmos son útiles para comprender la forma en que se conectan los datos [2]⁠. Algunos ejemplos son Dijkstra y A*. A* [4]⁠ es una extensión de Dijkstra, pero logra un mejor rendimiento mediante el uso de heurísticas para guiar su búsqueda. Además, a pesar de que emplea muchos recursos informáticos, sigue siendo la mejor opción en muchos casos [5]⁠. 

Aplicación: identificar rutas óptimas para vehículos de transporte.

• Cálculo de centralidad: para entender qué vértices son los más importantes en una red. Estos algoritmos son útiles para identificar la dinámica de grupo, por ejemplo, la velocidad a la que las cosas se propagan [2]⁠. Un algoritmo popularizado por Google es PageRank [6].

Aplicación: identificar a los influencers más populares en una red social.

• Detección de comunidades: para encontrar comunidades y cuantificar la calidad de las agrupaciones. Permite descubrir estructuras como jerarquías y tendencias para atraer o repeler a otros [2]⁠. Un ejemplo de algoritmo es el Método de Louvain [7].

Aplicación: para el análisis de fraude en el sector financiero.

¿Cómo puede usarse la teoría de grafos para mejorar ML?

• Proporcionando contexto: En ML, para aprender, los algoritmos iteran continuamente haciendo cambios para reducir el error. Además, cuando se les presentan nuevos datos pueden optimizarse. Por lo tanto, la forma en que se toma decisiones es similar a la de los humanos [2]⁠. 

Estos últimos utilizan información contextual para determinar lo esencial en una situación, intuir  información faltante o determinar cómo aplicar las lecciones del pasado en situaciones nuevas. Es decir, el contexto les ayuda a hacer predicciones [2]⁠. Por ejemplo, si una persona vota por un candidato, la probabilidad de que sus familiares y amigos voten es alta.

El ML es muy eficiente para tareas específicas y bien definidas, pero no para las ambiguas. Es por ello que, para mejorar su desempeño, es necesario proporcionarle información contextual a través de la teoría de grafos [2]⁠. Por ejemplo, las empresas minoristas personalizan la recomendación de productos no exclusivamente con datos históricos, sino con contextuales como la similaridad entre clientes y su comportamiento en línea.

Conclusiones

El mundo está impulsado por conexiones, y como tal puede modelarse como un grafo. La teoría de grafos estudia estos diagramas para comprender las relaciones existentes y fomentar avances en diferentes industrias.

Los grafos aportan contexto a la información, haciendo que el ML pueda hacer predicciones en situaciones ambiguas.

Referencias

[1] R. Ayala Meza, “Portafolio Fotográfico.” 2021, [Online]. Available:  

https://photos.app.goo.gl/9EPSEUyCGwKaNccD8.

[2] M. Needham and A. E. Hodler, Graph Algorithms: Practical Examples in Apache Spark and Neo4j. y O’Reilly Media, Inc, 2019.

[3] “Graph Theory: Definitions for Common Terms - Statistics How To.” https://www.statisticshowto.com/graph-theory/ (accessed May 11, 2022).

[4] “A* search algorithm - Wikipedia.” https://en.wikipedia.org/wiki/A*_search_algorithm (accessed May 11, 2022).

[5] W. Zeng and R. L. Church, “Finding shortest paths on real road networks: The case for A,” Int. J. Geogr. Inf. Sci., vol. 23, no. 4, pp. 531–543, 2009, doi: 10.1080/13658810801949850.

[6]        “PageRank - Wikipedia.” https://en.wikipedia.org/wiki/PageRank (accessed Jun. 09, 2022).

[7] “Louvain method - Wikipedia.” https://en.wikipedia.org/wiki/Louvain_method (accessed Jun. 09, 2022).