A Faculdade de Ciências e Tecnologia da Universidade de Cabo Verde, através do Grupo Disciplinar de Matemática e Estatística, vai realizar nesta sexta-feira, 11 de outubro, às 15 horas, no LABMAT | 205-E10, uma palestra intitulada “Deteção de Comunidades em Redes através de Agrupamento Robusto”, a ser proferida pelo docente e investigador da Universidade de Viena, Áustria, Immanuel Bomze.

Nos últimos anos, tornou-se cada vez mais evidente a importância de considerar a incerteza nos dados em problemas de otimização, uma vez que pequenas flutuações nos dados de entrada podem levar a decisões significativamente menos eficazes em muitos problemas práticos quando a incerteza é ignorada. Quando a distribuição de probabilidade dos dados incertos não é conhecida ou não pode ser estimada com precisão suficiente, uma técnica comum é estimar limites para os dados incertos e identificar soluções ótimas que sejam robustas contra flutuações dentro desses limites. Esta abordagem conduz ao paradigma da otimização robusta, permitindo considerar objetivos e restrições incertas.

Problemas de otimização onde apenas o objetivo é incerto surgem, por exemplo, de forma proeminente na análise de redes sociais. Isto deve-se ao facto de a força dos laços sociais (ou seja, a quantidade de influência que os indivíduos exercem uns sobre os outros) ou a disposição dos indivíduos para adotar e partilhar informação poder ser apenas aproximadamente estimada com base em observações. Um problema fundamental que surge na análise de redes sociais diz respeito à identificação de comunidades (por exemplo, grupos de trabalho, grupos de interesse), que pode ser modelado como um Problema de Agrupamento de Conjuntos Dominantes (Dominant Set Clustering Problem), o qual, por sua vez, conduz a Problemas de Otimização Quadrática Padrão (Standard Quadratic Optimization Problems - StQP). Neste contexto, as forças dos laços entram no objetivo, enquanto as restrições são as familiares restrições de probabilidade, podendo assim ser consideradas certas.

Na sua palestra, o investigador irá explorar a incerteza dos dados na função objetivo de StQPs, considerando diferentes conjuntos de incerteza, e derivar implicações para a complexidade das variantes robustas dos problemas determinísticos correspondentes. Demonstrará que considerar a incerteza dos dados num StQP resulta noutro StQP de complexidade semelhante se forem assumidos conjuntos de incerteza elipsoidais, esféricos ou de caixa (boxed uncertainty sets). Além disso, discutirá as implicações ao considerar conjuntos de incerteza poliédricos e derivará limites rigorosos para este caso, baseando-se em otimização copositiva.

Abordando modelos de cliques s-defeituosos para deteção de clusters baseados em redes, o investigador propõe uma abordagem de otimização não linear que lida eficientemente com esses modelos na prática. Em particular, introduz uma formulação contínua equivalente para o problema em análise e analisa algumas variantes adaptadas do algoritmo de Frank-Wolfe que permitem encontrar rapidamente cliques s-defeituosos máximos. O bom comportamento prático dessas ferramentas algorítmicas, intimamente ligado às suas propriedades de identificação de suporte, torna-as muito atrativas em aplicações práticas.