GitHub

Direct Bubble Hierarchy Tree

PortfolioOptimisers.EqualRoot — Type
struct EqualRoot <: DBHTRootMethod

Builds one root from the adjacency tree of every root candidate.

This keeps several equally plausible roots of the DBHT hierarchy rather than choosing between them.

Related

References

  • [53] W.-M. Song, T. Di Matteo and T. Aste. Nested hierarchies in planar graphs. Discrete Applied Mathematics 159, 2135–2146 (2011).
source
PortfolioOptimisers.DBHT — Type
struct DBHT{__T_sim<:AbstractNonNegativeSimilarityMatrixAlgorithm, __T_root} <: AbstractHierarchicalClusteringAlgorithm

Clusters assets by the bubble hierarchy of a triangulated maximally filtered graph.

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

Fields

  • sim: Similarity matrix algorithm. The PMFG cannot take a negative weight, so the family is the non-negative one and AngularSimilarity is refused.
  • root: Root selection method.

Constructors

DBHT(;    sim::AbstractNonNegativeSimilarityMatrixAlgorithm = MaximumDistanceSimilarity(),    root::DBHTRootMethod = UniqueRoot()) -> DBHT

Keywords correspond to the struct's fields.

Examples

julia> DBHT()DBHT   sim ┼ MaximumDistanceSimilarity()  root ┴ UniqueRoot()

Related

References

  • [54] W.-M. Song, T. Di Matteo and T. Aste. Hierarchical information clustering by means of topologically embedded graphs. PloS one 7, e31929 (2012).
source
struct LoGo{__T_de, __T_sim<:AbstractNonNegativeSimilarityMatrixAlgorithm, __T_pdm} <: InverseMatrixSparsificationAlgorithm

Sparsifies the inverse covariance matrix on the cliques of an information filtering network.

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 [55]. 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.

What is sparse is the precision, not the covariance

J_LoGo sums the inverse of each clique block and subtracts the inverse of each separator block, and the matrix that comes out is exactly zero wherever the network carries no edge. Measured over a 20-asset sample, the triangulated maximally filtered graph holds 54 edges — the 3n - 6 of a maximal planar graph — and the largest absolute entry of the precision matrix away from those edges is 0.0.

sigma is then replaced by the inverse of that precision matrix, so what the caller receives is dense. The filtering is a statement about which pairs are conditionally independent given the rest, and it survives only in the precision.

Fields

  • de: Distance matrix estimator.
  • sim: Similarity matrix algorithm. The PMFG cannot take a negative weight, so the family is the non-negative one and AngularSimilarity is refused.
  • pdm: Positive definite matrix estimator.

Constructors

LoGo(;    de::AbstractDistanceEstimator = Distance(; alg = CanonicalDistance()),    sim::AbstractNonNegativeSimilarityMatrixAlgorithm = MaximumDistanceSimilarity(),    pdm::Option{<:AbstractPosdefEstimator} = Posdef()) -> LoGo

Keywords correspond to the struct's fields.

Examples

julia> LoGo()LoGo   de ┼ Distance      │   power ┼ nothing      │     alg ┴ CanonicalDistance()  sim ┼ MaximumDistanceSimilarity()  pdm ┼ Posdef      │      alg ┼ UnionAll: NearestCorrelationMatrix.Newton      │   kwargs ┴ @NamedTuple{}: NamedTuple()

Related

References

  • [55] W. Barfuss, G. P. Massara, T. Di Matteo and T. Aste. Parsimonious modeling with information filtering networks. Phys. Rev. E 94, 062306 (2016).
source
PortfolioOptimisers.clusterise — Method
clusterise(cle::ClustersEstimator{<:Any, <:Any, <:DBHT, <:Any}, X::MatNum;
           branchorder::Symbol = :optimal, dims::Int = 1, kwargs...)

Perform Direct Bubble Hierarchical Tree (DBHT) clustering using a ClustersEstimator 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 Clusters result containing the hierarchical clustering, similarity and distance matrices, and the optimal number of clusters.

