Network Graph: private API

PortfolioOptimisers.graph_weight_matrix — Function
graph_weight_matrix(D::MatNum)

Return D as a matrix whose off-diagonal entries a SimpleWeightedGraphs edge weight can hold.

A distance matrix and a weighted graph give 0 different meanings. A distance of 0 is the smallest distance, so the two assets are as close as possible. In a weighted graph, a weight of 0 means that the edge is absent. SimpleWeightedGraph stores its input as a sparse matrix, and add_edge! refuses a zero weight. A zero distance in the constructor removes the edge that the minimum spanning tree wants most. The two assets are then not adjacent, and no error occurs.

A zero distance does not show bad data. SimpleAbsoluteDistance and LogDistance read abs(rho), so a pair with a correlation of -1 is at distance zero. An inverse ETF and its index are such a pair, and the two are as related as two assets can be. The square-root algorithms reach zero at the other end, because their clamp! sets the radicand to zero for every rho >= 1.

The function repairs a zero distance, and does not refuse it. Each off-diagonal zero moves to nextfloat(zero(T)), the smallest positive value of T = eltype(D). It is the value nearest to zero that an edge weight can hold. It is far below any distance that a caller can mean, and a sum with a distance of normal size does not change when it enters. When no entry moves, the function returns D and makes no copy.

The function reads D in its own element type. An integer distance matrix is outside the supported domain, because an Integer has no smallest positive value. A Rational also has none. nextfloat raises a MethodError for both.

The function refuses a negative entry and a NaN, because neither has a nearest value that an edge weight can hold. A negative distance inverts the order that it states, and the shortest path routines that read these weights return an answer for it with no error. An asset with zero variance gives a NaN correlation, and so a NaN distance. A NaN is false in every comparison that the tree algorithms make.

The function keeps Inf. LogDistance gives Inf for two uncorrelated assets, the graph accepts it, and a spanning tree takes those edges last.

Algorithm

  1. Read every off-diagonal entry of D. Throw a DomainError on a negative entry and on a NaN. Set repair to true if an entry is zero.
  2. Return D when repair is false. The function makes no copy of an input that needs no repair.
  3. Copy D into W, whose element type is T = eltype(D). Set tiny to the smallest positive value of T.
  4. Set every off-diagonal zero of W to tiny, and return W.

Arguments

  • D: Symmetric distance matrix.

Validation

  • Throws a DomainError if any off-diagonal entry is negative or NaN.

Returns

  • W::MatNum: D itself, or a repaired copy of it.

Related

source
PortfolioOptimisers.calc_weighted_adjacency_graph — Function
calc_weighted_adjacency_graph(alg::AbstractTreeType, D::MatNum)
calc_weighted_adjacency_graph(alg::AbstractNonNegativeSimilarityMatrixAlgorithm,
                              S::MatNum)
calc_weighted_adjacency_graph(nte::NetworkEstimator, X::MatNum; dims::Int = 1,
                              kwargs...)

Build the weighted graph whose edges are the network structure.

calc_weighted_adjacency and calc_adjacency each do one operation on the graph that this function returns, so they get the structure from it. calc_distance_weighted_graph builds the same edge set, and puts distances on it.

Polarity is per branch, and the two branches are not interchangeable

Each branch keeps the quantity that selected its edges, and the two quantities go in opposite directions.

  • alg::AbstractTreeType: calc_mst minimises the distance, so the weights are distances. A small weight means that the two assets are closely related.
  • alg::AbstractNonNegativeSimilarityMatrixAlgorithm: PMFG_T2s maximises the gain over the similarity, so the weights are similarities. A large weight means that the two assets are closely related.

With the other quantity, a branch gets its weights from a quantity that did not select its edges, so the function converts neither branch. The result carries no polarity tag, because dispatch on the algorithm gives the polarity.

A consumer that follows a path must first dispatch on nte.alg. A shortest path over similarities inverts the order that it must state, and it returns an answer with no error. The two graphs have the same shape and different meanings.

Two entry points, because the quantity that selects the edges is not always cheap

The methods that take alg take the quantity that selects the edges. It is the distance on the tree branch and the similarity on the PMFG branch. The methods that take nte compute that quantity from X, and pass it on. The same dispatch selects the branch in both cases, so the polarity above belongs to the algorithm and not to the entry point.

The methods that take alg are for a caller that already holds that matrix. clusterise is such a caller. It needs D and S for its sum of powers and for the Clusters that it returns. A second derivation here computes the same correlation two times. Under VariationInfoDistance, the derivation is 98% of the run time of clusterise, so a second one almost doubles it.

