tempnet.temporal_network#

# # flow stability # # Copyright (C) 2021 Alexandre Bovet <alexandre.bovet@maths.ox.ac.uk> # # This program is free software; you can redistribute it and/or modify it under # the terms of the GNU Lesser General Public License as published by the Free # Software Foundation; either version 3 of the License, or (at your option) any # later version. # # This program is distributed in the hope that it will be useful, but WITHOUT # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS # FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more # details. # # You should have received a copy of the GNU Lesser General Public License # along with this program. If not, see <http://www.gnu.org/licenses/>.

Attributes#

logger

Classes#

`ContTempInstNetwork`	Continuous time temporal network with instantaneous events.
`ContTempNetwork`	Continuous time temporal network

Functions#

`compute_stationary_transition`(T)	Compute the transition matrix at stationarity for matrix T
`compute_subspace_expm`(A[, n_comp, comp_labels, ...])	Compute the exponential matrix of A.
`csc_row_normalize`(X)	Row normalize scipy sparse csc matrices.
`find_spectral_gap`(L)	L is assummed to be connected
`lin_approx_trans_matrix`(T, t[, Pi, t_s])	Linear approximation of the continuous time transition matrix.
`numpy_rebuild_nnz_rowcol`(T_data, T_indices, T_indptr, ...)	Returns a CSR matrix.
`remove_nnz_rowcol`(L)	CSC or CSR matrix with removed zero row and columns
`set_to_ones`(Tcsr[, tol])	In-place replacement of ones in sparse matrix within the tolerence.
`set_to_zeroes`(Tcsr[, tol, relative, use_absolute_value])	In-place replacement of zeroes in sparse matrix within a tolerance.
`sparse_lapl_expm`(L, fact[, dense_expm, nproc, ...])	Computes the matrix exponential of a laplacian L.
`sparse_lin_approx`(T, t[, Pi, t_s, nz_rowcols])	Linear approximation of a continuous time transition matrix.
`sparse_stationary_trans`(T)

Module Contents#

class tempnet.temporal_network.ContTempInstNetwork(source_nodes=[], target_nodes=[], starting_times=[], relabel_nodes=True, reset_event_table_index=True, node_to_label_dict=None, events_table=None)[source]#

Bases: ContTempNetwork

Continuous time temporal network with instantaneous events.

This is a subclass of ContTempNetwork for continuous time temporal networks where events do not have a duration.

In practice, it is implemented as a ContTempNetwork where ending_times_k = starting_times_k+1 and where durations (tau_k) = 1 for all events for the computation of the transition matrices.

Parameters:

