abstract type NetalignMeasure end
abstract type NetalignScore end

Sub-types of NetalignMeasure are network alignment measures. A type instance will contain information such that given the type instance and an alignment, we are able to calculate the alignment score.

Sub-types of NetalignScore contain network alignment score information. The type instance will contain information of a particular network alignment measure and an alignment. The score field in the type instance will contain the network alignment score. score measures network similarity and will be between 0 and 1.

Two networks

Namely, let S3Measure <: NetalignMeasure be the S3 network alignment measure. It will be instantiated as meas = S3Measure(G1,G2) where G1 and G2 are the adjacency matrices of the two relevant networks such that n1 <= n2, where n1 and n2 are the number of nodes in G1 and G2, respectively.

Then, given an alignment (described using a vector of Ints, f, such that when node i in graph G1 is mapped to node j in graph G2, f[i] = j), we can calculate the alignment score using the measure and score functions.

Given a type NAM <: NetalignMeasure, the interface functions such a type under NetalignMeasure include:

measure(meas::NAM, f::Vector{Int}) -> NAS

Returns a struct of type NAS <: NetalignScore, which corresponds to type NAM, containing information regarding the alignment score of f with respect the alignment measure NAM.

Namely, given an instance of NAM, for example, meas = NAM(G1,G2), then x = measure(meas,f) x.score will contain the alignment score. x might also contain other information such as the numerator and denominator of the alignment score, or the number of conserved and non-conserved edges, etc.

score(meas::NAM, f::Vector{Int}) -> Float64

Returns the alignment score of f with respect the alignment measure NAM.

Multiple networks

Not all NetalignMeasures work for more than two networks. One that does it the LCCS (largest common conserved sub-graph) measure. This is an example with 3 networks but it is easily extended to k networks. Namely, let LCCSMeasure <: NetalignMeasure be the LCCS network alignment measure. It will be instantiated as meas = LCCSMeasure(G1,G2,G3) where G1,G2,G3 are the adjacency matrices of the four relevant networks such that n1 <= n2 <= n3, where n1,n2,n3 are the number of nodes in G1,G2,G3, respectively.

Then, given an alignment we can calculate the alignment score using the measure and score functions. An alignment between k networks, G[1],...,G[k], is described using a tuple, fs, of k-1 vectors of Ints. For a given vector of Ints, fs[l], fs[l] is 1-1 mapping from graph G[l] to graph G[k]. And similar to the two network case, each fs[l] is such that when node i in graph G[l] is mapped to node j in graph G[k], fs[l][i] = j).

Given a type NAM <: NetalignMeasure, the interface functions such a type under NetalignMeasure include:

measure(meas::NAM, fs::Tuple{Vector{Int}}) -> NAS
measure(meas::NAM, fs::Vector{Int}...) -> NAS

Returns a struct of type NAS <: NetalignScore, which corresponds to type NAM, containing information regarding the alignment score of fs with respect the alignment measure NAM.

score(meas::NAM, fs::Tuple{Vector{Int}}) -> Float64
score(meas::NAM, f::Vector{Int}...) -> Float64

Returns the alignment score of f with respect the alignment measure NAM.

score(x::NAS) -> Float64

Returns x.score.

dim(meas::NAM) -> Int

Returns the number of nodes in the largest network among the relevant networks. Note: this is always the last network since the networks _must_ be ordered w.r.t. node size.

dim : NAM x Int -> Int

Returns the number of nodes in the kth network.

Other functions

score(x::NAS) -> Float64

Returns x.score.

dim(meas::NAM) -> Int

Returns the number of nodes in the largest network among the relevant networks. Note: this is always the last network since the networks _must_ be ordered w.r.t. node size.

dim : NAM x Int -> Int

Returns the number of nodes in the kth network.

Note: The input adjacency matrices _must_ be symmetric.

S3Measure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)

S3 edge conservation measure.

DS3Measure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)

DS3 event conservation measure.

WECMeasure(G1::SparseMatrixCSC,G2::SparseMatrixCSC,S::AbstractMatrix)

Weighted edge conservation from WAVE.

DWECMeasure(G1::SparseMatrixCSC{Events},G2::SparseMatrixCSC{Events},S::AbstractMatrix)

Dynamic weighted edge conservation from DynaWAVE.

LCCSMeasure(G::SparseMatrixCSC...)

Largest common conserved sub-graph, from multiMAGNA++ paper. Works for >2 networks.

GHOST signature and node similarity

ConvexCombMeasure(S::A,T::B,alpha::Float64) where {A<:NetalignMeasure,B<:NetalignMeasure}

Convex combination of two NetalignMeasures. 0 <= alpha <= 1.

Node conservation measure

Null measure Always returns 0.0 score

NetalMeasure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)

Measure from NETAL paper.

An dynamic edge in a dynamic network is defined as a set of events. An event is an interaction between two nodes from start time t0 to stop time t1, t0 <= t1, and is represent as a tuple (t0,t1). The set of events is represented as a Vector, sorted wrt start time t0, and if two start times are equal, then stop time t1. Note: Unless specified, it is assumed that two events in an event set will not overlap, i.e. there exists no two tuples (t0,t1) and (s0,s1) s.t. intersect([t0,t1],[s0,s1]) != null

A dynamic network can be represented using a SparseMatrixCSC{Events} structure where an element in the matrix (i.e. an edge) is represented using the following structure

Calculates CET and NCET of the first n elements in a sorted array of events As in, the events from two node pairs are combined together and tis is the combined events Sortedness is not checked

Calculates CET and NCET of the events in tsl and tsr Assumes the events in each array are non-overlapping Sortedness is not checked

Sum of active duration over all events in G

Convert to snapshots with window size t_w

Total time during which events in event set are active
i.e. active duration of an edge

Input: adj. matrix of a dynamic network Output: adj. matrix of static network containing corresponding duration of each edge in the dynamic network

Given a vector of timestamps (sorted wrt the start time), with possibly overlapping durations, return a vector of timestamps with no overlapping durations

Given two vectors of timestamps (sorted wrt the start time), with possibly overlapping durations, return a vector of timestamps with no overlapping durations

Given a vector of timestamps (sorted wrt the start time), with possibly overlapping durations, modify vector of timestamps s.t. it has no overlapping durations

If event intersects with [t_s,t_e] then add edges to snapshot

Make each event in network wider by adding making each event occur pre time ahead and post time later

degree vector of an adjacency graph

probability that any of i's neighbors will be conserved (netal)

approx expected number of conserved interactions (netal)

expci(..)[i,j] = I[i,j] = expected # of conserved edges if i is aligned to j

Given an adj. matrix of a graph, return index of nodes adjacent to node i

Given an adj. matrix of a graph, return values of nodes adjacent to node i

Input: X : m x n matrix Each column of X is a feature vector Get the first dimensions containing k fraction of variance

Output: PCA object with mean, projection matrix, and variances U is projection matrix projection is T = U' * X U*T =~ X, where X is mean centered