Transport in weighted networks: partition into superhighways and roads

Tipping points, multistability, and stochasticity in a two-dimensional traffic network dynamics

Mitigating traffic jams is a critical step for the betterment of the urban transportation system, which comprises a large number of interconnected routes to form an intricate network. To understand distinct features of vehicular traffic flow on a network, a macroscopic two-dimensional traffic network model is proposed incorporating intra-nodal and inter-nodal vehicular interaction. Utilizing the popular techniques of nonlinear dynamics, we investigate the impact of different parameters like occupancy, entry rates, and exit rates of vehicles. The existence of saddle-node, Hopf, homoclinic, Bogdanov-Takens, and cusp bifurcations have been shown using single or biparametric bifurcation diagrams. The occurrences of different multistability (bistability/tristability) phenomena, stochastic switching, and critical transitions are explored in detail. Further, we calculate the possibility of achieving each alternative state using the basin stability metric to characterize multistability. In addition, critical transitions from free flow to congestion are identified at different magnitudes of stochastic fluctuations. The applicability of critical slowing down based generic indicators, e.g., variance, lag-1 autocorrelation, skewness, kurtosis, and conditional heteroskedasticity are investigated to forewarn the critical transition from free flow to traffic congestion. It is demonstrated through the use of simulated data that not all of the measures exhibit sensitivity to rapid phase transitions in traffic flow. Our study reveals that traffic congestion emerges because of either bifurcation or stochasticity. The result provided in this study may serve as a paradigm to understand the qualitative behavior of traffic jams and to explore the tipping mechanisms occurring in transport phenomena.

Unified scaling for the optimal path length in disordered lattices

In recent decades, much attention has been focused on the topic of optimal paths in weighted networks due to its broad scientific interest and technological applications. In this work we revisit the problem of the optimal path between two points and focus on the role of the geometry (size and shape) of the embedding lattice, which has received very little attention. This role becomes crucial, for example, in the strong disorder (SD) limit, where the mean length of the optimal path (ℓ[over ¯]_{opt}) for a fixed end-to-end distance r diverges as the lattice size L increases. We propose a unified scaling ansatz for ℓ[over ¯]_{opt} in D-dimensional disordered lattices. Our ansatz introduces two exponents, φ and χ, which respectively characterize the scaling of ℓ[over ¯]_{opt} with r for fixed L, and the scaling of ℓ[over ¯]_{opt} with L for fixed r, both in the SD limit. The ansatz is supported by a comprehensive numerical study of the problem on 2D lattices, yet we also present results in D=3. We show that it unifies well-known results in the strong and weak disorder regimes, including the crossover behavior, but it also reveals novel scaling scenarios not yet addressed. Moreover, it provides relevant insights into the origin of the universal exponents characterizing the scaling of the optimal path in the SD limit. For example, for the fractal dimension of the optimal path in the SD limit, d_{opt}, we find d_{opt}=φ+χ.

Fractured columnar small-world functional network organization in volumes of L2/3 of mouse auditory cortex

The sensory cortices of the brain exhibit large-scale functional topographic organization, such as the tonotopic organization of the primary auditory cortex (A1) according to sound frequency. However, at the level of individual neurons, layer 2/3 (L2/3) A1 appears functionally heterogeneous. To identify if there exists a higher-order functional organization of meso-scale neuronal networks within L2/3 that bridges order and disorder, we used in vivo two-photon calcium imaging of pyramidal neurons to identify networks in three-dimensional volumes of L2/3 A1 in awake mice. Using tonal stimuli, we found diverse receptive fields with measurable colocalization of similarly tuned neurons across depth but less so across L2/3 sublayers. These results indicate a fractured microcolumnar organization with a column radius of ∼50 µm, with a more random organization of the receptive field over larger radii. We further characterized the functional networks formed within L2/3 by analyzing the spatial distribution of signal correlations (SCs). Networks show evidence of Rentian scaling in physical space, suggesting effective spatial embedding of subnetworks. Indeed, functional networks have characteristics of small-world topology, implying that there are clusters of functionally similar neurons with sparse connections between differently tuned neurons. These results indicate that underlying the regularity of the tonotopic map on large scales in L2/3 is significant tuning diversity arranged in a hybrid organization with microcolumnar structures and efficient network topologies.

DomiRank Centrality reveals structural fragility of complex networks via node dominance

Determining the key elements of interconnected infrastructure and complex systems is paramount to ensure system functionality and integrity. This work quantifies the dominance of the networks' nodes in their respective neighborhoods, introducing a centrality metric, DomiRank, that integrates local and global topological information via a tunable parameter. We present an analytical formula and an efficient parallelizable algorithm for DomiRank centrality, making it applicable to massive networks. From the networks' structure and function perspective, nodes with high values of DomiRank highlight fragile neighborhoods whose integrity and functionality are highly dependent on those dominant nodes. Underscoring this relation between dominance and fragility, we show that DomiRank systematically outperforms other centrality metrics in generating targeted attacks that effectively compromise network structure and disrupt its functionality for synthetic and real-world topologies. Moreover, we show that DomiRank-based attacks inflict more enduring damage in the network, hindering its ability to rebound and, thus, impairing system resilience. DomiRank centrality capitalizes on the competition mechanism embedded in its definition to expose the fragility of networks, paving the way to design strategies to mitigate vulnerability and enhance the resilience of critical infrastructures.