source_nodes (Python list) – List of source nodes of each event, ordered according to starting_times.
target_nodes (Python list) – List of target nodes of each event
starting_times (Python list) – List of starting times of each event
relabel_nodes (boolean) – Relabel nodes from 0 to num_nodes and save original labels in self.node_to_label_dict. Default is True
reset_event_table_index (boolean) – Reset the index of the events_table DataFrame. Default is True.
node_to_label_dict (Python dict) – If relabel_nodes is `False, this can be used to save the original labels of the nodes.
events_table (Pandas Dataframe) – Dataframe with columns ‘source_nodes’, ‘target_nodes’, ‘starting_times’ and ‘ending_times’ and index corresponding to event index. Used for instantiating a new ConTempNetwork from the event_table of an other one.

compute_inter_transition_matrices(lamda=None, t_start=None, t_stop=None, use_sparse_stoch=False, dense_expm=True)[source]#

Compute interevent transition matrices.

T_k(lamda) = expm(-lamda*L_k).

Here, for instantaneous events, all events are assumed to have the same duration of unit time (i.e. tau_k =1 for all k).

The transition matrix T_k is saved in self.inter_T[lamda][k], where self.inter_T is a dictionary with lamda as keys and lists of transition matrices as values.

will compute from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1]

the transition matrix at step k, is the probability transition matrix between times[k] and times[k+1].

compute_laplacian_matrices(*, t_start=None, t_stop=None, save_adjacencies=False)[source]#

Compute all laplacian matrices and saves them in self.laplacians.

Computes from the first time index before or equal to t_start until the time index before t_stop.

laplacians are computed from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1]

The laplacian at step k, is the random walk laplacian between times[k] and times[k+1]

NOTE: This subclass implements pulse dynamics (state A, S, Dm1, degrees are reset to zero at every time step, and event ends are no-ops). This is intentionally distinct from ContTempNetwork.compute_laplacian_matrices which implements interval dynamics (persistent state across time steps, with event ends clearing the corresponding adjacency entry). The behavior here mirrors upstream TemporalNetwork.py at commit f99bca3, so the two classes are not expected to produce equal laplacians even when ending_times are aligned to start + 1.

The pulse semantics are encoded entirely via the _make_adjacency_buffer, _laplacian_prewarm, _laplacian_on_event_end and _laplacian_step_end hooks below; the loop body itself lives in the parent class.

compute_lin_inter_transition_matrices(lamda=None, t_start=None, t_stop=None, t_s=10, use_sparse_stoch=False)[source]#

Compute interevent transition matrices as a linear approximation.

Approximation is done for expm(-lamda*L_k) based on the discrete time transition matrix.

Here, for instantaneous events, all events are assumed to have the same duration of unit time (i.e. tau_k =1 for all k).

t_s is the time value for which the linear approximation reaches the stationary transition matrix (default is t_s=10).

The transition matrix T_k_lin is saved in self.inter_T_lin[lamda][t_s][k], where self.inter_T_lin is a dictionary with lamda as keys and lists of transition matrices as values.

will compute from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1]

the transition matrix at step k, is the probability transition matrix between times[k] and times[k+1]

instantaneous_events = True#

class tempnet.temporal_network.ContTempNetwork(*, source_nodes=[], target_nodes=[], starting_times=[], ending_times=[], extra_attrs=None, relabel_nodes=True, reset_event_table_index=True, node_to_label_dict=None, merge_overlapping_events=False, events_table=None, **kwargs)[source]#

Continuous time temporal network

Parameters:

source_nodes (Python list) – List of source nodes of each event, ordered according to starting_times.
target_nodes (Python list) – List of target nodes of each event.
starting_times (Python list) – List of starting times of each event.
ending_times (Python list) – List of ending times of each event.
extra_attrs (Dict) – Extra event attributes. Must be given in a dict with {attr_name: list_of_values}, where list_of_values has the same order and length as source_nodes.
relabel_nodes (boolean) – Relabel nodes from 0 to num_nodes and save original labels in self.node_to_label_dict. Default is True
reset_event_table_index (boolean) – Reset the index of the events_table DataFrame. Default is True.
node_to_label_dict (Python dict) – If relabel_nodes is `False, this can be used to save the original labels of the nodes.
merge_overlapping_events (boolean) – Check for overlapping events (between the same pair of nodes) and merges them. Default is False.
events_table (Pandas Dataframe) – Dataframe with columns ‘source_nodes’, ‘target_nodes’, ‘starting_times’ and ‘ending_times’ and index corresponding to event index. Used for instantiating a new ConTempNetwork from the event_table of an other one.

active_nodes(t_start, t_end)[source]#: Return the nodes active within the given time window.

compute_inter_transition_matrices(*, lamda=None, t_start=None, t_stop=None, fix_tau_k=False, use_sparse_stoch=False, dense_expm=True)[source]#

Computes interevent transition matrices.

T_k(lamda) = expm(-tau_k*lamda*L_k).

The transition matrix T_k is saved in self.inter_T[lamda][k], where self.inter_T is a dictionary with lamda as keys and lists of transition matrices as values.

will compute from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1]

the transition matrix at step k, is the probability transition matrix between times[k] and times[k+1]

