Higher-order organization of complex networks

被引:855
作者
Benson, Austin R. [1 ]
Gleich, David F. [2 ]
Leskovec, Jure [3 ]
机构
[1] Stanford Univ, Inst Computat & Math Engn, Stanford, CA 94305 USA
[2] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47906 USA
[3] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
基金
美国国家科学基金会;
关键词
MOTIFS;
D O I
10.1126/science.aad9029
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
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.
引用
收藏
页码:163 / 166
页数:4
相关论文
共 25 条
[1]  
Andersen R., 2006, P 47 ANN IEEE S FDN, P475
[2]  
[Anonymous], 1997, C ELEGANS
[3]  
Benson Austin R, 2015, Proc SIAM Int Conf Data Min, V2015, P118
[4]   Principal direction divisive partitioning [J].
Boley, D .
DATA MINING AND KNOWLEDGE DISCOVERY, 1998, 2 (04) :325-344
[5]   Clustering by passing messages between data points [J].
Frey, Brendan J. ;
Dueck, Delbert .
SCIENCE, 2007, 315 (5814) :972-976
[6]   METHOD FOR DETECTING STRUCTURE IN SOCIOMETRIC DATA [J].
HOLLAND, PW ;
LEINHARD.S .
AMERICAN JOURNAL OF SOCIOLOGY, 1970, 76 (03) :492-&
[7]   Network structure of cerebral cortex shapes functional connectivity on multiple time scales [J].
Honey, Christopher J. ;
Koetter, Rolf ;
Breakspear, Michael ;
Sporns, Olaf .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (24) :10240-10245
[8]   Nonoptimal component placement, but short processing paths, due to long-distance projections in neural systems [J].
Kaiser, Marcus ;
Hilgetag, Claus C. .
PLOS COMPUTATIONAL BIOLOGY, 2006, 2 (07) :805-815
[9]   Spectral redemption in clustering sparse networks [J].
Krzakala, Florent ;
Moore, Cristopher ;
Mossel, Elchanan ;
Neeman, Joe ;
Sly, Allan ;
Zdeborova, Lenka ;
Zhang, Pan .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2013, 110 (52) :20935-20940
[10]   Nictation, a dispersal behavior of the nematode Caenorhabditis elegans, is regulated by IL2 neurons [J].
Lee, Harksun ;
Choi, Myung-kyu ;
Lee, Daehan ;
Kim, Hye-sung ;
Hwang, Hyejin ;
Kim, Heekyeong ;
Park, Sungsu ;
Paik, Young-ki ;
Lee, Junho .
NATURE NEUROSCIENCE, 2012, 15 (01) :107-U134