Influence of heterogeneity of infection thresholds on epidemic spreading with neighbor resource supporting

The spread of disease on complex networks has attracted wide attention in physics, mathematics, and epidemiology. Recent works have demonstrated that individuals always exhibit different criteria for disease infection in a network that significantly influences the epidemic dynamics. In this paper, considering the heterogeneity of node susceptibility, we proposed an infection threshold model with neighbor resource support. The infection threshold of an individual is associated with the degree, and a parameter follows the normal distribution. Based on improved heterogeneous mean-field theory and extensive numerical simulations, we find that the mean and standard deviation of the infection threshold model can affect the phase transition and epidemic outbreak size. As the mean of the normal distribution parameter increases from a small value to a large value, the system shows a change from a continuous phase transition to a discontinuous phase transition, and the disease even stops spreading. The disease spreads from a discontinuous phase transition to continuous for the sizeable mean value as the standard deviation increases. Furthermore, the standard deviation also varies in the outbreak size.

Identification, cost evaluation, and prioritization of urban traffic congestions and their origin

The increasing urbanization in the last decades results in significant growth in urban traffic congestion around the world. This leads to enormous time people spent on roads and thus significant money waste and air pollution. Here, we present a novel methodology for identification, cost evaluation, and thus, prioritization of congestion origins, i.e., their bottlenecks. The presented work is based on network analysis of the entire road network from a global point of view. We identify and prioritize traffic bottlenecks based on big data of traffic speed retrieved in near-real-time. Our approach highlights the bottlenecks that have the most significant effect on the global urban traffic flow. We follow the evolution of every traffic congestion in the entire urban network and rank all the congestions, based on the cost they cause (in Vehicle Hours units). We show that the macro-stability that represents the seeming regularity of traffic load both in time and space, overshadows the existence of meso-dynamics, where the bottlenecks that create these congestions usually do not reappear on different days or hours. Thus, our method enables to identify in near-real-time both recurrent and nonrecurrent congestions and their sources.

Betweenness centrality in dense spatial networks

The betweenness centrality (BC) is an important quantity for understanding the structure of complex large networks. However, its calculation is in general difficult and known in simple cases only. In particular, the BC has been exactly computed for graphs constructed over a set of N points in the infinite density limit, displaying a universal behavior. We reconsider this calculation and propose an expansion for large and finite densities. We compute the lowest nontrivial order and show that it encodes how straight are shortest paths and is therefore nonuniversal and depends on the graph considered. We compare our analytical result to numerical simulations obtained for various graphs such as the minimum spanning tree, the nearest neighbor graph, the relative neighborhood graph, the random geometric graph, the Gabriel graph, or the Delaunay triangulation. We show that in most cases the agreement with our analytical result is excellent even for densities of points that are relatively low. This method and our results provide a framework for understanding and computing this important quantity in large spatial networks.

Topological analysis of the latent geometry of a complex network

Most real-world networks are embedded in latent geometries. If a node in a network is found in the vicinity of another node in the latent geometry, the two nodes have a disproportionately high probability of being connected by a link. The latent geometry of a complex network is a central topic of research in network science, which has an expansive range of practical applications, such as efficient navigation, missing link prediction, and brain mapping. Despite the important role of topology in the structures and functions of complex systems, little to no study has been conducted to develop a method to estimate the general unknown latent geometry of complex networks. Topological data analysis, which has attracted extensive attention in the research community owing to its convincing performance, can be directly implemented into complex networks; however, even a small fraction (0.1%) of long-range links can completely erase the topological signature of the latent geometry. Inspired by the fact that long-range links in a network have disproportionately high loads, we develop a set of methods that can analyze the latent geometry of a complex network: the modified persistent homology diagram and the map of the latent geometry. These methods successfully reveal the topological properties of the synthetic and empirical networks used to validate the proposed methods.

Special Patterns of Dynamic Brain Networks Discriminate Between Face and Non-face Processing: A Single-Trial EEG Study

Face processing is a spatiotemporal dynamic process involving widely distributed and closely connected brain regions. Although previous studies have examined the topological differences in brain networks between face and non-face processing, the time-varying patterns at different processing stages have not been fully characterized. In this study, dynamic brain networks were used to explore the mechanism of face processing in human brain. We constructed a set of brain networks based on consecutive short EEG segments recorded during face and non-face (ketch) processing respectively, and analyzed the topological characteristic of these brain networks by graph theory. We found that the topological differences of the backbone of original brain networks (the minimum spanning tree, MST) between face and ketch processing changed dynamically. Specifically, during face processing, the MST was more line-like over alpha band in 0-100 ms time window after stimuli onset, and more star-like over theta and alpha bands in 100-200 and 200-300 ms time windows. The results indicated that the brain network was more efficient for information transfer and exchange during face processing compared with non-face processing. In the MST, the nodes with significant differences of betweenness centrality and degree were mainly located in the left frontal area and ventral visual pathway, which were involved in the face-related regions. In addition, the special MST patterns can discriminate between face and ketch processing by an accuracy of 93.39%. Our results suggested that special MST structures of dynamic brain networks reflected the potential mechanism of face processing in human brain.

