Direct Bubble Hierarchy Tree

PortfolioOptimisers.MaximumDistanceSimilarity — Type
struct MaximumDistanceSimilarity <: AbstractSimilarityMatrixAlgorithm end

Similarity matrix algorithm using the maximum distance transformation.

\[\begin{align} S_{i,\,j} &= \left\lceil\max(\mathbf{D})^2\right\rceil - D_{i,\,j}^2\,, \end{align}\]

where S is the similarity, \mathbf{D} the distance matrix, and each subscript denotes an asset.

Related

source
PortfolioOptimisers.GeneralExponentialSimilarity — Type
struct GeneralExponentialSimilarity{T1, T2} <: AbstractSimilarityMatrixAlgorithm
    coef::T1
    power::T2
end

Similarity matrix algorithm using a generalised exponential transformation.

\[\begin{align} S_{i,\,j} &= e^{-c \cdot D_{i,\,j}^p}\,, \end{align}\]

where S is the similarity, \mathbf{D} the distance matrix, $c$ a scale factor, $p$ an exponent, and each subscript denotes an asset.

Fields

  • coef: Non-negative scaling coefficient.
  • power: Non-negative exponent applied to the distance matrix.

Constructor

GeneralExponentialSimilarity(; coef::Real = 1.0, power::Real = 1.0)

Keyword arguments correspond to the fields above.

Validation

  • coef >= 0.
  • power >= 0.

Examples

julia> GeneralExponentialSimilarity()
GeneralExponentialSimilarity
   coef | Float64: 1.0
  power | Float64: 1.0

Related

source
PortfolioOptimisers.DBHT — Type
struct DBHT{T1, T2} <: AbstractClusteringAlgorithm
    sim::T1
    root::T2
end

Direct Bubble Hierarchical Tree (DBHT) clustering algorithm configuration.

DBHT is a composable clustering algorithm type for constructing hierarchical clusterings using the Direct Bubble Hierarchical Tree (DBHT) method, as described in [1].

Fields

  • sim: Similarity matrix algorithm.
  • root: Root selection method.

Constructor

DBHT(; sim::AbstractSimilarityMatrixAlgorithm = MaximumDistanceSimilarity(),
     root::DBHTRootMethod = UniqueRoot())

Keyword arguments correspond to the fields above.

Examples

julia> DBHT()
DBHT
   sim | MaximumDistanceSimilarity()
  root | UniqueRoot()

Related

source
— Type
struct LoGo{T1, T2} <: InverseMatrixSparsificationAlgorithm
    dist::T1
    sim::T2
end

LoGo (Local-Global) sparse inverse covariance estimation algorithm.

LoGo is a composable algorithm type for estimating sparse inverse covariance matrices using the Planar Maximally Filtered Graph (PMFG) and clique-based decomposition, as described in [2]. It combines a distance estimator and a similarity matrix algorithm, both validated and extensible, to produce a robust, interpretable sparse precision matrix for use in portfolio optimization and risk management.

Fields

  • dist: Distance matrix estimator.
  • sim: Similarity matrix algorithm.

Constructor

LoGo(; dist::AbstractDistanceEstimator = Distance(; alg = CanonicalDistance()),
     sim::AbstractSimilarityMatrixAlgorithm = MaximumDistanceSimilarity())

Keyword arguments correspond to the fields above.

Examples

julia> LoGo()
LoGo
  dist | Distance
       |   alg | CanonicalDistance()
   sim | MaximumDistanceSimilarity()

Related

source
PortfolioOptimisers.DBHTClustering — Type
struct DBHTClustering{T1, T2, T3, T4} <: AbstractClusteringResult
    clustering::T1
    S::T2
    D::T3
    k::T4
end

Result type for Direct Bubble Hierarchical Tree (DBHT) clustering.

DBHTClustering encapsulates the output of a DBHT clustering analysis, including the hierarchical clustering result, similarity and distance matrices, and the optimal number of clusters. This struct is returned by clusterise when using a DBHT-based clustering estimator.

Fields

  • clustering: Hierarchical clustering result, typically a Clustering.Hclust object.
  • S: Similarity matrix used for DBHT clustering.
  • D: Distance (dissimilarity) matrix used for DBHT clustering.
  • k: Optimal number of clusters, as determined by the estimator's cluster selection method.

Constructor

DBHTClustering(; clustering::Clustering.Hclust, S::AbstractMatrix, D::AbstractMatrix,
               k::Integer)

Keyword arguments correspond to the fields above.

Validation

  • !isempty(S)
  • !isempty(D)
  • size(S) == size(D)
  • k >= 1.

Related

source
PortfolioOptimisers.clusterise — Method
clusterise(cle::ClusteringEstimator{<:Any, <:Any, <:DBHT, <:Any}, X::AbstractMatrix{<:Real};
           branchorder::Symbol = :optimal, dims::Int = 1, kwargs...)

Perform Direct Bubble Hierarchical Tree (DBHT) clustering using a ClusteringEstimator configured with a DBHT algorithm.

This method computes the similarity and distance matrices from the input data matrix X using the estimator's configured estimators and algorithms, applies the DBHT clustering pipeline, and returns a DBHTClustering result containing the hierarchical clustering, similarity and distance matrices, and the optimal number of clusters.

