Probability and Combinatorics Seminar: Edge-sampling and modularity

  • Date: –11:15
  • Location: Zoom. Meeting id: 67720169564. Password: first six digits of Pi after the decimal point.
  • Lecturer: Fiona Skerman
  • Organiser: Matematiska institutionen
  • Contact person: Clément Requilé
  • Seminarium


We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. In a natural model where we suppose edges in an underlying graph G appear 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. 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 conjectures and open problems.

Joint work with Colin McDiarmid.