Parameters:

lamda (float, optional) – Random walk rate, dynamical resolution parameter. The default (None) is 1 over the median inter event time.
t_start (float or int, optional) – Starting time, passed to compute_laplacian_matrices if the Laplacians have not yet been computed. Otherwise is not used. The computation starts at self.times[self._k_start_laplacians]. The default is None, i.e. starts at the beginning of times.
t_stop (float or int, optional) – Same than t_start but for the ending time of computations. Computations stop at self.times[self._k_stop_laplacians-1]. Default is end of times.
fix_tau_k (bool, optional) – If true, all interevent times (tau_k) in the formula above are set to 1. This decouples the dynamic scale from the length of event which is useful for temporal networks with instantaneous events. The default is False.
use_sparse_stoch (bool, optional) – Whether to use custom sparse stochastic matrix format to save the inter transition matrices. Especially useful for large networks as the matrix exponential is then computed on each connected component separately (more memory efficient). The default is False.
dense_expm (bool, optional) – Whether to use the dense version of the matrix exponential algorithm at each time steps. Recommended for not too large networks. The inter trans. matrices are still saved as sparse scipy matrices as they usually have many zero values. The default is True. Has no effect is use_sparse_stoch is True.

Return type:

None.

compute_laplacian_matrices(*, t_start=None, t_stop=None, save_adjacencies=False)[source]#

Computes the laplacian matrices and saves them in self.laplacians

Computes from the first event time (in self.times) before or equal to t_start until the event time index before t_stop.

Laplacians are computed from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1].

The laplacian at step k, is the random walk laplacian between times[k]. and times[k+1].

Parameters:

t_start (float or int, optional) – The default is None, i.e. starts at the beginning of times. The computation starts from the first time index before or equal to t_start. The corresponding starting time index is saved in self._k_start_laplacians and the real starting time is self.times[self._k_start_laplacians] which is saved in self._t_start_laplacians.
t_stop (float or int, optional) – Same than t_start but for the ending time of computations. Default is end of times. Computations stop at self.times[self._k_stop_laplacians-1]. Similarily to t_start, the corresponding times are saved in self._k_stop_laplacians and self._t_stop_laplacians.
save_adjacencies (bool, optional) – Default is False. Use to save adjacency matrices in self.adjacencies.

Return type:

None.

compute_lin_inter_transition_matrices(lamda=None, t_start=None, t_stop=None, t_s=10, fix_tau_k=False, use_sparse_stoch=False)[source]#

Compute interevent transition matrices as a linear approximation.

Approximated it expm(-tau_k*lamda*L_k) based on the discrete time transition matrix.

t_s is the time value for which the linear approximation reaches the stationary transition matrix (default is t_s=10).

The transition matrix T_k_lin is saved in self.inter_T_lin[lamda][t_s][k], where self.inter_T_lin is a dictionary with lamda as keys and lists of transition matrices as values.

will compute from self.times[self._k_start_laplacians] until self.times[self._k_stop_laplacians-1]

the transition matrix at step k, is the probability transition matrix between times[k] and times[k+1]

compute_lin_transition_matrices(lamda=None, t_start=None, t_stop=None, t_s=10, save_intermediate=True, reverse_time=False)[source]#

Compute transition matrices and saves them in a dict of lists.

The transition matrices are save as self.T_lin[lamda][t_s] where self.T_lin[lamda][t_s][k] is the product of all interevent transition matrices from t_0 to t_k computed with lamda and t_s.

compute_static_adjacency_matrix(start_time=None, end_time=None)[source]#

Returns the adjacency matrix of the static network built from the aggregagted edge activity between start_time and end_time.

Parameters:

start_time (float or int, optional) – Starting time for the aggregation. The default is None, i.e. the start time of the entire temporal network.
end_time (float or int, optional) – Ending time for the aggregation. The default is None, i.e. the end time of the entire temporal network.

Returns:

Symmetric adjacency matrix, where element ij is equal to the aggregated time during which egde ij was active after start_time and before end_time.

Return type:

CSR sparse matrix

compute_transition_matrices(lamda=None, t_start=None, t_stop=None, save_intermediate=True, reverse_time=False, force_csr=False, tol=None)[source]#

Compute transition matrices and saves them in a dict of lists.

The matrices are saved as self.T[lamda] where self.T[lamda][k] is the product of all interevent transition matrices from t_0 to t_k computed with lamda.

classmethod load(filename, matrices_list=None, attributes_list=None)[source]#

Load network from file and returns a ContTempNetwork instance.

Parameters:

filename (str) – Filename where the network is saved save. The extension is automatically added.
matrices_list (list of strings) –
List of names of matrices to load. The default list is:

`matrices_list = [‘laplacians’,
’adjacencies’, ‘inter_T’, ‘inter_T_lin’, ‘T’, ‘T_lin’, ‘_stationary_trans’, ‘delta_inter_T’, ‘delta_inter_T_lin’,]`
attributes_list (list of strings) –
List of attribute names to load. The default list is:

`attributes_list = [‘node_to_label_dict’,
’events_table’, ‘times’, ‘time_grid’, ‘num_nodes’, ‘_compute_times’, ‘_t_start_laplacians’, ‘_k_start_laplacians’, ‘_t_stop_laplacians’, ‘_k_stop_laplacians’, ‘_overlapping_events_merged’,]`

static load_T(filename)[source]#

Loads T and T_lin from ‘filename’ that was saved with save_T.

Returns a dictionary with the T restored.

static load_inter_T(filename)[source]#

Loads inter_T and inter_T_lin from ‘filename’.

The file must have been generated with save_inter_T.

Returns a dictionary with the inter_T restored.

num_active_edges(t_start, t_end)[source]#: Return the number of edges active within the given time window.

num_active_nodes(t_start, t_end)[source]#: Return the number of nodes active within the given time window.

save(filename, matrices_list=None, attributes_list=None)[source]#

Save graph event_table and matrices as pickle file

Parameters:

filename (str) – Filename where to save. The extension is automatically added.
matrices_list (list of strings) –
List of names of matrices to save. The default list is:

`matrices_list = [‘laplacians’,
’adjacencies’, ‘inter_T’, ‘inter_T_lin’, ‘T’, ‘T_lin’, ‘_stationary_trans’, ‘delta_inter_T’, ‘delta_inter_T_lin’,]`
attributes_list (list of strings) –
List of attribute names to save. The default list is:

`attributes_list = [‘node_to_label_dict’,
’events_table’, ‘times’, ‘time_grid’, ‘num_nodes’, ‘_compute_times’, ‘_t_start_laplacians’, ‘_k_start_laplacians’, ‘_t_stop_laplacians’, ‘_k_stop_laplacians’, ‘_overlapping_events_merged’,]`

save_T(filename, lamda=None, round_zeros=True, tol=1e-08, compressed=False)[source]#

Save a dict with ‘T’ as key and net.T as item with other attributes.

This also works with SparseStochMat.

It only works if net.T[lamda] is a matrix and not a list of matrices, i.e. if compute_transition_matrices was ran without save_intermediate.

save_T_lin(filename, lamda=None, round_zeros=True, tol=1e-08, compressed=False)[source]#

Saves a dict with ‘T_lin’ as key and net.T_lin and other attributes.

This also works with SparseStochMat instance.

It only works if net.T_lin[lamda][t_s] is a matrix and not a list of matrices, i.e. if compute_transition_matrices was ran without save_intermediate.

save_inter_T(filename, lamda=None, round_zeros=True, tol=1e-08, compressed=False, save_delta=False, replace_existing=False)[source]#

Saves all the inter transition matrices.

This method saves all matrixes in self.inter_T[lamda] in a pickle file togheter with a dictionary including parameters:

