Abstract In recent years, the summarisation and decomposition of social networks has become increasingly popular, from community ?nding to role equivalence. However, these approaches concentrate on one type of model only. Generalised blockmodelling decomposes a network into independent, interpretable, labeled blocks, where the block labels summarise the relationship between two sets of users. Existing algorithms for ?tting 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 ef?ciency and accuracy and show how generalised blockmodelling and our new approaches enable tractable network summarisation and modelling of medium sized networks.