Temporal network reachability

In a temporal network, reachability is a function of time, i.e., the possibility of going from vertex \(v_0\) at time \(t_0\) to \(v_1\) at \(t_1\).

Temporal reachability functions

The library comes with a variety of functions that calculates the temporal cluster types, the spreading cluster of an effect starting from a single vertex at a specific time, assuming that the spreading “effect” stays in each node for duration dictated by the temporal adjacency of that spreading process.

The variants are similar to those of static network reachability, with the possibility of starting from one vertex at one time, or calculating or estimating spreading clusters from all vertices at all starting times.

Similar to calculating spreading starting from a single vertex at some point time, the library allows you to run the spreading process backwards, calculating the set of starting vertices and times that, would a spreading process start at one of those points, can spread to our target. The contrast between this and forward and backwards process is similar to the contrast between calculating in- and out-components on a directed acyclic graph.

Hint

Check out a more in-depth temporal network reachability example to learn more!

From/to a single point

in_cluster(temporal_network, temporal_adjacency: adjacency_type, vertex: vert_type, time: time_type) → temporal_cluster[adjacency_type]
in_cluster(temporal_network, temporal_adjacency: adjacency_type, edge: edge_type) → temporal_cluster[adjacency_type]
out_cluster(temporal_network, temporal_adjacency: adjacency_type, vertex: vert_type, time: time_type) → temporal_cluster[adjacency_type]
out_cluster(temporal_network, temporal_adjacency: adjacency_type, edge: edge_type) → temporal_cluster[adjacency_type]
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
temporal_cluster<EdgeT, AdjT> in_cluster(const network<EdgeT> &temp, const AdjT &adj, const typename EdgeT::VertexType &v, typename EdgeT::TimeType t)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
temporal_cluster<EdgeT, AdjT> in_cluster(const network<EdgeT> &temp, const AdjT &adj, const EdgeT &e)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
temporal_cluster<EdgeT, AdjT> out_cluster(const network<EdgeT> &temp, const AdjT &adj, const typename EdgeT::VertexType &v, typename EdgeT::TimeType t)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
temporal_cluster<EdgeT, AdjT> out_cluster(const network<EdgeT> &temp, const AdjT &adj, const EdgeT &e)

From/to all points

in_clusters(temporal_network, temporal_adjacency: adjacency_type) → Iterable[Pair[edge_type, temporal_cluster[adjacency_type]]]
out_clusters(temporal_network, temporal_adjacency: adjacency_type) → Iterable[Pair[edge_type, temporal_cluster[adjacency_type]]]
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster<EdgeT, AdjT>>> in_clusters(const network<EdgeT> &temp, const AdjT &adj)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster<EdgeT, AdjT>>> out_clusters(const network<EdgeT> &temp, const AdjT &adj)

Cluster sizes from/to all points

in_cluster_sizes(temporal_network, temporal_adjacency: adjacency_type) → Iterable[Pair[edge_type, temporal_cluster_size[adjacency_type]]]
out_cluster_sizes(temporal_network, temporal_adjacency: adjacency_type) → Iterable[Pair[edge_type, temporal_cluster_size[adjacency_type]]]
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster_size<EdgeT, AdjT>>> in_cluster_sizes(const network<EdgeT> &temp, const AdjT &adj)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster_size<EdgeT, AdjT>>> out_cluster_sizes(const network<EdgeT> &temp, const AdjT &adj)

Cluster size estimates from/to all points

in_cluster_size_estimates(temporal_network, temporal_adjacency: adjacency_type, time_resolution: time_type, seed: int) → Iterable[Pair[edge_type, temporal_cluster_size_estimate[adjacency_type]]]
out_cluster_size_estimates(temporal_network, temporal_adjacency: adjacency_type, time_resolution: time_type, seed: int) → Iterable[Pair[edge_type, temporal_cluster_size_estimate[adjacency_type]]]
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster_size<EdgeT, AdjT>>> in_cluster_size_estimates(const network<EdgeT> &temp, const AdjT &adj, typename EdgeT::TimeType time_resolution, std::size_t seed)
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
std::vector<std::pair<EdgeT, temporal_cluster_size_estimate<EdgeT, AdjT>>> out_cluster_size_estimates(const network<EdgeT> &temp, const AdjT &adj, typename EdgeT::TimeType time_resolution, std::size_t seed)

Temporal adjacency

For the case of static network reachability we had a nice and concrete definition of adjacency. For example, in an undirected network if two edges share at least one incident vertex, an “effect” (e.g., a disease or a gossip) transmitted through one edge can also be transmitted through the other edge.

For temporal networks, however, this gets slightly more complicated. For starters, for an effect transmitted through event \(e_1\) to be transmitted again by another event \(e_2\), the two event have to happen in the correct order.

Many categories of effects have further temporal restrictions on adjacency of two events, e.g., many spreading processes have a maximum waiting-time which puts an upper-bound on the time distance between two events. For example, many diseases have a maximum duration where a patient can remain infectious.

This library defines a few common types of temporal adjacency. The simple adjacency describes the case where the only restriction is due to limitation of cause and effect, with no further limitations. Other temporal adjacency types describe commonly used stochastic or deterministic limits on spreading.

Simple adjacency

class temporal_adjacency.simple[edge_type]
template<temporal_network_edge EdgeT>
class temporal_adjacency::simple
simple()

