Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks
Jeffrey Chan, Samantha Lam and Conor Hayes
In recent years, the summarisation and decomposition of social networks has become increasingly popular, from community finding to role equivalence. However, these approaches concentrate on one type of model only. Generalised blockmodelling decomposes a network into independent, interpretable, labelled blocks, where the block labels summarise the relationship between two sets of users. This allows multiple relationships (block labels or types) in a single model, permitting general types of models. Existing algorithms for fitting generalised blockmodels do not scale beyond networks of 100 vertices. In this paper, we introduce two new algorithms, one based on genetic algorithms and the other on simulated annealing, that is at least two orders of magnitude faster than existing algorithms and obtaining similar accuracy. Using synthetic and real datasets, we demonstrate their efficiency and accuracy and show how generalised blockmodelling and our new approaches enable tractable network summarisation and modelling of medium sized networks.