Comparing complex networks through graphlet distributions

Abstract

Complex networks are topologically rich graphs, containing properties that are neither regular nor purely random. Complex networks model real complex systems, so analyzing and extracting information from networks provides knowledge about the system itself. Network comparison is a task within network analysis aimed at quantifying similarities and differences between networks. Graphlets are small patterns of connections whose distribution in the network has been shown to be one of the most informative properties of the structural organization of the network, hence have recently been increasingly adopted as features in network comparison algorithms and measures. NetEmd is a network comparison measure that uses graphlets as features for comparison, being able to identify random networks generated from the same random graph model or real networks from the same domain more accurately than previous network comparison measures for undirected networks, even when their size differs by multiple orders of magnitude. This thesis presents an extension of NetEmd to directed networks and a framework of noise reduction in graphlet frequencies prior to the using the NetEmd measure. Extensive testing is carried out on the performance of the extension and the noise reduction framework, showing the value of these techniques. Network comparison based on graphlets has seen the majority of its use when applied to networks from the biology domain. From an application perspective, this thesis aims to demonstrate how insights based on network comparison with graphlets can be useful in other domains: - Analysis of controversial discussion topics in online social networks often includes a component of sentiment labeling, detection or analysis. However, sentiment labeling is an expensive and labourious process, automatic sentiment detection shows poor performance in some domains and sentiment analysis cannot be performed without either of these. Considering vaccination discussions in online social networks in particular, this thesis shows how differences in network structure detected by network comparison are correlated with changes to the sentiment towards vaccination. Network comparison can be used as a tool to guide when to perform sentiment analysis as well as a technique to enhance the conclusions from sentiment analysis. - During the SARS-CoV-2 pandemic, social mixing prevention policies introduced changes in social contact networks in a way to prevent the spread of the virus. By generating networks based on age-mixing matrices obtained from social surveys representative of the UK population, this thesis performs an investigation of Test-Trace-Isolate strategies within an agent based model used to inform government policy, under different assumptions of social contact network structure.

Date of Award	31 Dec 2022
Original language	English
Awarding Institution	The University of Manchester
Supervisor	Caroline Jay (Supervisor) & Thomas House (Supervisor)