Arguments

  • cle: A ClustersEstimator 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: Dimension along which to perform the computation.
  • 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 distance_to_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 Clusters result encapsulating all relevant outputs.

Returns

  • clr::Clusters: DBHT clustering result.

Related

source
PortfolioOptimisers.DBHTRootMethod — Type
abstract type DBHTRootMethod <: AbstractAlgorithm

Abstract supertype for all Direct Bubble Hierarchy Tree (DBHT) root selection methods.

The root is chosen inside CliqHierarchyTree2s, which builds the clique hierarchy of the planar graph. A hierarchy needs one node with no parent, and the planar clique tree can present several candidates, so the choice of which of them becomes the root is a member of this family.

Related

References

  • [53] W.-M. Song, T. Di Matteo and T. Aste. Nested hierarchies in planar graphs. Discrete Applied Mathematics 159, 2135–2146 (2011).
  • [54] W.-M. Song, T. Di Matteo and T. Aste. Hierarchical information clustering by means of topologically embedded graphs. PloS one 7, e31929 (2012).
source
PortfolioOptimisers.InverseMatrixSparsificationAlgorithm — Type
abstract type InverseMatrixSparsificationAlgorithm <: AbstractMatrixProcessingAlgorithm

Abstract supertype for all inverse matrix sparsification algorithms.

A member of this family imposes a sparsity pattern on the inverse of a covariance matrix rather than on the matrix itself. The covariance that comes back is dense; what is sparse is its precision, and the zeros there are the conditional independences the information filtering network selected.

Related

References

  • [55] W. Barfuss, G. P. Massara, T. Di Matteo and T. Aste. Parsimonious modeling with information filtering networks. Phys. Rev. E 94, 062306 (2016).