Effective traffic-flow assignment strategy on multilayer networks

An efficient flow assignment strategy is of great importance to alleviate traffic congestion on multilayer networks. In this work, by considering the roles of nodes' local structures on the microlevel, and the different transporting speeds of layers in the macrolevel, an effective traffic-flow assignment strategy on multilayer networks is proposed. Both numerical and semianalytical results indicate that our proposed flow assignment strategy can reasonably redistribute the traffic flow of the low-speed layer to the high-speed layer. In particular, preferentially transporting the packets through small-degree nodes on the high-speed layer can enhance the traffic capacity of multilayer networks. We also find that the traffic capacity of multilayer networks can be improved by increasing the network size and the average degree of the high-speed layer. For a given multilayer network, there is a combination of optimal macrolevel parameter and optimal microlevel parameter with which the traffic capacity can be maximized. It is verified that real-world network topology does not invalidate the results. The semianalytical predictions agree with the numerical simulations.

Coordinating dynamical routes with statistical physics on space-time networks

Coordination of dynamical routes can alleviate traffic congestion and is essential for the coming era of autonomous self-driving cars. However, dynamical route coordination is difficult and many existing routing protocols are either static or without intervehicle coordination. In this paper, we first apply the cavity approach in statistical physics to derive the theoretical behavior and an optimization algorithm for dynamical route coordination, but they become computationally intractable as the number of time segments increases. We therefore map static spatial networks to space-time networks to derive a computational feasible message-passing algorithm compatible with arbitrary system parameters; it agrees well with the analytical and algorithmic results of the conventional cavity approach and outperforms multistart greedy search in saving total travel time by as much as 15% in simulations. The study sheds light on the design of dynamical route coordination protocols and the solution to other dynamical problems via static analytical approaches on space-time networks.

Brain Connectivity and Information-Flow Breakdown Revealed by a Minimum Spanning Tree-Based Analysis of MRI Data in Behavioral Variant Frontotemporal Dementia

Brain functional disruption and cognitive shortfalls as consequences of neurodegeneration are among the most investigated aspects in current clinical research. Traditionally, specific anatomical and behavioral traits have been associated with neurodegeneration, thus directly translatable in clinical terms. However, these qualitative traits, do not account for the extensive information flow breakdown within the functional brain network that deeply affect cognitive skills. Behavioural variant Frontotemporal Dementia (bvFTD) is a neurodegenerative disorder characterized by behavioral and executive functions disturbances. Deviations from the physiological cognitive functioning can be accurately inferred and modeled from functional connectivity alterations. Although the need for unbiased metrics is still an open issue in imaging studies, the graph-theory approach applied to neuroimaging techniques is becoming popular in the study of brain dysfunction. In this work, we assessed the global connectivity and topological alterations among brain regions in bvFTD patients using a minimum spanning tree (MST) based analysis of resting state functional MRI (rs-fMRI) data. Whilst several graph theoretical methods require arbitrary criteria (including the choice of network construction thresholds and weight normalization methods), MST is an unambiguous modeling solution, ensuring accuracy, robustness, and reproducibility. MST networks of 116 regions of interest (ROIs) were built on wavelet correlation matrices, extracted from 41 bvFTD patients and 39 healthy controls (HC). We observed a global fragmentation of the functional network backbone with severe disruption of information-flow highways. Frontotemporal areas were less compact, more isolated, and concentrated in less integrated structures, respect to healthy subjects. Our results reflected such complex breakdown of the frontal and temporal areas at both intra-regional and long-range connections. Our findings highlighted that MST, in conjunction with rs-fMRI data, was an effective method for quantifying and detecting functional brain network impairments, leading to characteristic bvFTD cognitive, social, and executive functions disorders.

A Pólya urn approach to information filtering in complex networks

The increasing availability of data demands for techniques to filter information in large complex networks of interactions. A number of approaches have been proposed to extract network backbones by assessing the statistical significance of links against null hypotheses of random interaction. Yet, it is well known that the growth of most real-world networks is non-random, as past interactions between nodes typically increase the likelihood of further interaction. Here, we propose a filtering methodology inspired by the Pólya urn, a combinatorial model driven by a self-reinforcement mechanism, which relies on a family of null hypotheses that can be calibrated to assess which links are statistically significant with respect to a given network's own heterogeneity. We provide a full characterization of the filter, and show that it selects links based on a non-trivial interplay between their local importance and the importance of the nodes they belong to.

Statistical methods for constructing disease comorbidity networks from longitudinal inpatient data

