- Previous Article
- JCD Home
- This Issue
-
Next Article
On the consistency of ensemble transform filter formulations
Modularity revisited: A novel dynamics-based concept for decomposing complex networks
1. | Freie Universität Berlin, Department of Mathematics and Computer Science, Arnimallee 6, 14195 Berlin, Germany, Germany, Germany, Germany, Germany |
References:
[1] |
A. H. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators,, SIAM J. Sci. Comput., 33 (2011), 488.
doi: 10.1137/100788860. |
[2] |
R. Albert and A. Barabasi, Statistical mechanics of complex networks,, Rev. Mod. Phys., 74 (2002), 47.
doi: 10.1103/RevModPhys.74.47. |
[3] |
D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs,, University of California, (2002). Google Scholar |
[4] |
M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation,, Neural Computation, 6 (2003), 1373.
doi: 10.1162/089976603321780317. |
[5] |
G. Cho and C. Meyer, Aggregation/Disaggregation Methods for Nearly Uncoupled MArkov Chains,, Technical Report NCSU no. 041600-0400, (0416), 041600. Google Scholar |
[6] |
M. Dellnitz and R. Preis, Congestion and almost invariant sets in dynamical systems,, in Proceedings of the 2nd international conference on Symbolic and numerical scientific computation, (2003), 183.
doi: 10.1007/3-540-45084-X_8. |
[7] |
P. Deuflhard, W. Huisinga, A. Fischer and C. Schuette, Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains,, Linear Algebra and its Applications, 315 (2000), 39.
doi: 10.1016/S0024-3795(00)00095-1. |
[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. Schuette, Random walks on complex modular networks,, Journal of Numerical Analysis, (). Google Scholar |
[10] |
N. Djurdjevac, M. Sarich and C. Schuette, On Markov state models for metastable processes,, Proceeding of the ICM 2010, (2010), 3105.
doi: 10.1142/9789814324359_0182. |
[11] |
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. |
[12] |
P. Doyle and J. Snell, Random Walks and Electric Networks,, Carus Mathematical Monographs, (1984).
|
[13] |
W. E and E. Vanden-Eijnden, Transition-path theory and path-finding algorithms for the study of rare events,, Annual Review of Physical Chemistry, 61 (2010), 391.
doi: 10.1146/annurev.physchem.040808.090412. |
[14] |
S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.
doi: 10.1016/j.physrep.2009.11.002. |
[15] |
P. Garrido and J. Marro (eds.), Exploring Complex Graphs by Random Walks, vol. 661,, American Institute of Physics, (2002). Google Scholar |
[16] |
M. Girvan and M. E. J. Newman, Community structure in social and biological networks,, Proceedings of the National Academy of Sciences, 99 (2002), 7821.
doi: 10.1073/pnas.122653799. |
[17] |
W. Huisinga and B. Schmidt, Metastability and dominant eigenvalues of transfer operators,, in New Algorithms for Macromolecular Simulation (eds. B. Leimkuhler, (2006), 167.
doi: 10.1007/3-540-31618-3_11. |
[18] |
H. Jeong, B. Tombor, R. Albert, Z. Oltvai and A. Barabasi, The large-scale organization of metabolic networks,, Nature, 407 (2000), 651. Google Scholar |
[19] |
S. Lafon and A. Lee, Diffusion maps and coarse-graining: A unified framework for dimensionality reduction,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (2006), 1393.
doi: 10.1109/TPAMI.2006.184. |
[20] |
T. Li, W. E and E. V. Eijnden, Optimal partition and effective dynamics of complex networks,, Proc. Nat. Acad. Sci., 105 (). Google Scholar |
[21] |
T. Li, J. Liu and W. E, A probabilistic framework for network partition,, Phys. Rev. E, 80 (2009).
doi: 10.1103/PhysRevE.80.026106. |
[22] |
L. Lovasz, Random walks on graphs: A survey.,, Bolyayi Society Mathematical Studies, 2 (1996), 353.
|
[23] |
U. Luxburg, A tutorial on spectral clustering,, Statistics and Computing, 17 (2007), 395.
doi: 10.1007/s11222-007-9033-z. |
[24] |
I. Marek and P. Mayer, Aggregation/disaggregation iterative methods applied to Leontev and Markov chain models,, Appl. Math., 47 (2002), 139.
doi: 10.1023/A:1021785102298. |
[25] |
R. Mattingly, A revised stochastic complementation algorithm for nearly completely decomposable Markov chains,, ORSA Journal on Computing, 7 (1995), 117.
doi: 10.1287/ijoc.7.2.117. |
[26] |
E. Meerbach, C. Schuette and A. Fischer, Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains,, Lin. Alg. Appl., 398 (2005), 141.
doi: 10.1016/j.laa.2004.10.018. |
[27] |
M. Meila and J. Shi, A random walks view of spectral segmentation,, AI and Statistics (AISTATS)., (). Google Scholar |
[28] |
P. Metzner, C. Schuette and E. Vanden-Eijnden, Transition path theory for Markov jump processes,, Multiscale Modeling and Simulation, 7 (2009), 1192.
doi: 10.1137/070699500. |
[29] |
C. D. Meyer, Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems,, SIAM Rev, 31 (1989), 240.
doi: 10.1137/1031050. |
[30] |
M. C. V. Nascimento and A. C. P. L. F. De Carvalho, Spectral methods for graph clustering: A survey,, European Journal Of Operational Research, 211 (2011), 221.
doi: 10.1016/j.ejor.2010.08.012. |
[31] |
M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices,, PHYS.REV.E, 74 (2006).
doi: 10.1103/PhysRevE.74.036104. |
[32] |
M. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167.
doi: 10.1137/S003614450342480. |
[33] |
M. Newman, A. Barabasi and D. Watts, The Structure and Dynamics of Networks,, Princeton Univ Press, (2006).
|
[34] |
M. Newman and M. Girvan, Finding and evaluating community structure in networks,, Phys. Rev. E, 69 (2004).
doi: 10.1103/PhysRevE.69.026113. |
[35] |
V. Nicosia, G. Mangioni, V. Carchiolo and M. Malgeri, Extending the definition of modularity to directed graphs with overlapping communities,, Journal of Statistical Mechanics: Theory and Experiment, 2009 (2009).
doi: 10.1088/1742-5468/2009/03/P03024. |
[36] |
J. Noh and H. Rieger, Random walks on complex networks,, Phys. Rev. Lett., 92 (2004).
doi: 10.1103/PhysRevLett.92.118701. |
[37] |
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. |
[38] |
M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, World Wide Web Internet And Web Information Systems, 56 (2009), 1082.
|
[39] |
J. Reichardt and S. Bornholdt, Statistical mechanics of community detection,, PHYS.REV.E, 74 (2006).
doi: 10.1103/PhysRevE.74.016110. |
[40] |
M. Rosvall and C. Bergstrom, Maps of random walks on complex networks reveal community structure,, Proc Natl Acad Sci, 105 (2008), 1118.
doi: 10.1073/pnas.0706851105. |
[41] |
F. Santo, Community detection in graphs,, Physics Reports, 486 (2010), 75.
doi: 10.1016/j.physrep.2009.11.002. |
[42] |
M. Sarich and C. Schuette, Approximating selected non-dominant timescales by markov state models,, Comm Math Sci., 10 (2012), 1001.
doi: 10.4310/CMS.2012.v10.n3.a14. |
[43] |
M. Sarich, C. Schuette and E. Vanden-Eijnden, Optimal fuzzy aggregation of networks,, Multiscale Modeling and Simulation, 8 (2010), 1535.
doi: 10.1137/090758519. |
[44] |
M. Sarich, Projected Transfer Operators,, PhD thesis, (2011). Google Scholar |
[45] |
C. Schuette and W. Huisinga, Biomolecular conformations can be identified as metastable sets of molecular dynamics,, in Handbook of Numerical Analysis, X (2003), 699.
|
[46] |
C. Schuette, F. Noe, J. Lu, M. Sarich and E. Vanden-Eijnden, State models based on milestoning,, J. Chem. Phys, 134 (2011).
doi: 10.1063/1.3590108. |
[47] |
S. Van Dongen, Graph Clustering by Flow Simulation,, PhD thesis, (2000). Google Scholar |
show all references
References:
[1] |
A. H. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators,, SIAM J. Sci. Comput., 33 (2011), 488.
doi: 10.1137/100788860. |
[2] |
R. Albert and A. Barabasi, Statistical mechanics of complex networks,, Rev. Mod. Phys., 74 (2002), 47.
doi: 10.1103/RevModPhys.74.47. |
[3] |
D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs,, University of California, (2002). Google Scholar |
[4] |
M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation,, Neural Computation, 6 (2003), 1373.
doi: 10.1162/089976603321780317. |
[5] |
G. Cho and C. Meyer, Aggregation/Disaggregation Methods for Nearly Uncoupled MArkov Chains,, Technical Report NCSU no. 041600-0400, (0416), 041600. Google Scholar |
[6] |
M. Dellnitz and R. Preis, Congestion and almost invariant sets in dynamical systems,, in Proceedings of the 2nd international conference on Symbolic and numerical scientific computation, (2003), 183.
doi: 10.1007/3-540-45084-X_8. |
[7] |
P. Deuflhard, W. Huisinga, A. Fischer and C. Schuette, Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains,, Linear Algebra and its Applications, 315 (2000), 39.
doi: 10.1016/S0024-3795(00)00095-1. |
[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. Schuette, Random walks on complex modular networks,, Journal of Numerical Analysis, (). Google Scholar |
[10] |
N. Djurdjevac, M. Sarich and C. Schuette, On Markov state models for metastable processes,, Proceeding of the ICM 2010, (2010), 3105.
doi: 10.1142/9789814324359_0182. |
[11] |
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. |
[12] |
P. Doyle and J. Snell, Random Walks and Electric Networks,, Carus Mathematical Monographs, (1984).
|
[13] |
W. E and E. Vanden-Eijnden, Transition-path theory and path-finding algorithms for the study of rare events,, Annual Review of Physical Chemistry, 61 (2010), 391.
doi: 10.1146/annurev.physchem.040808.090412. |
[14] |
S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.
doi: 10.1016/j.physrep.2009.11.002. |
[15] |
P. Garrido and J. Marro (eds.), Exploring Complex Graphs by Random Walks, vol. 661,, American Institute of Physics, (2002). Google Scholar |
[16] |
M. Girvan and M. E. J. Newman, Community structure in social and biological networks,, Proceedings of the National Academy of Sciences, 99 (2002), 7821.
doi: 10.1073/pnas.122653799. |
[17] |
W. Huisinga and B. Schmidt, Metastability and dominant eigenvalues of transfer operators,, in New Algorithms for Macromolecular Simulation (eds. B. Leimkuhler, (2006), 167.
doi: 10.1007/3-540-31618-3_11. |
[18] |
H. Jeong, B. Tombor, R. Albert, Z. Oltvai and A. Barabasi, The large-scale organization of metabolic networks,, Nature, 407 (2000), 651. Google Scholar |
[19] |
S. Lafon and A. Lee, Diffusion maps and coarse-graining: A unified framework for dimensionality reduction,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (2006), 1393.
doi: 10.1109/TPAMI.2006.184. |
[20] |
T. Li, W. E and E. V. Eijnden, Optimal partition and effective dynamics of complex networks,, Proc. Nat. Acad. Sci., 105 (). Google Scholar |
[21] |
T. Li, J. Liu and W. E, A probabilistic framework for network partition,, Phys. Rev. E, 80 (2009).
doi: 10.1103/PhysRevE.80.026106. |
[22] |
L. Lovasz, Random walks on graphs: A survey.,, Bolyayi Society Mathematical Studies, 2 (1996), 353.
|
[23] |
U. Luxburg, A tutorial on spectral clustering,, Statistics and Computing, 17 (2007), 395.
doi: 10.1007/s11222-007-9033-z. |
[24] |
I. Marek and P. Mayer, Aggregation/disaggregation iterative methods applied to Leontev and Markov chain models,, Appl. Math., 47 (2002), 139.
doi: 10.1023/A:1021785102298. |
[25] |
R. Mattingly, A revised stochastic complementation algorithm for nearly completely decomposable Markov chains,, ORSA Journal on Computing, 7 (1995), 117.
doi: 10.1287/ijoc.7.2.117. |
[26] |
E. Meerbach, C. Schuette and A. Fischer, Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains,, Lin. Alg. Appl., 398 (2005), 141.
doi: 10.1016/j.laa.2004.10.018. |
[27] |
M. Meila and J. Shi, A random walks view of spectral segmentation,, AI and Statistics (AISTATS)., (). Google Scholar |
[28] |
P. Metzner, C. Schuette and E. Vanden-Eijnden, Transition path theory for Markov jump processes,, Multiscale Modeling and Simulation, 7 (2009), 1192.
doi: 10.1137/070699500. |
[29] |
C. D. Meyer, Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems,, SIAM Rev, 31 (1989), 240.
doi: 10.1137/1031050. |
[30] |
M. C. V. Nascimento and A. C. P. L. F. De Carvalho, Spectral methods for graph clustering: A survey,, European Journal Of Operational Research, 211 (2011), 221.
doi: 10.1016/j.ejor.2010.08.012. |
[31] |
M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices,, PHYS.REV.E, 74 (2006).
doi: 10.1103/PhysRevE.74.036104. |
[32] |
M. Newman, The structure and function of complex networks,, SIAM Review, 45 (2003), 167.
doi: 10.1137/S003614450342480. |
[33] |
M. Newman, A. Barabasi and D. Watts, The Structure and Dynamics of Networks,, Princeton Univ Press, (2006).
|
[34] |
M. Newman and M. Girvan, Finding and evaluating community structure in networks,, Phys. Rev. E, 69 (2004).
doi: 10.1103/PhysRevE.69.026113. |
[35] |
V. Nicosia, G. Mangioni, V. Carchiolo and M. Malgeri, Extending the definition of modularity to directed graphs with overlapping communities,, Journal of Statistical Mechanics: Theory and Experiment, 2009 (2009).
doi: 10.1088/1742-5468/2009/03/P03024. |
[36] |
J. Noh and H. Rieger, Random walks on complex networks,, Phys. Rev. Lett., 92 (2004).
doi: 10.1103/PhysRevLett.92.118701. |
[37] |
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. |
[38] |
M. A. Porter, J.-P. Onnela and P. J. Mucha, Communities in networks,, World Wide Web Internet And Web Information Systems, 56 (2009), 1082.
|
[39] |
J. Reichardt and S. Bornholdt, Statistical mechanics of community detection,, PHYS.REV.E, 74 (2006).
doi: 10.1103/PhysRevE.74.016110. |
[40] |
M. Rosvall and C. Bergstrom, Maps of random walks on complex networks reveal community structure,, Proc Natl Acad Sci, 105 (2008), 1118.
doi: 10.1073/pnas.0706851105. |
[41] |
F. Santo, Community detection in graphs,, Physics Reports, 486 (2010), 75.
doi: 10.1016/j.physrep.2009.11.002. |
[42] |
M. Sarich and C. Schuette, Approximating selected non-dominant timescales by markov state models,, Comm Math Sci., 10 (2012), 1001.
doi: 10.4310/CMS.2012.v10.n3.a14. |
[43] |
M. Sarich, C. Schuette and E. Vanden-Eijnden, Optimal fuzzy aggregation of networks,, Multiscale Modeling and Simulation, 8 (2010), 1535.
doi: 10.1137/090758519. |
[44] |
M. Sarich, Projected Transfer Operators,, PhD thesis, (2011). Google Scholar |
[45] |
C. Schuette and W. Huisinga, Biomolecular conformations can be identified as metastable sets of molecular dynamics,, in Handbook of Numerical Analysis, X (2003), 699.
|
[46] |
C. Schuette, F. Noe, J. Lu, M. Sarich and E. Vanden-Eijnden, State models based on milestoning,, J. Chem. Phys, 134 (2011).
doi: 10.1063/1.3590108. |
[47] |
S. Van Dongen, Graph Clustering by Flow Simulation,, PhD thesis, (2000). Google Scholar |
[1] |
Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020390 |
[2] |
Guillaume Cantin, M. A. Aziz-Alaoui. Dimension estimate of attractors for complex networks of reaction-diffusion systems applied to an ecological model. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020283 |
[3] |
Xiaoxian Tang, Jie Wang. Bistability of sequestration networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1337-1357. doi: 10.3934/dcdsb.2020165 |
[4] |
Timothy Chumley, Renato Feres. Entropy production in random billiards. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1319-1346. doi: 10.3934/dcds.2020319 |
[5] |
Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020406 |
[6] |
D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346 |
[7] |
Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344 |
[8] |
Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020 doi: 10.3934/jcd.2021006 |
[9] |
Pedro Aceves-Sanchez, Benjamin Aymard, Diane Peurichard, Pol Kennel, Anne Lorsignol, Franck Plouraboué, Louis Casteilla, Pierre Degond. A new model for the emergence of blood capillary networks. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2021001 |
[10] |
Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021001 |
[11] |
Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, , () : -. doi: 10.3934/era.2021008 |
[12] |
Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020377 |
[13] |
Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310 |
[14] |
Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021016 |
[15] |
Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123 |
[16] |
Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329 |
[17] |
Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045 |
[18] |
Susmita Sadhu. Complex oscillatory patterns near singular Hopf bifurcation in a two-timescale ecosystem. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020342 |
[19] |
Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164 |
[20] |
Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]