LFCS seminar: Jessica Enright: Counting small subgraphs in multi-layer networks
What |
|
---|---|
When |
Apr 17, 2018 from 04:00 PM to 05:00 PM |
Where | IF 4.31/4.33 |
Add event to calendar |
![]() ![]() |
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.
Joint work with Kitty Meeks (Glasgow).