El profesor Nikolaos Sideropoulos de la Facultad de Ingeniería y Ciencias Aplicadas de la Universidad de Virginia ha introducido un gran avance en la minería de gráficos con el desarrollo de un nuevo algoritmo computacional.
La minería de gráficos, un método para analizar redes como conexiones de redes sociales o sistemas biológicos, ayuda a los investigadores a descubrir patrones significativos en cómo interactúan los diferentes elementos. El nuevo algoritmo aborda el desafío de larga data de encontrar grupos fuertemente conectados dentro de grandes redes, conocidos como subgrafos densos triangulares, un problema que es común en áreas como la detección de fraude, la biología computacional y el análisis de datos.
Investigación publicada en Transacciones IEEE sobre conocimiento e ingeniería de datosfue una colaboración dirigida por Aritra Konar, profesora asistente de ingeniería eléctrica en la KU Leuven en Bélgica, ex científica investigadora en la UVA.
Los algoritmos de minería de gráficos suelen centrarse en encontrar conexiones densas entre pares de puntos individuales, como dos personas que interactúan con frecuencia en las redes sociales. Sin embargo, el nuevo método de los investigadores, llamado problema del subgrafo k más denso del triángulo, va un paso más allá al observar los triángulos de conexión: grupos de tres puntos donde cada par está conectado. Este enfoque captura relaciones más estrechamente acopladas, como pequeños grupos de amigos que interactúan entre sí, o grupos de genes que trabajan juntos en procesos biológicos.
“Nuestro método no analiza sólo una conexión única, sino que considera cómo interactúan grupos de tres elementos, lo cual es importante para comprender redes más complejas”, explicó Sideropoulos, profesor de ingeniería eléctrica e informática. “Esto nos permite encontrar patrones más significativos, incluso en grandes conjuntos de datos”.
Encontrar subgrafos densos triangulares es particularmente difícil porque es difícil de resolver de manera eficiente con métodos convencionales. Pero el nuevo algoritmo utiliza lo que se llama relajación submodular, un atajo inteligente que simplifica el problema lo suficiente como para resolverlo rápidamente sin perder detalles importantes.
Estos desarrollos abren nuevas posibilidades para comprender sistemas complejos que dependen de estas relaciones profundas y de múltiples conexiones. La detección de subgrupos y patrones puede ayudar a descubrir actividades sospechosas en fraudes, identificar dinámicas comunitarias en las redes sociales o ayudar a los investigadores a analizar interacciones de proteínas o relaciones genéticas con mayor precisión.
