Characterising network paths through their role in induced substructures

Hudson, Lauren 2021. Characterising network paths through their role in induced substructures. PhD Thesis, Cardiff University. Item availability restricted.

Preview	PDF (PhD Thesis) - Accepted Post-Print Version Available under License Creative Commons Attribution No Derivatives. Download (6MB) | Preview
	PDF (Cardiff University Electronic Publication Form) - Supplemental Material Restricted to Repository staff only Download (134kB)

Abstract

Paths are vital in facilitating network connectivity and have been traditionally characterised by global graph theoretic measures. However, motivated by large or dynamic complex networks, alternative analysis methods have been become popular, based on assessing the presence of induced substructures. These typically involve profiling networks based on the under of over representation of particular induced triads. We examine in detail how induced triads support paths and network connectivity. We begin by considering a triadic census derived from all possible shortest paths as compared to a triadic census from the full network. We find distinct differences, and present a classification for induced triads based on the extent to which their edges can be used in a shortest path. This leads to a new binary classification for edges, called overt or covert, based on supporting flooding across induced triads. We develop these concepts to create local centrality measures that are computationally efficient and which can be used to express the potential for containment or spread from a path. We extend these measures to introduce a convenient edge criticality measure, and compare it against conventional criticality metrics. Results are demonstrated through networks from the literature and synthesised networks

Item Type:	Thesis (PhD)
Date Type:	Completion
Status:	Unpublished
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Date of First Compliant Deposit:	15 August 2022
Date of Acceptance:	12 August 2022
Last Modified:	05 Jan 2024 08:03
URI:	https://orca.cardiff.ac.uk/id/eprint/151924

Actions (repository staff only)

Edit Item