NetalignUtils documentation

NetalignUtils documentation

Introduction

NetalignUtils.jl contains function relevant to network alignment, including function to read/write static and dynamic networks, and other utility functions to deal with static and dynamic networks.

Installation

NetalignUtils can be installed as follows.

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

Types

immutable DynamicNetwork
    G :: SparseMatrixCSC{Events,Int}
    nodes :: Vector
end

A DynamicNetwork is a sparse matrix of Events and a list of nodes. G is assumed to be symmetric, unless specified otherwise. The Events structure is defined in the NetalignMeasures.jl package (it is a list of timestamps, where a timestamp is a tuple (start_time, end_time).

immutable Network
    G :: SparseMatrixCSC{Int,Int}
    nodes :: Vector
end

A Network is a sparse matrix and a list of nodes. G is assumed to be symmetric, unless specified otherwise.

Functions

Dynamic networks

readeventlist(fd::IO; <keyword args>)
readeventlist(file::AbstractString; <keyword args>) -> SparseMatrixCSC{Events}, node list

Read list of events from file returns undirected dynamic network represented as sparse matrix. An event is an interaction between two nodes from start time to stop time.

Keyword arguments

  • symmetric=true : If false, only fill the top right triangle, else make resulting matrix symmetric.

  • header=false : If true, ignore first line.

  • sortby=nothing: If not nothing, sort nodes w.r.t this function (by argument in sort).

  • format=:timefirst : If format=:timefirst, each line has format (start_time stop_time node1 node2). If format=:nodefirst, each line has format (node1 node2 start_time stop_time).

writeeventlist(fd::IO, dy::DynamicNetwork; <keyword args>)
writeeventlist(file::AbstractString, dy::DynamicNetwork; <keyword args>)

Write list of events to file from undirected dynamic network represented as sparse matrix. An event is an interaction between two nodes from start time to stop time.

Keyword arguments

  • format=:timefirst : If format=:timefirst, each line has format (start_time stop_time node1 node2). If format=:nodefirst, each line has format (node1 node2 start_time stop_time).

events2dynet(I, J, V, n, nodes; symmetric=true) -> SparseMatrixCSC{Events}, nodes

Similar to sparse, given indices and values, create an dynamic network.

Arguments

  • n : # of nodes in network

  • I,J: indices

  • V : vector of Events

  • symmetric=true : If true, make the sparse matrix symmetric.

snapshots2dynet(snaps::Vector{Network};
          symmetric=false,sortby=nothing)

Converts a vector of networks (i.e. temporal snapshots) into a dynamic network with event duration 1 and time starting at 0.

Static networks

NetalignUtils.readgwFunction.
readgw(fd::IO)
readgw(file::AbstractString) -> SparseMatrixCSC, node list

Reads LEDA format file describing a network. Outputs an undirected network. An example of a LEDA file is in the examples/ directory.

readedgelist(fd::IO; header=false)
readedgelist(file::AbstractString; header=false) -> SparseMatrixCSC, node list

Read list of edges and output undirected network

writeedgelist(fd::IO, st::Network; prefix="",suffix="")
writeedgelist(file::AbstractString, st::Network; prefix="",suffix="")

Write network to file as list of edges.

  • prefix,suffix : Prefix and suffix to each line.

NetalignUtils.writegwFunction.
writegw(fd::IO, st::Network)
writegw(file::AbstractString, st::Network)

Write undirected network to file as LEDA format.

Alignments

nodecorrectness(f::AbstractVector{Int},
                nodes1::AbstractVector,nodes2::AbstractVector) -> nc

Calculates node correctness when given an alignment.

Arguments

  • f : Alignment between nodes1 and nodes2. f[i] describes the aligned

node pairs nodes1[i] and nodes2[f[i]]. Thus, f describes length(f) aligned node pairs.

  • nodes1,nodes2 : Node sets that f desribes the alignment of.

Output

  • nc : Node correctness between 0 and 1.

NetalignUtils.readalnFunction.
readaln(file::AbstractString, nodes1::Vector,
         nodes2::Vector, flip=false)

Read alignment file for pairwise network alignment. Each line will contain a node pair, with the first node from nodes1, and the second node from nodes2. Returns permutation from nodes1 to nodes2 corresponding to the node pairs (so need length(nodes1) <= length(nodes2)) If flip=true, then returns permutation from nodes2 to nodes1, (so need length(nodes2) <= length(nodes1)) where first node in each line is from nodes2, and the second node is from nodes1.

writealn(fd::IO, nodes1::AbstractVector, nodes2::AbstractVector)
writealn(file::AbstractString, nodes1::AbstractVector, nodes2::AbstractVector)

Write alignment to file

readseeds(file::AbstractString,
          nodes1::AbstractVector,
          nodes2::AbstractVector) -> Matrix{Int} : n x 2

Outputs n x 2 matrix of node indices associates with nodes1 and nodes2

Matrices

readlistmat(fd::IO, nodes1::Vector, nodes2::Vector; <keyword arguments>)
readlistmat(file::AbstractString, nodes1::Vector, nodes2::Vector; <keyword arguments>)

Reads a numerical matrix stored in list format, where the first and second columns correspond to string vectors nodes1 and nodes2, respectively. E.g.

nodeA1 nodeA2 4.5
nodeB1 nodeB2 3.4
nodeA1 nodeB2 0.3
nodeB1 nodeA2 0.6

Returns a dense matrix by default. Set keyword option dense=false to return a sparse matrix.

Arguments

  • fd,file : file name or file I/O

  • nodes1,nodes1 : node vectors corresponding to 1st and 2nd columns

Keyword arguments

  • header=false : set to true to ignore first line

  • ignore=false : set to true to ignore nodes in file that is not in nodes1 or nodes2

  • dense=true : set to false to return sparse matrix

readlistmat!(fd::IO, B::AbstractMatrix, nodes1::Vector, nodes2::Vector; <keyword arguments>)
readlistmat!(file::AbstractString, B::AbstractMatrix, nodes1::Vector, nodes2::Vector; <keyword arguments>)

Same as readlistmat but stores the result in B.

Network measures

NetalignUtils.readgdvFunction.
readgdv(fd::IO, nodes::AbstractVector)
readgdv(file::AbstractString, nodes::AbstractVector)

Reads the .ndump2 file format that contains (static or dynamic) graphlet counts, outputted by GraphCrunch1 (ncount program in http://www0.cs.ucl.ac.uk/staff/natasa/graphcrunch/index.html), or Graphcrunch2 (http://www0.cs.ucl.ac.uk/staff/natasa/graphcrunch2/index.html), or the dynamic graphlets counting code (https://www3.nd.edu/~cone/DG/).

Graphlets are small, connected, induced sub-graphs of a network (Przulj N, Corneil DG, Jurisica I: Modeling Interactome, Scale-Free or Geometric?, Bioinformatics 2004, 20(18):3508-3515.), similar to network motifs.

writegdv(fd::IO, X::AbstractMatrix, nodes::AbstractVector)
writegdv(file::AbstractString, X::AbstractMatrix, nodes::AbstractVector)

Writes to graphlets file format. See readgdv.

Network generation

Scale-free gene duplication

  • p

  • q

  • arrival : node arrival function (:quad, :linear, :exp, :constant)

Vazquez, Alexei and Flammini, Alessandro and Maritan, Amos and Vespignani, Alessandro 2003 Modeling of protein interaction networks Complexus 1 38–44

Geometric gene duplication with probability cutoff

  • p : probability cutoff

  • ε : distance (set this to 1)

  • arrival : node arrival function (:quad, :linear, :exp, :constant)

Przulj, N., Kuchaiev, O., Stevanovic, A., and Hayes, W. (2010). Geometric evolutionary dynamics of protein interaction networks. In Proc. of the Pacific Symposium Biocomputing, pages 4–8.

Social network evolution model

  • λ : node active lifetime

  • α, β : how active a node is at adding edges

Leskovec, J., Backstrom, L., Kumar, R., and Tomkins, A. (2008). Microscopic evolution of social networks. In Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'08, pages 462–470.

Base.Random.randFunction.
rand([rng::AbstractRNG], gf::GraphGenerator, Ntot::Integer, Tmax::Number, N0::Integer=5)

Arguments

  • Ntot : total # of nodes

  • N0 : # of nodes at time 0

  • Tmax : end of timespan

Generates a random network depending on the GraphGenerator

Randomization

strict_events_shuffle(G::SparseMatrixCSC{Events}, prob::Number)
strict_events_shuffle!(G::SparseMatrixCSC{Events}, prob::Number)
  • prob : 0 <= prob <= 1

The following does the event shuffle as in page 15/30 of modern temporal network theory a colloquim eur phys j b 2015. After that it merges overlapping events between node pairs. The number of events between node pairs will not be conserved because it merges overlapping events.

The topology of the resulting network when it is flattened does not change since only the event times are changed.

links_shuffle(G::SparseMatrixCSC{Events}, prob::Number)
  • prob : 0 <= prob <= 1

Page 16/30 of modern temporal network theory. Rewires each link with probability prob.