### Sampling sufficiency for determining modularity

Probability Seminar

17th January 2020, 3:30 pm – 4:30 pm

Fry Building, LG.22

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.

We analyse when community structure of an underlying network can be determined from its observed network. 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 network.

Joint work with Colin McDiarmid.

## Comments are closed.