Arguments

  • cle: A ClusteringEstimator whose algorithm is a DBHT instance.
  • X: Data matrix (observations × assets or assets × observations depending on dims).
  • branchorder: Symbol specifying the dendrogram branch ordering method. Accepts :optimal (default), :barjoseph, or :r.
  • dims: Integer specifying the dimension along which to compute statistics (1 for columns/assets, 2 for rows).
  • kwargs...: Additional keyword arguments passed to the underlying estimators.

Details

  • Computes the similarity and distance matrices using the estimator's configured correlation and distance estimators.
  • Applies the selected similarity transformation via dbht_similarity.
  • Runs the full DBHT clustering pipeline via DBHTs, including PMFG construction, clique and bubble hierarchy extraction, and dendrogram construction.
  • Determines the optimal number of clusters using the estimator's cluster selection method.
  • Returns a DBHTClustering result encapsulating all relevant outputs.

Returns

  • clr::DBHTClustering: DBHT clustering result.

Related

source
PortfolioOptimisers.PMFG_T2s — Function
PMFG_T2s(W::AbstractMatrix{<:Real}; nargout::Integer = 3)

Constructs a Triangulated Maximally Filtered Graph (TMFG) starting from a tetrahedron and recursively inserting vertices inside existing triangles (T2 move) in order to approximate a Maximal Planar Graph with the largest total weight, also known as the Planar Maximally Filtered Graph (PMFG). All weights must be non-negative.

This function is a core step in the DBHT (Direct Bubble Hierarchical Tree) and LoGo algorithms, providing the planar graph structure and clique information required for hierarchical clustering and sparse inverse covariance estimation.

Arguments

  • W: N×N matrix of non-negative weights (e.g., similarity or correlation matrix).
  • nargout: Number of output arguments. All outputs are always computed, but if nargout <= 3, cliques and cliqueTree are returned as nothing.

Validation

  • N >= 9 is required for a meaningful PMFG.
  • All entries in W must be non-negative.

Details

  • The algorithm starts by selecting the four vertices with the largest strength to form an initial tetrahedron.
  • Vertices are recursively inserted into existing triangles to maximize the total weight, following the T2 move.
  • The resulting graph is planar and maximally filtered, preserving the most relevant connections for hierarchical clustering.
  • The function also identifies all 3-cliques and, optionally, all 4-cliques and their adjacency structure.

Returns

  • A::SparseMatrixCSC{<:Real, Int}: Adjacency matrix of the PMFG with weights.
  • tri::Matrix{Int}: List of triangles (triangular faces) in the PMFG.
  • clique3::Matrix{Int}: List of 3-cliques that are not triangular faces; all 3-cliques are given by [tri; clique3].
  • cliques::Union{Nothing, Matrix{Int}}: List of all 4-cliques (tetrahedra), or nothing if nargout <= 3.
  • cliqueTree::Union{Nothing, SparseMatrixCSC{Int, Int}}: 4-cliques tree structure (adjacency matrix), or nothing if nargout <= 4.

Related

source
PortfolioOptimisers.dbht_similarity — Function
dbht_similarity(se::AbstractSimilarityMatrixAlgorithm; D::AbstractMatrix, kwargs...)

Compute a similarity matrix from a distance matrix using the specified similarity algorithm.

This function dispatches on the type of se to apply the appropriate similarity transformation to the distance matrix D. Used internally by DBHT and related clustering algorithms.

Arguments

  • se: Similarity matrix algorithm.

    • se::MaximumDistanceSimilarity: Uses the maximum distance transformation.
    • se::ExponentialSimilarity: Uses the exponential transformation.
    • se::GeneralExponentialSimilarity: Uses a generalised exponential transformation.

  • D: Distance matrix.

  • kwargs...: Additional keyword arguments (not used).

Returns

  • S::Matrix{<:Real}: Similarity matrix of the same size as D.

Related

source
PortfolioOptimisers.distance_wei — Function
distance_wei(L::AbstractMatrix{<:Real})

Compute the shortest weighted path lengths between all node pairs in a network.

This function computes the distance matrix containing the lengths of the shortest paths between all node pairs in a (possibly weighted) network, using Dijkstra's algorithm. An entry [u, v] represents the length of the shortest path from node u to node v. The average shortest path length is the characteristic path length of the network.

Inputs

  • L: Directed or undirected connection-length matrix.

    • Lengths between disconnected nodes should be set to Inf.
    • Lengths on the main diagonal should be set to 0.
Note

The input matrix must be a connection-length matrix, typically obtained by mapping weights to lengths (e.g., inverse of a similarity or correlation matrix). In weighted networks, shortest weighted paths may traverse more edges than shortest binary paths.

Details

  • For each node, the function computes the shortest path to all other nodes using Dijkstra's algorithm.
  • The output D contains the minimal total length for each node pair, and B contains the number of edges in the corresponding shortest path.
  • Used internally for PMFG and DBHT clustering to compute geodesic distances on the graph.

Returns

  • D::Matrix{<:Real}: Distance (shortest weighted path) matrix.
  • B::Matrix{Int}: Number of edges in the shortest weighted path matrix.
Note

Based on a Matlab implementation by Mika Rubinov, Rick Betzel, and Andrea Avena.

Related

source
PortfolioOptimisers.clique3 — Function
clique3(A::AbstractMatrix{<:Real})

Computes the list of 3-cliques in a Maximal Planar Graph (MPG).

This function identifies all 3-cliques (triangles) in the adjacency matrix A of a MPG. It returns the candidate cliques, their edge indices, and a matrix listing all unique 3-cliques. Used internally in DBHT and related phylogenetic clustering algorithms.

