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 commu- nity 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 equally well on a selection of real-world networks, indi- cating that synthesizing Infomap produces reasonable results on real-world networks as well. The promising results of synthesizing Infomap encour- age further evaluation on real-world networks, as well as extensions to multilevel hierarchies and overlapping community structures