NetalignMeasures documentation

NetalignMeasures documentation

Network alignment measures including S3, DS3, WEC, DWEC, as well as node similarities for network alignment including GDV similarity, degree similarity, etc.

Installation

NetalignMeasures can be installed as follows.

Pkg.clone("https://github.com/vvjn/NetalignMeasures.jl")

Overview

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.

source

Measures

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

S3 edge conservation measure.

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

DS3 event conservation measure.

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

Weighted edge conservation from WAVE.

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

Dynamic weighted edge conservation from DynaWAVE.

source

LCCSMeasure(G::SparseMatrixCSC...)

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

source

GHOST signature and node similarity

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

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

source

Node conservation measure

source

Null measure Always returns 0.0 score

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

Measure from NETAL paper.

source

Dynamic Networks

Types

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

source

Functions

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

source

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

source

Sum of active duration over all events in G

source

Convert to snapshots with window size t_w

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

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

source

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

source

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

source

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

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

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

source

Static Networks

Functions

degree vector of an adjacency graph

source

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

source

approx expected number of conserved interactions (netal)

source

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

source

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

source

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

source

Other functions

NetalignMeasures.pcaFunction.

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

source