Fuzzy cycle-flow-based module detection in directed recurrence networks

  • Nataša Conrad (Zuse Institute Berlin, Biocomputing Group, Institut für Mathematik)
A3 01 (Sophus-Lie room)


Finding network modules (or communities, clusters) is a challenging task, especially when modules do not form a full decomposition of a network. In recent years many approaches for finding fuzzy network partitions have been developed, but most of them focus only on undirected networks. Approaches for finding modules in directed networks are usually based on network symmetrization which tend to ignore important directional information by considering only one-step, one-directional node connections.

In this talk I will present our novel random-walk based approach for fuzzy module identification in directed, weighted networks coming from time series data, where edge directions play a crucial role in defining how well nodes in a module are inter-connected. Our method introduces a novel measure of communication between nodes using multi-step, bidirectional transitions encoded by a cycle decomposition of the probability flow. Symmetric properties of this measure enable us to construct an undirected graph that captures information ow of the original graph seen by the data and apply clustering methods designed for undirected graphs. Additionally, we will show that spectral properties of a random-walk process on this new graph are related to the ones of the random-walk process defined on the adjoint cyclic graph (which can be seen as a generalization of line graphs used for fuzzy partitioning of undirected networks). Finally, we will demonstrate how our algorithm can be applied to analyzing earthquake time series data, which naturally induce (time-)directed networks.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail