Synthesizing Infomap – A Kullback-Leibler Divergence-Based Approach To Community Detection

Community detection is an essential tool for analyzing the organization of complex social, biological and information networks. Among the numerous community detection algorithms proposed so far, Infomap is a prominent and well-established framework. In this thesis, we propose a novel method for community detection inspired by Infomap. Whereas Infomap approaches community detection analytically by minimizing the average description length of a random walk on a network, our method minimizes dissimilarity, measured using Kullback-Leibler divergence, between a graph-induced and a synthetic random walker to arrive at a partition into communities. Hence, we call our method synthesizing Infomap. Specifically, we focus on community detection in undirected networks with non-overlapping communities and two-level hierarchies. In this work, we provide a formalization and a rigorous derivation of the synthesizing Infomap objective function. By applying synthesizing Infomap on a set of toy graphs we explore its properties and qualitative behavior. Our experiments on artificially generated benchmark networks show that synthesizing Infomap outperforms original Infomap in terms of adjusted mutual information on networks with weak community structure. Both methods perform on par with each other a selection of real-world networks, indicating that synthesizing Infomap produces reasonable results on real-world networks as well. The promising results of synthesizing Infomap encourage further evaluation on real-world networks, as well as extensions to multilevel hierarchies and overlapping community structures.