Network reachability of real-world contact sequences

We use real-world contact sequences, time-ordered lists of contacts from one person to another, to study how fast information or disease can spread across network of contacts. Specifically we measure the reachability time—the average shortest time for a series of contacts to spread information between a reachable pair of vertices (a pair where a chain of contacts exists leading from one person to the other)—and the reachability ratio—the fraction of reachable vertex pairs. These measures are studied using conditional uniform graph tests. We conclude, among other things, that the network reachability depends much on a core where the path lengths are short and communication frequent, that clustering of the contacts of an edge in time tends to decrease the reachability, and that the order of the contacts really does make sense for dynamical spreading processes.

Figure 1

(Color online.) An illustration of optimal spreading processes through a contact sequence. The information transfer (the contacts) occurs in the direction of the arrows at the times marked on the edges. The vertices that can have the information and the time respecting paths are shown in darker color.

Figure 2

(Color online.) The average number of edges per vertex (or the average in or out degree) and the average number of contacts per edge for our four data sets: (a) the Swedish Internet dating community, pussokram.com, (b) the e-mail data of Ebel et al., (c) the e-mail data of Eckmann et al., and (d) the e-mail data of Enron executives.

Figure 3

(Color online.) The fraction of reachable vertex pairs (vertex pairs between which a time-respecting path exists) plotted against the average reachability time for reachable vertex pairs. (a) shows results for the pussokram.com data, (b) represents the e-mail data of Ebel et al., (c) is the results of the e-mail data of Eckmann et al., and (d) the e-mail data of Enron executives. The actual values are tablelized in Table .

Figure 4

The cumulative distribution of the number of contacts over a directed edge $l$ (i.e., the probability that an observed $l$ is equal to or larger than the value on the abscissa). All data sets show right-skewed and broad distributions of $l$.

Figure 5

The number of contacts per edge $l$ plotted against the out degree of the from vertex (i.e., the first argument of the directed edge) $k_{\text{from}}$ and the in degree of the to vertex $k_{\text{from}}$. The plots are for the data of (a) pussokram.com, (b) Ebel et al., (c) Eckmann et al., and (d) Enron, respectively. The abscissae are logarithmically binned.

Figure 6

(Color online.) The reachability ratio $f$ as a function of the out degree of the start vertex of the time respecting path $k_{\text{start}}$ and the in degree of the final vertex of the path vertex $k_{\text{target}}$. The horizontal axes are logarithmically binned. (a) shows the result for the Internet community, pussokram.com; (b), (c), and (d) show the e-mail exchange sequences of the data of Ebel et al., Eckmann et al., and the Enron, respectively.

Figure 7

(Color online.) The convergence of $\widehat{\tau }$ as a function of the number sampling time of subsets of the contact sequences. The panes correspond to the different data set (with the same labeling as Fig. 2). The error bars are smaller than the symbol size except for in (d) where they are of about the same size as the symbols.