Separating temporal and topological effects in walk-based network centrality

The recently introduced concept of dynamic communicability is a valuable tool for ranking the importance of nodes in a temporal network. Two metrics, broadcast score and receive score, were introduced to measure the centrality of a node with respect to a model of contagion based on time-respecting walks. This article examines the temporal and structural factors influencing these metrics by considering a versatile stochastic temporal network model. We analytically derive formulas to accurately predict the expectation of the broadcast and receive scores when one or more columns in a temporal edge-list are shuffled. These methods are then applied to two publicly available data sets and we quantify how much the centrality of each individual depends on structural or temporal influences. From our analysis, we highlight two practical contributions: a way to control for temporal variation when computing dynamic communicability and the conclusion that the broadcast and receive scores can, under a range of circumstances, be replaced by the row and column sums of the matrix exponential of a weighted adjacency matrix given by the data.

Figure 1

A simple example of a directed temporal network. This example has been designed to illustrate the core concepts of this work. In Fig. 1 it is apparent that the dynamic communicability of a node is not necessarily determined by its overall activity. Figure 1 demonstrates how the dynamic communicability metrics can be broken down into temporal and structural elements. We apply the same visualization method to two real-world data sets in Figs. 4 and 5. (a) The left panel shows the network at each time step (above) and its corresponding adjacency matrix (below). On the right the same information is represented as a list of temporal edges. Shown also are the different possible ways to randomize (or shuffle) the columns. Notice that simultaneously shuffling any two columns yields the completely shuffled edge-list shown in (iv). (b) Each marker corresponds to a node in the example network. Each node is given a rank according to its broadcast score (left) and receive score (right). These rankings are plotted against the outgoing and incoming degree ranks respectively. The diagonal line divides the nodes into those that acheive higher broadcast (or receive) scores than expected and those that are lower. (c) The expectation values for each shuffling are calculated and the corresponding rank is plotted (we have chosen only to consider the target shuffling for broadcast score and source shuffling for receive score). The actual scores are shown by the darkness of the markers.

Figure 2

A demonstration of the accuracy of the derived formulas using a sample of 23 nodes from the Enron data set (all of which have at least one outgoing edge within the sample) and a total of 312 emails. Each marker represents an employee. In both plots the $x$ axis shows the receive score computed by shuffling one column of the edge-list, as shown in Fig. 1, and averaged over 100 shuffles. In the left-hand plot the time column was subjected to shuffling and the $y$ axis shows the receive score as predicted by Eq. (18); on the right the target column was subjected to shuffling and the $y$ axis shows the receive score as predicted by Eq. (27). $\alpha =0.02$.

Figure 3

Each marker (short horizontal line) represents an Enron employee or participant in the Sociopatterns experiment. The broadcast score, computed by Eq. (32), is displayed on the $y$ axis in panel (a) and, similarly, the receive score in panel (b) from Eq. (30) with $\alpha =0.01$ and $\alpha =0.005$, respectively. In both the employees (or participants) are divided into distinct categories shown along the $x$ axis. Abbreviations are given in Sec. 4. (a) Enron email results. (b) Hospital results.

Figure 4

The rank according to broadcast score [left, computed by Eq. (32)] and receive score [right, computed by Eq. (30)], with $\alpha =0.01$ and $\alpha =0.005$, respectively, plotted against the out-degree (left) and in-degree (right). Each individual in the network is represented by a data point, and their classification is given by their shape. The abbreviations in the legend are explained in Sec. 4. The one-to-one line is plotted as a visual aid to partition the nodes into two groups: those which have higher-than-expected scores (top left) and those which have lower-than-expected scores (bottom right). (a) Enron email directory. (b) Hospital contact network.

Figure 5

As demonstrated in Fig. 1. On the $y$ axis we show the ranking of each node according to expectation of the broadcast score [left, computed using Eq. (28)] and receive score [right, computed with Eq. (27)] for the expected outcomes of the source (left) and target (right) shuffled networks (with $\alpha =0.01$ and $\alpha =0.005$, respectively). The $x$ axes show the expected scores for a time-shuffled network computed with Eqs. (17) and (18). The actual broadcast score computed with Eqs. (32) and (30) is shown by the darkness of the markers. Different roles are indicated by the marker shapes, the abbreviations are explained in Sec. 4. These results are also presented in Tables 1 and 2 in Appendix pp2. (a) Enron email directory. (b) Hospital contact network.

Figure 6

Each marker (short horizontal line) represents an Enron employee or participant in the Sociopatterns experiment. The broadcast score, computed by Eq. (32), is displayed on the $y$ axis in panel (a) and similarly the receive score in panel (b) from Eq. (30) with $\alpha =0.005$ and $\alpha =0.01$, respectively. In both the employees (or participants) are divided into distinct categories shown along the $x$ axis. Abbreviations are given in Sec. 4. (a) Hospital results. (b) Enron email results.

Figure 7

The rank according to broadcast score [left, computed by Eq. (32)] and receive score [right, computed by Eq. (30)], with $\alpha =0.005$ and $\alpha =0.01$, respectively, plotted against the out-degree (left) and in-degree (right). Each individual in the network is represented by a data point, and their classification is given by their shape. The abbreviations in the legend are explained in Sec. 4. The one-to-one line is plotted as a visual aid to partition the nodes into two groups; those which have higher-than-expected scores (top left) and those who have lower-than-expected scores (bottom right). (a) Hospital contact network. (b) Enron email directory.

Figure 8

As demonstrated in Fig. 1. On the $y$ axis we show the ranking of each node according to expectation of the broadcast score [left, computed using Eq. (28)] and receive score [right, computed with Eq. (27)] for the expected outcomes of the source (left) and target (right) shuffled networks (with $\alpha =0.005$ and $\alpha =0.01$, respectively). The $x$ axes show the expected scores for a time-shuffled network computed with Eqs. (17) and (18). The actual broadcast score computed with Eqs. (32) and (30) is shown by the darkness of the markers. Different roles are indicated by the marker shapes, and the abbreviations are explained in Sec. 4. (a) Hospital contact network. (b) Enron email directory.