Network Diffusion

Network diffusion is an efficient way to model signal propagation in molecular networks. While it could not be regarded as an accurate simulation of biological system, network diffusion allows assessing complex molecular networks and revealing various topological structures, such as hubs, communities etc.

Currently, HierarchicalHotNet.jl package implements random walk with restart diffusion method. The input weighted graph is processed by stepmatrix() function, which prepares the adjacency matrix for the random walk. The resulting matrix is then submitted to random_walk_matrix() method that generates the matrix of random walk transition probabilities.

Alternatively, one can use stabilized_stepmatrix() method to weight the edges of the original network according to how frequently their edges are being utilized during the random walk.

Node and edge weights

TODO

HierarchicalHotNet.stepmatrix — Function

stepmatrix(g::Union{AbstractSimpleWeightedGraph, AbstractMatrix};
           inedge_weights::Union{AbstractVector, Nothing} = nothing,
           normalize_weights::Bool = true) -> AbstractMatrix

Construct the step probabilities matrix for the random walk on graph g.

Returns matrix $S$, where $s_{i,j}$ is the probability to travel along the edge $(v_j, v_i) ∈ g$.

inedge_weights::AbstractVector: (optional) an array of factors for each vertex to scale the weights of incoming edges
normalize_weights=true: normalize the weights of the columns in the final output, so that it sums to 1

source

HierarchicalHotNet.random_walk_matrix — Function

random_walk_matrix(g::AbstractSimpleWeightedGraph,
                   restart_probability::Number=0.1;
                   stepmtx_kwargs...) -> Matrix{Float64}

Calculate the stationary distribution of vertex transition probabilities for a random walk with restart on graph g.

Returns the matrix $W$, where $w_{i, j}$ is the $v_j → v_i$ transition probability along the edges of the graph g.

source

HierarchicalHotNet.similarity_matrix — Function

similarity_matrix(g::AbstractSimpleWeightedGraph,
                  node_weights::AbstractVector;
                  restart_probability::Union{Number, Nothing} = nothing,
                  stepmtx_kwargs...) -> Matrix{Float64}

Calculate the matrix of node transition probabilities for the random walk with restart taking into account the node restarting probabilities node_weights.

Returns the matrix $Ŵ$, where $ŵ_{i, j}$ is the probability of $v_j → v_i$ transition considering all possible starting vertices of graph g.

Parameters

node_weights::AbstractVector: vector of node restart probabilities
restart_probability: random walk restart probability
stepmatrix() keyword arguments

See also

HierarchicalHotNet.random_walk_matrix

source

HierarchicalHotNet.stabilized_stepmatrix — Function

stabilized_stepmatrix(g::AbstractSimpleWeightedGraph,
                      node_weights::AbstractVector;
                      restart_probability::Union{Number, Nothing} = nothing,
                      stepmtx_kwargs...) -> Matrix{Float64}

Calculate the matrix for the node transition probabilities at each iteration of the random walk with restart taking into account the probabilities of visiting the nodes.

Returns matrix $Ŝ$. If $w$ is the node starting probabilities (node_weights), $S$ is the step matrix, and $W$ is the corresponding transition probabilities matrix for a random walk with restart, then

\[ Ŝ = (1-r) S × \mathrm{diag}(W × w) + r \mathrm{diag}(w).\]

Parameters

node_weights::AbstractVector: vector of node restart probabilities
restart_probability: random walk restart probability
node_weights_diffused: precalculated node visiting weights for a random walk with restart (in case the random matrix is already calculated before)
stepmatrix() keyword arguments

source

HierarchicalHotNet.neighborhood_weights — Function

neighborhood_weights(adjmtx::AbstractMatrix, g::AbstractGraph) -> Vector{Float64}

Given the adjmtx adjacency matrix for the graph $g'$ and the graph g, calculate the sum of the weights of the $g'$ outgoing edges that are also present in g. Returns the vector with the weights sum for each vertex.

The graphs have to have the same number of nodes.

source

Node weights permutation

One way to confirm the relevance of network diffusion-based predictions is to show that the results based on real the data differ significantly from the ones based on randomized data, where no meaningful patterns are expected.

In the original HierarchicalHotNet paper by Reina et al (2018) it is proposed to group the vertices with similar in- and out-degrees into bins (see vertexbins()) and randomly shuffle the weights of the vertices within each bin (see randpermgroups()).

This scheme would reassign the weights of hub vertices to other hubs, and low-degree vertices – to other low-degree vertices. So, in addition to preserving the overall distribution of node weights, the correlation of node degree and its weight would be kept too. However, such reshuffling should eliminate the correlation of paths between the specific nodes and the node weights along these paths.

HierarchicalHotNet.vertexbins — Function

vertexbins(g::AbstractSimpleWeightedGraph,
           vertices::AbstractArray{Int}=1:nv(g);
           nbins::Integer=10, by::Symbol=:out, method=:tree) ->
    IndicesPartition

Partition the vertices of the weighted graph g into nbins bins, so that the vertices of the same bin have similar sum of edge weights.

Keyword arguments

nbins::Integer: the number of vertex bins. Use nbins ≥ 1 for bigger (nv ≥ 1) networks
by::Symbol: what edges to consider for grouping vertices. The supported options are:
- :out (default, as in the original paper) – use only the outgoing edges
- :in – use only the incoming edges
- :outXin (recommended) – use all edges, so that the vertices of the same bin have similar sums of both incoming and outgoing edges
method::Symbol: the method for binning vertices
- :sort (as in the original paper) – order the vertices by the sum of weights, then split the sorted array into equal bins. This method doesn't handle the by=:outXin well.
- :tree (default) – build the hierarchical tree of vertices based on their sum of weights, then cut the tree to get the requested number of bins.

source

HierarchicalHotNet.randpermgroups! — Function

randpermgroups!(v::AbstractVector{Int}, groups::AbstractPartition) -> v

Randomly reshuffle the elements of groups within each group and put the result into v, group by group.

source

HierarchicalHotNet.randpermgroups — Function

randpermgroups(groups::AbstractPartition) -> Vector{Int}

Randomly reshuffle the elements of groups within each group.

source