On the Structure of Complex Networks: Universality in Transportation, Borders in Human Mobility, and Robust Skeletons

Large-scale complex networks in natural, social, and technological systems generically exhibit an abundance of rich information, and extracting essential and meaningful structural features from network data is one of the most challenging tasks in network theory. Nonetheless, understanding these networks is essential to explaining phenomena in transportation, epidemiology, sociology, economics, and other fields. Here we address this issue first through a comparative approach by analyzing the structure of the largest transportation systems. We find that many properties are shared by both networks, suggesting that similar processes may guide their growth and that dynamic processes evolving on these networks may exhibit similar behavior. We go one to analyze a multi-scale human mobility network and compute effective geographic borders inherent to human mobility patterns in the United States. Such territorial subdivisions may influence the interregional flow of information and cross-border trade and affect the diffusion of innovation and technology. We find that effective borders, which cannot be reproduced using simple transportation models such as the gravity law, only partially overlap with existing administrative borders, and show that some of the strongest mobility borders exist in unexpected regions. We go on to introduce the concept of link salience, an approach for classifying network elements based on a consensus estimate of all nodes. We show that a wide range of empirical networks exhibit a natural, network-implicit, and robust classification of links into two qualitatively distinct groups. We show that despite significant differences in the networks' topology and statistical features, their salient skeletons exhibit generic topological and statistical features. In addition to a method for network reduction, link salience points the way towards a better understanding of universal, hidden features in real world networks that are masked by their complexity, which we demonstrate with an application to epidemic spread. Finally we relate link salience to effective borders through the hierarchical community structure of mobility networks. We show that network perturbations may have unexpected effects on the structure of the high-salience skeleton and shortest paths throughout the network, which could decrease the predictability of dynamic processes evolving on these networks.