American Institute of Mathematical Sciences

Advanced
January  2015, 2(1): 1-24. doi: 10.3934/jcd.2015.2.1

Modularity of directed networks: Cycle decomposition approach

Nataša Djurdjevac Conrad 1, , Ralf Banisch 1, and  Christof Schütte 1,

1. 

Freie Universität Berlin, Department of Mathematics and Computer Science, Arnimallee 6, 14195 Berlin, Germany, Germany

Received  August 2014 Revised  February 2015 Published  August 2015

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. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits important directional information of modular structures from the original network.
Keywords: Directed networks, measure of node communication., modules, cycle decomposition.
Mathematics Subject Classification: Primary: 60J20, 05C81; Secondary: 94C1.
Citation: Nataša Djurdjevac Conrad, Ralf Banisch, Christof Schütte. Modularity of directed networks: Cycle decomposition approach. Journal of Computational Dynamics, 2015, 2 (1) : 1-24. doi: 10.3934/jcd.2015.2.1
References:
[1]

B. Altaner, S. Grosskinsky, S. Herminghaus, L. Katthän, M. Timme and J. Vollmer, Network representations of nonequilibrium steady states: Cycle decompositions, symmetries, and dominant paths,, Phys. Rev. E, 85 (2012).  doi: 10.1103/PhysRevE.85.041133.  Google Scholar

[2]

A. Arenas, J. Duch, A. Fernández and S. Gómez, Size reduction of complex networks preserving modularity,, New Journal of Physics, 9 (2007).  doi: 10.1088/1367-2630/9/6/176.  Google Scholar

[3]

R. Banisch and N. D. Conrad, Cycle-flow based module detection in directed recurrence networks,, EPL (Europhysics Letters), 108 (2014), 0295.  doi: 10.1209/0295-5075/108/68008.  Google Scholar

[4]

A. Barrat, M. Barthelemy, R. Pastor-Satorras and A. Vespignani, The architecture of complex weighted networks,, Proceedings of the National Academy of Sciences of the United States of America, 101 (2004), 3747.  doi: 10.1073/pnas.0400087101.  Google Scholar

[5]

G. R. Bowman and V. S. Pande and F. Noé, editors, An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation,, volume 797 of Advances in Experimental Medicine and Biology, (2014).  doi: 10.1007/978-94-007-7606-7_11.  Google Scholar

[6]

J. Chen and B. Yuan, Detecting functional modules in the yeast protein-protein interaction network,, Bioinformatics, 22 (2006), 2283.  doi: 10.1093/bioinformatics/btl370.  Google Scholar

[7]

D. Cvetkovic, P. Rowlinson and S. Simic, Spectral Generalizations of Line Graphs,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511751752.  Google Scholar

[8]

P. Deuflhard and M. Weber, Robust perron cluster analysis in conformation dynamics,, Linear Algebra and its Applications, 398 (2005), 161.  doi: 10.1016/j.laa.2004.10.026.  Google Scholar

[9]

N. Djurdjevac, S. Bruckner, T. O. F. Conrad and C. Schütte, Random walks on complex modular networks,, Journal of Numerical Analysis, 6 (2011), 29.   Google Scholar

[10]

N. Djurdjevac, M. Sarich and C. Schütte, Estimating the eigenvalue error of markov state models,, Multiscale Modeling & Simulation, 10 (2012), 61.  doi: 10.1137/100798910.  Google Scholar

[11]

T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.016105.  Google Scholar

[12]

S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.  doi: 10.1016/j.physrep.2009.11.002.  Google Scholar

[13]

M. Girvan and M. Newman, Community structure in social and biological networks,, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002), 7821.  doi: 10.1073/pnas.122653799.  Google Scholar

[14]

D. Jiang, M. Qian and M.-P. Quian, Mathematical Theory of Nonequilibrium Steady States: On the Frontier of Probability and Dynamical Systems,, Springer, (2004).  doi: 10.1007/b94615.  Google Scholar

[15]

S. L. Kalpazidou, Cycle Representations of Markov Processes,, Springer, (2006).   Google Scholar

[16]

Y. Kim, S.-W. Son and H. Jeong, Finding communities in directed networks,, Phys. Rev. E, 81 (2010).  doi: 10.1103/PhysRevE.81.016103.  Google Scholar

[17]

R. Lambiotte, J. C. Delvenne and M. Barahona, Laplacian dynamics and multiscale modular structure in networks,, ArXiv., ().   Google Scholar

[18]

A. Lancichinetti and S. Fortunato, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.016118.  Google Scholar

[19]

