Communicability across evolving networks

Many natural and technological applications generate time-ordered sequences of networks, defined over a fixed set of nodes; for example, time-stamped information about “who phoned who” or “who came into contact with who” arise naturally in studies of communication and the spread of disease. Concepts and algorithms for static networks do not immediately carry through to this dynamic setting. For example, suppose A and B interact in the morning, and then B and C interact in the afternoon. Information, or disease, may then pass from A to C, but not vice versa. This subtlety is lost if we simply summarize using the daily aggregate network given by the chain A-B-C. However, using a natural definition of a walk on an evolving network, we show that classic centrality measures from the static setting can be extended in a computationally convenient manner. In particular, communicability indices can be computed to summarize the ability of each node to broadcast and receive information. The computations involve basic operations in linear algebra, and the asymmetry caused by time’s arrow is captured naturally through the noncommutativity of matrix-matrix multiplication. Illustrative examples are given for both synthetic and real-world communication data sets. We also discuss the use of the new centrality measures for real-time monitoring and prediction.

Figure 1

Simple example of an evolving network.

Figure 2

Comparison of centralities synthetically generated network of $1001$ nodes, where node number $1001$ is designed to have average activity, as measured by the aggregate degree, but enjoys high-quality connections at each time point. Upper pictures scatter the broadcast and receive centralities (5) with node $1001$ circled. Lower pictures show histograms of Katz centrality for the binarized aggregate network, with centrality for node $1001$ marked with a vertical dashed line.

Figure 3

Adjacency matrices for the MIT telecommunication data, symmetrized and aggregated into 13 sets of 28-day windows. Each plot shows the nonzero pattern: A dot in row $i$ and column $j$ represents at least one telephone interaction between those individuals.

Figure 4

Daily MIT telecommunication data. Upper right: Total activity per day. Upper left: Broadcast versus receive centrality; $\mathrm{corr}=0.14$, $\tau =0.15$, top 20 overlap size $4$. Lower left: Broadcast centrality versus total degree; $\mathrm{corr}=0.50$, $\tau =0.34$, top 20 overlap size $9$. Lower right: Receive centrality versus total degree; $\mathrm{corr}=0.28$, $\tau =0.28$, top 20 overlap size $6$.

Figure 5

Daily MIT telecommunication data. Upper: $a=0.1$ versus $a=0.05$; for broadcast $\mathrm{corr}=0.93$ and $\tau =0.82$, for receive $\mathrm{corr}=0.98$ and $\tau =0.87$. Respective top 20 overlap sizes are $14$ and $16$. Lower: $a=0.05$ versus $a=0.01$; for broadcast $\mathrm{corr}=0.82$ and $\tau =0.57$, for receive, $\mathrm{corr}=0.81$ and $\tau =0.54$. Respective top 20 overlap sizes are $16$ and $11$.

Figure 6

Results for Enron email data. Upper left: Total number of edges per day. Upper right: Scatter plot of broadcast and receive centralities; $\mathrm{corr}=0.00$, $\tau =0.05$, top 20 overlap size $2$. Lower left: Scatter plot of broadcast centrality and total out degree; $\mathrm{corr}=0.62$, $\tau =0.46$, top 20 overlap size $11$. Lower right: Scatter plot of receive centrality and total in degree; $\mathrm{corr}=0.28$, $\tau =0.31$, top 20 overlap size $6$.

Figure 7

Results for Enron email data. Upper left: Scatter plot of broadcast centralities for $a=0.2$ and $a=0.1$; $\mathrm{corr}=1.00$, $\tau =0.93$, top 20 overlap size $18$. Upper right: Scatter plot of receive centralities for $a=0.2$ and $a=0.1$; $\mathrm{corr}=0.97$, $\tau =0.88$, top 20 overlap size $14$. Lower left: Scatter plot of broadcast centralities for directed and undirected networks for $a=0.1$; $\mathrm{corr}=0.82$, $\tau =0.58$, top 20 overlap size $12$. Lower right: Scatter plot of receive centralities for directed and undirected networks for $a=0.1$; $\mathrm{corr}=0.76$, $\tau =0.81$, top 20 overlap size $13$.