Modularity of directed networks: Cycle decomposition approach

Previous Article
Preface: Special issue on the occasion of the 4th International Workshop on Set-Oriented Numerics (SON 13, Dresden, 2013)
JCD Home
This Issue
Next Article
Symmetry exploiting control of hybrid mechanical systems

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

Abstract
Related Papers

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.
[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.
[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.
[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.
[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.
[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.
[7]	D. Cvetkovic, P. Rowlinson and S. Simic, Spectral Generalizations of Line Graphs,, Cambridge University Press, (2004). doi: 10.1017/CBO9780511751752.
[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.
[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.
[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.
[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.
[12]	S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75. doi: 10.1016/j.physrep.2009.11.002.
[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.
[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.
[15]	S. L. Kalpazidou, Cycle Representations of Markov Processes,, Springer, (2006).
[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.
[17]	R. Lambiotte, J. C. Delvenne and M. Barahona, Laplacian dynamics and multiscale modular structure in networks,, ArXiv., ().
[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.
[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.
[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.
[21]	T. Li, J. Liu and W. E, Probabilistic framework for network partition,, Phys. Rev. E, 80 (2009). doi: 10.1103/PhysRevE.80.026106.
[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.
[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.
[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.
[25]	M. E. J. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167. doi: 10.1137/S003614450342480.
[26]	M. E. J. Newman, Fast algorithm for detecting community structure in networks,, Phys. Rev. E, 69 (2004). doi: 10.1103/PhysRevE.69.066133.
[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.
[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.
[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.
[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.
[31]	M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, Notices of the American Mathematical Society, 56 (2009), 1082.
[32]	H. Risken, The Fokker-Planck Equation,, Springer, (1996).
[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.
[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.
[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.
[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.
[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.
[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.
[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).
[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.
[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.

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.
[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.
[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.
[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.
[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.
[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.
[7]	D. Cvetkovic, P. Rowlinson and S. Simic, Spectral Generalizations of Line Graphs,, Cambridge University Press, (2004). doi: 10.1017/CBO9780511751752.
[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.
[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.
[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.
[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.
[12]	S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75. doi: 10.1016/j.physrep.2009.11.002.
[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.
[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.
[15]	S. L. Kalpazidou, Cycle Representations of Markov Processes,, Springer, (2006).
[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.
[17]	R. Lambiotte, J. C. Delvenne and M. Barahona, Laplacian dynamics and multiscale modular structure in networks,, ArXiv., ().
[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.
[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.
[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.
[21]	T. Li, J. Liu and W. E, Probabilistic framework for network partition,, Phys. Rev. E, 80 (2009). doi: 10.1103/PhysRevE.80.026106.
[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.
[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.
[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.
[25]	M. E. J. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167. doi: 10.1137/S003614450342480.
[26]	M. E. J. Newman, Fast algorithm for detecting community structure in networks,, Phys. Rev. E, 69 (2004). doi: 10.1103/PhysRevE.69.066133.
[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.
[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.
[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.
[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.
[31]	M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, Notices of the American Mathematical Society, 56 (2009), 1082.
[32]	H. Risken, The Fokker-Planck Equation,, Springer, (1996).
[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.
[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.
[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.
[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.
[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.
[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.
[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).
[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.
[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.

[1]	Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593
[2]	Joseph D. Skufca, Erik M. Bollt. Communication and Synchronization in Disconnected Networks with Dynamic Topology: Moving Neighborhood Networks. Mathematical Biosciences & Engineering, 2004, 1 (2) : 347-359. doi: 10.3934/mbe.2004.1.347
[3]	Michael Gekhtman, Michael Shapiro, Serge Tabachnikov, Alek Vainshtein. Higher pentagram maps, weighted directed networks, and cluster dynamics. Electronic Research Announcements, 2012, 19: 1-17. doi: 10.3934/era.2012.19.1
[4]	Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks & Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373
[5]	Zari Dzalilov, Iradj Ouveysi, Tolga Bektaş. An extended lifetime measure for telecommunications networks: Improvements and implementations. Journal of Industrial & Management Optimization, 2012, 8 (3) : 639-649. doi: 10.3934/jimo.2012.8.639
[6]	Leah Anderson, Thomas Pumir, Dimitrios Triantafyllos, Alexandre M. Bayen. Stability and implementation of a cycle-based max pressure controller for signalized traffic networks. Networks & Heterogeneous Media, 2018, 13 (2) : 241-260. doi: 10.3934/nhm.2018011
[7]	Chun-Gil Park. Stability of a linear functional equation in Banach modules. Conference Publications, 2003, 2003 (Special) : 694-700. doi: 10.3934/proc.2003.2003.694
[8]	Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[9]	Mauro Garavello, Paola Goatin. The Cauchy problem at a node with buffer. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 1915-1938. doi: 10.3934/dcds.2012.32.1915
[10]	Matthias Kunzer. A one-box-shift morphism between Specht modules. Electronic Research Announcements, 2000, 6: 90-94.
[11]	Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627
[12]	Dmitry N. Kozlov. Cobounding odd cycle colorings. Electronic Research Announcements, 2006, 12: 53-55.
[13]	Luca Schenato, Sandro Zampieri. On rendezvous control with randomly switching communication graphs. Networks & Heterogeneous Media, 2007, 2 (4) : 627-646. doi: 10.3934/nhm.2007.2.627
[14]	Lizhong Peng, Shujun Dang, Bojin Zhuang. Localization operator and digital communication capacity of channel. Communications on Pure & Applied Analysis, 2007, 6 (3) : 819-827. doi: 10.3934/cpaa.2007.6.819
[15]	Jesus R. Artalejo, Tuan Phung-Duc. Markovian retrial queues with two way communication. Journal of Industrial & Management Optimization, 2012, 8 (4) : 781-806. doi: 10.3934/jimo.2012.8.781
[16]	Jiaquan Zhan, Fanyong Meng. Cores and optimal fuzzy communication structures of fuzzy games. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1187-1198. doi: 10.3934/dcdss.2019082
[17]	Rui Dilão, András Volford. Excitability in a model with a saddle-node homoclinic bifurcation. Discrete & Continuous Dynamical Systems - B, 2004, 4 (2) : 419-434. doi: 10.3934/dcdsb.2004.4.419
[18]	Ping Liu, Junping Shi, Yuwen Wang. A double saddle-node bifurcation theorem. Communications on Pure & Applied Analysis, 2013, 12 (6) : 2923-2933. doi: 10.3934/cpaa.2013.12.2923
[19]	Claudio Qureshi, Daniel Panario, Rodrigo Martins. Cycle structure of iterating Redei functions. Advances in Mathematics of Communications, 2017, 11 (2) : 397-407. doi: 10.3934/amc.2017034
[20]	Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems & Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035

Impact Factor:

American Institute of Mathematical Sciences