The spectral analysis of random graph matrices

Dan Hu

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

145 Downloads (Pure)

Abstract

A random graph model is a set of graphs together with a probability distribution on that set. A random matrix is a matrix with entries consisting of random values from some specified distribution. Many different random matrices can be associated with a random graph. The spectra of these corresponding matrices are called the spectra of the random graph. The spectra of random graphs are critical to understanding the properties of random graphs.
This thesis contains a number of results on the spectra and related spectral properties of several random graph models.
In Chapter 1, we briefly present the background, some history as well as the main ideas behind our work. Apart from the introduction in Chapter 1, the first part of the main body of the thesis is Chapter 2. In this part we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs. We also investigate some spectral properties of random multipartite graphs, such as the Laplacian energy, the Laplacian Estrada index, and the von Neumann entropy.
The second part consists of Chapters 3, 4, 5 and 6. Guo and Mohar showed that mixed graphs are equivalent to digraphs if we regard (replace) each undirected edge as (by) two oppositely directed arcs. Motivated by the work of Guo and Mohar, we initially propose a new random graph model – the random mixed graph. Each arc is determined by an in-dependent random variable. The main themes of the second part are the spectra and related spectral properties of random mixed graphs.
In Chapter 3, we prove that the empirical distribution of the eigenvalues of the Hermitian adjacency matrix converges to Wigner’s semicircle law. As an application of the LSD of Hermitian adjacency matrices, we estimate the Hermitian energy of a random mixed graph.
In Chapter 4, we deal with the asymptotic behavior of the spectrum of the Hermitian adjacency matrix of random mixed graphs. We derive a separation result between the first and the remaining eigenvalues of the Hermitian adjacency matrix. As an application of the asymptotic behavior of the spectrum of the Hermitian adjacency matrix, we estimate the spectral moments of random mixed graphs.
In Chapter 5, we prove that the empirical distribution of the eigenvalues of the normalized Hermitian Laplacian matrix converges to Wigner’s semicircle law.
Moreover, in Chapter 6, we provide several results on the spectra of general random mixed graphs. In particular, we present a new probability inequality for sums of independent, random, self-adjoint matrices, and then apply this probability inequality to matrices arising from the study of random mixed graphs. We prove a concentration result involving the spectral norm of a random matrix and that of its expectation. Assuming that the probabilities of all the arcs of the mixed graph are mutually independent, we write the Hermitian adjacency matrix as a sum of random self-adjoint matrices. Using this, we estimate the spectrum of the Hermitian adjacency matrix, and prove a concentration result involving the spectrum of the normalized Hermitian Laplacian matrix and its expectation.
Finally, in Chapter 7, we estimate upper bounds for the spectral radii of the skew adjacency matrix and skew Randić matrix of random oriented graphs.
Original languageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Zhang, Shenggui, Supervisor
Award date5 Sep 2018
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4608-9
DOIs
Publication statusPublished - 5 Sep 2018

Fingerprint

Spectral Analysis
Random Graphs
Mixed Graphs
Hermitian matrix
Adjacency Matrix
Laplacian Matrix
Graph Model
Multipartite Graph
Random Matrices
Spectral Properties
Semicircle Law
Probability Inequalities
Eigenvalue
Arc of a curve
Estimate
Empirical Distribution
Skew
Asymptotic Behavior
Converge
Spectral Norm

Cite this

