Distance backbones of weighted graphs: computing path-lengths

December 13, 2023

Esta dissertação aborda o tema da esparsificação de grafos pesados. Em particular, apresenta em pormenor o método para obter um esqueleto de distância de um grafo pesado. Esse esqueleto de distância corresponde ao subgrafo que contém apenas as arestas que pertencem a algum caminho mais curto. A noção de comprimento de caminho é também generalizada e são apresentadas diferentes funções que calculam comprimentos de caminho. Como cada uma destas funções está associada ao respetivo esqueleto de distância, em seguida, comparam-se diferentes esqueletos, considerando alguns exemplos de redes de interacções sociais. Por fim, é analisado o modo como estes esqueletos preservam as características de simulações epidemiológicas efectuadas nestas redes utilizando os modelos Suscetível-Infetado e Suscetível-Infetado-Recuperado. This dissertation deals with the topic of the sparsification of weighted graphs. In particular, it presents in detail the method for obtaining a distance backbone of a weighted graph. The distance backbone is the subgraph that only contains the edges that belong to some shortest-path. The notion of path-length is also generalized and different functions that compute path-lengths are presented. Since each one of these functions is associated with the respective distance backbone, different backbones are compared by considering some examples of networks depicting social interactions. Lastly, it is examined how these backbones preserve characteristics of epidemiological simulations carried out on these networks using Susceptible-Infected and Susceptible-Infected-Recovered models.

Authors in the community:

• 

  M

  Miguel Bernardo Guerreiro Pereira

  ist1102211

Mestrado em Matemática Aplicada e Computação

mathematics - Mathematics

Keywords

• Weighted Graphs
• Path-Length
• Shortest-Path
• Distance Backbone
• Epidemiological Models
• Grafos Pesados
• Comprimento de caminho
• Caminho mais curto
• Esqueleto de Distância
• Modelos Epidemiológicos

eng - English

Instituto Superior Técnico

Financing entity

Fundação para a Ciência e a Tecnologia

Title of the project, award or grant: Redundancy effects on spread and control in network dynamics: applications in computational biomedicine

Visit project

Identifier for the funding entity: https://doi.org/10.13039/501100001871

Type of identifier of the funding entity: Crossref Funder

Number for the project, award or grant: 2022.09122.PTDC