source
PortfolioOptimisers.PMFG_T2s — Function
PMFG_T2s(W::MatNum, 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.

nargout is a positional argument, and every caller passes it positionally.

The TMFG approximates the PMFG, and is not it

The planar maximally filtered graph is the exact solution of the weighted maximal planar graph problem, which is costly. The triangulation this function builds is the cheap greedy approximation to it, so the name of the function is the problem and the algorithm is the approximation. Both are maximal planar graphs, so both carry exactly $3N - 6$ edges against the $N - 1$ of a minimum spanning tree: measured over a 20-asset sample, the graph holds 54 edges.

Arguments

  • W: N × N matrix of non-negative, finite weights (e.g. a similarity matrix from an AbstractNonNegativeSimilarityMatrixAlgorithm, or an absolute correlation matrix).
  • nargout: Number of outputs to build. cliques is built when nargout > 3 and cliqueTree when nargout > 4; each is nothing otherwise. The first three outputs are always built.

Validation

  • N >= 9 is required for a meaningful PMFG.
  • No entry in W is NaN.
  • All entries in W are non-negative.

An entry that is exactly zero passes all three and still costs the graph an edge, because A carries the structure in its sparsity pattern and this function declines no edge on the way in. That is assert_pmfg_weights's check, and it runs in the callers that consume the weighted structure rather than here, because logo! reads only the cliques and is unaffected by a zero.

The checks are a backstop, not the enforcement

Every estimator that reaches this function — NetworkEstimator, DBHT and LoGo — bounds its similarity field by AbstractNonNegativeSimilarityMatrixAlgorithm and calls assert_similarity_domain before it transforms, so a shipped configuration that would fail here fails earlier, at construction or at the seam, with a message that names the configuration rather than W.

These two checks are kept for the case those cannot cover: that family is open by declaration, so an extension can subtype it and return a negative anyway. The failure downstream is silent — DirectHb sums signed mass and a cancelling row manufactures a separating bubble — so a wrong clustering would come back with no error at all.

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{<:Number, 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::Option{Matrix{Int}}: List of all 4-cliques (tetrahedra), or nothing if nargout <= 3.
  • cliqueTree::Option{SparseMatrixCSC{Int, Int}}: 4-cliques tree structure (adjacency matrix), or nothing if nargout <= 4.

Related

References

  • [56] G. P. Massara, T. Di Matteo and T. Aste. Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks 5, 161–178 (2016).
  • [57] M. Tumminello, T. Aste, T. Di Matteo and R. N. Mantegna. A tool for filtering information in complex systems. Proceedings of the National Academy of Sciences 102, 10421–10426 (2005).
source
PortfolioOptimisers.assert_pmfg_weights — Function
assert_pmfg_weights(A::MatNum,
                    sim::Option{<:AbstractSimilarityMatrixAlgorithm} = nothing,
                    de::Option{<:AbstractDistanceEstimator} = nothing)

Check that the weights did not delete an edge from the graph PMFG_T2s built.

A maximal planar graph on N >= 3 vertices has exactly 3N - 6 edges, and PMFG_T2s returns the structure and the weights in one matrix, A = W ⊙ ((A + A') .== 1). An exactly zero weight is therefore an absent edge rather than a weak one, and what reaches the consumer is no longer a PMFG. This function counts the stored edges and refuses the difference.

The zero is admissible input and an unusable structure

PMFG_T2s's own check is >= 0 and stays that way, because a zero is an honest similarity. ExponentialSimilarity maps the infinite distance LogDistance returns at an exactly zero correlation to exp(-Inf), which is 0 exactly, and ComplementSimilarity maps D = 1 to 0. The value is right. What it cannot do is carry an edge.

Without this check the failure is a BoundsError about a matrix index, raised much later inside turn_into_Hclust_merges, because HierarchyConstruct4s then builds fewer merges than the dendrogram needs.

Where it runs, and where it deliberately does not

At the three sites that consume the weighted structure: DBHTs, calc_weighted_adjacency_graph and calc_distance_weighted_graph.

logo! is the fourth PMFG_T2s caller and is not guarded. It reads separators and cliques, which PMFG_T2s derives from the insertion order rather than from A, so a zero weight does not change its answer and refusing it would refuse a configuration that works.

Arguments

  • A: N × N weighted adjacency matrix, the first output of PMFG_T2s.
  • sim: Similarity matrix algorithm that produced the weights, named in the message. Read for nothing else, as assert_similarity_domain reads its de.
  • de: Distance estimator the similarity was derived from, named in the message beside sim.

Each caller passes what it holds, so the message names as much of the configuration as the site knows. calc_distance_weighted_graph holds both halves, calc_weighted_adjacency_graph and DBHTs hold the similarity, and a caller that holds only the matrices names neither.

Validation

  • The number of stored edges is 3N - 6.

Returns

  • nothing.

Related

source
PortfolioOptimisers.distance_wei — Function
distance_wei(L::MatNum)

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{<:Number}: 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::MatNum)

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::MatNum, 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::VecNum: 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::MatNum, Cliq::VecNum)

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::MatNum)

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::MatNum, CliqList::MatNum,
        CliqRoot::VecNum)

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::VecNum, Sb::VecNum)

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::VecNum, Pred::VecNum, 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::VecNum, Pred::VecNum, Nc::Integer,
           A::MatNum, CliqList::MatNum)

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::MatNum; 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: Adjacency matrix of the MPG, where nonzero entries indicate edges.
  • root: 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

References

  • [53] W.-M. Song, T. Di Matteo and T. Aste. Nested hierarchies in planar graphs. Discrete Applied Mathematics 159, 2135–2146 (2011).