Tools from network science can be utilized to study relations between diseases. Different studies focus on different types of inter-disease linkages. One of them is the comorbidity patterns derived from large-scale longitudinal data of hospital discharge records. Researchers seek to describe comorbidity relations as a network to characterize pathways of disease progressions and to predict future risks. The first step in such studies is the construction of the network itself, which subsequent analyses rest upon. There are different ways to build such a network. In this paper, we provide an overview of several existing statistical approaches in network science applicable to weighted directed networks. We discuss the differences between the null models that these models assume and their applications. We apply these methods to the inpatient data of approximately one million people, spanning approximately 17 years, pertaining to the Montreal Census Metropolitan Area. We discuss the differences in the structure of the networks built by different methods, and different features of the comorbidity relations that they extract. We also present several example applications of these methods.

From the betweenness centrality in street networks to structural invariants in random planar graphs

The betweenness centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of street networks from 97 cities worldwide, along with simulations of random planar graph models, indicates the observed invariance to be a consequence of a bimodal regime consisting of an underlying tree structure for high betweenness nodes, and a low betweenness regime corresponding to loops providing local path alternatives. Furthermore, the high betweenness nodes display a non-trivial spatial clustering with increasing spatial correlation as a function of the edge-density. Our results suggest that the spatial distribution of betweenness is a more accurate discriminator than its statistics for comparing  static congestion patterns and  its evolution across cities as demonstrated by analyzing 200 years of street data for Paris.

The betweenness centrality is a metric commonly used in network analysis. Here the authors show that the distribution of this metric in urban street networks is invariant in the case of 97 cities. This invariance could affect network flows, dynamics and congestion management in cities.

Robust MST-Based Clustering Algorithm

Minimax similarity stresses the connectedness of points via mediating elements rather than favoring high mutual similarity. The grouping principle yields superior clustering results when mining arbitrarily-shaped clusters in data. However, it is not robust against noises and outliers in the data. There are two main problems with the grouping principle: first, a single object that is far away from all other objects defines a separate cluster, and second, two connected clusters would be regarded as two parts of one cluster. In order to solve such problems, we propose robust minimum spanning tree (MST)-based clustering algorithm in this letter. First, we separate the connected objects by applying a density-based coarsening phase, resulting in a low-rank matrix in which the element denotes the supernode by combining a set of nodes. Then a greedy method is presented to partition those supernodes through working on the low-rank matrix. Instead of removing the longest edges from MST, our algorithm groups the data set based on the minimax similarity. Finally, the assignment of all data points can be achieved through their corresponding supernodes. Experimental results on many synthetic and real-world data sets show that our algorithm consistently outperforms compared clustering algorithms.

The angular nature of road networks

Road networks are characterised by several structural and geometrical properties. The topological structure determines partially the hierarchical arrangement of roads, but since these are networks that are spatially constrained, geometrical properties play a fundamental role in determining the network’s behaviour, characterising the influence of each of the street segments on the system. In this work, we apply percolation theory to the UK’s road network using the relative angle between street segments as the occupation probability. The appearance of the spanning cluster is marked by a phase transition, indicating that the system behaves in a critical way. Computing Shannon’s entropy of the cluster sizes, different stages of the percolation process can be discerned, and these indicate that roads integrate to the giant cluster in a hierarchical manner. This is used to construct a hierarchical index that serves to classify roads in terms of their importance. The obtained classification is in very good correspondence with the official designations of roads. This methodology hence provides a framework to consistently extract the main skeleton of an urban system and to further classify each road in terms of its hierarchical importance within the system.

Unification of theoretical approaches for epidemic spreading on complex networks

Models of epidemic spreading on complex networks have attracted great attention among researchers in physics, mathematics, and epidemiology due to their success in predicting and controlling scenarios of epidemic spreading in real-world scenarios. To understand the interplay between epidemic spreading and the topology of a contact network, several outstanding theoretical approaches have been developed. An accurate theoretical approach describing the spreading dynamics must take both the network topology and dynamical correlations into consideration at the expense of increasing the complexity of the equations. In this short survey we unify the most widely used theoretical approaches for epidemic spreading on complex networks in terms of increasing complexity, including the mean-field, the heterogeneous mean-field, the quench mean-field, dynamical message-passing, link percolation, and pairwise approximation. We build connections among these approaches to provide new insights into developing an accurate theoretical approach to spreading dynamics on complex networks.

Dynamics on networks: competition of temporal and topological correlations

Links in many real-world networks activate and deactivate in correspondence to the sporadic interactions between the elements of the system. The activation patterns may be irregular or bursty and play an important role on the dynamics of processes taking place in the network. Information or disease spreading in networks are paradigmatic examples of this situation. Besides burstiness, several correlations may appear in the process of link activation: memory effects imply temporal correlations, but also the existence of communities in the network may mediate the activation patterns of internal an external links. Here we study the competition of topological and temporal correlations in link activation and how they affect the dynamics of systems running on the network. Interestingly, both types of correlations by separate have opposite effects: one (topological) delays the dynamics of processes on the network, while the other (temporal) accelerates it. When they occur together, our results show that the direction and intensity of the final outcome depends on the competition in a non trivial way.

Uncovering the essential links in online commercial networks

