White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Entropic Characterization and Time Evolution of Complex Networks

Ye, Cheng (2016) Entropic Characterization and Time Evolution of Complex Networks. PhD thesis, University of York.

This is the latest version of this item.

PhD Thesis Cheng Ye.pdf - Examined Thesis (PDF)
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (7Mb) | Preview


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.

Item Type: Thesis (PhD)
Academic Units: The University of York > Computer Science (York)
Depositing User: Mr Cheng Ye
Date Deposited: 29 Nov 2016 12:17
Last Modified: 29 Nov 2016 12:17
URI: http://etheses.whiterose.ac.uk/id/eprint/15550

Available Versions of this Item

  • Entropic Characterization and Time Evolution of Complex Networks. (deposited 29 Nov 2016 12:17) [Currently Displayed]

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)