Dissertação
{en_GB=Distributed Algorithm for the Analysis of Properties of Complex Networks } {} EVALUATED
{pt=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. , en= This thesis proposes a Monte Carlo method to compute metrics of complex networks, such as the centrality of nodes in a network. Concrete metrics of networks can be calculated using functions of the matrices that represent them. The proposed method uses random walks over a matrix to calculate functions based on the powers of the matrix. In particular, several interesting metrics can be derived, such as the inverse of the matrix multiplied by a vector, corresponding to Katz centrality, and the trace of the inverse of the matrix. The proposed method aims to be parallel and scalable, in order to deal with large networks, that may exceed the memory limits of individual machines. To this end, state of the art parallelism frameworks and tools are used to distribute the computation across processes and threads on several machines. The implementation of the Monte Carlo method is executed in two supercomputers featured among the top twenty fastest machines in the world at the moment. These consist on high speed networks interconnecting nodes with several processors, allowing the evaluation of the implementation's parallelism. The method is tested regarding precision and performance, and compared against state of the art alternatives. It is shown to be highly scalable, taking advantage of large numbers of computing nodes, and therefore being able to tackle large problem sizes. This method is shown to be a viable, high performance method to compute approximations of metrics in large scale networks. }
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
