• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.76.2021.tde-02092021-161413
Documento
Autor
Nombre completo
Guilherme Schimidt Domingues
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2021
Director
Tribunal
Costa, Luciano da Fontoura (Presidente)
Gallo, Alexsandro Giacomo Grimbert
Marana, Aparecido Nilceu
Título en portugués
Caminhos mínimos em redes complexas: estrutura e otimização
Palabras clave en portugués
Ciência de redes
Otimização
Topologia de redes
Resumen en portugués
Dentre as várias propriedades topológicas de redes complexas, o caminho mínimo representa uma característica particularmente importante devido ao seu potencial efeito em vários processos dinâmicos. Além disso, várias situações práticas, como o tráfego de veículos nas cidades, por exemplo, podem se beneficiar da redução dos respectivos caminhos mínimos nos sistemas relacionados. No presente trabalho, abordamos o problema da redução do mínimo caminho médio de várias redes complexas teóricas e uma do mundo real, adicionando um determinado número de arestas de acordo com diferentes estratégias e fazemos a comparação do desempenhos destas estratégias. Mais especificamente, consideramos: a adição de novas arestas entre vértices com grau, centralidade de intermediação, centralidade de proximidade e acessibilidade relativamente baixo/baixo, baixo/alto e alto/alto; melhorar a regularidade do grau da rede; e ligação preferencial de acordo com o grau. Também verificamos se a maleabilidade da rede pode ser usada como um meio de prever o potencial desta rede em ser otimizada. Vários resultados interessantes foram obtidos, incluindo a identificação de estratégias baseadas em conectar vértices com valores máximos e mínimos de uma medida como resultante na maior redução do comprimento do mínimo caminho médio em geral e estratégias baseadas em conectar vértices com valores máximos entre si como melhores no caso de redes modulares. Outra descoberta interessante foi que, para vários tipos de redes, os métodos baseados em graus tendem a fornecer melhorias comparáveis àquelas obtidas pelo uso de uma medida muito mais dispendiosa computacionalmente que é a centralidade de intermediação.
Título en inglés
Shortest paths in complex networks: structure and optimization
Palabras clave en inglés
Network science
Network topology
Optimization
Resumen en inglés
Among the several topological properties of complex networks, the shortest path represents a particularly important characteristic due to its potential impact on several dynamical processes. In addition, several practical situations, such as transit in cities, for example, can benefit from reducing their respective shortest path in the related system. In the present work, we addressed the problem of trying to reduce the average shortest path of several theoretical and one real-world complex networks by adding a given number of links according to different strategies and we also compare the performance of these strategies. More specifically, we considered: placing new links between nodes with relatively low/low, low/high, and high/high degrees, betweenness centralities, closeness centralities and accessibilities; enhancing the degree regularity of the network; and preferential attachment according to the degree. We also checked whether the malleability of the network can be used as a means of predicting the potential of this network to be optimized. Several interesting results have been obtained, including the identification of the strategies based in connect nodes with higher and lower values of a measurement as those providing the largest reduction of the average shortest path length in general and strategies based in connect two nodes with higher values in the case of modular networks. Another interesting finding is that, for several types of networks, the degree-based methods tend to provide improvements comparable to those obtained by using the much more computationally expensive betweenness centrality measurement.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-09-06
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.