source
PortfolioOptimisers.DirectHb — Function
DirectHb(Rpm::MatNum, Hb::MatNum,
         Mb::MatNum, Mv::MatNum,
         CliqList::MatNum)

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: N × N sparse weighted adjacency matrix of the PMFG.
  • Hb: Undirected bubble tree of the PMFG (as from BubbleHierarchy).
  • Mb: Nc×Nb bubble membership matrix for 3-cliques. Mb[n, bi] = 1 indicates 3-clique n belongs to bubble bi.
  • Mv: N × Nb bubble membership matrix for vertices. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • CliqList: 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{Number, 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::MatNum, Dpm::MatNum,
                Hb::MatNum, Mb::MatNum,
                Mv::MatNum, CliqList::MatNum)

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: N × N sparse weighted adjacency matrix of the PMFG.
  • Dpm: N × N shortest path lengths matrix of the PMFG.
  • Hb: Undirected bubble tree of the PMFG (from BubbleHierarchy).
  • Mb: Nc×Nb bubble membership matrix for 3-cliques. Mb[n, bi] = 1 indicates 3-clique n belongs to bubble bi.
  • Mv: N × Nb bubble membership matrix for vertices. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
  • CliqList: 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::MatNum, Mv::MatNum,
             Mc::MatNum)

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 may 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 may 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::MatNum, LabelVec1::VecNum,
                LabelVec2::VecNum,
                LinkageDist::Num_VecNum)

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::MatNum: Linkage matrix at iteration i + 1 in the same format as the output from Matlab.

Related

source
PortfolioOptimisers.LinkageFunction — Function
LinkageFunction(d::MatNum, labelvec::VecNum)

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::Number: Value of the best linkage (maximum inter-cluster distance).

Related

source
PortfolioOptimisers.build_link_and_dendro — Function
build_link_and_dendro(
    rg::AbstractRange,
    dpm::MatNum,
    LabelVec::VecNum,
    LabelVec1::VecNum,
    LabelVec2::VecNum,
    V::VecNum,
    nc::Number,
    Z::MatNum
)

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::Number: 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::MatNum: Updated linkage matrix after all merges in the range.
  • nc::Number: Updated inverse linkage distance or merge counter.
  • LabelVec1::VecNum: Updated label vector for the next iteration.

Related

source
PortfolioOptimisers.HierarchyConstruct4s — Function
HierarchyConstruct4s(
    Rpm::MatNum,
    Dpm::MatNum,
    Tc::VecNum,
    Mv::MatNum
)

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.
  • It constructs intra-bubble and intra-cluster linkages using build_link_and_dendro.
  • 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 using turn_into_Hclust_merges.
  • Used internally by DBHT clustering routines for dendrogram construction.

Returns

  • Z::MatNum: (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::MatNum)

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::MatNum: Linkage matrix in Clustering.Hclust format, with updated indices and cluster sizes.

Related

source
PortfolioOptimisers.DBHTs — Function
DBHTs(D::MatNum, S::MatNum; branchorder::Symbol = :optimal,
      root::DBHTRootMethod = UniqueRoot(),
      sim::Option{<:AbstractSimilarityMatrixAlgorithm} = nothing)

Perform Direct Bubble Hierarchical Tree clustering, a deterministic clustering algorithm [54]. 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.
  • sim: Similarity matrix algorithm that produced S. It is forwarded to assert_pmfg_weights and read for nothing else, so that a refusal names the configuration rather than the matrix. A caller that holds only the matrices leaves it nothing.

Validation

  • !isempty(D) && LinearAlgebra.issymmetric(D).
  • !isempty(S) && LinearAlgebra.issymmetric(S).
  • size(D) == size(S).
  • The PMFG built from S keeps its 3N - 6 edges, by assert_pmfg_weights. An exactly zero similarity is an absent edge.

Details

Returns

  • T8::Vector{Int}: N × 1 cluster membership vector.
  • Rpm::SparseMatrixCSC{<:Number, Int}: N × N adjacency matrix of the Planar Maximally Filtered Graph (PMFG).
  • Adjv::SparseMatrixCSC{Int, Int}: Bubble cluster membership matrix from BubbleCluster8s.
  • Dpm::Matrix{<:Number}: 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{<:Number}: (N-1)×3 linkage matrix in Matlab format.
  • Z_hclust::Clustering.Hclust: Dendrogram in Clustering.Hclust format.

Related