Inputs

  • A: N×N adjacency matrix of a Maximal Planar Graph (MPG).

Details

  • The function searches for all triangles (3-cliques) by examining pairs of connected nodes and their shared neighbors.
  • Duplicates are removed and the resulting list is sorted for consistency.
  • The output clique matrix is used as the basis for further hierarchical and bubble structure construction in DBHT.

Returns

  • K3::Vector{Vector{Int}}: Vector of vectors, each containing the indices of nodes forming a candidate 3-clique.
  • E::Matrix{Int}: Matrix with nonzero indices and entries of candidate cliques (edge pairs).
  • clique::Matrix{Int}: Nc×3 matrix. Each row lists the three vertices of a unique 3-clique in the MPG.

Related

source
PortfolioOptimisers.breadth — Function
breadth(CIJ::AbstractMatrix{<:Real}, source::Integer)

Breadth-first search.

This function performs a breadth-first search (BFS) on a binary (directed or undirected) connection matrix, starting from a specified source vertex. It computes the shortest path distances from the source to all other vertices and records the predecessor (branch) for each node in the BFS tree.

Inputs

  • CIJ: Binary (0/1) connection matrix representing the graph.
  • source: Index of the source vertex from which to start the search.

Returns

  • distance::Vector{<:Real}: Vector of shortest path distances from the source to each vertex (0 for the source itself, Inf for unreachable nodes).
  • branch::Vector{Int}: Vector of predecessor indices for each vertex in the BFS tree (-1 for the source).

Details

  • The function explores the entire graph, layer by layer, starting from the source vertex.
  • For each node, it records the minimum number of steps required to reach it from the source.
  • The branch vector allows reconstruction of the BFS tree.
  • Used internally for component analysis and separating set identification in DBHT and related algorithms.

Notes

  • The BFS tree does not contain all paths (or all shortest paths), but allows the determination of at least one path with minimum distance.
  • Original implementation by Olaf Sporns, Indiana University, 2002/2007/2008.

Related

source
PortfolioOptimisers.FindDisjoint — Function
FindDisjoint(Adj::AbstractMatrix{<:Real}, Cliq::AbstractVector{<:Real})

Finds disjointed cliques in an adjacency matrix.

This function identifies nodes that are not adjacent to a given 3-clique in the adjacency matrix, and classifies all nodes into three groups: members of the clique, nodes in the same connected component as the clique, and nodes in a disjoint component.

Arguments

  • Adj: N×N adjacency matrix.
  • Cliq: 3×1 vector of node indices forming a 3-clique.

Details

  • The function removes the clique nodes from the adjacency matrix and performs a breadth-first search to classify the remaining nodes.
  • Nodes unreachable from the first non-clique node are marked as disjoint.
  • Used internally by DBHT routines to determine separating sets and clique membership.

Returns

  • T::Vector{Int}: N×1 vector containing the adjacency number of each node:

    • 0 for nodes in the clique,
    • 1 for nodes in a disjoint component,
    • 2 for nodes in the same component as the clique.

  • IndxNot::Vector{Int}: N×1 vector of nodes with no adjacencies to the clique.

Related

source
PortfolioOptimisers.BuildHierarchy — Function
BuildHierarchy(M::AbstractMatrix{<:Real})

Builds the predicted parent hierarchy for 3-cliques in a Maximal Planar Graph (MPG).

This function constructs the parent index vector (Pred) for each 3-clique, given the node-to-clique membership matrix M. It is a core step in the DBHT (Direct Bubble Hierarchical Tree) clustering pipeline, enabling the construction of the clique hierarchy tree.

Arguments

  • M: N×Nc binary matrix of node-to-3-clique memberships, where M[i, n] = 1 if node i belongs to 3-clique n.

Details

  • For each 3-clique, the function identifies its parent clique as the smallest superset among all cliques containing its nodes.
  • If multiple parent candidates exist, the one with the smallest overlap is chosen.
  • Root cliques (with no parent) are assigned a parent index of 0.
  • Used internally by CliqHierarchyTree2s and DBHT clustering routines.

Returns

  • Pred::Vector{Int}: Nc×1 vector of predicted parent indices for each 3-clique. Pred[n] = 0 indicates a root clique.

Related

source
PortfolioOptimisers.AdjCliq — Function
AdjCliq(A::AbstractMatrix{<:Real}, CliqList::AbstractMatrix{<:Real},
        CliqRoot::AbstractVector{<:Real})

Find adjacent cliques to the root candidates in a Maximal Planar Graph (MPG).

This function computes the adjacency matrix among root candidate 3-cliques, identifying which root cliques are adjacent (i.e., share two vertices) in the graph. Used internally by CliqueRoot with EqualRoot to construct a root from the adjacency tree of all root candidates.

Arguments

  • A: N×N adjacency matrix of the MPG.
  • CliqList: Nc×3 matrix. Each row lists the three vertices of a 3-clique in the MPG.
  • CliqRoot: Vector of indices of root candidate cliques.

Details

  • For each root candidate clique, the function checks which other root cliques share exactly two vertices (i.e., are adjacent in the clique graph).
  • The resulting adjacency matrix is symmetric and encodes the adjacency structure among root cliques.
  • Used to build a connected root structure when multiple root candidates exist in the DBHT hierarchy.

