CIM Seminar with Fiona Skerman

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.
 

Registration