El profesor Nikolaos Sidiropoulos 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 de cómo interactúan los diferentes componentes. El nuevo algoritmo resuelve el antiguo desafío de encontrar grupos estrechamente conectados, conocidos como subgrafos densos en triángulos, dentro de grandes redes, un problema importante en campos como la detección de fraude, la biología computacional y el análisis de datos.
Investigación, publicada Transacciones IEEE sobre conocimiento e ingeniería de datosLa colaboración fue dirigida por Aritra Kona, profesora asistente de ingeniería eléctrica en la 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 interactúan con frecuencia en las redes sociales. Sin embargo, el nuevo enfoque de los investigadores, conocido como el problema del subgrafo k más denso del triángulo, va un paso más allá al observar triángulos conectados: grupos de tres puntos donde cada par está conectado. Este método captura con mayor fuerza las relaciones de vínculo, como pequeños grupos de amigos que interactúan entre sí o grupos de genes que trabajan juntos en procesos biológicos.
“Nuestro enfoque no se centra únicamente en conexiones individuales, sino que considera cómo interactúan grupos de tres componentes, lo cual es importante para comprender redes más complejas”, explicó Sideropoulos, profesor del Departamento de Ingeniería Eléctrica e Informática. “Esto nos permite encontrar patrones más significativos, incluso en conjuntos de datos enormes”.
Encontrar subgrafos densos en triángulos es particularmente desafiante porque es difícil de resolver de manera eficiente con métodos tradicionales. Pero utilizando un nuevo algoritmo llamado relajación submodular, un atajo inteligente que simplifica el problema para que pueda resolverse rápidamente sin perder detalles importantes.
Estos avances abren nuevas posibilidades para comprender sistemas complejos que dependen de estas relaciones profundas y multivínculos. La identificación de subgrupos y patrones puede ayudar a descubrir actividades sospechosas de fraude, 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.