The simple temporal adjacency specifies the physical minimum requirements for two events to be considered adjacent.

Note

Two event happening at the same time cannot be adjacent. If your network representation has a low temporal resolution, you might need to manually adjust timestamps.

Limited waiting-time adjacency

class temporal_adjacency.limited_waiting_time[edge_type](dt: time_type)
template<temporal_network_edge EdgeT>
class temporal_adjacency::limited_waiting_time
limited_waiting_time(typename EdgeType::TimeType dt)

Exponential adjacency

class temporal_adjacency.exponential[edge_type](rate: time_type, seed: int)
template<temporal_network_edge EdgeT>
class temporal_adjacency::exponential
exponential(typename EdgeType::TimeType rate, std::size_t seed)

In an exponential temporal adjacency regime, the effect remains on an affected vertex for a duration of time drawn from an exponential distribution with the given rate rate. The parameter seed makes sure that the same instance of a stochastic adjacency type on the same network produces the same outcome every time.

Note

The exponential temporal adjacency type, similar to the exponential distribution, is only well defined for continious time types. If you are dealing with data with timestamps that cannot be represented faithfully as continious variables, you might want to use a geometric adjacency type.

Geometric adjacency

class temporal_adjacency.geometric[edge_type](rate: time_type, seed: int)
template<temporal_network_edge EdgeT>
class temporal_adjacency::geometric
geometric(typename EdgeType::TimeType rate, std::size_t seed) const

In an geometric temporal adjacency regime, the effect remains on an affected vertex for a duration of time drawn from a geometric distribution with the given rate rate and mean \(rate^{-1}\). The parameter seed makes sure that the same instance of a stochastic adjacency type on the same network produces the same outcome every time.

Note

The geometric temporal adjacency type, similar to the geometric distribution, is only well defined for discrete time types. If you are dealing with data with timestamps that cannot be represented faithfully as discrete variables, you might want to use an exponential adjacency type.

Your own temporal adjacency type

template<typename T>
concept temporal_adjacency

In C++, you can use your own temporal adjacency type as long as it satisfies the concept temporal_adjacency. To wit, that it should have well defined member types EdgeType and VetexType and defines member functions linger(EdgeType e, VetexType v) and maximum_linger(VertexType v), the former describing how long vertex v remains affected by an effect transmitted by event e, and the latter describing a worst case (upper-bound) on the duration that a vertex v can remain affected by an effect.

Temporal cluster types

Clusters are to temporal networks what a component is to a static network. They store subsets of the temporal network. While storing a subset of a static network required only storing a set of vertices, a subset of a temporal network also requires temporal information.

class temporal_cluster[temporal_adjacency](temporal_adjacency: adjacency_type, size_hint: int = 0)
insert(event: edge_type)
insert(events: list[edge_type])
merge(other: temporal_cluster[adjacency_type])
covers(vertex: vert_type, time: time_type) → bool
interval_sets() → dict[vert_type, interval_set[time_type]]
lifetime() → tuple[time_type, time_type]
volume() → int
mass() → time_type
__eq__(other: temporal_cluster[adjacency_type]) → bool
__len__() → int
__contains__(event: edge_type) → bool
static vertex_type() → type
static adjacency_type() → type
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
class temporal_cluster
type VertexType
type AdjacencyType
type IteratorType
template<std::ranges::input_range Range>
requires std::convertible_to<std::ranges::range_value_t<Range>, EdgeT>
void insert(Range &events)
void insert(const EdgeT &e)
void merge(const temporal_cluster<EdgeT, AdjT> &other)
bool operator==(const temporal_cluster<EdgeT, AdjT> &c) const
std::size_t size() const
bool contains(const EdgeT &e) const
bool covers(typename EdgeT::VertexType v, typename EdgeT::TimeType t) const
bool empty() const
IteratorType begin() const
IteratorType end() const
const std::unordered_map<typename EdgeT::VertexType, interval_set<typename EdgeT::TimeType>, hash<typename EdgeT::VertexType>> &interval_sets() const
std::pair<typename EdgeT::TimeType, typename EdgeT::TimeType> lifetime() const;
std::size_t volume() const
typename EdgeT::TimeType mass() const
class temporal_cluster_size[temporal_adjacency]
lifetime() → tuple[time_type, time_type]
volume() → int
mass() → time_type
static vertex_type() → type
static adjacency_type() → type
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
class temporal_cluster_size
type VertexType
type AdjacencyType
explicit temporal_cluster_size(const temporal_cluster<EdgeT, AdjT> &c)
std::size_t size() const
std::pair<typename EdgeT::TimeType, typename EdgeT::TimeType> lifetime() const
std::size_t volume() const
typename EdgeT::TimeType mass() const
class temporal_cluster_size_estimate[temporal_adjacency]
lifetime() → tuple[time_type, time_type]
volume_estimate() → float
mass_estimate() → float
static vertex_type() → type
static adjacency_type() → type
template<temporal_network_edge EdgeT, temporal_adjacency::temporal_adjacency AdjT>
class temporal_cluster_size_estimate
type VertexType
type AdjacencyType
double size_estimate() const
std::pair<typename EdgeT::TimeType, typename EdgeT::TimeType> lifetime() const
double volume_estimate() const
double mass_estimate() const
EdgeT::TimeType temporal_resolution() const