Modularity of Directed Networks: Cycle Decomposition Approach

Please always quote using this URN: urn:nbn:de:0297-zib-51166
  • The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarsegrained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Author:Natasa Djurdjevac Conrad, Ralf Banisch, Christof Schütte
Document Type:ZIB-Report
Tag:directed networks, modules, cycle decomposition, measure of node communication
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C81 Random walks on graphs
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Jxx Markov processes / 60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) [See also 90B30, 91D10, 91D35, 91E40]
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Cxx Circuits, networks / 94C15 Applications of graph theory [See also 05Cxx, 68R10]
Date of first Publication:2014/08/01
Series (Serial Number):ZIB-Report (14-31)
Published in:Appeared in: Journal of Computational Dynamics 2 (2015) pp. 1-24

$Rev: 13581 $