2014, 1(1): 191-212. doi: 10.3934/jcd.2014.1.191

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

Received  December 2011 Revised  July 2012 Published  April 2014

Finding modules (or clusters) in large, complex networks is a challenging task, in particular if one is not interested in a full decomposition of the whole network into modules. We consider modular networks that also contain nodes that do not belong to one of modules but to several or to none at all. A new method for analyzing such networks is presented. It is based on spectral analysis of random walks on modular networks. In contrast to other spectral clustering approaches, we use different transition rules of the random walk. This leads to much more prominent gaps in the spectrum of the adapted random walk and allows for easy identification of the network's modular structure, and also identifying the nodes belonging to these modules. We also give a characterization of that set of nodes that do not belong to any module, which we call transition region. Finally, by analyzing the transition region, we describe an algorithm that identifies so called hub-nodes inside the transition region that are important connections between modules or between a module and the rest of the network. The resulting algorithms scale linearly with network size (if the network connectivity is sparse) and thus can also be applied to very large networks.
Citation: Marco Sarich, Natasa Djurdjevac Conrad, Sharon Bruckner, Tim O. F. Conrad, Christof Schütte. Modularity revisited: A novel dynamics-based concept for decomposing complex networks. Journal of Computational Dynamics, 2014, 1 (1) : 191-212. doi: 10.3934/jcd.2014.1.191
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).

[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.

[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, ().

[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).

[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.

[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 ().

[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)., ().

[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).

[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).

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).

[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.

[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, ().

[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).

[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.

[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 ().

[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)., ().

[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).

[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).

[1]

Brendan Weickert. Infinite-dimensional complex dynamics: A quantum random walk. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 517-524. doi: 10.3934/dcds.2001.7.517

[2]

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

[3]

Wafa Hamrouni, Ali Abdennadher. Random walk's models for fractional diffusion equation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (8) : 2509-2530. doi: 10.3934/dcdsb.2016058

[4]

Edward Belbruno. Random walk in the three-body problem and applications. Discrete & Continuous Dynamical Systems - S, 2008, 1 (4) : 519-540. doi: 10.3934/dcdss.2008.1.519

[5]

Kumiko Hattori, Noriaki Ogo, Takafumi Otsuka. A family of self-avoiding random walks interpolating the loop-erased random walk and a self-avoiding walk on the Sierpiński gasket. Discrete & Continuous Dynamical Systems - S, 2017, 10 (2) : 289-311. doi: 10.3934/dcdss.2017014

[6]

Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295

[7]

E. Kapsza, Gy. Károlyi, S. Kovács, G. Domokos. Regular and random patterns in complex bifurcation diagrams. Discrete & Continuous Dynamical Systems - B, 2003, 3 (4) : 519-540. doi: 10.3934/dcdsb.2003.3.519

[8]

Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393

[9]

Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks. Networks & Heterogeneous Media, 2012, 7 (3) : 441-461. doi: 10.3934/nhm.2012.7.441

[10]

F. S. Vannucchi, S. Boccaletti. Chaotic spreading of epidemics in complex networks of excitable units. Mathematical Biosciences & Engineering, 2004, 1 (1) : 49-55. doi: 10.3934/mbe.2004.1.49

[11]

Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292

[12]

Xiwei Liu, Tianping Chen, Wenlian Lu. Cluster synchronization for linearly coupled complex networks. Journal of Industrial & Management Optimization, 2011, 7 (1) : 87-101. doi: 10.3934/jimo.2011.7.87

[13]

Simone Göttlich, Stephan Martin, Thorsten Sickenberger. Time-continuous production networks with random breakdowns. Networks & Heterogeneous Media, 2011, 6 (4) : 695-714. doi: 10.3934/nhm.2011.6.695

[14]

Massimiliano Zanin, Ernestina Menasalvas, Pedro A. C. Sousa, Stefano Boccaletti. Preprocessing and analyzing genetic data with complex networks: An application to Obstructive Nephropathy. Networks & Heterogeneous Media, 2012, 7 (3) : 473-481. doi: 10.3934/nhm.2012.7.473

[15]

Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic & Related Models, 2017, 10 (1) : 1-32. doi: 10.3934/krm.2017001

[16]

Jin-Liang Wang, Zhi-Chun Yang, Tingwen Huang, Mingqing Xiao. Local and global exponential synchronization of complex delayed dynamical networks with general topology. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 393-408. doi: 10.3934/dcdsb.2011.16.393

[17]

Regino Criado, Rosa M. Benito, Miguel Romance, Juan C. Losada. Preface: Mesoscales and evolution in complex networks: Applications and related topics. Networks & Heterogeneous Media, 2012, 7 (3) : i-iii. doi: 10.3934/nhm.2012.7.3i

[18]

Raoul-Martin Memmesheimer, Marc Timme. Stable and unstable periodic orbits in complex networks of spiking neurons with delays. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1555-1588. doi: 10.3934/dcds.2010.28.1555

[19]

Suoqin Jin, Fang-Xiang Wu, Xiufen Zou. Domain control of nonlinear networked systems and applications to complex disease networks. Discrete & Continuous Dynamical Systems - B, 2017, 22 (6) : 2169-2206. doi: 10.3934/dcdsb.2017091

[20]

Junyuan Yang, Yuming Chen, Jiming Liu. Stability analysis of a two-strain epidemic model on complex networks with latency. Discrete & Continuous Dynamical Systems - B, 2016, 21 (8) : 2851-2866. doi: 10.3934/dcdsb.2016076

[Back to Top]