The weights

  • Tree branch: each weight is positive, and finite or Inf. graph_weight_matrix moves every zero distance away from 0, the value that means an absent edge. It refuses a negative distance and a NaN. The graph accepts Inf, which LogDistance gives for two uncorrelated assets.
  • PMFG branch: each weight is positive and finite. PMFG_T2s checks that its input is non-negative. It inserts every vertex whatever the gain, so it declines no edge. The graph stores a zero weight as an absent edge, so the structure then has fewer edges. For this reason, assert_pmfg_weights refuses a zero weight.

Algorithm

The tree branch, under an AbstractTreeType:

  1. Compute the distance matrix D from X with nte.de and nte.ce. The entry point that takes alg receives D and starts at step 2.
  2. Repair D with graph_weight_matrix. Build the complete SimpleWeightedGraphs.SimpleWeightedGraph G over the repaired matrix.
  3. Find the edges of the minimum spanning tree of G with calc_mst.
  4. Return the subgraph of G on those edges. It is the tree, and its weights are the distances of D.

The similarity branch, under an AbstractNonNegativeSimilarityMatrixAlgorithm:

  1. Compute the correlation and the distance matrix D from X with nte.de and nte.ce. Check D against the domain of nte.alg with assert_similarity_domain. Convert the pair to the similarity matrix S with distance_to_similarity. The entry point that takes alg receives S and starts at step 2.
  2. Build the triangulated maximally filtered graph over S with PMFG_T2s. Its weighted adjacency matrix is A.
  3. Refuse a zero weight in A with assert_pmfg_weights.
  4. Return the SimpleWeightedGraphs.SimpleWeightedGraph over A. Its weights are the similarities of S.

Arguments

  • alg: Tree or similarity matrix algorithm.
  • D: Distance matrix.
  • S: Similarity matrix.
  • nte: Network estimator.
  • X: Data matrix observations × assets if the dims keyword does not exist or dims = 1, assets × observations when dims = 2.
  • dims: Dimension along which the computation runs.
  • kwargs...: Additional keyword arguments.

Validation

  • On the entry points that take nte: no diagonal entry of D is NaN. Raises a DistanceReaderRefusalError that names the columns of the assets that the reader could not estimate, through assert_distance_reader_rows. A fit catches it and drops those assets.
  • Tree branch: throws a DomainError if an off-diagonal entry of D is negative or NaN, through graph_weight_matrix.
  • Similarity branch: throws a DomainError if a zero weight removes an edge of the triangulated maximally filtered graph, through assert_pmfg_weights.
  • Similarity branch, on the entry point that takes nte only: throws a DomainError if D leaves the domain of alg, through assert_similarity_domain. The entry point that takes alg receives S and does not read D.

Returns

  • G::SimpleWeightedGraphs.SimpleWeightedGraph: The network structure, with the weights of its branch.

Related

source
PortfolioOptimisers.calc_weighted_adjacency — Function
calc_weighted_adjacency(G::Graphs.AbstractGraph)
calc_weighted_adjacency(alg::Tree_SimMat, W::MatNum)
calc_weighted_adjacency(nte::NetworkEstimator, X::MatNum; dims::Int = 1, kwargs...)

Compute the weighted adjacency matrix of the network structure.

Graphs.adjacency_matrix of a weighted graph returns the weights, and not 0 and 1. This function gives the matrix form of calc_weighted_adjacency_graph, with the same polarity on each branch. The entries are distances on the tree branch and similarities on the PMFG branch. Read the section on polarity of calc_weighted_adjacency_graph before you use the values.

The pattern of nonzero entries is the structure, so it is the same as that of calc_adjacency on the same input. Only the stored values are different.

The entry points are those of calc_weighted_adjacency_graph, with one more call to Graphs.adjacency_matrix. One more method takes a graph that the caller already holds. W is the quantity that selects the edges, the distance on the tree branch and the similarity on the PMFG branch. clusterise builds the graph from that quantity, and reads the matrix from the graph through the method that takes G. It keeps the graph, because it needs the graph again to resolve a budget rule.

Algorithm

  1. Build the network structure with calc_weighted_adjacency_graph, through the entry point that the arguments name. The method that takes G receives the graph and starts at step 2.
  2. Return Graphs.adjacency_matrix of that graph. The graph is weighted, so the entries are its edge weights and not 0 and 1.