Hu, Dan . / The spectral analysis of random graph matrices. Enschede : Ipskamp Printing, 2018. 162 p.
@phdthesis{d6e0c7257ceb4d70892cda0d886a12b7,
title = "The spectral analysis of random graph matrices",
abstract = "A random graph model is a set of graphs together with a probability distribution on that set. A random matrix is a matrix with entries consisting of random values from some specified distribution. Many different random matrices can be associated with a random graph. The spectra of these corresponding matrices are called the spectra of the random graph. The spectra of random graphs are critical to understanding the properties of random graphs. This thesis contains a number of results on the spectra and related spectral properties of several random graph models.In Chapter 1, we briefly present the background, some history as well as the main ideas behind our work. Apart from the introduction in Chapter 1, the first part of the main body of the thesis is Chapter 2. In this part we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs. We also investigate some spectral properties of random multipartite graphs, such as the Laplacian energy, the Laplacian Estrada index, and the von Neumann entropy.The second part consists of Chapters 3, 4, 5 and 6. Guo and Mohar showed that mixed graphs are equivalent to digraphs if we regard (replace) each undirected edge as (by) two oppositely directed arcs. Motivated by the work of Guo and Mohar, we initially propose a new random graph model – the random mixed graph. Each arc is determined by an in-dependent random variable. The main themes of the second part are the spectra and related spectral properties of random mixed graphs.In Chapter 3, we prove that the empirical distribution of the eigenvalues of the Hermitian adjacency matrix converges to Wigner’s semicircle law. As an application of the LSD of Hermitian adjacency matrices, we estimate the Hermitian energy of a random mixed graph.In Chapter 4, we deal with the asymptotic behavior of the spectrum of the Hermitian adjacency matrix of random mixed graphs. We derive a separation result between the first and the remaining eigenvalues of the Hermitian adjacency matrix. As an application of the asymptotic behavior of the spectrum of the Hermitian adjacency matrix, we estimate the spectral moments of random mixed graphs.In Chapter 5, we prove that the empirical distribution of the eigenvalues of the normalized Hermitian Laplacian matrix converges to Wigner’s semicircle law.Moreover, in Chapter 6, we provide several results on the spectra of general random mixed graphs. In particular, we present a new probability inequality for sums of independent, random, self-adjoint matrices, and then apply this probability inequality to matrices arising from the study of random mixed graphs. We prove a concentration result involving the spectral norm of a random matrix and that of its expectation. Assuming that the probabilities of all the arcs of the mixed graph are mutually independent, we write the Hermitian adjacency matrix as a sum of random self-adjoint matrices. Using this, we estimate the spectrum of the Hermitian adjacency matrix, and prove a concentration result involving the spectrum of the normalized Hermitian Laplacian matrix and its expectation.Finally, in Chapter 7, we estimate upper bounds for the spectral radii of the skew adjacency matrix and skew Randić matrix of random oriented graphs.",
author = "Dan Hu",
year = "2018",
month = "9",
day = "5",
doi = "10.3990/1.9789036546089",
language = "English",
isbn = "978-90-365-4608-9",
series = "DSI Ph.D. Thesis Series",
publisher = "Ipskamp Printing",
number = "18-012",
address = "Netherlands",
school = "University of Twente",

}

The spectral analysis of random graph matrices. / Hu, Dan .

Enschede : Ipskamp Printing, 2018. 162 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - The spectral analysis of random graph matrices

AU - Hu, Dan

PY - 2018/9/5

Y1 - 2018/9/5

N2 - A random graph model is a set of graphs together with a probability distribution on that set. A random matrix is a matrix with entries consisting of random values from some specified distribution. Many different random matrices can be associated with a random graph. The spectra of these corresponding matrices are called the spectra of the random graph. The spectra of random graphs are critical to understanding the properties of random graphs. This thesis contains a number of results on the spectra and related spectral properties of several random graph models.In Chapter 1, we briefly present the background, some history as well as the main ideas behind our work. Apart from the introduction in Chapter 1, the first part of the main body of the thesis is Chapter 2. In this part we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs. We also investigate some spectral properties of random multipartite graphs, such as the Laplacian energy, the Laplacian Estrada index, and the von Neumann entropy.The second part consists of Chapters 3, 4, 5 and 6. Guo and Mohar showed that mixed graphs are equivalent to digraphs if we regard (replace) each undirected edge as (by) two oppositely directed arcs. Motivated by the work of Guo and Mohar, we initially propose a new random graph model – the random mixed graph. Each arc is determined by an in-dependent random variable. The main themes of the second part are the spectra and related spectral properties of random mixed graphs.In Chapter 3, we prove that the empirical distribution of the eigenvalues of the Hermitian adjacency matrix converges to Wigner’s semicircle law. As an application of the LSD of Hermitian adjacency matrices, we estimate the Hermitian energy of a random mixed graph.In Chapter 4, we deal with the asymptotic behavior of the spectrum of the Hermitian adjacency matrix of random mixed graphs. We derive a separation result between the first and the remaining eigenvalues of the Hermitian adjacency matrix. As an application of the asymptotic behavior of the spectrum of the Hermitian adjacency matrix, we estimate the spectral moments of random mixed graphs.In Chapter 5, we prove that the empirical distribution of the eigenvalues of the normalized Hermitian Laplacian matrix converges to Wigner’s semicircle law.Moreover, in Chapter 6, we provide several results on the spectra of general random mixed graphs. In particular, we present a new probability inequality for sums of independent, random, self-adjoint matrices, and then apply this probability inequality to matrices arising from the study of random mixed graphs. We prove a concentration result involving the spectral norm of a random matrix and that of its expectation. Assuming that the probabilities of all the arcs of the mixed graph are mutually independent, we write the Hermitian adjacency matrix as a sum of random self-adjoint matrices. Using this, we estimate the spectrum of the Hermitian adjacency matrix, and prove a concentration result involving the spectrum of the normalized Hermitian Laplacian matrix and its expectation.Finally, in Chapter 7, we estimate upper bounds for the spectral radii of the skew adjacency matrix and skew Randić matrix of random oriented graphs.

