Modularity of directed networks: cycle decomposition approach

DOI10.3934/JCD.2015.2.1zbMATH Open1346.60144arXiv1407.8039OpenAlexW2963115731MaRDI QIDQ494276FDOQ494276

Authors: Christof Schütte, Ralf Banisch, Natasa Djurdjevac 

Publication date: 31 August 2015

Published in: Journal of Computational Dynamics (Search for Journal in Brave)

Abstract: The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarse-grained 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. walk process, for which we will prove that although being time-reversible it inherits all necessary information about directions and modular structure of the original network. 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.

Full work available at URL: https://arxiv.org/abs/1407.8039

Recommendations

• Modularity revisited: a novel dynamics-based concept for decomposing complex networks
• Modularity of complex networks models
• Modularity and dynamics on complex networks
• The modular structure of Kauffman networks
• Community structure detection for directed networks through modularity optimisation
• Hierarchical organization of modularity in complex networks
• Modularity in several random graph models

zbMATH Keywords

random walkdirected networksmodulescycle decompositionnode communication

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Communication theory (94A05) Sums of independent random variables; random walks (60G50) Special processes (60K99) Random walks on graphs (05C81) Stochastic network models in operations research (90B15) Communication networks in operations research (90B18) Applications of graph theory to circuits and networks (94C15)

Cites Work

• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• Robust Perron cluster analysis in conformation dynamics
• Title not available (Why is that?)
• On the approximation quality of Markov state models
• The Fokker-Planck equation. Methods of solutions and applications.
• Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise.
• Transition Path Theory for Markov Jump Processes
• Metastability and Markov state models in molecular dynamics. Modeling, analysis, algorithmic approaches
• Mathematical theory of nonequilibrium steady states. On the frontier of probability and dynamical systems.
• An introduction to Markov state models and their application to long timescale molecular simulation
• Cycle Representations of Markov Processes
• Estimating the eigenvalue error of Markov state models
• Communities in Networks
• Modularity revisited: a novel dynamics-based concept for decomposing complex networks
• Random walks on complex modular networks
• Optimal Fuzzy Aggregation of Networks
• Families of line-graphs and their quantization
• Clustering and community detection in directed networks: a survey
• Activity ageing in growing networks
• Study of the phase transition in the 3D Ising spin glass from out-of-equilibrium numerical simulations

Cited In (2)

• The modular structure of Kauffman networks
• Mixed-integer programming for cycle detection in nonreversible Markov processes

This page was built for publication: Modularity of directed networks: cycle decomposition approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494276)