14:00
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^\ast(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0 \leq q^\ast(G) \leq 1$.
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 with some probability in our observed graph $G'$ we describe how high a sampling probability we need to infer the community structure of the underlying graph.
Joint work with Colin McDiarmid.