source
PortfolioOptimisers.jlogo! — Function
jlogo!(jlogo::MatNum, sigma::MatNum, source::MatNum, 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
J_LoGo(sigma::MatNum, separators::MatNum, cliques::MatNum)

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

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{<:Number}: The LoGo sparse inverse covariance matrix.

Related

source
PortfolioOptimisers.LoGo_dist_assert — Function
LoGo_dist_assert(de::AbstractDistanceEstimator, sigma::MatNum, X::MatNum)

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

The check runs for a VariationInfoDistance estimator alone, which is the only family that reads X rather than the correlation matrix. Every other estimator takes the no-op fallback, so a mismatched X passes.

Arguments

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

Validation

  • size(sigma, 1) == size(X, 2).

Returns

  • nothing.

Related

source
LoGo_dist_assert(args...)

No-op fallback for other distance estimators.

Returns

  • nothing.
source
PortfolioOptimisers.logo! — Function
logo!(::Nothing, args...; kwargs...)

No-op fallback: return nothing when no LoGo algorithm is configured.

Related

source
logo!(je::LoGo, sigma::MatNum, X::MatNum;
      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 not nothing.

Arguments

  • je: LoGo algorithm instance.
  • sigma: Covariance matrix (N × N), updated in-place with the LoGo sparse inverse covariance.
  • X: Data matrix (T × N).
  • dims: Dimension along which to perform the computation.
  • kwargs...: Additional keyword arguments passed to distance and similarity estimators.

Details

  • If sigma is a covariance matrix, a correlation matrix is derived from it with StatsBase.cov2cor and used for the distance and the similarity. sigma itself stays a covariance, and it is what J_LoGo decomposes.
  • 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 not nothing.

Validation

  • size(sigma, 1) == size(sigma, 2).
  • size(sigma, 1) == size(X, 2), only when je.de reads X. LoGo_dist_assert carries the check, and it has a method for the variation-of-information estimators alone; every other estimator takes the no-op fallback. A default LoGo() therefore accepts a 20 × 20 sigma beside a 400 × 10 X and returns without raising, because CanonicalDistance derives the distance from the correlation matrix and never touches X.

Returns

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

Related

source
logo(je::LoGo, sigma::MatNum, X::MatNum; dims::Int = 1, kwargs...) -> MatNum

Apply the LoGo (Local-Global) transformation to the covariance matrix and return the result as a new matrix.

This is the non-mutating variant of logo!. It copies sigma before applying the transformation.

Arguments

  • je::LoGo: LoGo algorithm configuration.
  • sigma::MatNum: Covariance matrix to transform (not mutated).
  • X::MatNum: Returns data matrix.
  • dims::Int = 1: Observation dimension.

Returns

  • New matrix with LoGo transformation applied.

Related

source
PortfolioOptimisers.matrix_processing_algorithm! — Method
matrix_processing_algorithm!(je::LoGo, sigma::MatNum,
                             X::MatNum; dims::Int = 1, kwargs...)

Apply the LoGo (Local-Global) transformation in-place to the covariance matrix, as a step of the matrix processing pipeline.

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 not nothing, the result is projected to the nearest positive definite matrix.

Arguments

  • je: LoGo algorithm instance (LoGo). Its own pdm field carries the positive definite repair, so there is no pdm argument here.
  • sigma: Covariance matrix (N × N), updated in-place.
  • X: Data matrix (T × N or N × T).
  • dims: Dimension along which to perform the computation.
  • 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

References

[53]
[54]
W.-M. Song, T. Di Matteo and T. Aste. Hierarchical information clustering by means of topologically embedded graphs. PloS one 7, e31929 (2012).
[55]
W. Barfuss, G. P. Massara, T. Di Matteo and T. Aste. Parsimonious modeling with information filtering networks. Phys. Rev. E 94, 062306 (2016).
[56]
[57]
M. Tumminello, T. Aste, T. Di Matteo and R. N. Mantegna. A tool for filtering information in complex systems. Proceedings of the National Academy of Sciences 102, 10421–10426 (2005).