Submitted by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:05Z
No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:18Z (GMT) No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5) / Made available in DSpace on 2017-04-06T18:25:28Z (GMT). No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5)
Previous issue date: 2016-06-22 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Different graph generalizations have been recently used in an ad hoc manner to represent time-varying complex networks, i.e. networks in which vertices and edges may vary in time. Similar constructions have also been used to represent multilayer networks, i.e. systems formed by distinct interdependent layers where each layer can be seen as a complex network. In this thesis, we introduce the concept of MultiAspect Graph (MAG). We show that a MAG is isomorphic to a directed graph, which is an important theoretical result because this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a MAG and the behavior of dynamic processes over a MAG. In our proposal, the set of vertices, layers, time instants, or any other independent feature of the system being modelled is considered as an aspect of the MAG. For instance, a MAG is able to represent multilayer or time-varying networks, while both concepts can also be combined to represent a multilayer time-varying network. Since the MAG structure admits an arbitrary (finite) number of aspects, it hence introduces a powerful modelling abstraction for networked complex systems. Further, we present algebraic representations and basic algorithms for MAGs, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Building upon the basic MAG concept, we also present derived applications, such as a MAG-based unifying model for time-varying graphs as well as MAG-based centrality notions. / Recentemente, várias generalizações de grafos têm sido propostas para tratar problemas específicos envolvendo redes complexas variantes no tempo e redes complexas multi-camadas. Essas representações são propostas de maneira adequada para resolver problemas específicos, mas não são adequadas para uso geral e muitas vezes são incompatíveis entre si. Nesta tese apresentamos o conceito de Grafo Multi-Aspectos (MAG), que é uma generalização de grafos capaz de representar redes variantes no tempo, redes multi-camadas e redes simultaneamente multi-camadas e variantes no tempo. Mostramos que todo MAG é isomorfo a um grafo direcionado, o que é um importante resultado teórico. Com base nesse resultado é possível utilizar o conhecimento previamente obtido em teoria de grafos para problemas envolvendo MAGs. Dessa maneira, torna-se possível criar representações algébricas para MAGs com características semelhantes às encontradas nas representações para grafos orientados. Além disso, pode-se construir algoritmos básicos para MAGs através da adaptação de algoritmos conhecidos para grafos. Esses algoritmos básicos podem servir como modelo para criação de outros algoritmos para MAGs, bem como serem utilizados como primitivas para construção de novos algoritmos. Utilizando essas primitivas, introduzimos o conceito de centralidades em MAGs, bem como construimos algoritmos apropriadas para calcular essas centralidades.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede-server.lncc.br:tede/244 |
| Date | 22 June 2016 |
| Creators | Wehmuth, Klaus |
| Contributors | Ziviani, Artur, Szwarcfiter, Jayme Luiz, Albuquerque, Célio Vinicius Neves de, Menasché, Daniel Sadoc, Gomes, Antônio Tadeu Azevedo, Vieira, Paulo César Marques |
| Publisher | Laboratório Nacional de Computação Científica, Programa de Pós-Graduação em Modelagem Computacional, LNCC, Brasil, Coordenação de Pós-Graduação e Aperfeiçoamento |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações do LNCC, instname:Laboratório Nacional de Computação Científica, instacron:LNCC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0033 seconds