Arguments

  • G: Network structure that the caller holds, from calc_weighted_adjacency_graph.
  • alg: Tree or similarity matrix algorithm.
  • W: Quantity that selects the edges on the branch of alg. It is a distance matrix under an AbstractTreeType, and a similarity matrix under an AbstractNonNegativeSimilarityMatrixAlgorithm.
  • nte: Network estimator.
  • X: Data matrix observations × assets if the dims keyword does not exist or dims = 1, assets × observations when dims = 2.
  • dims: Dimension along which the computation runs.
  • kwargs...: Additional keyword arguments.

Returns

  • adj::SparseArrays.SparseMatrixCSC: Weighted adjacency matrix of the network, in the polarity of its branch.

Related

source
PortfolioOptimisers.calc_adjacency — Function
calc_adjacency(nte::NetworkEstimator, X::MatNum; dims::Int = 1, kwargs...)

Compute the binary adjacency matrix of the network that nte builds.

The structure comes from calc_weighted_adjacency_graph. This function converts it to a Graphs.SimpleGraph, which removes the weights. Both branches use the same method, because calc_weighted_adjacency_graph selects the branch.

A consumer that needs the weights calls calc_weighted_adjacency. It must then obey the polarity of each branch, which calc_weighted_adjacency_graph states. This function removes the weights, so the polarity does not apply to it.

Algorithm

  1. Build the weighted network structure with calc_weighted_adjacency_graph.
  2. Convert it to a Graphs.SimpleGraph, which keeps the edge set and removes the weights.
  3. Return Graphs.adjacency_matrix of that graph, which is binary.

Arguments

  • nte: Network estimator.
  • X: Data matrix observations × assets if the dims keyword does not exist or dims = 1, assets × observations when dims = 2.
  • dims: Dimension along which the computation runs.
  • kwargs...: Additional keyword arguments.

Returns

  • adj::SparseArrays.SparseMatrixCSC{Int, Int}: Binary adjacency matrix of the network.

Related

source
PortfolioOptimisers.calc_distance_weighted_graph — Function
calc_distance_weighted_graph(nte::NetworkEstimator, X::MatNum; dims::Int = 1,
                             kwargs...)

Build the network structure with distances on its edges, on either branch.

calc_weighted_adjacency_graph gives each branch the quantity that selected its edges, so its two branches have opposite polarities. This function gives both branches the distance. The edge set is the same, vertex for vertex. Only the weights are different, and only on the PMFG branch.

Why this function can put distances on the PMFG branch

calc_weighted_adjacency_graph does not put on a structure a quantity that did not select it. The distance is a different case. Every AbstractSimilarityMatrixAlgorithm is a strictly decreasing function of the distance. The order of the similarities that selected the edges is then the reverse of the order of the distances, pair for pair. PMFG_T2s selects the edges from S, and D gives each selected edge its length.

A shortest path over the similarities is wrong. A shortest path minimises the sum of its edge weights, so over similarities it takes the route through the weakest links. Its order is then the reverse of the correct order. Nothing shows the error. Over the four similarity algorithms, the measured correlation of the reversed answer with the correct one is 0.95 to 0.97.

Algorithm

The tree branch, under an AbstractTreeType:

  1. Return the graph of calc_weighted_adjacency_graph. That branch already puts the distances of D on its edges, so the two structures are one graph.

The similarity branch, under an AbstractNonNegativeSimilarityMatrixAlgorithm:

  1. Compute the correlation and the distance matrix D from X. Check D against the domain of nte.alg with assert_similarity_domain. Convert the pair to the similarity matrix S with distance_to_similarity.
  2. Repair D into W with graph_weight_matrix. The tree branch does the same repair for the same reason, because a zero weight means an absent edge.
  3. Select the edges of the triangulated maximally filtered graph over S with PMFG_T2s, into A. Refuse a zero weight in A with assert_pmfg_weights.
  4. Read the row and the column of every stored entry of A. The entry of W at each of them is the length of that edge.
  5. Return the SimpleWeightedGraphs.SimpleWeightedGraph over those indices and lengths. It has the edge set of A and the distances of D.

Arguments

  • nte: Network estimator.
  • X: Data matrix observations × assets if the dims keyword does not exist or dims = 1, assets × observations when dims = 2.
  • dims: Dimension along which the computation runs.
  • kwargs...: Additional keyword arguments.

Validation

Returns

  • G::SimpleWeightedGraphs.SimpleWeightedGraph: The network structure, weighted by distance on both branches.

Related

source