Higher-order Organization of Complex Networks

Overview

Journal Science

Specialty Science

Date 2016 Jul 9

PMID 27387949

Citations 105

Authors

Austin R Benson

David F Gleich

Jure Leskovec

Affiliations

Soon will be listed here.

Abstract

Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks--at the level of small network subgraphs--remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.

Citing Articles

Resolving discrepancies between chimeric and multiplicative measures of higher-order epistasis.

Chitra U, Arnold B, Raphael B Nat Commun. 2025; 16(1):1711.

PMID: 39962081 PMC: 11833126. DOI: 10.1038/s41467-025-56986-5.

Coarse-graining network flow through statistical physics and machine learning.

Zhang Z, Ghavasieh A, Zhang J, De Domenico M Nat Commun. 2025; 16(1):1605.

PMID: 39948344 PMC: 11825948. DOI: 10.1038/s41467-025-56034-2.

CompLex: Legal systems through the lens of complexity science.

Vivo P, Katz D, Ruhl J Europhys Lett. 2025; 149(2):22001.

PMID: 39866179 PMC: 7617345. DOI: 10.1209/0295-5075/ad99fc.

Interpretable identification of cancer genes across biological networks via transformer-powered graph representation learning.

Su X, Hu P, Li D, Zhao B, Niu Z, Herget T Nat Biomed Eng. 2025; .

PMID: 39789329 DOI: 10.1038/s41551-024-01312-5.

Unifying topological structure and self-attention mechanism for node classification in directed networks.

Peng Y, Xia J, Liu D, Liu M, Xiao L, Shi B Sci Rep. 2025; 15(1):805.

PMID: 39755762 PMC: 11700118. DOI: 10.1038/s41598-024-84816-z.

References

Przulj N, Corneil D, Jurisica I . Modeling interactome: scale-free or geometric?. Bioinformatics. 2004; 20(18):3508-15. DOI: 10.1093/bioinformatics/bth436. View

Frey B, Dueck D . Clustering by passing messages between data points. Science. 2007; 315(5814):972-6. DOI: 10.1126/science.1136800. View

Mangan S, Zaslaver A, Alon U . The coherent feedforward loop serves as a sign-sensitive delay element in transcription networks. J Mol Biol. 2003; 334(2):197-204. DOI: 10.1016/j.jmb.2003.09.049. View

Benson A, Gleich D, Leskovec J . Tensor Spectral Clustering for Partitioning Higher-order Network Structures. Proc SIAM Int Conf Data Min. 2015; 2015:118-126. PMC: 5089081. DOI: 10.1137/1.9781611974010.14. View

Michoel T, Joshi A, Nachtergaele B, Van de Peer Y . Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks. Mol Biosyst. 2011; 7(10):2769-78. DOI: 10.1039/c1mb05241a. View

Lee H, Choi M, Lee D, Kim H, Hwang H, Kim H . Nictation, a dispersal behavior of the nematode Caenorhabditis elegans, is regulated by IL2 neurons. Nat Neurosci. 2011; 15(1):107-12. DOI: 10.1038/nn.2975. View

Milo R, Itzkovitz S, Kashtan N, Chklovskii D, Alon U . Network motifs: simple building blocks of complex networks. Science. 2002; 298(5594):824-7. DOI: 10.1126/science.298.5594.824. View

Kaiser M, Hilgetag C . Nonoptimal component placement, but short processing paths, due to long-distance projections in neural systems. PLoS Comput Biol. 2006; 2(7):e95. PMC: 1513269. DOI: 10.1371/journal.pcbi.0020095. View

Krzakala F, Moore C, Mossel E, Neeman J, Sly A, Zdeborova L . Spectral redemption in clustering sparse networks. Proc Natl Acad Sci U S A. 2013; 110(52):20935-40. PMC: 3876200. DOI: 10.1073/pnas.1312486110. View

10.

Mangan S, Alon U . Structure and function of the feed-forward loop network motif. Proc Natl Acad Sci U S A. 2003; 100(21):11980-5. PMC: 218699. DOI: 10.1073/pnas.2133841100. View

11.

Rosvall M, Esquivel A, Lancichinetti A, West J, Lambiotte R . Memory in network flows and its effects on spreading dynamics and community detection. Nat Commun. 2014; 5:4630. DOI: 10.1038/ncomms5630. View

12.

Honey C, Kotter R, Breakspear M, Sporns O . Network structure of cerebral cortex shapes functional connectivity on multiple time scales. Proc Natl Acad Sci U S A. 2007; 104(24):10240-5. PMC: 1891224. DOI: 10.1073/pnas.0701519104. View

13.

Yaveroglu O, Malod-Dognin N, Davis D, Levnajic Z, Janjic V, Karapandza R . Revealing the hidden language of complex networks. Sci Rep. 2014; 4:4547. PMC: 3971399. DOI: 10.1038/srep04547. View