Defesa de Tese de TIAGO ALVES SCHIEBER DE JESUS

Quantification of graph dissimilarities

 

Identificar e quantificar diferenças entre os grafos representam um dos problemas fundamentais e difíceis de importância prática em vários campos da ciência. Eles têm muitas aplicações práticas devido à utilização generalizada de redes em ciências sociais, medicina, biologia, física, etc. Os métodos atuais de comparação de rede são limitados em extrair apenas informações parciais ou são computacionalmente muito exigentes. Esta tese de doutorado objetiva propor medidas de dissimilaridade computacionalmente eficientes baseados em extração de características capazes de distinguir e quantificar diferenças entre grafos pelo uso de quantificadores da teoria da informação.

Com o objectivo de dinamicamente capturar mudanças topológicas na evolução de uma rede, propomos um modelo capaz de quantificar e reproduzir várias características de uma determinada estrutura, utilizando a raiz quadrada da divergência Jensen-Shannon, em combinação com o grau médio e do coeficiente de agrupamento. Propomos também uma definição dinâmica da robustez de uma rede, que considera medidas sobre mudanças estruturais causadas por falhas em seus componentes. A robustez é então avaliada medindo diferenças entre topologias depois de cada passo de tempo, fornecendo uma informação dinâmica sobre os danos topológicos. Além disso, propomos e testamos uma medida exata para a comparação de rede, que é baseada na quantificação de diferenças entre as distribuições de probabilidade associada à distância de cada vértice da rede. Esta medida pode identificar e quantificar diferenças topológicos estruturais, tais como a presença ou ausência de links críticos que desligam componentes do grafo. Finalmente, apresentamos uma medida de dissimilaridade em redes multiplex. A medida pode ser representada numa configuração espacial, que mostra os padrões de vértices e outras características das camadas. Redes multivariadas, tais como redes climáticas, podem se beneficiar dessa informação espacial. Em redes temporais, características dinâmicas do sistema podem surgir à partir dos variações nos padrões presentes em variáveis dinâmicas.

 

04/11/2016

14:00