Element contents
Modularity and Dynamics on Complex Networks
Published online by Cambridge University Press: 21 December 2021
Summary
Complex networks are typically not homogeneous, as they tend to display an array of structures at different scales. A feature that has attracted a lot of research is their modular organisation, i.e., networks may often be considered as being composed of certain building blocks, or modules. In this Element, the authors discuss a number of ways in which this idea of modularity can be conceptualised, focusing specifically on the interplay between modular network structure and dynamics taking place on a network. They discuss, in particular, how modular structure and symmetries may impact on network dynamics and, vice versa, how observations of such dynamics may be used to infer the modular structure. They also revisit several other notions of modularity that have been proposed for complex networks and show how these can be related to and interpreted from the point of view of dynamical processes on networks.
- Type
- Element
- Information
- Online ISBN: 9781108774116Publisher: Cambridge University PressPrint publication: 03 February 2022
References
Abbe, E. (2017). Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18 (1), 6446–6531.Google Scholar
Abrams, D. M., Mirollo, R., Strogatz, S. H., & Wiley, D. A. (2008). Solvable model for chimera states of coupled oscillators. Physical Review Letters, 101 (8),084103.Google Scholar
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466 (7307), 761–764.Google Scholar
Almquist, Z. W. (2012, October). Random errors in egocentric networks. Social Networks, 34(4), 493–505. doi: https://doi.org/10.1016/j.socnet.2012.03.002Google Scholar
Alpert, C. J., & Kahng, A. B. (1995). Recent directions in netlist partitioning: a survey. Integration, 19(1–2), 1–81.Google Scholar
Altafini, C. (2012). Dynamics of opinion forming in structurally balanced social networks. PloS One, 7(6), e38135.Google Scholar
Altafini, C. (2013, April). Consensus problems on networks with antagonistic interactions. IEEE Transactions on Automatic Control, 58(4), 935–946. doi: https://doi.org/10.1109/TAC.2012.2224251Google Scholar
Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008). Synchronization in complex networks. Physics Reports, 469 (3), 93–153.Google Scholar
Arenas, A., Díaz-Guilera, A., & Pérez-Vicente, C. J. (2006). Synchronization reveals topological scales in complex networks. Physical Review Letters, 96 (11),114102.Google Scholar
Asllani, M., Lambiotte, R., & Carletti, T. (2018). Structure and dynamical behavior of non-normal networks. Science Advances, 4(12),eaau9403.Google Scholar
Avella-Medina, M., Parise, F., Schaub, M. T., & Segarra, S. (2020). Centrality measures for graphons: accounting for uncertainty in networks. IEEE Transactions on Network Science and Engineering, 7 (1), 520–537. doi: https://doi.org/10.1109/TNSE.2018.2884235Google Scholar
Aynaud, T., Blondel, V. D., Guillaume, J. L., & Lambiotte, R. (2013). Multilevel local optimization of modularity. In: Bichot, C.-E., Siarry, P. (eds.), Graph Partitioning, (pp. 315–345). John Wiley and Sons, Hoboken, NJ.Google Scholar
Banisch, R., & Conrad, N. D. (2015). Cycle-flow–based module detection in directed recurrence networks. EPL (Europhysics Letters), 108 (6), 68008.Google Scholar
Barabási, A.-L., et al. (2016). Network science. Cambridge University Press, Cambridge, UK.Google Scholar
Barbarossa, S., & Sardellitti, S. (2020). Topological signal processing: making sense of data building on multiway relations. IEEE Signal Processing Magazine, 37 (6), 174–183.Google Scholar
Battiston, F., Cencetti, G., Iacopini, I. et al. (2020). Networks beyond pairwise interactions: structure and dynamics. Physics Reports, 874, 1–92.Google Scholar
Belkin, M., & Niyogi, P. (2001). Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems, 14, 585–591.Google Scholar
Bhatia, R. (2013). Matrix analysis (vol. 169). Springer Science & Business Media, London.Google Scholar
Blondel, V. D., Gajardo, A., Heymans, M., Senellart, P., & Van Dooren, P. (2004). A measure of similarity between graph vertices: applications to synonym extraction and web searching. SIAM Review, 46 (4), 647–666.Google Scholar
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008 (10),P10008.Google Scholar
Bohlin, L., Edler, D., Lancichinetti, A., & Rosvall, M. (2014). Community detection and visualization of networks with the map equation framework. In: Ding, Y., Rousseau, R., & Wolfram, D. (eds.), Measuring scholarly impact, (pp. 3–34). Springer, New York.Google Scholar
Borgatti, S. P., Carley, K. M., & Krackhardt, D. (2006). On the robustness of centrality measures under conditions of imperfect data. Social Networks, 28(2), 124–136. doi: https://doi.org/10.1016/j.socnet.2005.05.001Google Scholar
Brandes, U. (2005). Network analysis: methodological foundations, (vol. 3418). Springer Science & Business Media, London.Google Scholar
Brandes, U., Delling, D., Gaertler, M. et al. (2007). On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2), 172–188.Google Scholar
Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.Google Scholar
Broido, A. D., & Clauset, A. (2019). Scale-free networks are rare. Nature Communications, 10 (1), 1–10.Google Scholar
Bui-Xuan, B.-M., & Jones, N. S. (2014). How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 470 (2170),20140224.Google Scholar
Bullo, F. (2019). Lectures on network systems. Kindle Direct Publishing. ISBN 978-1-986425-64-3.Google Scholar
Burt, R. S. (2004). Structural holes and good ideas. American Journal of Sociology, 110 (2), 349–399.Google Scholar
Cardoso, D. M., Delorme, C., & Rama, P. (2007). Laplacian eigenvectors and eigenvalues and almost equitable partitions. European Journal of Combinatorics, 28 (3), 665–673.Google Scholar
Carletti, T., Fanelli, D., & Lambiotte, R. (2020). Random walks and community detection in hypergraphs. arXiv preprint arXiv:2010.14355.Google Scholar
Cason, T. P. (2014). Role extraction in networks. (unpublished doctoral dissertation). Catholic University of Louvain.Google Scholar
Cavallari, S., Zheng, V. W., Cai, H., Chang, K. C.-C., & Cambria, E. (2017). Learning community embedding with community detection and node embedding on graphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, (pp. 377–386).Google Scholar
Chan, A., & Godsil, C. D. (1997). Symmetry and eigenvectors. In: Hahn, G., & Sabidussi, G. (eds.), Graph Symmetry, (pp. 75–106). Springer, New York.Google Scholar
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1996). The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6 (4), 312–340.Google Scholar
Chodrow, P. S., Veldt, N., & Benson, A. R. (2021). Hypergraph clustering: from blockmodels to modularity. arXiv preprint arXiv:2101.09611.Google Scholar
Chung, F., & Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6 (2), 125–145.Google Scholar
Chung, F. R. (1997). Spectral graph theory, (vol. 92). American Mathematical Society, Providence, RI.Google Scholar
Coifman, R. R., Lafon, S., Lee, A. B. et al. (2005). Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps. Proceedings of the National Academy of Sciences of the United States of America, 102 (21), 7426–7431.CrossRefGoogle ScholarPubMed
Conrad, N. D., Weber, M., & Schütte, C. (2016). Finding dominant structures of nonreversible Markov processes. Multiscale Modeling & Simulation, 14 (4), 1319–1340.Google Scholar
Cooper, K., & Barahona, M. (2010). Role-based similarity in directed networks. arXiv preprint arXiv:1012.2726.Google Scholar
Dasgupta, A., Hopcroft, J. E., & McSherry, F. (2004). Spectral analysis of random graphs with skewed degree distributions. In 45th Annual IEEE Symposium on Foundations of Computer Science, (pp. 602–610). doi: https://doi.org/10.1109/FOCS.2004.61.Google Scholar
De Domenico, M., Solé-Ribalta, A., Cozzo, E. et al. (2013). Mathematical formulation of multilayer networks. Physical Review X, 3 (4),041022.Google Scholar
Delvenne, J.-C., & Libert, A.-S. (2011). Centrality measures and thermodynamic formalism for complex networks. Physical Review E, 83(4), 046117.Google Scholar
Delvenne, J.-C., Schaub, M. T., Yaliraki, S. N., & Barahona, M. (2013). The stability of a graph partition: a dynamics-based framework for community detection. In A. Mukherjee, M. Choudhury, F. Peruani, N. Ganguly, & B. Mitra (eds.), Dynamics On and Of Complex Networks, Volume 2 (pp. 221–242). Springer, New York. doi: https://doi.org/10.1007/978-1-4614-6729-8_11CrossRefGoogle Scholar
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010). Stability of graph communities across time scales. Proceedings of the National Academy of Sciences, 107 (29),12755–12760. doi: https://doi.org/10.1073/pnas.0903215107Google Scholar
Derrida, B., & Flyvbjerg, H. (1986). Multivalley structure in Kauffman’s model: analogy with spin glasses. Journal of Physics A: Mathematical and General, 19 (16),L1003.Google Scholar
Devriendt, K. (2020). Effective resistance is more than distance: Laplacians, simplices and the Schur complement. arXiv preprint arXiv:2010.04521.Google Scholar
Devriendt, K. (2020). Effective resistance is more than distance: Laplacians, simplices and the Schur complement. arXiv preprint arXiv:2010.04521.Google Scholar
Doreian, P., Batagelj, V., & Ferligoj, A. (2020). Advances in Network Clustering and Blockmodeling. John Wiley & Hoboken, NJ.Google Scholar
Egerstedt, M., Martini, S., Cao, M., Camlibel, K., & Bicchi, A. (2012). Interacting with networks: how does structure relate to controllability in single-leader, consensus networks? Control Systems, IEEE, 32 (4),66–73. doi: https://doi.org/10.1109/MCS.2012.2195411Google Scholar
Eriksson, A., Edler, D., Rojas, A., & Rosvall, M. (2020). Mapping flows on hypergraphs. arXiv preprint arXiv:2101.00656.Google Scholar
Eriksson, A., Edler, D., Rojas, A., & Rosvall, M. (2021). Mapping flows on hypergraphs. arXiv preprint arXiv:2101.00656.Google Scholar
Estrada, E., & Hatano, N. (2008). Communicability in complex networks. Physical Review E, 77 (3),036111.Google Scholar
Everett, M. G., & Borgatti, S. P. (1994). Regular equivalence: general theory. Journal of Mathematical Sociology, 19 (1), 29–52.Google Scholar
Expert, P., Evans, T. S., Blondel, V. D., & Lambiotte, R. (2011). Uncovering space-independent communities in spatial networks. Proceedings of the National Academy of Sciences, 108 (19), 7663–7668.CrossRefGoogle ScholarPubMed
Faccin, M., Schaub, M. T., & Delvenne, J.-C. (2018). Entrograms and coarse graining of dynamics on complex networks. Journal of Complex Networks, 6 (5), 661–678.CrossRefGoogle Scholar
Faccin, M., Schaub, M. T., & Delvenne, J.-C. (2020). State aggregations in Markov chains and block models of networks. arXiv preprint arXiv:2005.00337.Google Scholar
Faqeeh, A., Osat, S., & Radicchi, F. (2018). Characterizing the analogy between hyperbolic embedding and community structure of complex networks. Physical Review Letters, 121(9), 098301.Google Scholar
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298–305.CrossRefGoogle Scholar
Fiedler, M. (2011). Matrices and Graphs in Geometry. Cambridge University Press, Cambridge, UK. doi: https://doi.org/10.1017/cbo9780511973611CrossRefGoogle Scholar
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3–5), 75–174. doi: https://doi.org/10.1016/j.physrep.2009.11.002Google Scholar
Fortunato, S., & Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1),36–41.Google Scholar
Fortunato, S., & Hric, D. (2016). Community detection in networks: a user guide. Physics Reports, 659, 1–44.CrossRefGoogle Scholar
Fosdick, B. K., Larremore, D. B., Nishimura, J., & Ugander, J. (2018). Configuring random graph models with fixed degree sequences. SIAM Review, 60 (2), 315–355.Google Scholar
Fouss, F., Saerens, M., & Shimbo, M. (2016). Algorithms and models for network data and link analysis. Cambridge University Press, Cambridge, UK.Google Scholar
Ghasemian, A., Hosseinmardi, H., & Clauset, A. (2019). Evaluating overfit and underfit in models of network community structure. IEEE Transactions on Knowledge and Data Engineering, 32(9), 1722–1735. doi: https://doi.org/10.1109/TKDE.2019.2911585.Google Scholar
Godsil, C., & Royle, G. F. (2013). Algebraic graph theory (vol. 207). Springer Science & Business Media, London.Google Scholar
Golub, G., & Van Loan, C. (2013). Matrix computations. 4th ed. Johns Hopkins. University Press, Baltimore, MD.Google Scholar
Golubitsky, M., & Stewart, I. (2006). Nonlinear dynamics of networks: the groupoid formalism. Bulletin of the American Mathematical Society, 43 (3), 305–364.CrossRefGoogle Scholar
Golubitsky, M., & Stewart, I. (2015). Recent advances in symmetric and network dynamics. Chaos: An Interdisciplinary Journal of Nonlinear Science, 25(9),097612.Google Scholar
Good, B. H., De Montjoye, Y.-A., & Clauset, A. (2010). Performance of modularity maximization in practical contexts. Physical Review E, 81 (4),046106.Google Scholar
Grohe, M., Kersting, K., Mladenov, M., & Selman, E. (2014). Dimension reduction via colour refinement. In European Symposium on Algorithms, (pp. 505–516). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_42Google Scholar
Grohe, M., & Schweitzer, P. (2020). The graph isomorphism problem. Communications of the ACM, 63 (11), 128–134.Google Scholar
Grover, A., & Leskovec, J. (2016). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (pp. 855–864).Google Scholar
Gvishiani, A. D., & Gurvich, V. A. (1987). Metric and ultrametric spaces of resistances. Uspekhi Matematicheskikh Nauk, 42 (6), 187–188.Google Scholar
Hage, P., Harary, F., & Harary, F. (1983). Structural models in anthropology. Cambridge Studies in Anthropology, Social. No. 46. Cambridge University Press, Cambridge, UK.Google Scholar
Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: first steps. Social Networks, 5 (2), 109–137.CrossRefGoogle Scholar
Holland, P. W., & Leinhardt, S. (1973). The structural implications of measurement error in sociometry. Journal of Mathematical Sociology, 3 (1), 85–111.Google Scholar
Karrer, B., & Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107. doi: https://doi.org/10.1103/PhysRevE.83.016107Google Scholar
Kivela, M., Arenas, A., Barthelemy, M. et al. (2014). Multilayer networks. Journal of Complex Networks, 2 (3),203–271. doi: https://doi.org/10.1093/comnet/cnu016Google Scholar
Klein, D. J., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12 (1), 81–95. doi: https://doi.org/10.1007%2Fbf01164627Google Scholar
Klimm, F., Jones, N. S., & Schaub, M. T. (2021). Modularity maximisation for graphons. arXiv preprint arXiv:2101.00503.Google Scholar
Kloumann, I. M., Ugander, J., & Kleinberg, J. (2017). Block models and personalized pagerank. Proceedings of the National Academy of Sciences, 114 (1), 33–38.Google Scholar
Komarek, A., Pavlik, J., & Sobeslav, V. (2015). Network visualization survey. In Computational Collective Intelligence, (pp. 275–284). Springer.CrossRefGoogle Scholar
Kondor, R., & Lafferty, J. (2002). Diffusion kernels on graphs and other discrete input spaces. In Proceedings of the ICML’02: Nineteenth International Joint Conference on Machine Learning, (pp. 315–322).Google Scholar
Kossinets, G. (2006). Effects of missing data in social networks. Social Networks, 28(3),247–268. Accessed 1 October 2020 from https://linkinghub.elsevier.com/retrieve/pii/S0378873305000511 doi: https://doi.org/10.1016/j.socnet.2005.07.002Google Scholar
Krzakala, F., Moore, C., Mossel, E. et al. (2013). Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110 (52), 20935–20940.Google Scholar
Kunegis, J., Schmidt, S., Lommatzsch, A. et al. (2010). Spectral analysis of signed graphs for clustering, prediction and visualization. In Proceedings of the 2010 SIAM International Conference on Data Mining (SDM) (vol. 10, pp. 559–570). Society for Industrial and Applied Mathematics.Google Scholar
Lafon, S., & Lee, A. (2006). Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 28(9), 1393–1403. doi: https://doi.org/10.1109/TPAMI.2006.184CrossRefGoogle ScholarPubMed
Lambiotte, R., Ausloos, M., & Holyst, J. (2007). Majority model on a network with communities. Physical Review E, 75 (3),030101.Google Scholar
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014). Random walks, Markov processes and the multiscale modular organization of complex networks. IEEE Transactions on Network Science and Engineering, 1(2), 76–90. doi: https://doi.org/10.1109/TNSE.2015.2391998Google Scholar
Lambiotte, R., & Rosvall, M. (2012). Ranking and clustering of nodes in networks with smart teleportation. Physical Review E, 85 (5),056107.Google Scholar
Lambiotte, R., Rosvall, M., & Scholtes, I. (2019). From networks to optimal higher-order models of complex systems. Nature Physics, 15(4), 313–320.Google Scholar
Langville, A. N., & Meyer, C. D. (2011). Google’s PageRank and beyond: the science of search engine rankings. Princeton University Press.Google Scholar
Le, C. M., Levina, E., & Vershynin, R. (2017). Concentration and regularization of random graphs. Random Structures & Algorithms, 51 (3), 538–561.Google Scholar
Lei, J., & Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43 (1), 215–237.CrossRefGoogle Scholar
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008). Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web (pp. 695–704).Google Scholar
Lorrain, F., & White, H. C. (1971). Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology, 1 (1), 49–80.Google Scholar
Malliaros, F. D., & Vazirgiannis, M. (2013). Clustering and community detection in directed networks: a survey. Physics Reports, 533 (4), 95–142.Google Scholar
Martin, T., Ball, B., & Newman, M. E. J. (2016). Structural inference for uncertain networks. Physical Review E, 93 (1),012306.Google Scholar
Masuda, N., & Lambiotte, R. (2020). A guide To Temporal Networks (vol. 6). World Scientific.Google Scholar
Masuda, N., Porter, M. A., & Lambiotte, R. (2017). Random walks and diffusion on networks. Physics Reports, 716, 1–58.Google Scholar
Mauroy, A., Susuki, Y., & Mezić, I. (2020). The Koopman Operator in Systems and Control. Springer.Google Scholar
McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: homophily in social networks. Annual Review of Sociology, 27(1), 415–444.Google Scholar
Meilǎ, M. (2007). Comparing clusterings – an information based distance. Journal of Multivariate Analysis, 98 (5), 873–895.Google Scholar
Menczer, F., Fortunato, S., & Davis, C. A. (2020). A First Course in Network Science. Cambridge University Press.Google Scholar
Meunier, D., Lambiotte, R., & Bullmore, E. T. (2010). Modular and hierarchically modular organization of brain networks. Frontiers in Neuroscience, 4, 200.CrossRefGoogle ScholarPubMed
Milo, R., Shen-Orr, S., Itzkovitz, S. et al. (2002). Network motifs: simple building blocks of complex networks. Science, 298 (5594), 824–827.Google Scholar
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science, 328 (5980), 876–878.Google Scholar
Newman, M. E., et al. (2003). Random graphs as models of networks. Handbook of Graphs and Networks, 1, 35–68.Google Scholar
Newman, M. E. J. (2013). Spectral methods for community detection and graph partitioning. Physical Review E, 88 (4),042822.Google Scholar
Newman, M. E. J. (2016). Community detection in networks: modularity optimization and maximum likelihood are equivalent. arXiv preprint arXiv:1606.02319.Google Scholar
Newman, M. E. J. (2018b). Network structure from rich but noisy data. Nature Physics, 14, 5.Google Scholar
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.Google Scholar
Nicosia, V., Mangioni, G., Carchiolo, V., & Malgeri, M. (2009). Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment, 2009(03),P03024.Google Scholar
O’Clery, N., Yuan, Y., Stan, G.-B., & Barahona, M. (2013). Observability and coarse graining of consensus dynamics through the external equitable partition. Physical Review E, 88(4). doi: https://doi.org/10.1103/physreve.88.042805Google Scholar
Park, J., & Newman, M. E. (2004). Statistical mechanics of networks. Physical Review E, 70 (6),066117.Google Scholar
Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015). Epidemic processes in complex networks. Reviews of Modern Physics, 87 (3), 925.Google Scholar
Pecora, L. M., Sorrentino, F., Hagerstrom, A. M., Murphy, T. E., & Roy, R. (2014). Cluster synchronization and isolated desynchronization in complex networks with symmetries. Nature Communications, 5, 4079.Google Scholar
Peel, L., Larremore, D. B., & Clauset, A. (2017). The ground truth about metadata and community detection in networks. Science Advances, 3 (5),e1602548.Google Scholar
Peixoto, T. P. (2018). Reconstructing networks with unknown and heterogeneous errors. Physical Review X, 8 (4),041011.CrossRefGoogle Scholar
Peixoto, T. P. (2019). Bayesian stochastic blockmodeling. Advances in Network Clustering and Blockmodeling, 289–332.Google Scholar
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 701–710).Google Scholar
Piccardi, C. (2011). Finding and testing network communities by lumped Markov chains. PLoS One, 6(11), e27028. doi: 10.1371/journal.pone.0027028Google Scholar
Pons, P., & Latapy, M. (2005). Computing communities in large networks using random walks. In: Yolum, P., Güngör, T., Gürgen, F., & Özturan, C. (eds.), International symposium on computer and information sciences, (pp. 284–293). Springer, Berlin, Heidelberg. doi: https://doi.org/10.1007/11569596_31Google Scholar
Porter, M., Onnela, J., & Mucha, P. (2009). Communities in networks. Notices of the AMS, 56 (9),1082–1097, 1164–1166.Google Scholar
Porter, M. A., & Gleeson, J. P. (2016). Dynamical systems on networks. Frontiers in Applied Dynamical Systems: Reviews and Tutorials, 4. doi: https://doi.org/10.1101/2021.01.21.427609Google Scholar
Proskurnikov, A. V., & Tempo, R. (2017). A tutorial on modeling and analysis of dynamic social networks. Part i. Annual Reviews in Control, 43, 65–79. doi: https://doi.org/10.1016/j.arcontrol.2017.03.002Google Scholar
Putra, P., Thompson, T. B., & Goriely, A. (2021). Braiding braak and braak: staging patterns and model selection in network neurodegeneration. bioRxiv. Accessed at www.biorxiv.org.Google Scholar
Read, K. E. (1954). Cultures of the Central Highlands, New Guinea. Southwestern Journal of Anthropology, 10 (1), 1–43.Google Scholar
Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74 (1),016110.Google Scholar
Reichardt, J., & White, D. R. (2007). Role models for complex networks. The European Physical Journal B, 60 (2), 217–224.Google Scholar
Rényi, A., et al. (1961). On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability Volume 1: contributions to the theory of statistics.Google Scholar
Rohe, K., Chatterjee, S., Yu, B., et al. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39 (4), 1878–1915.Google Scholar
Rombach, M. P., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2014). Core-periphery structure in networks. SIAM Journal on Applied Mathematics, 74 (1), 167–190.Google Scholar
Rossetti, G., & Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), 51(2), 1–37.Google Scholar
Rossi, R. A., Jin, D., Kim, S. et al. (2020). On proximity and structural role-based embeddings in networks: misconceptions, techniques, and applications. ACM Transactions on Knowledge Discovery from Data (TKDD), 14 (5), 1–37.Google Scholar
Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105 (4), 1118–1123.Google Scholar
Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D., & Lambiotte, R. (2014). Memory in network flows and its effects on spreading dynamics and community detection. Nature Communications, 5, 4630. doi: https://doi.org/10.1038/ncomms5630CrossRefGoogle ScholarPubMed
Ruggeri, N., & De Bacco, C. (2019, August). Sampling on networks: estimating eigenvector centrality on incomplete graphs. arXiv:1908.00388v1 [cs.SI].Google Scholar
Salnikov, V., Schaub, M. T., & Lambiotte, R. (2016). Using higher-order Markov models to reveal flow-based communities in networks. Scientific Reports, 6, 23194. doi: https://doi.org/10.1038/srep23194Google Scholar
Sanchez-Garcia, R. J. (2018). Exploiting symmetry in network analysis. arXiv preprint arXiv:1803.06915.Google Scholar
Schaeffer, S. E. (2007). Graph clustering. Computer Science Review, 1(1), 27–64. doi: https://doi.org/10.1016/j.cosrev.2007.05.001Google Scholar
Schaub, M. T. (2014). Unraveling complex networks under the prism of dynamical processes: relations between structure and dynamics. (Doctoral dissertation). Imperial College London.Google Scholar
Schaub, M. T., Benson, A. R., Horn, P., Lippner, G., & Jadbabaie, A. (2020). Random walks on simplicial complexes and the normalized Hodge 1-Laplacian. SIAM Review, 62 (2), 353–391.Google Scholar
Schaub, M. T., Billeh, Y. N., Anastassiou, C. A., Koch, C., & Barahona, M. (2015). Emergence of slow-switching assemblies in structured neuronal networks. PLOS Computational Biology, 11 (7),e1004196.Google Scholar
Schaub, M. T., Delvenne, J.-C., Lambiotte, R., & Barahona, M. (2019a). Multiscale dynamical embeddings of complex networks. Physical Review E, 99 (6),062308. doi: https://doi.org/10.1103/PhysRevE.99.062308Google Scholar
Schaub, M. T., Delvenne, J.-C., Lambiotte, R., & Barahona, M. (2019b). Structured networks and coarse-grained descriptions: a dynamical perspective. Advances in Network Clustering and Blockmodeling, pp. 333–361.Google Scholar
Schaub, M. T., Delvenne, J.-C., Rosvall, M., & Lambiotte, R. (2017, 02). The many facets of community detection in complex networks. Applied Network Science, 2(1), 4. doi: 10.1007/s41109-017-0023-6Google Scholar
Schaub, M. T., Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2012a). Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit. PloS One, 7(2), e32210.Google Scholar
Schaub, M. T., Lambiotte, R., & Barahona, M. (2012b). Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation. Physical Review E, 86 (2),026112.Google Scholar
Schaub, M. T., O’Clery, N., Billeh, Y. N. et al. (2016). Graph partitions and cluster synchronization in networks of oscillators. Chaos: An Interdisciplinary Journal of Nonlinear Science, 26 (9),094821.Google Scholar
Schaub, M. T., & Peel, L. (2020). Hierarchical community structure in networks. arXiv preprint arXiv:2009.07196.Google Scholar
Schaub, M. T., Zhu, Y., Seby, J.-B., Roddenberry, T. M., & Segarra, S. (2021). Signal processing on higher-order networks: Livin’ on the edge... and beyond. Signal Processing, 187, 108149. doi: https://doi.org/10.1016/j.sigpro.2021.108149Google Scholar
Serrano, M. A., & Boguná, M. (2021). The shortest path to network geometry. Cambridge University Press.Google Scholar
Serrano, M. A., Krioukov, D., & Boguná, M. (2008). Self-similarity of complex networks and hidden metric spaces. Physical Review Letters, 100 (7),078701.Google Scholar
Shi, J., & Malik, J. (1997). Normalized cuts and image segmentation. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (pp. 731–737).Google Scholar
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30 (3), 83–98.Google Scholar
Simon, H. A. (1962). The architecture of complexity. Proceedings of the American Philosophical Society, 106 (6), 467–482.Google Scholar
Simon, H. A., & Ando, A. (1961). Aggregation of variables in dynamic systems. Econometrica: Journal of the Econometric Society, 111–138.Google Scholar
Smiljanić, J., Edler, D., & Rosvall, M. (2020). Mapping flows on sparse networks with missing links. Physical Review E, 102 (1),012302.Google Scholar
Spielman, D. A., & Teng, S.-H. (2011). Spectral sparsification of graphs. SIAM Journal on Computing, 40(4), 981–1025. doi: https://doi.org/10.1137/08074489XGoogle Scholar
Stamm, F. I., Neuhäuser, L., Lemmerich, F., Schaub, M. T., & Strohmaier, M. (2020). Systematic edge uncertainty in attributed social networks and its effects on rankings of minority nodes. arXiv:2010.11546v2 [cs.SI]Google Scholar
Stewart, I., Golubitsky, M., & Pivato, M. (2003). Symmetry groupoids and patterns of synchrony in coupled cell networks. SIAM Journal on Applied Dynamical Systems, 2 (4), 609–646.Google Scholar
Stumpf, M. P., Wiuf, C., & May, R. M. (2005). Subnets of scale-free networks are not scale-free: sampling properties of networks. Proceedings of the National Academy of Sciences, 102 (12), 4221–4224.Google Scholar
Tian, F., Gao, B., Cui, Q., Chen, E., & Liu, T.-Y. (2014). Learning deep representations for graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (vol. 28).CrossRefGoogle Scholar
Traag, V. A., Waltman, L., & Van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9 (1), 1–12.Google Scholar
Trefethen, L. N., & Embree, M. (2005). Spectra and pseudospectra: the behavior of nonnormal matrices and operators. Princeton University Press.Google Scholar
Van Lierde, H., Chow, T. W., & Delvenne, J.-C. (2019). Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs. Journal of Complex Networks, 7 (1), 1–53.Google Scholar
Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395–416.Google Scholar
Wagner, C., Singer, P., & Karimi, F. (2017). Sampling from social networks with attributes, pp. 1181–1190. doi: https://doi.org/10.1145/3038912.3052665Google Scholar
Wainwright, M. J. (2019). High-dimensional statistics: a non-asymptotic viewpoint, (vol. 48). Cambridge University Press.CrossRefGoogle Scholar
Wasserman, S., & Faust, K. (1994). Social network analysis: methods and applications, (vol. 8). Cambridge University Press.Google Scholar
Wu, Z., Pan, S., Chen, F. et al. (2020). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems. arXiv:1901.00596v4 [cs.LG]Google Scholar
Young, J.-G., Cantwell, G. T., & Newman, M. E. J. (2020). Robust Bayesian inference of network structure from unreliable data. arXiv:2008.03334v2 [cs.SI]Google Scholar
Yu, Y., Wang, T., & Samworth, R. J. (2015). A useful variant of the Davis–Kahan theorem for statisticians. Biometrika, 102 (2), 315–323.Google Scholar
- 11
- Cited by