CCSI Weekly Seminar: Partially Observing Graphs - When Can We Infer Underlying Community Structure?

Suppose edges in an underlying graph G appear independently with some probability in our observed graph G' - or alternately that we can query uniformly random edges. We describe how high a sampling probability we need to infer the modularity of the underlying graph.

Modularity is a function on graphs which is used in algorithms for community detection. For a given graph 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 graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1.

In the seminar I will spend time on intuition for the behaviour of modularity, how it can be approximated, links to other graph parameters and to present some open problems.

Joint work with Colin McDiarmid.