In this thesis, we address problems encountered in complex network analysis using graph theoretic methods. The thesis specifically centers on the challenge of how to characterize the structural properties and time evolution of graphs. We commence by providing a brief roadmap for our research in Chapter 1, followed by a review of the relevant research literature in Chapter 2. The remainder of the thesis is structured as follows.
In Chapter 3, we focus on the graph entropic characterizations and explore whether the von Neumann entropy recently defined only on undirected graphs, can be extended to the domain of directed graphs. The substantial contribution involves a simplified form of the entropy which can be expressed in terms of simple graph statistics, such as graph size and vertex in-degree and out-degree. Chapter 4 further investigates the uses and applications of the von Neumann entropy in order to solve a number of network analysis and machine learning problems. The contribution in this chapter includes an entropic edge assortativity measure and an entropic graph embedding method, which are developed for both undirected and directed graphs.
The next part of the thesis analyzes the time-evolving complex networks using physical and information theoretic approaches. In particular, Chapter 5 provides a thermodynamic framework for handling dynamic graphs using ideas from algebraic graph theory and statistical mechanics. This allows us to derive expressions for a number of thermodynamic functions, including energy, entropy and temperature, which are shown to be efficient in identifying abrupt structural changes and phase transitions in real-world dynamical systems. Chapter 6 develops a novel method for constructing a generative model to analyze the structure of labeled data, which provides a number of novel directions to the study of graph time-series. Finally, in Chapter 7, we provide concluding remarks and discuss the limitations of our methodologies, and point out possible future research directions.