Returns

  • Adj::SparseMatrixCSC{Int, Int}: Nc×Nc adjacency matrix of the cliques, where Adj[i, j] = 1 if cliques i and j are adjacent among the root candidates.

Related

source
PortfolioOptimisers.BubbleHierarchy — Function
BubbleHierarchy(Pred::AbstractVector{<:Real}, Sb::AbstractVector{<:Real})

Build the bubble hierarchy from the clique hierarchy and separating set information.

This function constructs the bubble hierarchy tree and the bubble membership matrix for 3-cliques, given the predicted parent indices (Pred) and separating set vector (Sb). It is a core step in the DBHT (Direct Bubble Hierarchical Tree) clustering pipeline, grouping 3-cliques into bubbles and building the adjacency structure among bubbles.

Arguments

  • Pred: Nc×1 vector of predicted parent indices for each 3-clique, as returned by BuildHierarchy.
  • Sb: Nc×1 vector indicating the size of the separating set for each 3-clique (Sb[n] ≠ 0 means clique n is separating).

Details

  • The function iteratively groups 3-cliques into bubbles, starting from root cliques and traversing the hierarchy.
  • For each bubble, the membership of 3-cliques is recorded in Mb.
  • The adjacency matrix H encodes the connections between bubbles, based on shared membership and hierarchical relationships.
  • If there are multiple root cliques, an initial bubble is created for each root.
  • Used internally by CliqHierarchyTree2s and DBHT clustering routines.

Returns

  • H::SparseMatrixCSC{Int, Int}: Nb×Nb symmetric adjacency matrix representing the bubble hierarchy tree, where Nb is the number of bubbles.
  • Mb::Matrix{Int}: Nc×Nb bubble membership matrix for 3-cliques. Mb[n, bi] = 1 indicates that 3-clique n belongs to bubble bi.

Related

source
PortfolioOptimisers.CliqueRoot — Function
CliqueRoot(::UniqueRoot, Root::AbstractVector, Pred::AbstractVector, Nc::Integer, args...)

Construct the hierarchical adjacency matrix for 3-cliques in a Maximal Planar Graph (MPG) using the unique root selection method.

This method enforces a unique root in the clique hierarchy. If multiple root candidates are present, a synthetic root is created and all root candidates are attached to it. Used internally by CliqHierarchyTree2s when the root selection method is UniqueRoot.

Arguments

  • ::UniqueRoot: Root selection method enforcing a unique root.
  • Root: Vector of indices of root candidate cliques.
  • Pred: Vector of predicted parent indices for each clique.
  • Nc: Number of 3-cliques.
  • args...: Additional arguments (ignored for this method).

Details

  • If there is more than one root candidate, a synthetic root node is appended and all root candidates are connected to it.
  • The resulting matrix encodes the parent-child relationships among cliques, ensuring a single connected hierarchy.
  • Used internally by DBHT clustering and related routines.

Returns

  • H::SparseMatrixCSC{Int, Int}: Symmetric adjacency matrix representing the hierarchical tree of 3-cliques.

Related

source
CliqueRoot(::EqualRoot, Root::AbstractVector, Pred::AbstractVector, Nc::Integer,
           A::AbstractMatrix{<:Real}, CliqList::AbstractMatrix{<:Real})

Construct the hierarchical adjacency matrix for 3-cliques in a Maximal Planar Graph (MPG) using the equal root selection method.

This method creates a root from the adjacency tree of all root candidate cliques, allowing for multiple equally plausible roots in the DBHT hierarchy. It is used internally by CliqHierarchyTree2s when the root selection method is EqualRoot.

Arguments

  • ::EqualRoot: Root selection method that creates a root from the adjacency tree of all root candidates.
  • Root: Vector of indices of root candidate cliques.
  • Pred: Vector of predicted parent indices for each clique.
  • Nc: Number of 3-cliques.
  • A: N×N adjacency matrix of the MPG.
  • CliqList: Nc×3 matrix. Each row vector lists the three vertices consisting of a 3-clique in the MPG.

Details

  • If there are multiple root candidates, their adjacency structure is computed using AdjCliq and incorporated into the hierarchy.
  • The resulting matrix encodes both the parent-child relationships from Pred and the adjacency among root cliques.
  • Used internally by DBHT clustering to support alternative root strategies.

Returns

  • H::SparseMatrixCSC{Int, Int}: Symmetric adjacency matrix representing the hierarchical tree of 3-cliques.

Related

source
PortfolioOptimisers.CliqHierarchyTree2s — Function
CliqHierarchyTree2s(Apm::AbstractMatrix{<:Real}; root::DBHTRootMethod = UniqueRoot())

Construct the clique and bubble hierarchy trees for a Maximal Planar Graph (MPG) using the DBHT (Direct Bubble Hierarchical Tree) approach.

This function builds the hierarchical structure of 3-cliques (triangles) and bubbles from the adjacency matrix of a planar graph, supporting different root selection strategies via the root argument. It is a core routine for DBHT clustering and related phylogenetic analyses.

Arguments

  • Apm::AbstractMatrix{<:Real}: Adjacency matrix of the MPG, where nonzero entries indicate edges.
  • root::DBHTRootMethod: Root selection method for the clique hierarchy.

Details

  • The function first identifies all 3-cliques in the graph and computes their separating sets.
  • It then builds the clique hierarchy using the specified root selection method.
  • The bubble hierarchy is constructed from the clique hierarchy and separating sets.
  • Used internally by DBHT clustering and for extracting hierarchical structures from planar graphs.

