Higher-Order Organization of Complex Networks. Benson, A. R.; Gleich, D. F.; and Leskovec, J. 353(6295):163–166.
Higher-Order Organization of Complex Networks [link]Paper  doi  abstract   bibtex   
[Resolving a network of hubs] Graphs are a pervasive tool for modeling and analyzing network data throughout the sciences. Benson et al. developed an algorithmic framework for studying how complex networks are organized by higher-order connectivity patterns (see the Perspective by Pržulj and Malod-Dognin). Motifs in transportation networks reveal hubs and geographical elements not readily achievable by other methods. A motif previously suggested as important for neuronal networks is part of a ” rich club” of subnetworks. [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.
@article{bensonHigherorderOrganizationComplex2016,
  title = {Higher-Order Organization of Complex Networks},
  author = {Benson, A. R. and Gleich, D. F. and Leskovec, J.},
  date = {2016-07},
  journaltitle = {Science},
  volume = {353},
  pages = {163--166},
  issn = {0036-8075},
  doi = {10.1126/science.aad9029},
  url = {http://mfkp.org/INRMM/article/14090983},
  abstract = {[Resolving a network of hubs]

Graphs are a pervasive tool for modeling and analyzing network data throughout the sciences. Benson et al. developed an algorithmic framework for studying how complex networks are organized by higher-order connectivity patterns (see the Perspective by Pržulj and Malod-Dognin). Motifs in transportation networks reveal hubs and geographical elements not readily achievable by other methods. A motif previously suggested as important for neuronal networks is part of a ” rich club” of subnetworks.

[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.},
  archivePrefix = {arXiv},
  eprint = {1612.08447},
  eprinttype = {arxiv},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-14090983,~to-add-doi-URL,complexity,connectivity,networks,pattern},
  number = {6295}
}
Downloads: 0