Graph clustering, also known as community detection, is one of the most popular social network analysis tasks, for which a large number of algorithms have been developed. The number of existing methods is not only justified by the importance of this task, but also by the absence of a unique definition of what a community is: different algorithms are often designed to identify different types of communities, and it is thus practically important for a social network analyst to have a toolbox with alternative algorithms.

During the last decade stochastic blockmodelling has emerged as one of the most promising approaches to cluster graphs. The objective of this project is to implement and test a well-known method for stochastic blockmodelling and provide an experimental comparison between this approach and the other main state-of-the-art graph clustering methods, to identify its properties and weaknesses. The other methods will not need to be implemented, but they will be executed using existing network analysis libraries. The candidate must have knowledge of programming in C++.

The article on which this project is based is: Brian Karrer and M. E. J. Newman (2011), Stochastic blockmodels and community structure in networks, PHYSICAL REVIEW E 83, 016107

Supervisors: Davide Vega (davide.vega@it.uu.se) and Matteo Magnani (matteo.magnani@it.uu.se)