Characterisation of Complex Networks from their Topologies

Abstract

Complex networks appear everywhere in the world. They describe everything from the Internet and transport networks to neuronal networks and social networks. Characterising these networks, that is, describing them quantitatively, is vitally important to understanding them, comparing them and tracking their temporal evolution. The connection patterns, or topologies, of networks are often very different across different networks and sometimes even between different parts of a single network, or over time in temporal networks. This work focuses particularly on these connection patterns and how they can characterise networks at multiple scales: we use the topology to characterise nodes, communities and entire networks. On the subject of node characterisation, we demonstrate the merits of using colour in graphlet profiles when characterising ego-networks, using this technique to discover that, in scientific co-authorship networks, the proportion of graphlets of a specific kind centred on an author early in their career is correlated with that author's final academic career length. These graphlets which are correlated with career length are 4-stars; induced subgraphs containing four nodes where one node is the author and the other three nodes only have a link to the author. For whole-network characterisation, we use matrix decomposition of data matrices formed from topological properties such as degree-mixing matrices and graphlet profiles to clearly distinguish between real networks and network models and track changes in networks over time. We introduce the term piecewise static networks to describe the application of standard static network analysis to temporal networks. Finally, on community characterisation, we introduce a new way of assessing the goodness-of-fit for tensor decompositions of temporal networks by applying adjusted mutual information and employ this technique to throw more light on software dependency networks, where we use it to highlight the uniqueness of the R language's software package ecosystem due to R's rolling-release cycle policy and semantic networks, where we start to study the evolution of the English language over the past thousand years.

Date of Award	1 Aug 2020
Original language	English
Awarding Institution	The University of Manchester
Supervisor	Jonathan Shapiro (Supervisor), Andrea Schalk (Supervisor) & Eva Navarro Lopez (Supervisor)