(Backward or forward) reachability in temporal networks is a measure of the position of nodes, akin to the centrality measures of static networks. The (forward, or downstream) reachability of a node i is the fraction of nodes that can be reached by time-respecting paths from i at time t, averaged over time from the beginning to the end of the data set. The backward (upstream) reachability is just what you’d expect—how many nodes that could reach (rather than be reached by) i. (A time-respecting path is a sequence of contacts (i,j,t) that is strictly increasing in time.) We assume the temporal network can be described as a sequence of such ID-ID-time triples.
Reachability is interesting because it is conceptually simple and intuitive—how large a part of the network can you, on average, reach from a node—and it highlights why temporal networks are a different kind of beast from static networks. For static networks, one rarely considers the component size of a node to measure its importance—usually, almost all nodes are connected to one giant component. Reachability, on the other hand, tends to practically fully discriminate the nodes.
Calculating reachability is not entirely trivial. I just shared my C code on GitHub. I tried to make the code as fast as possible, but it needs N2 space. (But fortunately only two bits per node, so even a temporal network of 10,000 nodes should fit into my MacBook’s 32 Gb memory. I have tried up to 18,719 nodes and 9,094,619 contacts on my workstation, which took 9.1 seconds.
The algorithm works as follows. Every node has one bit-string representing what nodes that are reachable at a given time. (In my code, it is an array of N/16+1 16-bit unsigned integers.) It runs through the contacts backward (so to calculate the backward reachability, it runs forward). Initially, every node can only reach itself. At every time step t with at least one contact, the code loops over all active nodes i (those having at least one contact at t). It merges the reachable nodes of i with the nodes of i‘s neighbors (nodes j such that (i,j,t) is a contact) that were reachable before t.
The merging itself is fast—just one bitwise-or operation per 16-nodes of merging. A final trick needed is to count the number of bits in an integer, for which I use a lookup table. I store the reachability arrays as 16-bit integers because one lookup table can cover all 65,536 such values. Even though merging arrays of 32-bit numbers should take half the time on modern processors, calculating the number of bits in them needs two extra bitwise operations and one addition, which makes code based on arrays of 32-bit numbers slower.
Petter Holme 