A. Lancichinetti, F. Radicchi, J. J. Ramasco and S. Fortunato, Finding statistically significant communities in networks,, PLoS ONE, 6 (2011).  doi: 10.1371/journal.pone.0018961.  Google Scholar

[20]

E. A. Leicht and M. E. J. Newman, Community structure in directed networks,, Phys. Rev. Lett., 100 (2008).  doi: 10.1103/PhysRevLett.100.118703.  Google Scholar

[21]

T. Li, J. Liu and W. E, Probabilistic framework for network partition,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.026106.  Google Scholar

[22]

F. D. Malliaros and M. Vazirgiannis, Clustering and community detection in directed networks: A survey,, Physics Reports, 533 (2013), 95.  doi: 10.1016/j.physrep.2013.08.002.  Google Scholar

[23]

J. Mattingly, A. M. Stuart and D. J. Higham, Ergodicity for SDEs and approximations: Locally Lipschitz vector fields and degenerated noise,, Stochastic Process Appl., 101 (2002), 185.  doi: 10.1016/S0304-4149(02)00150-3.  Google Scholar

[24]

P. Metzner, C. Schütte and E. Vanden-Eijnden, Transition path theory for markov jump processes,, Multiscale Modeling & Simulation, 7 (2008), 1192.  doi: 10.1137/070699500.  Google Scholar

[25]

M. E. J. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167.  doi: 10.1137/S003614450342480.  Google Scholar

[26]

M. E. J. Newman, Fast algorithm for detecting community structure in networks,, Phys. Rev. E, 69 (2004).  doi: 10.1103/PhysRevE.69.066133.  Google Scholar

[27]

M. E. J. Newman, Modularity and community structure in networks,, Proceedings of the National Academy of Sciences, 103 (2006), 8577.  doi: 10.1073/pnas.0601602103.  Google Scholar

[28]

V. Nicosia, G. Mangioni, V. Carchiolo and M. Malgeri, Extending the definition of modularity of directed graphs with overlapping communities,, Journal of Statistical Mechanics: Theory and Experiment, 2009 (2009).  doi: 10.1088/1742-5468/2009/03/P03024.  Google Scholar

[29]

P. Pakoński, G. Tanner and K. .Zyczkowski, Families of line-graphs and their quantization,, Journal of Statistical Physics, 111 (2003), 1331.  doi: 10.1023/A:1023012502046.  Google Scholar

[30]

G. Palla, I. Derenyi, I. Farkas and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society,, Nature, 435 (2005), 814.  doi: 10.1038/nature03607.  Google Scholar

[31]

M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, Notices of the American Mathematical Society, 56 (2009), 1082.   Google Scholar

[32]

H. Risken, The Fokker-Planck Equation,, Springer, (1996).   Google Scholar

[33]

M. Sarich, N. Djurdjevac, S. Bruckner, T. O. F. Conrad and C. Schütte, Modularity revisited: A novel dynamics-based concept for decomposing complex networks,, Journal of Computational Dynamics, 1 (2014), 191.  doi: 10.3934/jcd.2014.1.191.  Google Scholar

[34]

M. Sarich, F. Noé and C. Schütte, On the Approximation Quality of Markov State Models,, Multiscale Modeling & Simulation, 8 (2010), 1154.  doi: 10.1137/090764049.  Google Scholar

[35]

M. Sarich, C. Schütte and E. Vanden-Eijnden, Optimal fuzzy aggregation of networks,, Multiscale Modeling & Simulation, 8 (2010), 1535.  doi: 10.1137/090758519.  Google Scholar

[36]

M. T. Schaub, J.-C. Delvenne, S. N. Yaliraki and M. Barahona, Markov dynamics as a zooming lens for multiscale community detection: Non clique-like communities and the field-of-view limit,, PLoS ONE, 7 (2012).  doi: 10.1371/journal.pone.0032210.  Google Scholar

[37]

M. T. Schaub, R. Lambiotte and M. Barahona, Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation,, Phys. Rev. E, 86 (2012).  doi: 10.1103/PhysRevE.86.026112.  Google Scholar

[38]

J. Schnakenberg, Network theory of microscopic and macroscopic behavior of master equation systems,, Rev. Mod. Phys., 48 (1976), 571.  doi: 10.1103/RevModPhys.48.571.  Google Scholar

[39]

Ch. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches,, volume 24 of Courant Lecture Notes, (2013).   Google Scholar

[40]

A. Viamontes Esquivel and M. Rosvall, Compression of flow can reveal overlapping-module organization in networks,, Phys. Rev. X, 1 (2011).  doi: 10.1103/PhysRevX.1.021025.  Google Scholar

[41]

