Reformulations of the Map Equation for Community Finding and Blockmodelling

Among the many community-finding algorithms that have been proposed in the last decade and more, the Infomapalgorithm of Rosvall and Bergstrom has proven among the best. The algorithm finds good community structure in directed aswell as undirected networks by abstracting information flow inthe network as a random walk. In this paper, we reformulate the objective in terms of the Kullback-Leibler distance between thedistribution of the random walk transitions and that of a modelwalk. The choice of model can be used to constrain the typeof partition that the method extracts. This generalisation makesthe method suitable for extracting other types of meso-structurefrom the network, enabling the analyst to explicitly control thetype of extracted structure.