ABSTRACT: Betweenness centrality quantifies the importance of a vertex for the information flow in a network. The standard betweenness centrality applies to static single-layer networks, but many real world networks are both dynamic and made of several layers. We propose a definition of betweenness centrality for temporal multiplexes. This definition accounts for the topological and temporal structure and for the duration of paths in the determination of the shortest paths. We propose an algorithm to compute the new metric using a mapping to a static graph. We apply the metric to a dataset of [Formula: see text]k European flights and compare the results with those obtained with static or single-layer metrics. The differences in the airports rankings highlight the importance of considering the temporal multiplex structure and an appropriate distance metric.
Project description:This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.
Project description:Unlike many traditional measures of centrality based on paths that do not allow any repeated nodes or lines, we propose a new measure of centrality based on walks, walk-betweenness, that allows any number of repeated nodes or lines. To illustrate the value of walk-betweenness, we examine the transmission of syphilis in Chicago area and the diffusion of microfinance in 43 rural Indian villages. Walk-betweenness allows us to identify hidden bridging communities in Chicago that were essential in the transmission dynamics. We also find that village leaders with high walk-betweenness are more likely to accelerate the rate of microfinance take-up among their followers, outperforming other traditional centrality measures in regression analyses.
Project description:Betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node. Most of real-world large networks display a hierarchical community structure, and their betweenness computation possesses rather high complexity. Here we propose a new hierarchical decomposition approach to speed up the betweenness computation of complex networks. The advantage of this new method is its effective utilization of the local structural information from the hierarchical community. The presented method can significantly speed up the betweenness calculation. This improvement is much more evident in those networks with numerous homogeneous communities. Furthermore, the proposed method features a parallel structure, which is very suitable for parallel computation. Moreover, only a small amount of additional computation is required by our method, when small changes in the network structure are restricted to some local communities. The effectiveness of the proposed method is validated via the examples of two real-world power grids and one artificial network, which demonstrates that the performance of the proposed method is superior to that of the traditional method.
Project description: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.
Project description:Recent developments in network theory have allowed for the study of the structure and function of the human brain in terms of a network of interconnected components. Among the many nodes that form a network, some play a crucial role and are said to be central within the network structure. Central nodes may be identified via centrality metrics, with degree, betweenness, and eigenvector centrality being three of the most popular measures. Degree identifies the most connected nodes, whereas betweenness centrality identifies those located on the most traveled paths. Eigenvector centrality considers nodes connected to other high degree nodes as highly central. In the work presented here, we propose a new centrality metric called leverage centrality that considers the extent of connectivity of a node relative to the connectivity of its neighbors. The leverage centrality of a node in a network is determined by the extent to which its immediate neighbors rely on that node for information. Although similar in concept, there are essential differences between eigenvector and leverage centrality that are discussed in this manuscript. Degree, betweenness, eigenvector, and leverage centrality were compared using functional brain networks generated from healthy volunteers. Functional cartography was also used to identify neighborhood hubs (nodes with high degree within a network neighborhood). Provincial hubs provide structure within the local community, and connector hubs mediate connections between multiple communities. Leverage proved to yield information that was not captured by degree, betweenness, or eigenvector centrality and was more accurate at identifying neighborhood hubs. We propose that this metric may be able to identify critical nodes that are highly influential within the network.
Project description:The study of connectivity patterns in networks has brought novel insights across diverse fields ranging from neurosciences to epidemic spreading or climate. In this context, betweenness centrality has demonstrated to be a very effective measure to identify nodes that act as focus of congestion, or bottlenecks, in the network. However, there is not a way to define betweenness outside the network framework. By analytically linking dynamical systems and network theory, we provide a trajectory-based formulation of betweenness, called Lagrangian betweenness, as a function of Lyapunov exponents. This extends the concept of betweenness beyond the context of network theory relating hyperbolic points and heteroclinic connections in any dynamical system to the structural bottlenecks of the network associated with it. Using modeled and observational velocity fields, we show that such bottlenecks are present and surprisingly persistent in the oceanic circulation across different spatio-temporal scales and we illustrate the role of these areas in driving fluid transport over vast oceanic regions. Analyzing plankton abundance data from the Kuroshio region of the Pacific Ocean, we find significant spatial correlations between measures of diversity and betweenness, suggesting promise for ecological applications.
Project description:This paper begins to build a theoretical framework that would enable the pharmaceutical industry to use network complexity measures as a way to identify drug targets. The variability of a betweenness measure for a network node is examined through different methods of network perturbation. Our results indicate a robustness of betweenness centrality in the identification of target genes.
Project description:Locating influential nodes in temporal networks has attracted a lot of attention as data driven and diverse applications. Classic works either looked at analysing static networks or placed too much emphasis on the topological information but rarely highlighted the dynamics. In this paper, we take account the network dynamics and extend the concept of Dynamic-Sensitive centrality to temporal network. According to the empirical results on three real-world temporal networks and a theoretical temporal network for susceptible-infected-recovered (SIR) models, the temporal Dynamic-Sensitive centrality (TDC) is more accurate than both static versions and temporal versions of degree, closeness and betweenness centrality. As an application, we also use TDC to analyse the impact of time-order on spreading dynamics, we find that both topological structure and dynamics contribute the impact on the spreading influence of nodes, and the impact of time-order on spreading influence will be stronger when spreading rate b deviated from the epidemic threshold bc, especially for the temporal scale-free networks.
Project description:The most important goals of brain network analyses are to (a) detect pivotal regions and connections that contribute to disproportionate communication flow, (b) integrate global information, and (c) increase the brain network efficiency. Most centrality measures assume that information propagates in networks with the shortest connection paths, but this assumption is not true for most real networks given that information in the brain propagates through all possible paths. This study presents a methodological pipeline for identifying influential nodes and edges in human brain networks based on the self-regulating biological concept adopted from the Physarum model, thereby allowing the identification of optimal paths that are independent of the stated assumption. Network hubs and bridges were investigated in structural brain networks using the Physarum model. The optimal paths and fluid flow were used to formulate the Physarum centrality measure. Most network hubs and bridges are overlapped to some extent, but those based on Physarum centrality contain local and global information in the superior frontal, anterior cingulate, middle temporal gyrus, and precuneus regions. This approach also reduced individual variation. Our results suggest that the Physarum centrality presents a trade-off between the degree and betweenness centrality measures.
Project description:BACKGROUND: Network visualization would serve as a useful first step for analysis. However, current graph layout algorithms for biological pathways are insensitive to biologically important information, e.g. subcellular localization, biological node and graph attributes, or/and not available for large scale networks, e.g. more than 10000 elements. RESULTS: To overcome these problems, we propose the use of a biologically important graph metric, betweenness, a measure of network flow. This metric is highly correlated with many biological phenomena such as lethality and clusters. We devise a new fast parallel algorithm calculating betweenness to minimize the preprocessing cost. Using this metric, we also invent a node and edge betweenness based fast layout algorithm (BFL). BFL places the high-betweenness nodes to optimal positions and allows the low-betweenness nodes to reach suboptimal positions. Furthermore, BFL reduces the runtime by combining a sequential insertion algorim with betweenness. For a graph with n nodes, this approach reduces the expected runtime of the algorithm to O(n2) when considering edge crossings, and to O(n log n) when considering only density and edge lengths. CONCLUSION: Our BFL algorithm is compared against fast graph layout algorithms and approaches requiring intensive optimizations. For gene networks, we show that our algorithm is faster than all layout algorithms tested while providing readability on par with intensive optimization algorithms. We achieve a 1.4 second runtime for a graph with 4000 nodes and 12000 edges on a standard desktop computer.