_k_start_laplacians
_k_stop_laplacians
_t_start_laplacians
_t_stop_laplacians
_t_stop_laplacians
times_k_start_to_k_stop + 1

given by ``` self.times.values[

self._k_start_laplacians: self._k_stop_laplacians + 1

num_nodes and _compute_times.

if save_delta is True, creates delta_inter_T if it is not already present and saves it together with inter_T[lamda][0] in a pickle file. otherwise, saves inter_T[lamda] directly (good if used with SparseStochMat instances).

Parameters:

filename (str)
.gz). (Filename where the data is saved (.pickle or)

lamda: float or int, optional.: Use to save to results for a specific lamba. If None, the results for all the computed lambdas will be saved. Default is None.
round_zeros: bool.: If True, values smaller than tol*max(abs(inter_T_k)) will be set to zero to preserve sparsity. Default is True.
tol: float: See round_zeros. Default is 1e-8.
compressed: bool: Used to compress the file with gzip. Default is False.
save_delta: bool: If True, creates delta_inter_T if it is not already present and saves it together with inter_T[lamda][0]. Only the differences between two consecutives inter_Ts are saved in order to minimize file size. Must not be used if use_sparse_stoch was used in compute_inter_transition_matrices.
replace_existing: bool: If True, erase and replace files if they already exists. Default is False.

Return type:: None

save_inter_T_lin(filename, lamda=None, round_zeros=True, tol=1e-08, compressed=False, replace_existing=True, save_delta=False)[source]#

Creates delta_inter_T_lin if it is not already present.

The delta_inter_T_lin is saves together with inter_T_lin[lamda][t_s][0] in a pickle file.

end_time#

instantaneous_events = False#

is_directed = False#

node_array#

property nodes#: Sorted list of original node labels.

num_events#

num_nodes#

start_time#

tempnet.temporal_network.compute_stationary_transition(T)[source]#

Compute the transition matrix at stationarity for matrix T

Parameters:

T (scipy.sparse matrix or numpy.ndarray)
walk. (Transition matrix of the discrete time random)
matrix. (Can be a CSC or CSR)

Returns:

Pi (scipy.sparse.csr matrix)
Stationary transition matrix.

tempnet.temporal_network.compute_subspace_expm(A, n_comp=None, comp_labels=None, thresh_ratio=None, normalize_rows=True)[source]#

Compute the exponential matrix of A.

The computation is done by applying expm on each connected subgraphs defined by A and recomposing it to return expm(A).

Parameters:: A (scipy.sparse.csc_matrix)

thresh_ratio: float, optional.: Threshold ratio used to trim negligible values in the resulting matrix. Values smaller than max(expm(A))/thresh_ratio are set to zero. Default is None.
normalize_rows: bool, optional.: Whether rows of the resulting matrix are normalized to sum to 1.

Returns:

expm(A) (scipy.sparse.csr_matrix)
matrix exponential of A

tempnet.temporal_network.csc_row_normalize(X)[source]#: Row normalize scipy sparse csc matrices. returns a copy of X row-normalized and in CSC format.

tempnet.temporal_network.find_spectral_gap(L)[source]#: L is assummed to be connected

tempnet.temporal_network.lin_approx_trans_matrix(T, t, Pi=None, t_s=10)[source]#

Linear approximation of the continuous time transition matrix.

\(T(t) = e^{-tL}\) based on an interpolation between \(I\) and \(T\) and a second interpolation between \(T\) and \(\Pi\), the transition matrix at stationarity.

For each connected component of the graph, \(T(t)\) is approximated as

\[\begin{split}\tilde{T}(t) & = & (1-t) I + tT \text{ for } 0\leq t \leq 1 \\ \tilde{T}(t) & = & \frac{1}{1-t_s}[T(t-t_s) + \Pi(1-t)] \text{ for } 1 < t \leq t_s \\ \tilde{T}(t) & = & \Pi \text{ for } t > t_s\end{split}\]

where \(t_s\) is the mixing time of the random walk (default is t_s=10).

Parameters:

T (scipy.sparse csr matrix)
walk (Transition matrix of the discrete time random)

tfloat: Time, greater or equal to zero.
Piscipy.sparse matrix: Transition matrix of the discrete time random walk at stationarity. If None, it will be computed from T.
t_sfloat: Stationarity time at which the interpolation reaches Pi.

Returns:

Tapprox (scipy.sparse.csr matrix)
Linear approximation of expmL at time t.

tempnet.temporal_network.numpy_rebuild_nnz_rowcol(T_data, T_indices, T_indptr, zero_indices)[source]#

Returns a CSR matrix.

The CSR matrix (data, indices, rownnz, shape) is built from the CSR matrix T_small but with added row-colums at zero_indicies (with 1 on the diagonal)

tempnet.temporal_network.remove_nnz_rowcol(L)[source]#

CSC or CSR matrix with removed zero row and columns

This also returns an array of the indices of rows/columns with non-zero values and the (linear) size of L.

Return type:: L_small, nonzero_indices, size

tempnet.temporal_network.set_to_ones(Tcsr, tol=1e-08)[source]#

In-place replacement of ones in sparse matrix within the tolerence.

Replace values within a tolerance to one with actual ones.

tempnet.temporal_network.set_to_zeroes(Tcsr, tol=1e-08, relative=True, use_absolute_value=False)[source]#

In-place replacement of zeroes in sparse matrix within a tolerance.

Replace values that are, within the tolerence, close to zero with actual zeroes.

If tol is None, does nothing

tempnet.temporal_network.sparse_lapl_expm(L, fact, dense_expm=True, nproc=1, thresh_ratio=None, normalize_rows=True)[source]#

Computes the matrix exponential of a laplacian L.

The exponential, expm(-fact*L), is computed considering only the non-zeros rows/cols of L

Parameters:

L (scipy sparse csc matrix) – Laplacian matrix with large proportion of zero rows/cols.
fact (float) – factor in front of the laplacian
dense_expm (boolean) – Whether to compute the expm on the small Laplacian as a dense or sparse array. Default is True.
nproc (int, optional) – number of parallel processes for dense_expm=False. The default is 1.
thresh_ratio (float, optional.) – Threshold ratio used to trim negligible values in the resulting matrix. Values smaller than max(expm(A))/thresh_ratio are set to zero. For dense_expm=False. Default is None.
normalize_rows (bool, optional.) – Whether rows of the resulting matrix are normalized to sum to 1. For dense_expm=False

Returns:

expm(-fact*L) – Transition matrix

Return type:

SparseStochMat object

tempnet.temporal_network.sparse_lin_approx(T, t, Pi=None, t_s=10, nz_rowcols=None)[source]#

Linear approximation of a continuous time transition matrix.

This is desgned for sparse transition matrices.

Performs computation using lin_approx_trans_matrix on a smallest L matrices with no zeros row/cols and returns a SparseStochMat

Parameters:

T (scipy sparse csr matrix) – Original full size laplacian matrix.
t (float) – Interpolation time.
Pi (scipcy sparse csr matrix, optional) – Transition matrix at stationarity. Same shape that T. The default is None, i.e. computed from T.
t_s (float, optional) – Stationarity time at which the interpolation reaches Pi. The default is 10.
nz_rowcols (ndarray of int32) – indices of T of nonzero offdiagonal rows/cols to build a SparseStochMat.

Returns:

Tapprox – Linear approximation at time t.

Return type:

SparseStochMat object

tempnet.temporal_network.sparse_stationary_trans(T)[source]#

Parameters:: T (scipy sparse csr matrix) – Discrete time transition matrix.
Returns:: Pi – Transition matrix at stationarity
Return type:: scipy sparse csr matrix

tempnet.temporal_network.logger#