Image constrained blockmodelling: a constraint programming approach

Blockmodelling is an important technique for detecting un-derlying patterns in graphs. However, existing blockmod-elling algorithms do not provide the user with any explicit control to specify which patterns might be of interest. Fur-thermore, existing algorithms focus on finding standard com-munity structures in graphs, and are likely to overlook in-formative but more complex patterns, such as hierarchical or ring blockmodel structures. In this paper, we propose a generic constraint programming framework for blockmod-elling, which allows a user to specify and search for complex blockmodel patterns in graphs. Our proposed framework can be incorporated into existing iterative blockmodelling algorithms, operating as a hybrid optimization scheme that provides high exibility and expressiveness. We demonstrate the power of our framework for discovering complex pat-terns, via experiments over a range of synthetic and real data sets.