Gaussianization of the spectra of graphs and networks : theory and applications

Student thesis: Doctoral Thesis

Abstract

Matrix functions of the adjacency matrix are very useful for understanding important structural properties of graphs and networks, such as communicability, node centrality, bipartivity and many more. Here we propose a new matrix function based on the Gaussianization of the adjacency matrix of a graph. This function gives more weight to a selected reference eigenvalue λref, which may be located in any region of the graph spectra. In particular, we study the Gaussian Estrada indices for two reference eigenvalues 0 and -1 separately. In each case, we obtain bounds for this index in simple graphs. We also obtain formulas for the Gaussian Estrada index of Erdos-Renyi random graphs as well as for the Barabasi-Albert graphs. Moreover, for λref = 0, we show that in real-world networks this index is related to the existence of important structural patterns, such as complete bipartite subgraphs (bicliques). Such bicliques appear naturally in many real-world networks as a consequence of evolutionary processes giving rise to them. In addition, we fold the graph spectrum at a given pair of reference eigenvalues, then exponentiate the resulting folded graph spectrum to produce the double Gaussian function of the graph adjacency matrix which give more importance to the reference eigenvalues than to the rest of the spectrum. Based on evidence from mathematical chemistry we focus here our attention on the reference eigenvalues ±1. They enclose most of the HOMO (highest occupied molecular orbital) and LUMO (lowest unoccupied molecular orbital) of organic molecular graphs. We prove several results for the trace of the double Gaussian adjacency matrix of simple graphs - the double Gaussian Estrada index - and we apply this index to the classification of polycyclic aromatic hydrocarbons (PAHs) as carcinogenic or non-carcinogenic. We discover that local indices based on the previously developed matrix function allow to classify correctly 100% of the PAHs analyzed. In general, folding the spectrum of the adjacency matrix of networks characterizes important structural information not described in previously used matrix functions of graphs.
Date of Award12 Aug 2021
Original languageEnglish
Awarding Institution
  • University Of Strathclyde
SupervisorPhilip Knight (Supervisor) & Ernesto Estrada (Supervisor)

Cite this

'