Vertex betweenness centrality is a metric that seeks to quantify a sense of the importance of a vertex in a network in terms of its ‘control’ on the flow of information along geodesic paths ...throughout the network. Two natural ways to extend vertex betweenness centrality to sets of vertices are (i) in terms of geodesic paths that pass through at least one of the vertices in the set, and (ii) in terms of geodesic paths that pass through all vertices in the set. The former was introduced by Everett and Borgatti Everett, M., Borgatti, S., 1999. The centrality of groups and classes. Journal of Mathematical Sociology 23 (3), 181–201, and called
group betweenness centrality. The latter, which we call
co-betweenness centrality here, has not been considered formally in the literature until now, to the best of our knowledge. In this paper, we show that these two notions of centrality are in fact intimately related and, furthermore, that this relationship may be exploited to obtain deeper insight into both. In particular, we provide an expansion for group betweenness in terms of increasingly higher orders of co-betweenness, in a manner analogous to the Taylor series expansion of a mathematical function in calculus. We then demonstrate the utility of this expansion by using it to construct analytic lower and upper bounds for group betweenness that involve only simple combinations of (i) the betweenness of individual vertices in the group, and (ii) the co-betweenness of pairs of these vertices. Accordingly, we argue that the latter quantity, i.e., pairwise co-betweenness, is itself a fundamental quantity of some independent interest, and we present a computationally efficient algorithm for its calculation, which extends the algorithm of Brandes Brandes, U., 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 163 in a natural manner. Applications are provided throughout, using a handful of different communication networks, which serve to illustrate the way in which our mathematical contributions allow for insight to be gained into the interaction of network structure, coalitions, and information flow in social networks.
Disentangling collective trends from local dynamics Barthélemy, Marc; Nadal, Jean-Pierre; Berestycki, Henri
Proceedings of the National Academy of Sciences - PNAS,
04/2010, Letnik:
107, Številka:
17
Journal Article
Recenzirano
Odprti dostop
A single social phenomenon (such as crime, unemployment, or birthrate) can be observed through temporal series corresponding to units at different levels (i.e., cities, regions, and countries). Units ...at a given local level may follow a collective trend imposed by external conditions, but also may display fluctuations of purely local origin. The local behavior is usually computed as the difference between the local data and a global average (e.g, a national average), a viewpoint that can be very misleading. We propose here a method for separating the local dynamics from the global trend in a collection of correlated time series. We take an independent component analysis approach in which we do not assume a small average local contribution in contrast with previously proposed methods. We first test our method on synthetic series generated by correlated random walkers. We then consider crime rate series (in the United States and France) and the evolution of obesity rate in the United States, which are two important examples of societal measures. For the crime rates in the United States, we observe large fluctuations in the transition period of mid-70s during which crime rates increased significantly, whereas since the 80s, the state crime rates are governed by external factors and the importance of local specificities being decreasing. In the case of obesity, our method shows that external factors dominate the evolution of obesity since 2000, and that different states can have different dynamical behavior even if their obesity prevalence is similar.
In our global world, the increasing complexity of social relations and transport infrastructures are key factors in the spread of epidemics. In recent years, the increasing availability of computer ...power has enabled both to obtain reliable data allowing one to quantify the complexity of the networks on which epidemics may propagate and to envision computational tools able to tackle the analysis of such propagation phenomena. These advances have put in evidence the limits of homogeneous assumptions and simple spatial diffusion approaches, and stimulated the inclusion of complex features and heterogeneities relevant in the description of epidemic diffusion. In this paper, we review recent progresses that integrate complex systems and networks analysis with epidemic modelling and focus on the impact of the various complex features of real systems on the dynamics of epidemic spreading.
We present a thorough inspection of the dynamical behavior of epidemic phenomena in populations with complex and heterogeneous connectivity patterns. We show that the growth of the epidemic ...prevalence is virtually instantaneous in all networks characterized by diverging degree fluctuations, independently of the structure of the connectivity correlation functions characterizing the population network. By means of analytical and numerical results, we show that the outbreak time evolution follows a precise hierarchical dynamics. Once reached the most highly connected hubs, the infection pervades the network in a progressive cascade across smaller degree classes. Finally, we show the influence of the initial conditions and the relevance of statistical results in single case studies concerning heterogeneous networks. The emerging theoretical framework appears of general interest in view of the recently observed abundance of natural networks with complex topological features and might provide useful insights for the development of adaptive strategies aimed at epidemic containment.
Scaling in transportation networks Louf, Rémi; Roth, Camille; Barthelemy, Marc
PloS one,
07/2014, Letnik:
9, Številka:
7
Journal Article
Recenzirano
Odprti dostop
Subway systems span most large cities, and railway networks most countries in the world. These networks are fundamental in the development of countries and their cities, and it is therefore crucial ...to understand their formation and evolution. However, if the topological properties of these networks are fairly well understood, how they relate to population and socio-economical properties remains an open question. We propose here a general coarse-grained approach, based on a cost-benefit analysis that accounts for the scaling properties of the main quantities characterizing these systems (the number of stations, the total length, and the ridership) with the substrate's population, area and wealth. More precisely, we show that the length, number of stations and ridership of subways and rail networks can be estimated knowing the area, population and wealth of the underlying region. These predictions are in good agreement with data gathered for about 140 subway systems and more than 50 railway networks in the world. We also show that train networks and subway systems can be described within the same framework, but with a fundamental difference: while the interstation distance seems to be constant and determined by the typical walking distance for subways, the interstation distance for railways scales with the number of stations.
We review the main tools which allow for the statistical characterization of weighted networks. We then present two case studies, the airline connection network and the scientific collaboration ...network which are representatives of critical infrastructure and social system, respectively. The main empirical results are (i) the broad distributions of various quantities and (ii) the existence of weight-topology correlations. These measurements show that weights are relevant and that in general the modeling of complex networks must go beyond topology. We review a model which provides an explanation for the features observed in several real-world networks. This model of weighted network formation relies on the dynamical coupling between topology and weights, considering the rearrangement of new links are introduced in the system.
One of the most important features of spatial networks—such as transportation networks, power grids, the Internet, and neural networks—is the existence of a cost associated with the length of links. ...Such a cost has a profound influence on the global structure of these networks, which usually display a hierarchical spatial organization. The link between local constraints and large-scale structure is not elucidated, however, and we introduce here a generic model for the growth of spatial networks based on the general concept of cost–benefit analysis. This model depends essentially on a single scale and produces a family of networks that range from the star graph to the minimum spanning tree and are characterized by a continuously varying exponent. We show that spatial hierarchy emerges naturally, with structures composed of various hubs controlling geographically separated service areas, and appears as a large-scale consequence of local cost–benefit considerations. Our model thus provides the basic building blocks for a better understanding of the evolution of spatial networks and their properties. We also find that, surprisingly, the average detour is minimal in the intermediate regime as a result of a large diversity in link lengths. Finally, we estimate the important parameters for various world railway networks and find that, remarkably, they all fall in this intermediate regime, suggesting that spatial hierarchy is a crucial feature for these systems and probably possesses an important evolutionary advantage.
We review measures of street network structure proposed in the recent literature, establish their relevance to practice, and identify open challenges facing researchers. These measures’ empirical ...values vary substantially across world regions and development eras, indicating street networks’ geometric and topological heterogeneity.
Engineering multilayer networks that efficiently connect sets of points in space is a crucial task in all practical applications that concern the transport of people or the delivery of goods. ...Unfortunately, our current theoretical understanding of the shape of such optimal transport networks is quite limited. Not much is known about how the topology of the optimal network changes as a function of its size, the relative efficiency of its layers, and the cost of switching between layers. Here, we show that optimal networks undergo sharp transitions from symmetric to asymmetric shapes, indicating that it is sometimes better to avoid serving a whole area to save on switching costs. Also, we analyze the real transportation networks of the cities of Atlanta, Boston, and Toronto using our theoretical framework and find that they are farther away from their optimal shapes as traffic congestion increases.
Spatial structure of city population growth Reia, Sandro M.; Rao, P. Suresh C.; Barthelemy, Marc ...
Nature communications,
10/2022, Letnik:
13, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Abstract
We show here that population growth, resolved at the county level, is spatially heterogeneous both among and within the U.S. metropolitan statistical areas. Our analysis of data for over ...3,100 U.S. counties reveals that annual population flows, resulting from domestic migration during the 2015–2019 period, are much larger than natural demographic growth, and are primarily responsible for this heterogeneous growth. More precisely, we show that intra-city flows are generally along a negative population density gradient, while inter-city flows are concentrated in high-density core areas. Intra-city flows are anisotropic and generally directed towards external counties of cities, driving asymmetrical urban sprawl. Such domestic migration dynamics are also responsible for tempering local population shocks by redistributing inflows within a given city. This spill-over effect leads to a smoother population dynamics at the county level, in contrast to that observed at the city level. Understanding the spatial structure of domestic migration flows is a key ingredient for analyzing their drivers and consequences, thus representing a crucial knowledge for urban policy makers and planners.
PDF