Recommender systems are designed to effectively support individuals' decision-making process on various web sites. It can be naturally represented by a user-object bipartite network, where a link indicates that a user has collected an object. Recently, research on the information backbone has attracted researchers' interests, which is a sub-network with fewer nodes and links but carrying most of the relevant information. With the backbone, a system can generate satisfactory recommenda- tions while saving much computing resource. In this paper, we propose an enhanced topology-aware method to extract the information backbone in the bipartite network mainly based on the information of neighboring users and objects. Our backbone extraction method enables the recommender systems achieve more than 90% of the accuracy of the top-L recommendation, however, consuming only 20% links. The experimental results show that our method outperforms the alternative backbone extraction methods. Moreover, the structure of the information backbone is studied in detail. Finally, we highlight that the information backbone is one of the most important properties of the bipartite network, with which one can significantly improve the efficiency of the recommender system.

Percolation thresholds for discrete-continuous models with nonuniform probabilities of bond formation

We introduce a class of discrete-continuous percolation models and an efficient Monte Carlo algorithm for computing their properties. The class is general enough to include well-known discrete and continuous models as special cases. We focus on a particular example of such a model, a nanotube model of disintegration of activated carbon. We calculate its exact critical threshold in two dimensions and obtain a Monte Carlo estimate in three dimensions. Furthermore, we use this example to analyze and characterize the efficiency of our algorithm, by computing critical exponents and properties, finding that it compares favorably to well-known algorithms for simpler systems.

Hierarchical clustering in minimum spanning trees

The identification of clusters or communities in complex networks is a reappearing problem. The minimum spanning tree (MST), the tree connecting all nodes with minimum total weight, is regarded as an important transport backbone of the original weighted graph. We hypothesize that the clustering of the MST reveals insight in the hierarchical structure of weighted graphs. However, existing theories and algorithms have difficulties to define and identify clusters in trees. Here, we first define clustering in trees and then propose a tree agglomerative hierarchical clustering (TAHC) method for the detection of clusters in MSTs. We then demonstrate that the TAHC method can detect clusters in artificial trees, and also in MSTs of weighted social networks, for which the clusters are in agreement with the previously reported clusters of the original weighted networks. Our results therefore not only indicate that clusters can be found in MSTs, but also that the MSTs contain information about the underlying clusters of the original weighted network.

Percolation transition in dynamical traffic network with evolving critical bottlenecks

A critical phenomenon is an intrinsic feature of traffic dynamics, during which transition between isolated local flows and global flows occurs. However, very little attention has been given to the question of how the local flows in the roads are organized collectively into a global city flow. Here we characterize this organization process of traffic as "traffic percolation," where the giant cluster of local flows disintegrates when the second largest cluster reaches its maximum. We find in real-time data of city road traffic that global traffic is dynamically composed of clusters of local flows, which are connected by bottleneck links. This organization evolves during a day with different bottleneck links appearing in different hours, but similar in the same hours in different days. A small improvement of critical bottleneck roads is found to benefit significantly the global traffic, providing a method to improve city traffic with low cost. Our results may provide insights on the relation between traffic dynamics and percolation, which can be useful for efficient transportation, epidemic control, and emergency evacuation.

The loss of efficiency caused by agents' uncoordinated routing in transport networks

Large-scale daily commuting data were combined with detailed geographical information system (GIS) data to analyze the loss of transport efficiency caused by drivers' uncoordinated routing in urban road networks. We used Price of Anarchy (POA) to quantify the loss of transport efficiency and found that both volume and distribution of human mobility demand determine the POA. In order to reduce POA, a small number of highways require considerable decreases in traffic, and their neighboring arterial roads need to attract more traffic. The magnitude of the adjustment in traffic flow can be estimated using the fundamental measure traffic flow only, which is widely available and easy to collect. Surprisingly, the most congested roads or the roads with largest traffic flow were not those requiring the most reduction of traffic. This study can offer guidance for the optimal control of urban traffic and facilitate improvements in the efficiency of transport networks.

Encapsulating urban traffic rhythms into road networks

Using road GIS (geographical information systems) data and travel demand data for two U.S. urban areas, the dynamical driver sources of each road segment were located. A method to target road clusters closely related to urban traffic congestion was then developed to improve road network efficiency. The targeted road clusters show different spatial distributions at different times of a day, indicating that our method can encapsulate dynamical travel demand information into the road networks. As a proof of concept, when we lowered the speed limit or increased the capacity of road segments in the targeted road clusters, we found that both the number of congested roads and extra travel time were effectively reduced. In addition, the proposed modeling framework provided new insights on the optimization of transport efficiency in any infrastructure network with a specific supply and demand distribution.

Efficient immunization strategies to prevent financial contagion

Many immunization strategies have been proposed to prevent infectious viruses from spreading through a network. In this work, we study efficient immunization strategies to prevent a default contagion that might occur in a financial network. An essential difference from the previous studies on immunization strategy is that we take into account the possibility of serious side effects. Uniform immunization refers to a situation in which banks are “vaccinated” with a common low-risk asset. The riskiness of immunized banks will decrease significantly, but the level of systemic risk may increase due to the de-diversification effect. To overcome this side effect, we propose another immunization strategy, called counteractive immunization, which prevents pairs of banks from failing simultaneously. We find that counteractive immunization can efficiently reduce systemic risk without altering the riskiness of individual banks.

