Impact of physicality on network structure

• DOI: 10.1038/s41567-023-02267-1
• Publication Date: 2023-11-06T17:02:29Z
• Authors: Márton Pósfai; Balázs Szegedy; Iva Bačić; Luka Blagojević; Miklós Abért; János Kertész; László Lovász; Albert-László Bar...
• Keywords: 0301 basic medicine; QA75 Electronic computers. Computer science / számítástechnika; 03 medical and health sciences; Statistical Mechanics (cond-mat.stat-mech); számítógéptudomány; FOS: Physical sciences; Condensed Matter - Statistical Mechanics

The emergence of detailed maps of physical networks, like the brain connectome, vascular networks, or composite networks in metamaterials, whose nodes and links are physical entities, have demonstrated the limits of the current network science toolset. Link physicality imposes a non-crossing condition that affects both the evolution and the structure of a network, in a way that the adjacency matrix alone -- the starting point of all graph-based approaches -- cannot capture. Here, we introduce a meta-graph that helps us discover an exact mapping between linear physical networks and independent sets, a central concept in graph theory. The mapping allows us to analytically derive both the onset of physical effects and the emergence of a jamming transition, and show that physicality impacts the network structure even when the total volume of the links is negligible. Finally, we construct the meta-graphs of several real physical networks, which allows us to predict functional features, such as synapse formation in the brain connectome, that agree with empirical data. Overall, our results show that, in order to understand the evolution and behavior of real complex networks, the role of physicality must be fully quantified.