Abstract:

Many real-world systems are most naturally modelled by “multi-layer” networks, which allow for different types of connections between entities; it is therefore important to develop efficient algorithms to extract information from such networks. However, most existing results concerning the structural properties of graphs/networks which allow us to solve NP-hard problems efficiently consider only the case of a “single-layer” graph (in which each pair of vertices is either adjacent or not). A natural question to ask is whether, if each individual layer has well-understood structure which allows the design of efficient algorithms, we can still exploit this structure to solve problems on the combined, multi-layer network. We address this question for the specific problem of counting small substructures in the network: in most cases the problem becomes intractable on the combined network, but we identify one case in which structural restrictions on the individual layers can be exploited effectively.

This is joint work with Jessica Enright (University of Stirling).

Speaker Bio:

Kitty Meeks obtained her PhD from the University of Oxford in 2013, and from 2012 to 2014 worked as a Postdoctoral Research Assistant at Queen Mary University of London. She joined the University of Glasgow in 2014, initially to the School of Mathematics and Statistics, before moving across the road to the School of Computing Science in 2016. She currently holds a Royal Society of Edinburgh Personal Research Fellowship for the project “Exploiting Realistic Graph Structure”.