R. K. P. Zia and B. Schmittmann, Probability currents as principal characteristics in the statistical mechanics of non-equilibrium steady states,, Journal of Statistical Mechanics-theory and Experiment, 2007 (2007).  doi: 10.1088/1742-5468/2007/07/P07012.  Google Scholar

show all references

References:
[1]

B. Altaner, S. Grosskinsky, S. Herminghaus, L. Katthän, M. Timme and J. Vollmer, Network representations of nonequilibrium steady states: Cycle decompositions, symmetries, and dominant paths,, Phys. Rev. E, 85 (2012).  doi: 10.1103/PhysRevE.85.041133.  Google Scholar

[2]

A. Arenas, J. Duch, A. Fernández and S. Gómez, Size reduction of complex networks preserving modularity,, New Journal of Physics, 9 (2007).  doi: 10.1088/1367-2630/9/6/176.  Google Scholar

[3]

R. Banisch and N. D. Conrad, Cycle-flow based module detection in directed recurrence networks,, EPL (Europhysics Letters), 108 (2014), 0295.  doi: 10.1209/0295-5075/108/68008.  Google Scholar

[4]

A. Barrat, M. Barthelemy, R. Pastor-Satorras and A. Vespignani, The architecture of complex weighted networks,, Proceedings of the National Academy of Sciences of the United States of America, 101 (2004), 3747.  doi: 10.1073/pnas.0400087101.  Google Scholar

[5]

G. R. Bowman and V. S. Pande and F. Noé, editors, An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation,, volume 797 of Advances in Experimental Medicine and Biology, (2014).  doi: 10.1007/978-94-007-7606-7_11.  Google Scholar

[6]

J. Chen and B. Yuan, Detecting functional modules in the yeast protein-protein interaction network,, Bioinformatics, 22 (2006), 2283.  doi: 10.1093/bioinformatics/btl370.  Google Scholar

[7]

D. Cvetkovic, P. Rowlinson and S. Simic, Spectral Generalizations of Line Graphs,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511751752.  Google Scholar

[8]

P. Deuflhard and M. Weber, Robust perron cluster analysis in conformation dynamics,, Linear Algebra and its Applications, 398 (2005), 161.  doi: 10.1016/j.laa.2004.10.026.  Google Scholar

[9]

N. Djurdjevac, S. Bruckner, T. O. F. Conrad and C. Schütte, Random walks on complex modular networks,, Journal of Numerical Analysis, 6 (2011), 29.   Google Scholar

[10]

N. Djurdjevac, M. Sarich and C. Schütte, Estimating the eigenvalue error of markov state models,, Multiscale Modeling & Simulation, 10 (2012), 61.  doi: 10.1137/100798910.  Google Scholar

[11]

T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.016105.  Google Scholar

[12]

S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.  doi: 10.1016/j.physrep.2009.11.002.  Google Scholar

[13]

M. Girvan and M. Newman, Community structure in social and biological networks,, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002), 7821.  doi: 10.1073/pnas.122653799.  Google Scholar

[14]

D. Jiang, M. Qian and M.-P. Quian, Mathematical Theory of Nonequilibrium Steady States: On the Frontier of Probability and Dynamical Systems,, Springer, (2004).  doi: 10.1007/b94615.  Google Scholar

[15]

S. L. Kalpazidou, Cycle Representations of Markov Processes,, Springer, (2006).   Google Scholar

[16]

Y. Kim, S.-W. Son and H. Jeong, Finding communities in directed networks,, Phys. Rev. E, 81 (2010).  doi: 10.1103/PhysRevE.81.016103.  Google Scholar

[17]

R. Lambiotte, J. C. Delvenne and M. Barahona, Laplacian dynamics and multiscale modular structure in networks,, ArXiv., ().   Google Scholar

[18]

A. Lancichinetti and S. Fortunato, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.016118.  Google Scholar

[19]

A. Lancichinetti, F. Radicchi, J. J. Ramasco and S. Fortunato, Finding statistically significant communities in networks,, PLoS ONE, 6 (2011).  doi: 10.1371/journal.pone.0018961.  Google Scholar

[20]

E. A. Leicht and M. E. J. Newman, Community structure in directed networks,, Phys. Rev. Lett., 100 (2008).  doi: 10.1103/PhysRevLett.100.118703.  Google Scholar

[21]

T. Li, J. Liu and W. E, Probabilistic framework for network partition,, Phys. Rev. E, 80 (2009).  doi: 10.1103/PhysRevE.80.026106.  Google Scholar

[22]

F. D. Malliaros and M. Vazirgiannis, Clustering and community detection in directed networks: A survey,, Physics Reports, 533 (2013), 95.  doi: 10.1016/j.physrep.2013.08.002.  Google Scholar

