{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T18:03:40Z","timestamp":1790705020334,"version":"4.1.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T00:00:00Z","timestamp":1459382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T00:00:00Z","timestamp":1459382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci Rep"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Complex systems made of interacting elements are commonly abstracted as networks, in which nodes are associated with dynamic state variables, whose evolution is driven by interactions mediated by the edges. Markov processes have been the prevailing paradigm to model such a network-based dynamics, for instance in the form of random walks or other types of diffusions. Despite the success of this modelling perspective for numerous applications, it represents an over-simplification of several real-world systems. Importantly, simple Markov models lack memory in their dynamics, an assumption often not realistic in practice. Here, we explore possibilities to enrich the system description by means of second-order Markov models, exploiting empirical pathway information. We focus on the problem of community detection and show that standard network algorithms can be generalized in order to extract novel temporal information about the system under investigation. We also apply our methodology to temporal networks, where we can uncover communities shaped by the temporal correlations in the system. Finally, we discuss relations of the framework of second order Markov processes and the recently proposed formalism of using non-backtracking matrices for community detection.<\/jats:p>","DOI":"10.1038\/srep23194","type":"journal-article","created":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T09:02:31Z","timestamp":1459414951000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["Using higher-order Markov models to reveal flow-based communities in networks"],"prefix":"10.1038","volume":"6","author":[{"given":"Vsevolod","family":"Salnikov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael T.","family":"Schaub","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renaud","family":"Lambiotte","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,3,31]]},"reference":[{"key":"BFsrep23194_CR1","unstructured":"Newman, M. E. J. Networks: An Introduction (Oxford University Press, USA, 2010)."},{"key":"BFsrep23194_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1093\/comnet\/cnu017","volume":"3","author":"R Lambiotte","year":"2015","unstructured":"Lambiotte, R., Salnikov, V. & Rosvall, M. Effect of memory on the dynamics of random walks on networks. J. Complex Netw. 3, 177\u2013188 (2015).","journal-title":"J. Complex Netw"},{"key":"BFsrep23194_CR3","doi-asserted-by":"publisher","first-page":"12755","DOI":"10.1073\/pnas.0903215107","volume":"107","author":"J-C Delvenne","year":"2010","unstructured":"Delvenne, J.-C., Yaliraki, S. N. & Barahona, M. Stability of graph communities across time scales. Proc. Natl. Acad. Sci. 107, 12755\u201312760 (2010).","journal-title":"Proc. Natl. Acad. Sci"},{"key":"BFsrep23194_CR4","doi-asserted-by":"publisher","first-page":"e32210","DOI":"10.1371\/journal.pone.0032210","volume":"7","author":"MT Schaub","year":"2012","unstructured":"Schaub, M. T., Delvenne, J.-C., Yaliraki, S. N. & Barahona, M. Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View Limit. PLoS ONE 7, e32210 (2012).","journal-title":"PLoS ONE"},{"key":"BFsrep23194_CR5","doi-asserted-by":"publisher","first-page":"042822","DOI":"10.1103\/PhysRevE.88.042822","volume":"88","author":"ME Newman","year":"2013","unstructured":"Newman, M. E. Spectral methods for community detection and graph partitioning. Phys. Rev. E 88, 042822 (2013).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR6","doi-asserted-by":"crossref","unstructured":"Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D. & Lambiotte, R. Memory in network flows and its effects on spreading dynamics and community detection. Nat. Commun. 5 (2014).","DOI":"10.1038\/ncomms5630"},{"key":"BFsrep23194_CR7","doi-asserted-by":"crossref","unstructured":"Scholtes, I. et al. Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks. Nat. Commun. 5 (2014).","DOI":"10.1038\/ncomms6024"},{"key":"BFsrep23194_CR8","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1126\/science.1177170","volume":"327","author":"C Song","year":"2010","unstructured":"Song, C., Qu, Z., Blumm, N. & Barab\u00e1si, A.-L. Limits of Predictability in Human Mobility. Science 327, 1018\u20131021 (2010).","journal-title":"Science"},{"key":"BFsrep23194_CR9","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1137\/090761070","volume":"52","author":"E Estrada","year":"2010","unstructured":"Estrada, E. & Higham, D. Network Properties Revealed through Matrix Functions. SIAM Rev. 52, 696\u2013714 (2010).","journal-title":"SIAM Rev."},{"key":"BFsrep23194_CR10","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1073\/pnas.0706851105","volume":"105","author":"M Rosvall","year":"2008","unstructured":"Rosvall, M. & Bergstrom, C. T. Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. 105, 1118\u20131123 (2008).","journal-title":"Proc. Natl. Acad. Sci"},{"key":"BFsrep23194_CR11","doi-asserted-by":"crossref","unstructured":"Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D., & Lambiotte, R. Memory in network flows and its effects on spreading dynamics and community detection. Nature communications, 5, (2014).","DOI":"10.1038\/ncomms5630"},{"key":"BFsrep23194_CR12","doi-asserted-by":"crossref","unstructured":"Delvenne, J.-C., Schaub, M. T., Yaliraki, S. N. & Barahona, M. The Stability of a Graph Partition: A Dynamics-Based Framework for Community Detection. In Mukherjee, A., Choudhury, M., Peruani, F., Ganguly, N. & Mitra, B. (eds.) Dynamics On and Of Complex Networks, Volume 2, Modeling and Simulation in Science, Engineering and Technology, 221\u2013242 (Springer, New York, 2013).","DOI":"10.1007\/978-1-4614-6729-8_11"},{"key":"BFsrep23194_CR13","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1109\/TNSE.2015.2391998","volume":"1","author":"R Lambiotte","year":"2014","unstructured":"Lambiotte, R., Delvenne, J.-C. & Barahona, M. Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks. IEEE Trans. Netw. Sc. Eng. 1, 76\u201390 (2014).","journal-title":"IEEE Trans. Netw. Sc. Eng."},{"key":"BFsrep23194_CR14","doi-asserted-by":"publisher","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"MEJ Newman","year":"2006","unstructured":"Newman, M. E. J. Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103, 8577\u20138582 (2006).","journal-title":"Proc. Natl. Acad. Sci"},{"key":"BFsrep23194_CR15","doi-asserted-by":"publisher","first-page":"218701","DOI":"10.1103\/PhysRevLett.93.218701","volume":"93","author":"J Reichardt","year":"2004","unstructured":"Reichardt, J. & Bornholdt, S. Detecting Fuzzy Community Structures in Complex Networks with a Potts Model. Phys. Rev. Lett. 93, 218701 (2004).","journal-title":"Phys. Rev. Lett."},{"key":"BFsrep23194_CR16","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/BF01591018","volume":"25","author":"M Fiedler","year":"1975","unstructured":"Fiedler, M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Math. J. 25, 619\u2013633 (1975).","journal-title":"Czechoslovak Math. J"},{"key":"BFsrep23194_CR17","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J. & Malik, J. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell 22, 888\u2013905 (2000).","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"BFsrep23194_CR18","doi-asserted-by":"publisher","first-page":"20935","DOI":"10.1073\/pnas.1312486110","volume":"110","author":"F Krzakala","year":"2013","unstructured":"Krzakala, F. et al. Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. 110, 20935\u201320940 (2013).","journal-title":"Proc. Natl. Acad. Sci"},{"key":"BFsrep23194_CR19","doi-asserted-by":"publisher","first-page":"016105","DOI":"10.1103\/PhysRevE.80.016105","volume":"80","author":"TS Evans","year":"2009","unstructured":"Evans, T. S. & Lambiotte, R. Line graphs, link partitions and overlapping communities. Phys. Rev. E 80, 016105 (2009).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR20","doi-asserted-by":"crossref","unstructured":"Friggeri, A., Chelius, G. & Fleury, E. Triangles to Capture Social Cohesion. In Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), MIT, Boston, USA (2011).","DOI":"10.1109\/PASSAT\/SocialCom.2011.169"},{"key":"BFsrep23194_CR21","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1038\/nature09182","volume":"466","author":"Y-Y Ahn","year":"2010","unstructured":"Ahn, Y.-Y., Bagrow, J. P. & Lehmann, S. Link communities reveal multiscale complexity in networks. Nature 466, 761\u2013764 (2010).","journal-title":"Nature"},{"key":"BFsrep23194_CR22","doi-asserted-by":"publisher","first-page":"056107","DOI":"10.1103\/PhysRevE.85.056107","volume":"85","author":"R Lambiotte","year":"2012","unstructured":"Lambiotte, R. & Rosvall, M. Ranking and clustering of nodes in networks with smart teleportation. Phys. Rev. E 85, 056107 (2012).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR23","doi-asserted-by":"publisher","first-page":"055010","DOI":"10.1088\/1478-3975\/8\/5\/055010","volume":"8","author":"A Delmotte","year":"2011","unstructured":"Delmotte, A., Tate, E. W., Yaliraki, S. N. & Barahona, M. Protein multi-scale organization through graph partitioning and robustness analysis: application to the myosin? myosin light chain interaction. Phys. Biol. 8, 055010 (2011).","journal-title":"Phys. Biol."},{"key":"BFsrep23194_CR24","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"V Blondel","year":"2008","unstructured":"Blondel, V., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. 2008, P10008 (2008).","journal-title":"J. Stat. Mech. Theor. Exp"},{"key":"BFsrep23194_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","volume":"9","author":"F Chung","year":"2005","unstructured":"Chung, F. Laplacians and the Cheeger inequality for directed graphs. Ann. Comb. 9, 1\u201319 (2005).","journal-title":"Ann. Comb."},{"key":"BFsrep23194_CR26","doi-asserted-by":"crossref","unstructured":"Satuluri, V. & Parthasarathy, S. Symmetrizations for clustering directed graphs. In Proceedings of the 14th International Conference on Extending Database Technology, Uppsala, Sweden. Publisher: ACM Digital Library (2011).","DOI":"10.1145\/1951365.1951407"},{"key":"BFsrep23194_CR27","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1073\/pnas.0605965104","volume":"104","author":"F Fortunato","year":"2006","unstructured":"Fortunato, F. & Barthel\u00e9my, M. Resolution limit in community detection. Proc. Natl. Acad. Sci. USA 104, 36\u201341 (2006).","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"BFsrep23194_CR28","doi-asserted-by":"publisher","first-page":"046106","DOI":"10.1103\/PhysRevE.81.046106","volume":"81","author":"BH Good","year":"2010","unstructured":"Good, B. H., de Montjoye, Y.-A. & Clauset, A. The performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106 (2010).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR29","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"F Fortunato","year":"2010","unstructured":"Fortunato, F. Community detection in graphs. Phys. Rep. 486, 75\u2013174 (2010).","journal-title":"Phys. Rep"},{"key":"BFsrep23194_CR30","doi-asserted-by":"publisher","first-page":"026112","DOI":"10.1103\/PhysRevE.86.026112","volume":"86","author":"MT Schaub","year":"2012","unstructured":"Schaub, M. T., Lambiotte, R. & Barahona, M. Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation. Phys. Rev. E 86, 026112 (2012).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR31","unstructured":"Lambiotte, R. Multi-scale modularity in complex networks. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on, 546\u2013553 (IEEE, 2010)."},{"key":"BFsrep23194_CR32","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"P Holland","year":"1983","unstructured":"Holland, P., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: First steps. Soc. Netw. 5, 109\u2013137 (1983).","journal-title":"Soc. Netw"},{"key":"BFsrep23194_CR33","doi-asserted-by":"publisher","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","volume":"83","author":"B Karrer","year":"2011","unstructured":"Karrer, B. & Newman, M. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).","journal-title":"Phys. Rev. E"},{"key":"BFsrep23194_CR34","first-page":"011047","volume":"4","author":"T Peixoto","year":"2014","unstructured":"Peixoto, T. Hierarchical block structures and high-resolution model selection in large networks. Phys. Rev. X 4, 011047 (2014).","journal-title":"Phys. Rev. X"},{"key":"BFsrep23194_CR35","unstructured":"Peixoto, T. & Rosvall, M. Modeling sequences and temporal networks with dynamic community structures. arXiv:1509.04740 (2015)."},{"key":"BFsrep23194_CR36","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.jmva.2006.11.013","volume":"98","author":"M Meila","year":"2007","unstructured":"Meila, M. Comparing clusterings-an information based distance. J. Multivariate Anal. 98, 873\u2013895 (2007).","journal-title":"J. Multivariate Anal."},{"key":"BFsrep23194_CR37","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme, P. & Saramki, J. Temporal networks. Phys. Rep. 519, 97\u2013125 (2012).","journal-title":"Phys. Rep"},{"key":"BFsrep23194_CR38","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1126\/science.1184819","volume":"328","author":"P Mucha","year":"2010","unstructured":"Mucha, P., Richardson, T., Macon, K., Porter, M. & Onnela, J.-P. Community Structure in Time-Dependent, Multiscale and Multiplex Networks. Science 328, 876\u2013878 (2010).","journal-title":"Science"},{"key":"BFsrep23194_CR39","doi-asserted-by":"crossref","unstructured":"Delvenne, J.-C., Lambiotte, R. & Rocha, L. Diffusion on networked systems is a question of time or structure. Nat. Commun. 6 (2015).","DOI":"10.1038\/ncomms8366"},{"key":"BFsrep23194_CR40","doi-asserted-by":"crossref","unstructured":"Saramaki, J. & Holme, P. Exploring Temporal Networks with Greedy Walks. arXiv:1508.00693 (2015).","DOI":"10.1140\/epjb\/e2015-60660-9"},{"key":"BFsrep23194_CR41","doi-asserted-by":"crossref","unstructured":"Gueuning, M., Delvenne, J.-C. & Lambiotte, R. Imperfect diffusion on temporal networks. arXiv:1508.04006 (2015).","DOI":"10.1140\/epjb\/e2015-60596-0"},{"key":"BFsrep23194_CR42","doi-asserted-by":"publisher","first-page":"15274","DOI":"10.1073\/pnas.0900282106","volume":"106","author":"N Eagle","year":"2009","unstructured":"Eagle, N., Pentland, A. S. & Lazer, D. Inferring friendship network structure by using mobile phone data. Proc. Natl. Acad. Sci. 106, 15274\u201315278 (2009).","journal-title":"Proc. Natl. Acad. Sci"},{"key":"BFsrep23194_CR43","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1186\/s12879-014-0695-9","volume":"14","author":"V Gemmetto","year":"2014","unstructured":"Gemmetto, V., Barrat, A. & Cattuto, C. Mitigation of infectious disease at school: targeted class closure vs school closure. BMC Infect. Dis. 14, 695 (2014).","journal-title":"BMC Infect. Dis."},{"key":"BFsrep23194_CR44","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9, J. et al. High-resolution measurements of face-to-face contact patterns in a primary school. PLoS ONE (2011).","DOI":"10.1371\/journal.pone.0023176"},{"key":"BFsrep23194_CR45","unstructured":"Newman, M. Spectral community detection in sparse networks. arXiv:1308.6494 (2013)."},{"key":"BFsrep23194_CR46","unstructured":"Newman, M., Barabasi, A.-L. & Watts, D. The structure and dynamics of networks (Princeton University Press, 2006)."},{"key":"BFsrep23194_CR47","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1093\/comnet\/cnu016","volume":"2","author":"M Kivel\u00e4","year":"2014","unstructured":"Kivel\u00e4, M. et al. Multilayer networks. J. Complex Netw. 2, 203\u2013271 (2014).","journal-title":"J. Complex Netw"}],"container-title":["Scientific Reports"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/srep23194","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/srep23194.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/srep23194.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T13:08:37Z","timestamp":1672837717000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/srep23194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,31]]},"references-count":47,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,9,2]]}},"alternative-id":["BFsrep23194"],"URL":"https:\/\/doi.org\/10.1038\/srep23194","relation":{},"ISSN":["2045-2322"],"issn-type":[{"value":"2045-2322","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,31]]},"assertion":[{"value":"18 September 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing financial interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"23194"}}