Classification of transport backbones of complex networks

Transport properties in random and scale-free (SF) networks are studied by analyzing the betweenness centrality (BC) distribution P(B) in the minimum spanning trees (MSTs) and infinite incipient percolation clusters (IIPCs) of the networks. It is found that P(B) in MSTs scales as P(B)∼B(-δ). The obtained values of δ are classified into two different categories, δ≃1.6 and δ≃2.0. Using the mapping between BC and the branch size of tree structures, it is proved that δ in MSTs which are close to critical trees is 1.6. In contrast, δ in MSTs which are supercritical trees is shown to be 2.0. We also find δ=1.5 in IIPCs, which is a natural result because IIPC is physically critical. Based on the results in MSTs, a physical reason why δ≥2 in the original networks is suggested.

Extracting the information backbone in online system

Information overload is a serious problem in modern society and many solutions such as recommender system have been proposed to filter out irrelevant information. In the literature, researchers have been mainly dedicated to improving the recommendation performance (accuracy and diversity) of the algorithms while they have overlooked the influence of topology of the online user-object bipartite networks. In this paper, we find that some information provided by the bipartite networks is not only redundant but also misleading. With such “less can be more” feature, we design some algorithms to improve the recommendation performance by eliminating some links from the original networks. Moreover, we propose a hybrid method combining the time-aware and topology-aware link removal algorithms to extract the backbone which contains the essential information for the recommender systems. From the practical point of view, our method can improve the performance and reduce the computational time of the recommendation system, thus improving both of their effectiveness and efficiency.

Understanding road usage patterns in urban areas

In this paper, we combine the most complete record of daily mobility, based on large-scale mobile phone data, with detailed Geographic Information System (GIS) data, uncovering previously hidden patterns in urban road usage. We find that the major usage of each road segment can be traced to its own - surprisingly few - driver sources. Based on this finding we propose a network of road usage by defining a bipartite network framework, demonstrating that in contrast to traditional approaches, which define road importance solely by topological measures, the role of a road segment depends on both: its betweeness and its degree in the road usage network. Moreover, our ability to pinpoint the few driver sources contributing to the major traffic flow allows us to create a strategy that achieves a significant reduction of the travel time across the entire road system, compared to a benchmark approach.

Robust classification of salient links in complex networks

Complex networks in natural, social and technological systems generically exhibit an abundance of rich information. Extracting meaningful structural features from data is one of the most challenging tasks in network theory. Many methods and concepts have been proposed to address this problem such as centrality statistics, motifs, community clusters and backbones, but such schemes typically rely on external and arbitrary parameters. It is unknown whether generic networks permit the classification of elements without external intervention. Here we show that link salience is a robust approach to classifying network elements based on a consensus estimate of all nodes. A wide range of empirical networks exhibit a natural, network-implicit classification of links into qualitatively distinct groups, and the salient skeletons have generic statistical properties. Salience also predicts essential features of contagion phenomena on networks, and points towards a better understanding of universal features in empirical networks that are masked by their complexity.

Competition for shortest paths on sparse graphs

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised.

Epidemic spreading in weighted networks: an edge-based mean-field solution

Weight distribution greatly impacts the epidemic spreading taking place on top of networks. This paper presents a study of a susceptible-infected-susceptible model on regular random networks with different kinds of weight distributions. Simulation results show that the more homogeneous weight distribution leads to higher epidemic prevalence, which, unfortunately, could not be captured by the traditional mean-field approximation. This paper gives an edge-based mean-field solution for general weight distribution, which can quantitatively reproduce the simulation results. This method could be applied to characterize the nonequilibrium steady states of dynamical processes on weighted networks.

Information filtering in complex weighted networks

Many systems in nature, society, and technology can be described as networks, where the vertices are the system's elements, and edges between vertices indicate the interactions between the corresponding elements. Edges may be weighted if the interaction strength is measurable. However, the full network information is often redundant because tools and techniques from network analysis do not work or become very inefficient if the network is too dense, and some weights may just reflect measurement errors and need to be be discarded. Moreover, since weight distributions in many complex weighted networks are broad, most of the weight is concentrated among a small fraction of all edges. It is then crucial to properly detect relevant edges. Simple thresholding would leave only the largest weights, disrupting the multiscale structure of the system, which is at the basis of the structure of complex networks and ought to be kept. In this paper we propose a weight-filtering technique based on a global null model [Global Statistical Significance (GloSS) filter], keeping both the weight distribution and the full topological structure of the network. The method correctly quantifies the statistical significance of weights assigned independently to the edges from a given distribution. Applications to real networks reveal that the GloSS filter is indeed able to identify relevant connections between vertices.

Spanning trees in a fractal scale-free lattice

Spanning trees provide crucial insight into the origin of fractality in fractal scale-free networks. In this paper, we present the number of spanning trees in a particular fractal scale-free lattice (network). We first study analytically the topological characteristics of the lattice and show that it is simultaneously scale-free, highly clustered, "large-world," fractal, and disassortative. Any previous model does not have all the properties as the studied one. Then, by using the renormalization group technique we derive analytically the number of spanning trees in the network under consideration, based on which we also determine the entropy for the spanning trees of the network. These results shed light on understanding the structural characteristics of and dynamical processes on scale-free networks with fractality. Moreover, our method and process for employing the decimation technique to enumerate spanning trees are general and can be easily extended to other deterministic media with self-similarity.