[23]

J. Mattingly, A. M. Stuart and D. J. Higham, Ergodicity for SDEs and approximations: Locally Lipschitz vector fields and degenerated noise,, Stochastic Process Appl., 101 (2002), 185.  doi: 10.1016/S0304-4149(02)00150-3.  Google Scholar

[24]

P. Metzner, C. Schütte and E. Vanden-Eijnden, Transition path theory for markov jump processes,, Multiscale Modeling & Simulation, 7 (2008), 1192.  doi: 10.1137/070699500.  Google Scholar

[25]

M. E. J. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167.  doi: 10.1137/S003614450342480.  Google Scholar

[26]

M. E. J. Newman, Fast algorithm for detecting community structure in networks,, Phys. Rev. E, 69 (2004).  doi: 10.1103/PhysRevE.69.066133.  Google Scholar

[27]

M. E. J. Newman, Modularity and community structure in networks,, Proceedings of the National Academy of Sciences, 103 (2006), 8577.  doi: 10.1073/pnas.0601602103.  Google Scholar

[28]

V. Nicosia, G. Mangioni, V. Carchiolo and M. Malgeri, Extending the definition of modularity of directed graphs with overlapping communities,, Journal of Statistical Mechanics: Theory and Experiment, 2009 (2009).  doi: 10.1088/1742-5468/2009/03/P03024.  Google Scholar

[29]

P. Pakoński, G. Tanner and K. .Zyczkowski, Families of line-graphs and their quantization,, Journal of Statistical Physics, 111 (2003), 1331.  doi: 10.1023/A:1023012502046.  Google Scholar

[30]

G. Palla, I. Derenyi, I. Farkas and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society,, Nature, 435 (2005), 814.  doi: 10.1038/nature03607.  Google Scholar

[31]

M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, Notices of the American Mathematical Society, 56 (2009), 1082.   Google Scholar

[32]

H. Risken, The Fokker-Planck Equation,, Springer, (1996).   Google Scholar

[33]

M. Sarich, N. Djurdjevac, S. Bruckner, T. O. F. Conrad and C. Schütte, Modularity revisited: A novel dynamics-based concept for decomposing complex networks,, Journal of Computational Dynamics, 1 (2014), 191.  doi: 10.3934/jcd.2014.1.191.  Google Scholar

[34]

M. Sarich, F. Noé and C. Schütte, On the Approximation Quality of Markov State Models,, Multiscale Modeling & Simulation, 8 (2010), 1154.  doi: 10.1137/090764049.  Google Scholar

[35]

M. Sarich, C. Schütte and E. Vanden-Eijnden, Optimal fuzzy aggregation of networks,, Multiscale Modeling & Simulation, 8 (2010), 1535.  doi: 10.1137/090758519.  Google Scholar

[36]

M. T. Schaub, J.-C. Delvenne, S. N. Yaliraki and M. Barahona, Markov dynamics as a zooming lens for multiscale community detection: Non clique-like communities and the field-of-view limit,, PLoS ONE, 7 (2012).  doi: 10.1371/journal.pone.0032210.  Google Scholar

[37]

M. T. Schaub, R. Lambiotte and M. Barahona, Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation,, Phys. Rev. E, 86 (2012).  doi: 10.1103/PhysRevE.86.026112.  Google Scholar

[38]

J. Schnakenberg, Network theory of microscopic and macroscopic behavior of master equation systems,, Rev. Mod. Phys., 48 (1976), 571.  doi: 10.1103/RevModPhys.48.571.  Google Scholar

[39]

Ch. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches,, volume 24 of Courant Lecture Notes, (2013).   Google Scholar

[40]

A. Viamontes Esquivel and M. Rosvall, Compression of flow can reveal overlapping-module organization in networks,, Phys. Rev. X, 1 (2011).  doi: 10.1103/PhysRevX.1.021025.  Google Scholar

[41]

R. K. P. Zia and B. Schmittmann, Probability currents as principal characteristics in the statistical mechanics of non-equilibrium steady states,, Journal of Statistical Mechanics-theory and Experiment, 2007 (2007).  doi: 10.1088/1742-5468/2007/07/P07012.  Google Scholar

[1]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[2]

Juan Manuel Pastor, Javier García-Algarra, José M. Iriondo, José J. Ramasco, Javier Galeano. Dragging in mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 37-52. doi: 10.3934/nhm.2015.10.37
[3]

Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065
[4]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[5]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[6]

Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299
[7]

Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53
[8]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[9]

Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021013
[10]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[11]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200
[12]

Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221

 Impact Factor: 

Tools

Metrics

  • PDF downloads (64)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences