Nikolaos Sidiropoulos, profesor 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 estrechamente conectados, conocidos como subgrafos densos en triángulos, dentro de grandes redes, un problema que es crítico en campos como la detección de fraude, la biología computacional y el análisis de datos.
La 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 KU Leuven en Bélgica, quien anteriormente fue 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 se comunican con frecuencia en las redes sociales. Sin embargo, el nuevo método de los investigadores, conocido como problema del subgrafo k más denso del triángulo, va un paso más allá al observar triángulos de conexiones: grupos de tres puntos donde cada par está vinculado. Este enfoque captura relaciones más estrechamente unidas, 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 únicamente conexiones individuales, sino que considera cómo interactúan grupos de tres elementos, lo cual es crucial para comprender redes más complejas», explicó Sidiropoulos, profesor del Departamento de Ingeniería Eléctrica e Informática. «Esto nos permite encontrar patrones más significativos, incluso en conjuntos de datos masivos».
Encontrar subgrafos densos en triángulos es especialmente desafiante porque es difícil de resolver de manera eficiente con los métodos tradicionales. Pero el nuevo algoritmo utiliza lo que se llama relajación submodular, un atajo inteligente que simplifica el problema lo suficiente para que sea más rápido de resolver sin perder detalles importantes.
Este avance abre nuevas posibilidades para comprender sistemas complejos que dependen de estas relaciones más profundas y de múltiples conexiones. Localizar subgrupos y patrones podría 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.