Spectral dimensions of hierarchical scale-free networks with weighted shortcuts

Spectral dimensions have been widely used to understand transport properties on regular and fractal lattices. However, they have received little attention with regard to complex networks such as scale-free and small-world networks. Here, we study the spectral dimension and the return-to-origin probability of random walks on hierarchical scale-free networks, which can be either fractal or nonfractal depending on the weight of the shortcuts. Applying the renormalization-group (RG) approach to a Gaussian model, we obtain the exact spectral dimension. While the spectral dimension varies between 1 and 2 for the fractal case, it remains at 2, independent of the variation in the network structure, for the nonfractal case. The crossover behavior between the two cases is studied by carrying out the RG flow analysis. The analytical results are confirmed by simulation results and their implications for the architecture of complex systems are discussed.

Theory of minimum spanning trees. I. Mean-field theory and strongly disordered spin-glass model

The minimum spanning tree (MST) is a combinatorial optimization problem: given a connected graph with a real weight ("cost") on each edge, find the spanning tree that minimizes the sum of the total cost of the occupied edges. We consider the random MST, in which the edge costs are (quenched) independent random variables. There is a strongly disordered spin-glass model due to Newman and Stein [Phys. Rev. Lett. 72, 2286 (1994)], which maps precisely onto the random MST. We study scaling properties of random MSTs using a relation between Kruskal's greedy algorithm for finding the MST, and bond percolation. We solve the random MST problem on the Bethe lattice (BL) with appropriate wired boundary conditions and calculate the fractal dimension D=6 of the connected components. Viewed as a mean-field theory, the result implies that on a lattice in Euclidean space of dimension d , there are of order W(d-D) large connected components of the random MST inside a window of size W , and that d=d(c)=D=6 is a critical dimension. This differs from the value 8 suggested by Newman and Stein. We also critique the original argument for 8, and provide an improved scaling argument that again yields d(c)=6 . The result implies that the strongly disordered spin-glass model has many ground states for d>6 , and only of order one below six. The results for MSTs also apply on the Poisson-weighted infinite tree, which is a mean-field approach to the continuum model of MSTs in Euclidean space, and is a limit of the BL. In a companion paper we develop an epsilon=6-d expansion for the random MST on critical percolation clusters.

Better synchronizability in generalized adaptive networks

In this paper, to study the interaction between network structure and dynamical property in the context of synchronization, a previously proposed adaptive coupling method is generalized where the coupling strength of a node from its neighbors not only develops adaptively according to the local synchronization property between the node and its neighbors (dynamical part) but also is modulated by its local structure, degree of the node with the form 1/k(i)(alpha) (topological part). We can show both numerically and analytically that the input coupling strength of the network after adaptation displays a power-law dependence on the degree, k(-theta), where the exponent theta is controlled by alpha as theta=(1+alpha)/2. Compared to the original adaptive coupling method, after the addition of modulation, the distribution of the node's intensity is tunable and can be more homogenous with alpha approximately 1, which results in better synchronizability. It is also found that the synchronization time can shrink greatly. Our theoretical work in the context of synchronization provides not only a deeper understanding of the interplay between structure and dynamics in real world systems, such as opinion formation and concensus, but also potential approaches to manipulate the global collective dynamics through local adaptive control.

Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold

Continuing the program begun by the authors in a previous paper, we develop an exact low-density expansion for the random minimum spanning tree (MST) on a finite graph and use it to develop a continuum perturbation expansion for the MST on critical percolation clusters in space dimension d . The perturbation expansion is proved to be renormalizable in d=6 dimensions. We consider the fractal dimension D(p) of paths on the latter MST; our previous results lead us to predict that D(p)=2 for d>d(c)=6 . Using a renormalization-group approach, we confirm the result for d>6 and calculate D(p) to first order in epsilon=6-d for d<6 using the connection with critical percolation, with the result D(p)=2-epsilon/7+O(epsilon(2)) .

Multiscale mobility networks and the spatial spreading of infectious diseases

Among the realistic ingredients to be considered in the computational modeling of infectious diseases, human mobility represents a crucial challenge both on the theoretical side and in view of the limited availability of empirical data. To study the interplay between short-scale commuting flows and long-range airline traffic in shaping the spatiotemporal pattern of a global epidemic we (i) analyze mobility data from 29 countries around the world and find a gravity model able to provide a global description of commuting patterns up to 300 kms and (ii) integrate in a worldwide-structured metapopulation epidemic model a timescale-separation technique for evaluating the force of infection due to multiscale mobility processes in the disease dynamics. Commuting flows are found, on average, to be one order of magnitude larger than airline flows. However, their introduction into the worldwide model shows that the large-scale pattern of the simulated epidemic exhibits only small variations with respect to the baseline case where only airline traffic is considered. The presence of short-range mobility increases, however, the synchronization of subpopulations in close proximity and affects the epidemic behavior at the periphery of the airline transportation infrastructure. The present approach outlines the possibility for the definition of layered computational approaches where different modeling assumptions and granularities can be used consistently in a unifying multiscale framework.

