Dissertação
Distributed Algorithm for the Analysis of Properties of Complex Networks EVALUATED
Esta tese propõe um método Monte Carlo para o cálculo de métricas em redes complexas, tal como a centralidade de nós numa rede. Métricas de redes podem ser calculadas com base em funções das matrizes que as representam. O método proposto utiliza caminhos aleatórios em matrizes para calcular funções baseadas nas potências da matriz. Em particular, várias métricas interessantes podem ser derivadas, tal como a inversa da matriz multiplicada por um vetor, que corresponde à centralidade de Katz, ou o traço da inversa da matriz. O método proposto é paralelo e escalável, de modo a lidar com redes de elevadas dimensões, que podem exceder os limites de memória de máquinas individuais. \textit{Frameworks} e ferramentas do estado da arte são utilizadas para distribuir a computação por múltiplos processos e \textit{threads} em várias máquinas. A implementação do método Monte Carlo é executada em dois supercomputadores, entre as vinte máquinas mais rápidas do mundo, de momento. Estas máquinas consistem em redes de alta velocidade a ligar nós com múltiplos processadores, permitindo uma avaliação do paralelismo da implementação. O método é testado quanto à precisão e performance, bem como comparado com as alternativas do estado da arte. Demonstra-se que a implementação é altamente escalável, tirando partido de elevados números de nós para abordar problemas de larga escala. Os resultados analisados mostram que o método proposto é uma possibilidade viável e eficiente para calcular aproximações de métricas de matrizes de grande escala.
junho 26, 2018, 9:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
José Carlos Alves Pereira Monteiro
Departamento de Engenharia Informática (DEI)
Professor Catedrático
