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
NetalignMeasures.NetalignMeasure
— Type.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 Int
s, 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 NetalignMeasure
s 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 Int
s. For a given vector of Int
s, 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.
Measures
NetalignMeasures.S3Measure
— Type.S3Measure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)
S3 edge conservation measure.
NetalignMeasures.DS3Measure
— Type.DS3Measure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)
DS3 event conservation measure.
NetalignMeasures.WECMeasure
— Type.WECMeasure(G1::SparseMatrixCSC,G2::SparseMatrixCSC,S::AbstractMatrix)
Weighted edge conservation from WAVE.
NetalignMeasures.DWECMeasure
— Type.DWECMeasure(G1::SparseMatrixCSC{Events},G2::SparseMatrixCSC{Events},S::AbstractMatrix)
Dynamic weighted edge conservation from DynaWAVE.
NetalignMeasures.LCCSMeasure
— Type.LCCSMeasure(G::SparseMatrixCSC...)
Largest common conserved sub-graph, from multiMAGNA++ paper. Works for >2 networks.
NetalignMeasures.GhostMeasure
— Type.GHOST signature and node similarity
ConvexCombMeasure(S::A,T::B,alpha::Float64) where {A<:NetalignMeasure,B<:NetalignMeasure}
Convex combination of two NetalignMeasure
s. 0 <= alpha <= 1
.
NetalignMeasures.NodeSimMeasure
— Type.Node conservation measure
NetalignMeasures.NullMeasure
— Type.Null measure Always returns 0.0 score
NetalignMeasures.NetalMeasure
— Type.NetalMeasure(G1::SparseMatrixCSC,G2::SparseMatrixCSC)
Measure from NETAL paper.
Dynamic Networks
Types
NetalignMeasures.Events
— Type.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
Functions
NetalignMeasures.cet_ncet
— Function.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
NetalignMeasures.networkactivity
— Function.Sum of active duration over all events in G
NetalignMeasures.snapshots
— Function.Convert to snapshots with window size t_w
NetalignMeasures.nodeactivity
— Function.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
NetalignMeasures.fixevents
— Function.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
NetalignMeasures.fixevents!
— Function.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
NetalignMeasures.snapshot
— Function.If event intersects with [t_s,t_e] then add edges to snapshot
NetalignMeasures.widenevents!
— Function.Make each event in network wider by adding making each event occur pre
time ahead and post
time later
Static Networks
Functions
NetalignMeasures.degree
— Function.degree vector of an adjacency graph
NetalignMeasures.dependency
— Function.probability that any of i's neighbors will be conserved (netal)
NetalignMeasures.expci
— Function.approx expected number of conserved interactions (netal)
expci(..)[i,j] = I[i,j] = expected # of conserved edges if i is aligned to j
NetalignMeasures.adjnodes
— Function.Given an adj. matrix of a graph, return index of nodes adjacent to node i
NetalignMeasures.adjnzval
— Function.Given an adj. matrix of a graph, return values of nodes adjacent to node i
Other functions
NetalignMeasures.pca
— Function.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