Thesis
A linear algebra approach to graph melting
- Creator
- Rights statement
- Awarding institution
- University of Strathclyde
- Date of award
- 2022
- Thesis identifier
- T16179
- Person Identifier (Local)
- 201550992
- Qualification Level
- Qualification Name
- Department, School or Faculty
- Abstract
- Robustness is often regarded as the ability of a given system to maintain its functionality when faced with some external perturbation or when some of its parts fail to operate. The ability of the system to cope with disturbances vary from system to system, and there are many examples in daily life which illustrate this concept. Communication networks, for example, transportation and telephone networks, or the internet, often manage to cope with errors or damage within some of their components without leading to the system failing entirely. As an example, within a social network of employees within a company, the absence of some employees within some given threshold will not lead to failure of the company. However, in a financial network, economic failure in some parts of the system could lead to the complete failure of the entire system. In order to understand how external perturbations or failures within particular parts of the system affect a network we can study the robustness of the network. The robustness of a complex system in graph theory, is the ability of the network to maintain its connectivity after the removal of some nodes or edges. The process of changing of a graph from being connected to being disconnected, via deletion of nodes or edges, is called graph melting. We introduce a melting phase transition for simple connected graphs and networks faced with external perturbations with positive second largest eigenvalue λ2 > 0. In order to calibrate our method of studying network robustness, we consider the network-theoretic representation of some materials which, in the real-world, are affected by melting. In particular, we will consider granular materials. A granular material is a material which is composed of discrete macroscopic solid particles, for example, sand, rice, and coffee. Granular materials are commonly used in a wide range of real world applications. There are already various models of granular materials within network theory, which has allowed us to study the structure and physical behaviour of such systems when they have an external perturbations applied to them. In this thesis, we represent granular solids by simple graphs capturing their topological structure and ordering, in order to study their robustness and the melting process. The melting process is related to the algebraic structure of the adjacency matrix of the graph and the concept of network communicability. At the melting phase transition, a graph in question transfers from being connected to being disconnected. We study melting in graphs with the second largest eigenvalue being positive, namely, in windmill graphs, dumbbell graphs and cycle graphs. Also, we investigate melting in complete multipartite graphs where the second largest eigenvalue is non-positive. We found a melting phase transition in simple connected graphs with λ2 > 0 and λ2 λ3, which resembles the melting process of a given system. We found that there is no melting phase transition in complete multipartite graphs. Also, we found the spectral decomposition for dumbbell graphs and complete multipartite graphs, which until now have not been done. Moreover, in this thesis, we show that crystalline-like granular materials melt at lower temperatures and display a sharper transition between solid to liquid phases than amorphous granular materials. In addition, we show the evolution mechanism of melting in these granular materials with tools from network theory. In the particular case of crystalline materials, the process starts by melting the central core of the crystal network, then melting spreads out from the central core until the whole network (material) transfers into a liquid. We also investigate computationally the melting process in some real-world networks. We found that the melting process of a network correlates well with the topological structure of the network.
- Advisor / supervisor
- Kitaev, Sergey, 1975-
- Resource Type
- DOI
- Funder
Relations
Contenu
| La vignette | Titre | Date de téléchargement | Visibilité | actes |
|---|---|---|---|---|
|
|
PDF of thesis T16179 | 2022-03-24 | Public | Télécharger |