Model Selection for Stochastic Block Models

As a flexible representation for complex systems, networks (graphs) model entities and their interactions as nodes and edges. In many real-world networks, nodes divide naturally into functional communities, where nodes in the same group connect to the rest of the network in similar ways. Discovering such communities is an important part of modeling networks, as community structure offers clues to the processes which generated the graph. The stochastic block model is a popular network model based on community structures. It splits nodes into blocks, within which all nodes are stochastically equivalent in terms of how they connect to the rest of the network. As a generative model, it has a well-defined likelihood function with consistent parameter estimates. It is also highly flexible, capable of modeling a wide variety of community structures, including degree specific and overlapping communities. Performance of different block models vary under different scenarios. Picking the right model is crucial for successful network modeling. A good model choice should balance the trade-off between complexity and fit. The task of model selection is to automatically choose such a model given the data and the inference task. As a problem of wide interest, numerous statistical model selection techniques have been developed for classic independent data. Unfortunately, it has been a common mistake to use these techniques in block models without rigorous examinations of their derivations, ignoring the fact that some of the fundamental assumptions has been violated by moving into the domain of relational data sets such as networks. In this dissertation, I thoroughly exam the literature of statistical model selection techniques, including both Frequentist and Bayesian approaches. My goal is to develop principled statistical model selection criteria for block models by adapting classic methods for network data. I do this by running bootstrapping simulations with an efficient algorithm, and correcting classic model selection theories for block models based on the simulation data. The new model selection methods are verified by both synthetic and real world data sets.

Name thesis:degree_name

Computer Science

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Department of Computer Science

Year

2013

Author dc:creator

• Yan, Xiaoran

Contributors dc:contributor

• Moore, Cristopher
• Hayes, Thomas
• Shalizi, Cosma
• Saia, Jared
• Lane, Terran

• complex networks
• community detection
• block model
• model selection
• information criterion
• variational inference

Language dc:language

English

Identifier

https://digitalrepository.unm.edu/cs_etds/37

OAI identifier oai:identifier

oai:digitalrepository.unm.edu:cs_etds-1036