Returns

  • H::SparseMatrixCSC{Int, Int}: Symmetric adjacency matrix representing the hierarchical tree of 3-cliques.
  • H2::SparseMatrixCSC{Int, Int}: Symmetric adjacency matrix representing the bubble hierarchy tree.
  • Mb::Matrix{Int}: Bubble membership matrix for 3-cliques (Nc×Nb), where Mb[n, bi] = 1 indicates 3-clique n belongs to bubble bi.
  • CliqList::Matrix{Int}: List of 3-cliques (Nc×3), each row contains the vertex indices of a 3-clique.
  • Sb::Vector{Int}: Vector indicating the size of the separating set for each 3-clique.

Related

source
PortfolioOptimisers.DirectHb — Function
DirectHb(Rpm::AbstractMatrix{<:Real}, Hb::AbstractMatrix{<:Real},
         Mb::AbstractMatrix{<:Real}, Mv::AbstractMatrix{<:Real},
         CliqList::AbstractMatrix{<:Real})

Compute the directed bubble hierarchy tree (DBHT) for a Maximal Planar Graph (MPG).

This function assigns directions to each separating 3-clique in the undirected bubble tree of a Planar Maximally Filtered Graph (PMFG), producing the directed bubble hierarchy tree (DBHT). The direction is determined by comparing the sum of edge weights on either side of each separating clique, enabling the identification of converging and diverging bubbles.

Arguments

  • Rpm::AbstractMatrix{<:Real}: N×N sparse weighted adjacency matrix of the PMFG.
  • Hb::AbstractMatrix{<:Real}: Undirected bubble tree of the PMFG (as from BubbleHierarchy).
  • Mb::AbstractMatrix{<:Real}: Nc×Nb bubble membership matrix for 3-cliques. Mb[n, bi] = 1 indicates 3-clique n belongs to bubble bi.
  • Mv::AbstractMatrix{<:Real}: N×Nb bubble membership matrix for vertices. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • CliqList::AbstractMatrix{<:Real}: Nc×3 matrix. Each row lists the three vertices of a 3-clique in the MPG.

Details

  • For each edge in the undirected bubble tree, the function determines the direction by removing the edge and comparing the sum of edge weights for the separating clique on each side.
  • The resulting directed tree encodes the flow of hierarchical structure among bubbles, which is used for cluster assignment and further phylogenetic analysis.
  • Used internally by BubbleCluster8s and DBHT clustering routines.

Returns

  • Hc::SparseMatrixCSC{Real, Int}: Nb×Nb unweighted directed adjacency matrix of the DBHT. Hc[i, j] = 1 indicates a directed edge from bubble i to bubble j.
  • Sep::Vector{Int}: Vector indicating the type of each bubble (e.g., converging, diverging, or neutral).

Related

source
PortfolioOptimisers.BubbleCluster8s — Function
BubbleCluster8s(Rpm::AbstractMatrix{<:Real}, Dpm::AbstractMatrix{<:Real},
                Hb::AbstractMatrix{<:Real}, Mb::AbstractMatrix{<:Real},
                Mv::AbstractMatrix{<:Real}, CliqList::AbstractMatrix{<:Real})

Obtain non-discrete and discrete clusterings from the bubble topology of the Planar Maximally Filtered Graph (PMFG).

This function assigns each vertex to a cluster based on the directed bubble hierarchy tree (DBHT) structure. It computes both a non-discrete cluster membership matrix and a discrete cluster assignment vector, using the converging bubbles identified in the directed bubble tree.

Arguments

  • Rpm::AbstractMatrix{<:Real}: N×N sparse weighted adjacency matrix of the PMFG.
  • Dpm::AbstractMatrix{<:Real}: N×N shortest path lengths matrix of the PMFG.
  • Hb::AbstractMatrix{<:Real}: Undirected bubble tree of the PMFG (from BubbleHierarchy).
  • Mb::AbstractMatrix{<:Real}: Nc×Nb bubble membership matrix for 3-cliques. Mb[n, bi] = 1 indicates 3-clique n belongs to bubble bi.
  • Mv::AbstractMatrix{<:Real}: N×Nb bubble membership matrix for vertices. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • CliqList::AbstractMatrix{<:Real}: Nc×3 matrix. Each row lists the three vertices of a 3-clique in the MPG.

Details

  • The function first computes the directed bubble hierarchy tree using DirectHb.
  • Converging bubbles are identified as cluster centers.
  • Non-discrete cluster membership (Adjv) is determined by traversing the directed bubble tree from each converging bubble.
  • Discrete cluster assignments (Tc) are made by resolving overlaps and assigning each vertex to the most strongly associated converging bubble, or, if ambiguous, to the closest converging bubble by shortest path.
  • Used internally by DBHT clustering and for extracting cluster assignments from the PMFG bubble structure.

Returns

  • Adjv::SparseMatrixCSC{Int, Int}: N×Nk cluster membership matrix for vertices for non-discrete clustering via the bubble topology. Adjv[n, k] = 1 indicates cluster membership of vertex n to the k'th non-discrete cluster.
  • Tc::Vector{Int}: N×1 cluster membership vector. Tc[n] = k indicates cluster membership of vertex n to the k'th discrete cluster.

Related

source
PortfolioOptimisers.BubbleMember — Function
BubbleMember(Rpm::AbstractMatrix{<:Real}, Mv::AbstractMatrix{<:Real},
             Mc::AbstractMatrix{<:Real})

