Betweenness Preference

Many complex systems exhibit dynamically changing interaction topologies. In order to simplify their analysis such systems are typically studied using static, time-aggregated networks. Recent works have argued that properties of dynamic processes evolving on complex networks change significantly when the dynamics of the network topology is taken into account. It has been observed that e.g. spreading processes evolve slower on such temporal networks.

In the dynamics networks literature, so far mainly bursty node activity patterns have been discussed as an explanation for this slow-down. A common line of argument is that - by comparing empirical dynamic networks to sequence where only time-stamps are reshuffled - all characteristics of a dynamic network (like edge weights or aggregate topology) are preserved, except bursty activity patterns.

In our work we show that this is essentially wrong. Even in cases with no bursty patterns, one can still have a spreading-inhibiting effect - so-called betweenness preference - that is just due to the ordering of edges. In particular, this ordering can lead to a preference for particular pathways through the network, while other paths (that exist in the aggregated view) are completely absent in the dynamic network sense (i.e. in terms of time-respecting paths). We prove that this effect exists in empirical networks, where it inhibits spreading. We further show that a shuffling of edges also destroys betweenness preference. In other words, if you shuffle edges (I guess this is what you do in the RP model) you also create new time-respecting paths that may not have existed before. And this is another topological explanation for the speeding up of epidemic processes when edges are reshuffled. 

Below is a brief explanation of our approach.

Quantifying Transitivity-Limiting Effects of Topological Dynamics

Focusing on structural properties of temporal networks, rather than on node activity distributions, we study to what extent nodes preferentially mediate information flows between particular pairs of neighboring nodes. We propose a measure, betweenness preference, to study this preferential mediation. Our study is motivated by the idea that in many networks nodes contact particular other nodes based on the previous contact - a general effect that has been suggested to exist in real-world networks based on interevent time distributions. One example is the influence of context in information dissemination: work-related emails are more likely to be forwarded to a work-related subset of social contacts. Another example are spatial constraints in disease spreading: an infected individual will not infect all of her (aggregated) social contacts at once. Rather there will be a sequence of contacts, based on the individual's mobility pattern. Here we study the influence of such special classes of dynamical contact patterns, i.e. the actual pathways arising in temporal networks. We argue that betweenness preference, and hence correlation in the temporal order of contacts, a) is not captured in the time-aggregated network, b) is present in empirical temporal network data and c) critically influences dynamical processes evolving on temporal networks. Figure 2 below shows two examples of temporal sequences with (right) and without (left) betweenness preference. 

Our simulation results show that betweenness preference has a transitivity-limiting effect, which leads to a significant slow-down of SI spreading dynamics (see Figure 4). All details of the proposed measure as well as the associated null models can be found in the paper referenced below.

The data we used for this publication is available here.

Selected Publications