AB - A random graph model is a set of graphs together with a probability distribution on that set. A random matrix is a matrix with entries consisting of random values from some specified distribution. Many different random matrices can be associated with a random graph. The spectra of these corresponding matrices are called the spectra of the random graph. The spectra of random graphs are critical to understanding the properties of random graphs. This thesis contains a number of results on the spectra and related spectral properties of several random graph models.In Chapter 1, we briefly present the background, some history as well as the main ideas behind our work. Apart from the introduction in Chapter 1, the first part of the main body of the thesis is Chapter 2. In this part we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs. We also investigate some spectral properties of random multipartite graphs, such as the Laplacian energy, the Laplacian Estrada index, and the von Neumann entropy.The second part consists of Chapters 3, 4, 5 and 6. Guo and Mohar showed that mixed graphs are equivalent to digraphs if we regard (replace) each undirected edge as (by) two oppositely directed arcs. Motivated by the work of Guo and Mohar, we initially propose a new random graph model – the random mixed graph. Each arc is determined by an in-dependent random variable. The main themes of the second part are the spectra and related spectral properties of random mixed graphs.In Chapter 3, we prove that the empirical distribution of the eigenvalues of the Hermitian adjacency matrix converges to Wigner’s semicircle law. As an application of the LSD of Hermitian adjacency matrices, we estimate the Hermitian energy of a random mixed graph.In Chapter 4, we deal with the asymptotic behavior of the spectrum of the Hermitian adjacency matrix of random mixed graphs. We derive a separation result between the first and the remaining eigenvalues of the Hermitian adjacency matrix. As an application of the asymptotic behavior of the spectrum of the Hermitian adjacency matrix, we estimate the spectral moments of random mixed graphs.In Chapter 5, we prove that the empirical distribution of the eigenvalues of the normalized Hermitian Laplacian matrix converges to Wigner’s semicircle law.Moreover, in Chapter 6, we provide several results on the spectra of general random mixed graphs. In particular, we present a new probability inequality for sums of independent, random, self-adjoint matrices, and then apply this probability inequality to matrices arising from the study of random mixed graphs. We prove a concentration result involving the spectral norm of a random matrix and that of its expectation. Assuming that the probabilities of all the arcs of the mixed graph are mutually independent, we write the Hermitian adjacency matrix as a sum of random self-adjoint matrices. Using this, we estimate the spectrum of the Hermitian adjacency matrix, and prove a concentration result involving the spectrum of the normalized Hermitian Laplacian matrix and its expectation.Finally, in Chapter 7, we estimate upper bounds for the spectral radii of the skew adjacency matrix and skew Randić matrix of random oriented graphs.

U2 - 10.3990/1.9789036546089

DO - 10.3990/1.9789036546089

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4608-9

T3 - DSI Ph.D. Thesis Series

PB - Ipskamp Printing

CY - Enschede

ER -

Hu D. The spectral analysis of random graph matrices. Enschede: Ipskamp Printing, 2018. 162 p. (DSI Ph.D. Thesis Series; 18-012). https://doi.org/10.3990/1.9789036546089