Signal Processing and Speech Communication Laboratory
hometheses & projects › Synthesizing Infomap - A Kullback-Leibler Divergence-Based Approach To Community Detection

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

Status
Finished
Type
Master Thesis
Announcement date
01 Jan 2020
Student
Christian Toth
Mentors
Research Areas

Abstract

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 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.