Title: Finite sample goodness-of-fit tests for the stochastic block model
Authors: Vishesh Karwa - Temple University (United States) [presenting]
Abstract: 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. We 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.