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.

Minería de gráficos, un método para analizar redes como conexiones de redes sociales osistemas 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 enTransacciones IEEE sobre conocimiento e ingeniería de datos, fue 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 sólo analiza conexiones individuales, sino que considera cómo interactúan grupos de tres elementos, lo cual es crucial para comprender másredes 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 elnuevo algoritmoutiliza 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 descubriractividad sospechosaen fraude, identificar dinámicas comunitariasredes sociales, o ayudar a los investigadores a analizar las interacciones de proteínas o las relaciones genéticas con mayor precisión.

Más información:Aritra Konar et al, Subgrafos densos en triángulos mineros de un tamaño fijo: dureza, extensión de Lovasz y aplicaciones,Transacciones IEEE sobre conocimiento e ingeniería de datos(2024).DOI: 10.1109/TKDE.2024.3444608