Interplay between function and structure in complex networks

Abstract

We show that abrupt structural transitions can arise in functionally optimal networks, driven by small changes in the level of transport congestion. Our results offer an explanation as to why so many diverse species of network structure arise in Nature (e.g. fungal systems) under essentially the same environmental conditions. Our findings are based on an exactly solvable model system which mimics a variety of biological and social networks. We then extend our analysis by introducing a novel renormalization scheme involving cost motifs, to describe analytically the average shortest path across multiple-ring-and-hub networks. As a consequence, we uncover a 'skin effect' whereby the structure of the inner multi-ring core can cease to play any role in terms of determining the average shortest path across the network.

Expanded version of physics/0508228 with additional new results

References in corpus (9)

• The structure and function of complex networks
• Network robustness and fragility: Percolation on random graphs
• Topology of evolving networks: local events and universality
• Optimal network topologies for local search with congestion
• Optimal design of spatial distribution networks
• Optimal Paths in Disordered Complex Networks
• Exactly solvable analogy of small-world networks
• Effect of congestion costs on shortest paths through complex networks
• Network Structures from Selection Principles

Cited by in corpus (17)

• Spatial Networks
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Road planning with slime mould: If Physarum built motorways it would route M6/M74 through Newcastle
• Morphology of travel routes and the organization of cities
• Approximating Mexican highways with slime mould
• Congestion diffusion and decongestion strategy in networked traffic
• Hate multiverse spreads malicious COVID-19 content online beyond individual platform control
• Bio-Development of Motorway Networks in the Netherlands: A Slime Mould Approach
• Evolution of road infrastructures in large urban areas
• Central loops in random planar graphs
• The Emergence and Dynamical Evolution of Complex Transport Networks from Simple Low-Level Behaviours
• The World's Colonisation and Trade Routes Formation as Imitated by Slime Mould
• Transitions in spatial networks
• Social media cluster dynamics create resilient global hate highways
• Growth-induced mass flows in fungal networks
• Braess like Paradox in a Small World Network
• Braess like Paradox on Ladder Network