Goodness-of-Fit Tests for Stochastic Block Models Using Algebraic Tools

Stochastic Block models (SBM) with unknown block structure are widely used to detect community structure in real world networks. SBM comes in many variants, hence it is essential to evaluate the fit of these variants. Testing the goodness-of-fit of such models is a challenging task due to the fact that the parameters of an SBM are usually estimated from a single observed network. Usual asymptotic tests are not valid. In this talk I will introduce three different variations of Stochastic Block Models and present a finite sample goodness-of-fit test for these models, when the block structure is unknown. The finite sample test is based on extending the classic fisher's exact test to SBMs with known and unknown blocks. The machinery of Algebraic Statistics is used in constructing this test. In particular, a key building block for the test is a sampler from the so called "fibers" of SBMs with known block assignments - the set of all graphs with a fixed sufficient statistic. Sampling from these fibers is carried out using Markov bases. The talk will be at a high level explaining the essential ideas and hence no prior knowledge of algebra or exact tests will be assumed.

Event Topic

Nonlinear Algebra and Statistics (NLASTATS)