Qualitative and quantitative research on graphs via matrices: Gram mates, Fiedler vectors, Kemeny's constant, and perfect state transfer

Loading...
Thumbnail Image
Date
2021-08
Authors
Kim, Sooyeong
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A fundamental mathematical approach uses graphs to understand networks representing objects with their interrelationships. This thesis is dedicated to qualitative and quantitative research through a bridge---the connections in a graph---with Gram mates arising in social networks; Fiedler vectors in networks; Kemeny's constant in road networks; and perfect state transfer in quantum spin networks. We use techniques from graph theory together with matrix theory---combinatorial matrix theory, algebraic graph theory, and spectral graph theory. Our main work is to examine two-mode networks retaining their information under the conversion approach in social networks. We characterize the relationship of two-mode networks (Gram mates) with the same single-mode networks via their singular values and vectors. So, we produce pairs of Gram mates that inform the retention of the information of two-mode networks. Furthermore, we provide Gram mates under mathematical restrictions. Our next goal is to inspect the robustness of the usage of Fiedler vectors in networks. One popular technique for detecting community structures is based on spectral bisection that uses Fiedler vectors for graph partitioning. We examine graphs where the partite sets resulting from spectral bisection are extremely different in size. We discuss pathological graphs where any choice of Fiedler vectors produces the bisection where one is a singleton and the other the rest. We furnish some classes of graphs that are potentially pathological. Our third task is to explain Braess' paradox in road networks. Kemeny's constant for a Markov chain can be used to measure the travel time of vehicles between two randomly chosen places. We present graphs where the insertion of an edge increases Kemeny's constant. We provide tools for identifying such an edge with examples of graphs, and produce families of graphs with such edges. Our goal of the final research is to switch interactions between qubits in a quantum spin network corresponding to a hypercube, in order for the manipulated spin network to become insensitive to external environments under perfect state transfer (PST). We investigate differences and similarities between hypercubes and the resulting graphs regarding the graph structure, PST, and the sensitivity of PST.
Description
Keywords
Gram mates, Fiedler vectors, Kemeny's constant, Perfect state transfer
Citation