Assign each vertex to a specific bubble in the bubble hierarchy.

This function determines the bubble membership of each vertex, resolving ambiguities when a vertex could belong to multiple bubbles. Assignment is based on the strength of connections (edge weights) between the vertex and each candidate bubble.

Arguments

  • Rpm: N×N sparse weighted adjacency matrix of the PMFG.
  • Mv: N×Nb bubble membership matrix for vertices. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • Mc: Matrix indicating bubbles that coincide with clusters.

Details

  • Vertices belonging to a single bubble are assigned directly.
  • For vertices that could belong to multiple bubbles, assignment is made to the bubble with the strongest normalized connection (fraction of edge weights).
  • Used internally for intra- and inter-cluster hierarchy construction in DBHT clustering.

Returns

  • Mvv::Matrix{Int}: N×Nb matrix where Mvv[n, bi] = 1 if vertex n is assigned to bubble bi.

Related

source
PortfolioOptimisers.DendroConstruct — Function
DendroConstruct(Zi::AbstractMatrix{<:Real}, LabelVec1::AbstractVector{<:Real},
                LabelVec2::AbstractVector{<:Real},
                LinkageDist::Union{<:Real, <:AbstractVector{<:Real}})

Construct the linkage matrix by continually adding rows to the matrix.

This function appends a new row to the linkage matrix at each iteration, recording the merge of clusters as indicated by changes in the label vectors. It is used internally for building dendrograms in DBHT and related hierarchical clustering routines.

Inputs

  • Zi: Linkage matrix at iteration i in the same format as the output from Matlab.
  • LabelVec1: Label vector for the vertices in the bubble for the previous valid iteration.
  • LabelVec2: Label vector for the vertices in the bubble for the trial iteration.
  • LinkageDist: Linkage distance(s) for the current merge.

Details

  • The function identifies which clusters have changed between LabelVec1 and LabelVec2 and appends a new row to the linkage matrix for the merge.
  • The linkage matrix Z can be converted to a format compatible with Clustering.Hclust using turn_into_Hclust_merges.
  • Used internally by HierarchyConstruct4s and related routines for DBHT dendrogram construction.

Returns

  • Z::AbstractMatrix{<:Real}: Linkage matrix at iteration i + 1 in the same format as the output from Matlab.

Related

source
PortfolioOptimisers.LinkageFunction — Function
LinkageFunction(d::AbstractMatrix{<:Real}, labelvec::AbstractVector{<:Real})

Find the pair of clusters with the best linkage in a bubble.

This function searches for the pair of clusters (as indicated by labelvec) with the strongest linkage according to the provided distance matrix d. The best linkage is defined as the pair with the maximum inter-cluster distance among all pairs of clusters in the bubble. Used internally for hierarchical linkage construction in DBHT dendrogram routines.

Inputs

  • d: Nv×Nv distance matrix for the vertices assigned to a bubble.
  • labelvec: Label vector for the vertices in the bubble.

Details

  • For each unique pair of cluster labels, the function computes the maximum distance between their members.
  • Returns the pair with the largest such distance and the corresponding value.
  • Used in build_link_and_dendro and HierarchyConstruct4s to determine which clusters to merge at each step.

Returns

  • PairLink::Vector{Int}: Pair of cluster labels with the best linkage.
  • dvu::Real: Value of the best linkage (maximum inter-cluster distance).

Related

source
PortfolioOptimisers.build_link_and_dendro — Function
build_link_and_dendro(rg::AbstractRange, dpm::AbstractMatrix{<:Real},
                      LabelVec::AbstractVector{<:Real}, LabelVec1::AbstractVector{<:Real},
                      LabelVec2::AbstractVector{<:Real}, V::AbstractVector{<:Real},
                      nc::Real, Z::AbstractMatrix{<:Real})

Iteratively construct the linkage matrix for a bubble or cluster.

This function iterates over the vertices in a bubble or cluster, merging the pair of clusters with the best linkage at each step (as determined by LinkageFunction), and appending the corresponding row to the linkage matrix using DendroConstruct. Used internally for building dendrograms in DBHT and related hierarchical clustering routines.

Inputs

  • rg: Range of indices for the vertices in the bubble or cluster.
  • dpm: Distance matrix for the vertices assigned to the bubble or cluster.
  • LabelVec: Current label vector for the clusters.
  • LabelVec1: Label vector for the previous valid iteration.
  • LabelVec2: Label vector for the trial iteration.
  • V: Indices of the vertices in the bubble or cluster.
  • nc::Real: Inverse of the linkage distance (or a counter for the merge steps).
  • Z: Current linkage matrix.

Details

  • At each iteration, finds the pair of clusters with the best linkage using LinkageFunction.
  • Merges the pair by updating the label vector, and appends a new row to the linkage matrix using DendroConstruct.
  • Continues until all clusters in the range are merged.

Returns

  • Z::AbstractMatrix{<:Real}: Updated linkage matrix after all merges in the range.
  • nc::Real: Updated inverse linkage distance or merge counter.
  • LabelVec1::AbstractVector{<:Real}: Updated label vector for the next iteration.

Related

source
PortfolioOptimisers.HierarchyConstruct4s — Function
HierarchyConstruct4s(Rpm::AbstractMatrix{<:Real}, Dpm::AbstractMatrix{<:Real},
                     Tc::AbstractVector{<:Real}, Mv::AbstractMatrix{<:Real})

