March 28, 2011 to April 20, 2011
Europe/Stockholm timezone

Overlapping communities in networks from the flow perspective of the map equation

Apr 6, 2011, 1:30 PM


Alcides Viamontes Esquivel (IceLab, Umeå University)


Infomap clusters networks using the correspondence between compression, regularity detection and learning expressed in the minimum description length principle. Here we extend that approach to find partitions with overlaps, considering flow on the nodes near the boundary of modules. Specifically, we analyze how affects the modular structure the return proportion of flow on those nodes, versus the proportion going to different modules. We show that the return proportion characteristic can be better captured -- in terms of average bit-length per step -- by allowing nodes to belong to several modules, effectively making the modules to overlap. This work introduces both the updated framework and a fast greedy algorithm that finds the module overlappings. Also, we present the outcomes of our new method when processing several real world networks and in the context of a benchmark procedure. For the later one, we devised a way of calculating the mutual information between two partitions that deals with overlaps consistently.

Presentation materials

There are no materials yet.