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 functionalitywhen 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, andthere are many examples in daily life which illustrate this concept. Communicationnetworks, for example, transportation and telephone networks, or the internet, oftenmanage to cope with errors or damage within some of their components without leadingto the system failing entirely. As an example, within a social network of employeeswithin a company, the absence of some employees within some given threshold will notlead to failure of the company. However, in a financial network, economic failure insome parts of the system could lead to the complete failure of the entire system.In order to understand how external perturbations or failures within particularparts of the system affect a network we can study the robustness of the network. Therobustness of a complex system in graph theory, is the ability of the network to maintainits connectivity after the removal of some nodes or edges. The process of changing ofa 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 connectedgraphs and networks faced with external perturbations with positive second largesteigenvalue λ2 > 0.In order to calibrate our method of studying network robustness, we consider thenetwork-theoretic representation of some materials which, in the real-world, are affectedby melting. In particular, we will consider granular materials. A granular material is amaterial 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 networktheory, which has allowed us to study the structure and physical behaviour of suchsystems 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 thegraph and the concept of network communicability. At the melting phase transition,a graph in question transfers from being connected to being disconnected. We studymelting in graphs with the second largest eigenvalue being positive, namely, in windmillgraphs, dumbbell graphs and cycle graphs. Also, we investigate melting in completemultipartite graphs where the second largest eigenvalue is non-positive. We found amelting phase transition in simple connected graphs with λ2 > 0 and λ2 λ3, whichresembles the melting process of a given system. We found that there is no meltingphase transition in complete multipartite graphs. Also, we found the spectral decomposition for dumbbell graphs and complete multipartite graphs, which until now havenot been done.Moreover, in this thesis, we show that crystalline-like granular materials melt atlower temperatures and display a sharper transition between solid to liquid phasesthan amorphous granular materials. In addition, we show the evolution mechanism ofmelting in these granular materials with tools from network theory. In the particularcase of crystalline materials, the process starts by melting the central core of the crystalnetwork, then melting spreads out from the central core until the whole network (material) transfers into a liquid. We also investigate computationally the melting processin some real-world networks. We found that the melting process of a network correlateswell with the topological structure of the network.
- Advisor / supervisor
- Kitaev, Sergey, 1975-
- Resource Type
- DOI
- Funder
Las relaciones
Elementos
| Miniatura | Título | Fecha de subida | Visibilidad | Acciones |
|---|---|---|---|---|
|
|
PDF of thesis T16179 | 2022-03-24 | Público | Descargar |