Constructs the intra- and inter-cluster hierarchy by utilizing the Bubble Hierarchy structure of a Maximal Planar Graph, specifically a Planar Maximally Filtered Graph (PMFG).

This function builds a hierarchical clustering (dendrogram) by first constructing intra-cluster linkages within each cluster (using the bubble structure), and then merging clusters to form the global hierarchy. It is a core step in the DBHT (Direct Bubble Hierarchical Tree) clustering pipeline.

Inputs

  • Rpm: N×N sparse weighted adjacency matrix of the PMFG.
  • Dpm: N×N shortest path lengths matrix of the PMFG.
  • Tc: N×1 cluster membership vector. Tc[n] = k indicates cluster membership of vertex n to the k'th discrete cluster.
  • Mv: N×Nb bubble membership matrix. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.

Details

- For each cluster, the function identifies the bubbles that coincide with the cluster and assigns each vertex to a specific bubble using [`BubbleMember`](@ref).
- It constructs intra-bubble and intra-cluster linkages using [`build_link_and_dendro`](@ref).
- After intra-cluster linkage, it merges clusters to form the global hierarchy using inter-cluster linkage steps.
- The resulting linkage matrix can be converted to a format compatible with [`Clustering.Hclust`](https://juliastats.org/Clustering.jl/stable/hclust.html#Clustering.Hclust) using [`turn_into_Hclust_merges`](@ref).
- Used internally by DBHT clustering routines for dendrogram construction.

Returns

  • Z::AbstractMatrix{<:Real}: (N-1)×3 linkage matrix in the same format as the output from Matlab, suitable for conversion to Clustering.Hclust.

Related

source
PortfolioOptimisers.turn_into_Hclust_merges — Function
turn_into_Hclust_merges(Z::AbstractMatrix{<:Real})

Convert a Matlab-style linkage matrix to a format compatible with Clustering.Hclust.

This function transforms a linkage matrix produced by DBHT or similar hierarchical clustering routines into the format required by Clustering.Hclust, including proper indexing and cluster size tracking.

Inputs

  • Z: Matlab-style linkage matrix, where each row represents a merge step with cluster indices and linkage heights.

Details

  • For each merge, leaf indices are converted to negative values, and cluster sizes are accumulated in the fourth column.
  • Internal cluster indices are updated to reference the correct merged clusters.
  • The resulting matrix can be passed directly to Clustering.Hclust for dendrogram construction and further analysis.

Returns

  • Z::AbstractMatrix{<:Real}: Linkage matrix in Clustering.Hclust format, with updated indices and cluster sizes.

Related

source
PortfolioOptimisers.DBHTs — Function
DBHTs(D::AbstractMatrix{<:Real}, S::AbstractMatrix{<:Real}; branchorder::Symbol = :optimal,
      root::DBHTRootMethod = UniqueRoot())

Perform Direct Bubble Hierarchical Tree clustering, a deterministic clustering algorithm [1]. This version uses a graph-theoretic filtering technique called Triangulated Maximally Filtered Graph (TMFG).

This function implements the full DBHT clustering pipeline: it constructs a Planar Maximally Filtered Graph (PMFG) from the similarity matrix, extracts the clique and bubble hierarchies, assigns clusters, and builds a hierarchical clustering (dendrogram) compatible with Clustering.Hclust.

Arguments

  • D: N×N dissimilarity matrix (e.g., a distance matrix). Must be symmetric and non-empty.
  • S: N×N non-negative similarity matrix. Must be symmetric and non-empty.
  • branchorder: Ordering method for the dendrogram branches. Accepts :optimal, :barjoseph, or :r.
  • root: Root selection method for the clique hierarchy.

Validation

  • !isempty(D) && issymmetric(D).
  • !isempty(S) && issymmetric(S).
  • size(D) == size(S).

Details

Returns

  • T8::Vector{Int}: N×1 cluster membership vector.
  • Rpm::SparseMatrixCSC{<:Real, Int}: N×N adjacency matrix of the Planar Maximally Filtered Graph (PMFG).
  • Adjv::SparseMatrixCSC{Int, Int}: Bubble cluster membership matrix from BubbleCluster8s.
  • Dpm::Matrix{<:Real}: N×N shortest path length matrix of the PMFG.
  • Mv::SparseMatrixCSC{Int, Int}: N×Nb bubble membership matrix. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • Z::Matrix{<:Real}: (N-1)×3 linkage matrix in Matlab format.
  • Z_hclust::Clustering.Hclust: Dendrogram in Clustering.Hclust format.

Related

source
PortfolioOptimisers.jlogo! — Function
jlogo!(jlogo::AbstractMatrix, sigma::AbstractMatrix, source::AbstractMatrix, sign::Integer)

Efficiently accumulate contributions to the sparse inverse covariance matrix for LoGo/DBHT.

This internal function updates the jlogo matrix in-place by iterating over a list of cliques or separators (source), extracting the corresponding submatrix from the covariance matrix sigma, inverting it, and adding (or subtracting) the result to the appropriate block in jlogo, scaled by sign.

Arguments

  • jlogo: The matrix to be updated in-place.
  • sigma: The full covariance matrix.
  • source: Each row contains indices of a clique or separator (e.g., 4-cliques or 3-cliques).
  • sign: +1 for cliques, -1 for separators.

Details

  • For each row in source, the function extracts the submatrix of sigma corresponding to the clique/separator.
  • The inverse of this submatrix is computed and added to (or subtracted from) the corresponding block in jlogo.
  • Used internally by J_LoGo to efficiently compute the sparse inverse covariance matrix for LoGo/DBHT.

Returns

  • nothing, updates jlogo in-place.

Related

source
— Function
J_LoGo(sigma::AbstractMatrix, separators::AbstractMatrix, cliques::AbstractMatrix)

Compute the sparse inverse covariance matrix using the LoGo (Local-Global) algorithm [2].

This function implements the LoGo sparse inverse covariance estimation by combining clique and separator contributions from a Planar Maximally Filtered Graph (PMFG) or similar clique tree structure. It efficiently accumulates the inverses of covariance submatrices corresponding to cliques and separators, producing a sparse precision (inverse covariance) matrix suitable for robust portfolio optimization and risk management.

Arguments

  • sigma: The covariance matrix (N×N).
  • separators: Each row contains indices of a separator (typically 3-cliques).
  • cliques: Each row contains indices of a clique (typically 4-cliques).

Details

  • For each clique, the inverse of the corresponding submatrix of sigma is added to the output.
  • For each separator, the inverse of the corresponding submatrix is subtracted.
  • The resulting matrix is the sparse inverse covariance estimate, as described in the LoGo methodology.
  • Used internally by LoGo and related estimators.

Returns

  • jlogo::Matrix{<:Real}: The LoGo sparse inverse covariance matrix.

Related

source
PortfolioOptimisers.LoGo_dist_assert — Function
LoGo_dist_assert(dist::AbstractDistanceEstimator, sigma::AbstractMatrix, X::AbstractMatrix)

Validate compatibility of the distance estimator and covariance matrix for LoGo sparse inverse covariance estimation by checking size(sigma, 1) == size(X, 2).

Arguments

  • dist: Distance estimator, typically a subtype of AbstractDistanceEstimator.
  • sigma: Covariance matrix (N×N).
  • X: Data matrix (T×N or N×T).

Returns

  • nothing. Throws an error if validation fails.

Related

source
LoGo_dist_assert(args...)

No-op fallback for other distance estimators.

Returns

  • nothing.
source
PortfolioOptimisers.logo! — Function
logo!(je::LoGo, pdm::Union{Nothing, <:Posdef}, sigma::AbstractMatrix, X::AbstractMatrix;
      dims::Int = 1, kwargs...)

Compute the LoGo (Local-Global) covariance matrix and update sigma in-place.

This method implements the LoGo algorithm for sparse inverse covariance estimation using the Planar Maximally Filtered Graph (PMFG) and clique-based decomposition. It validates inputs, computes the similarity and distance matrices, constructs the PMFG, identifies cliques and separators, and updates the input covariance matrix sigma in-place by inverting the LoGo sparse inverse covariance estimate. The result is projected to the nearest positive definite matrix if a Posdef estimator is provided.

Arguments

  • je: LoGo algorithm instance.
  • pdm: Optional positive definite matrix estimator.
  • sigma: Covariance matrix (N×N), updated in-place with the LoGo sparse inverse covariance.
  • X: Data matrix (T×N).
  • dims: Dimension along which to compute statistics (1 for columns/assets, 2 for rows). Default: 1.
  • kwargs...: Additional keyword arguments passed to distance and similarity estimators.

Details

  • If rho is a covariance matrix, it is converted to a correlation matrix using StatsBase.cov2cor.
  • Computes the distance matrix using the configured distance estimator.
  • Computes the similarity matrix using the configured similarity algorithm.
  • Constructs the PMFG and extracts cliques and separators.
  • Computes the LoGo sparse inverse covariance matrix via J_LoGo.
  • Updates sigma in-place with the inverse of the LoGo estimate.
  • Projects the result to the nearest positive definite matrix if pdm is provided.

Validation

- `size(sigma, 1) == size(sigma, 2)`.
- `size(sigma, 1) == size(X, 2)`.

Returns

  • nothing. The input sigma is updated in-place.

Related

source
PortfolioOptimisers.matrix_processing_algorithm! — Method
matrix_processing_algorithm!(je::LoGo, pdm::Union{Nothing, <:Posdef}, sigma::AbstractMatrix,
                             X::AbstractMatrix; dims::Int = 1, kwargs...)

Apply the LoGo (Local-Global) transformation in-place to the covariance matrix as a matrix processing algorithm to.

This method provides a standard interface for applying the LoGo algorithm to a covariance matrix within the matrix processing pipeline of PortfolioOptimisers.jl. It validates inputs, computes the LoGo sparse inverse covariance matrix, and updates sigma in-place. If a positive definite matrix estimator (pdm) is provided, the result is projected to the nearest positive definite matrix.

Arguments

  • je: LoGo algorithm instance (LoGo).
  • pdm: Optional positive definite matrix estimator (e.g., Posdef()), or nothing.
  • sigma: Covariance matrix (N×N), updated in-place.
  • X: Data matrix (T×N or N×T).
  • dims: Dimension along which to compute statistics (1 for columns/assets, 2 for rows). Default: 1.
  • kwargs...: Additional keyword arguments passed to distance and similarity estimators.

Details

  • Internally, it calls logo! to perform the LoGo sparse inverse covariance estimation and update sigma in-place.
  • Used in composable workflows for covariance matrix estimation.

Returns

  • nothing. The input sigma is updated in-place.

Related

source