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.

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#