Extracting the multiscale backbone of complex weighted networks

A large number of complex systems find a natural abstraction in the form of weighted networks whose nodes represent the elements of the system and the weighted edges identify the presence of an interaction and its relative strength. In recent years, the study of an increasing number of large-scale networks has highlighted the statistical heterogeneity of their interaction pattern, with degree and weight distributions that vary over many orders of magnitude. These features, along with the large number of elements and links, make the extraction of the truly relevant connections forming the network's backbone a very challenging problem. More specifically, coarse-graining approaches and filtering techniques come into conflict with the multiscale nature of large-scale systems. Here, we define a filtering method that offers a practical procedure to extract the relevant connection backbone in complex multiscale networks, preserving the edges that represent statistically significant deviations with respect to a null model for the local assignment of weights to edges. An important aspect of the method is that it does not belittle small-scale interactions and operates at all scales defined by the weight distribution. We apply our method to real-world network instances and compare the obtained results with alternative backbone extraction techniques.

Localizations on complex networks

We study the structural characteristics of complex networks using the representative eigenvectors of the adjacent matrix. The probability distribution function of the components of the representative eigenvectors are proposed to describe the localization on networks where the Euclidean distance is invalid. Several quantities are used to describe the localization properties of the representative states, such as the participation ratio, the structural entropy, and the probability distribution function of the nearest neighbor level spacings for spectra of complex networks. Whole-cell networks in the real world and the Watts-Strogatz small-world and Barabasi-Albert scale-free networks are considered. The networks have nontrivial localization properties due to the nontrivial topological structures. It is found that the ascending-order-ranked series of the occurrence probabilities at the nodes behave generally multifractally. This characteristic can be used as a structural measure of complex networks.

Betweenness centrality in a weighted network

When transport in networks follows the shortest paths, the union of all shortest path trees G union or logical sum SPT can be regarded as the "transport overlay network." Overlay networks such as peer-to-peer networks or virtual private networks can be considered as a subgraph of G union or logical sum SPT. The traffic through the network is examined by the betweenness Bl of links in the overlay G union or logical sum SPT. The strength of disorder can be controlled by, e.g., tuning the extreme value index alpha of the independent and identically distributed polynomial link weights. In the strong disorder limit (alpha-->0), all transport flows over a critical backbone, the minimum spanning tree (MST). We investigate the betweenness distributions of wide classes of trees, such as the MST of those well-known network models and of various real-world complex networks. All these trees with different degree distributions (e.g., uniform, exponential, or power law) are found to possess a power law betweenness distribution Pr[Bl=j] approximately j(-c). The exponent c seems to be positively correlated with the degree variance of the tree and to be insensitive of the size N of a network. In the weak disorder regime, transport in the network traverses many links. We show that a link with smaller link weight tends to carry more traffic. This negative correlation between link weight and betweenness depends on alpha and the structure of the underlying topology.

Transport on weighted networks: When the correlations are independent of the degree

Most real-world networks are weighted graphs with the weight of the edges reflecting the relative importance of the connections. In this work, we study nondegree dependent correlations between edge weights, generalizing thus the correlations beyond the degree dependent case. We propose a simple method to introduce weight-weight correlations in topologically uncorrelated graphs. This allows us to test different measures to discriminate between the different correlation types and to quantify their intensity. We also discuss here the effect of weight correlations on the transport properties of the networks, showing that positive correlations dramatically improve transport. Finally, we give two examples of real-world networks (social and transport graphs) in which weight-weight correlations are present.

Brain, music, and non-Poisson renewal processes

In this paper we show that both music composition and brain function, as revealed by the electroencephalogram (EEG) analysis, are renewal non-Poisson processes living in the nonergodic dominion. To reach this important conclusion we process the data with the minimum spanning tree method, so as to detect significant events, thereby building a sequence of times, which is the time series to analyze. Then we show that in both cases, EEG and music composition, these significant events are the signature of a non-Poisson renewal process. This conclusion is reached using a technique of statistical analysis recently developed by our group, the aging experiment (AE). First, we find that in both cases the distances between two consecutive events are described by nonexponential histograms, thereby proving the non-Poisson nature of these processes. The corresponding survival probabilities Psi(t) are well fitted by stretched exponentials [Psi(t) proportional, variant exp (-(gammat){alpha}) , with 0.5<alpha<1 .] The second step rests on the adoption of AE, which shows that these are renewal processes. We show that the stretched exponential, due to its renewal character, is the emerging tip of an iceberg, whose underwater part has slow tails with an inverse power law structure with power index mu=1+alpha. Adopting the AE procedure we find that both EEG and music composition yield mu<2. On the basis of the recently discovered complexity matching effect, according to which a complex system S with mu{S}<2 responds only to a complex driving signal P with mu{P}< or =mu{S}, we conclude that the results of our analysis may explain the influence of music on the human brain.