LFCS Seminar: 17 April 2018 - Jessica Enright

Title: Counting Small Subgraphs in Multi-layer Networks

Abstract:

Multi-layer networks occur widely in natural and social systems. I’ll outline details of a few of these, including the sheep and cattle contact networks in Britain. Motivated by a desire to compute efficiently on such networks, I’ll talk about the problem of counting the number of occurrences of (small) subgraphs or motifs in multi-layer graphs in which each layer of the graph has useful structural properties.  Focussing on the parameterised complexity of motif-counting problems, I’ll outline conditions on the layers of a network that yield fixed-parameter tractable algorithms for motif-counting in the overall network, and discuss the results of a few experiments on the Scottish cattle-trading network.