CIM Seminar with Fiona Skerman
- Date: –13:00
- Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 Å4004
- Lecturer: Fiona Skerman
- Organiser: The Centre for Interdisciplinary Mathematics
- Contact person: Ekaterina Toropova
Title: Partially observing graphs - when can we infer underlying community structure
Abstract: Modularity is at the heart of the most popular algorithms for community detection. For a given network G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the network G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0≤q*(G)≤1.
Suppose we have an underlying graph but cannot observe it directly - rather, each edge in the underlying graph G appears independently with some probability in our observed graph G'. We describe how high a sampling probability we need to infer the modularity of the underlying graph G from our observed graph G'.
It was noted when analysing ecological networks that under-sampled networks tended to over-estimate modularity - we indicate how the asymmetry of our results gives some theoretical backing for this phenomenon - but questions remain.
We also show that the modularity of a graph is robust to changes in a few edges, which is in contrast to the sensitivity of optimal vertex partitions.
In the seminar I will spend time on intuition for the behaviour of modularity, how it can be approximated and links to other graph parameters.