Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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.

[thumbnail of PhD Thesis]
PDF (PhD Thesis) - Accepted Post-Print Version
Available under License Creative Commons Attribution No Derivatives.

Download (6MB) | Preview
[thumbnail of Cardiff University Electronic Publication Form] PDF (Cardiff University Electronic Publication Form) - Supplemental Material
Restricted to Repository staff only

Download (134kB)


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

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics