Bubble Tree: private API
The functions on this page and on the DBHT dendrogram page are two parts of DBHTs. The functions here build the bubble tree of the planar graph and assign each asset to a cluster. The functions on the dendrogram page turn the clusters into a hierarchy. Each function takes and returns matrices, so you can call each one on its own. The bubble hierarchy Hb is a sparse matrix.
PortfolioOptimisers.BubbleHierarchy — Function
BubbleHierarchy(Pred::VecNum, Sb::VecNum)Build the bubble tree from the parents of the 3-cliques and the sizes of their interiors.
The function puts the 3-cliques into bubbles, from the parent vector Pred and the interior sizes Sb. It builds the adjacency matrix of the bubbles and the bubble membership matrix of the 3-cliques.
Algorithm
- Take
Root, the cliques whose entry ofPredis zero, and mark them inCliqCount. - When more than one root exists, open one bubble that holds all of them, as the first column of
Mb. - For each root
n, open a bubble that holdsnand its direct children, the cliques whose parent isn. Append the bubble as a column ofMb, and mark those children inCliqCount. - Collect as the next roots the direct children whose interior is not empty, where
Sbis not zero. - Repeat from step 3 until
CliqCountmarks every clique. - Build
H. Two bubbles are neighbours when at least one 3-clique belongs to both. - Symmetrise
Hand clear its diagonal, so a bubble is not its own neighbour.
Arguments
Pred:Nc×1vector of the parent of each 3-clique, fromBuildHierarchy.Sb:Nc×1vector of the number of vertices in the interior of each 3-clique.Sb[n] ≠ 0means that cliquenseparates the graph.
Returns
H::SparseMatrixCSC{Int, Int}:Nb×Nbsymmetric adjacency matrix of the bubble tree, whereNbis the number of bubbles.Mb::Matrix{Int}:Nc×Nbbubble membership matrix of the 3-cliques.Mb[n, bi] = 1means that 3-cliquenbelongs to bubblebi.
Related
PortfolioOptimisers.DirectHb — Function
DirectHb(Rpm::MatNum, Hb::MatNum,
Mb::MatNum, Mv::MatNum,
CliqList::MatNum)Give a direction to each edge of the bubble tree of a Maximal Planar Graph (MPG).
Each edge of the undirected bubble tree of a Planar Maximally Filtered Graph (PMFG) holds one separating 3-clique. The function gives each edge a direction, and the result is the directed bubble hierarchical tree (DBHT). The sums of the edge weights on the two sides of the clique set the direction. The directions then show the converging and the diverging bubbles.
Mathematical definition
Each edge of the bubble tree holds one separating 3-clique. A cut of the edge splits the bubbles into two sides, and the mass that each side draws through the clique sets the direction.
\[m(\mathcal{V}) = \sum_{u \in \mathcal{V}_{0}} \sum_{v \in \mathcal{V}} R_{u,\,v}\,.\]
Where:
- $R_{u,\,v}$: Weight of the PMFG edge between vertices $u$ and $v$.
- $\mathcal{V}_{0}$: The three vertices of the separating clique.
- $\mathcal{V}$: Vertices of one side of the cut, with $\mathcal{V}_{0}$ removed.
- $m(\mathcal{V})$: Mass the clique draws from that side.
The function directs the edge towards the heavier side. A bubble that is the heavier side of each of its edges has no outgoing edge, and it is a converging bubble.
Algorithm
- Reduce
Hbto binary, and read the row and column index of each edge of its upper triangle. - For each such edge, find the 3-cliques that both of its bubbles hold, and record
(row, column, clique)as a row ofCliqEdge. - For each row of
CliqEdge, remove that edge from a copy ofHb, runbreadthfrom bubble1, and mark every bubble it did not reach with-1. - Split the two bubbles of the edge into
bleft, the one on the reached side, andbright, the one on the cut side. - Collect
vleftandvright, the vertices of the bubbles of each side, and remove from both the three verticesvoof the separating clique. - Sum the PMFG weights from
vointo each side, which givesleftandright. Write the heavier of the two intoHcas an edge directed towards the heavier side. A tie directs the edge towardsbright. - Set
Sep[b] = 1for a bubble with no outgoing edge inHc, then setSep[b] = 2for a bubble with no incoming edge that has more than one neighbour inHb.
Arguments
Rpm:N × Nsparse weighted adjacency matrix of the PMFG.Hb:Nb×Nbundirected bubble tree of the PMFG, fromBubbleHierarchy. A non-zero entry joins two bubbles.Mb:Nc×Nbbubble membership matrix of the 3-cliques.Mb[n, bi] = 1means that 3-cliquenbelongs to bubblebi.Mv:N × Nbbubble membership matrix of the vertices.Mv[n, bi] = 1means that vertexnis a vertex of bubblebi.CliqList:Nc×3matrix. Each row lists the three vertices of a 3-clique of the MPG.
Returns
Hc::SparseMatrixCSC{Float64, Int}:Nb×Nbdirected adjacency matrix of the DBHT. A non-zeroHc[i, j]is a directed edge from bubbleito bubblej, and its value is the mass of the heavier side.Sep::Vector{Int}:Nb×1vector of the type of each bubble.1is a converging bubble, which has no outgoing edge inHc.2is a diverging bubble, which has no incoming edge and more than one neighbour inHb.0is every other bubble.
Related
PortfolioOptimisers.BubbleCluster8s — Function
BubbleCluster8s(Rpm::MatNum, Dpm::MatNum,
Hb::MatNum, Mb::MatNum,
Mv::MatNum, CliqList::MatNum)Get a non-discrete and a discrete clustering of the vertices from the bubble tree of the Planar Maximally Filtered Graph (PMFG).
Each converging bubble of the directed bubble hierarchical tree (DBHT) is one cluster. The function computes a non-discrete membership matrix, in which a vertex can belong to more than one cluster. It also computes a discrete membership vector, in which each vertex belongs to one cluster.
Mathematical definition
The function assigns a vertex that more than one converging bubble holds to the bubble of the largest $\chi$. $\chi$ is the weight that joins the vertex to the bubble, divided by the edge count of the bubble.
\[\chi(v,\, b) = \frac{\displaystyle\sum_{u \in b} R_{u,\,v}}{3\left(\left|b\right| - 2\right)}\,.\]
Where:
- $R_{u,\,v}$: Weight of the PMFG edge between vertices $u$ and $v$.
- $b$: Vertex set of a converging bubble, and $\left|b\right|$ its vertex count.
- $\chi(v,\, b)$: Association of vertex $v$ with bubble $b$.
The denominator is the edge count of a maximal planar graph on $\left|b\right|$ vertices, the same $3n - 6$ that the PMFG has. It removes the effect of the size of the bubble, so a large bubble does not win only because it is large.
Algorithm
- Direct the bubble tree with
DirectHb, which givesHcandSep. - Take
indx, the converging bubbles,Sep .== 1. When one or none exists, put every vertex in cluster1, leaveAdjvat0 × 0, and stop. - For each converging bubble, run
breadthon the transpose ofHc, and mark in columnnofAdjvevery vertex of every bubble that the search reaches. The function can mark a vertex in more than one column, soAdjvis non-discrete. - Gather
Bubv, the vertex membership of the converging bubbles alone. Copy intoMdjvthe rows ofBubvfor the verticescvthat exactly one converging bubble holds. - For each vertex of
uv, the vertices that more than one converging bubble holds, take the converging bubble of largest $\chi$ and mark it inMdjv. - Read the discrete assignment
Tcoff the stored entries ofMdjv. - For a vertex that no converging bubble holds, compute
Udjv, the mean shortest path length from the vertex to the vertices thatMdjvassigns to each converging bubble. SetUdjvtotypemaxat each cluster ofAdjvthat does not hold the vertex, and assign the vertex to the closest of the other clusters.
Arguments
Rpm:N × Nsparse weighted adjacency matrix of the PMFG.Dpm:N × Nmatrix of the shortest path lengths of the PMFG.Hb:Nb×Nbundirected bubble tree of the PMFG, fromBubbleHierarchy.Mb:Nc×Nbbubble membership matrix of the 3-cliques.Mb[n, bi] = 1means that 3-cliquenbelongs to bubblebi.Mv:N × Nbbubble membership matrix of the vertices.Mv[n, bi] = 1means that vertexnis a vertex of bubblebi.CliqList:Nc×3matrix. Each row lists the three vertices of a 3-clique of the MPG.
Returns
Adjv::SparseMatrixCSC{Int, Int}:N × Nkmembership matrix of the non-discrete clustering, whereNkis the number of converging bubbles.Adjv[n, k] = 1means that vertexnbelongs to thek-th non-discrete cluster, and a vertex can belong to more than one. It is0 × 0when step 2 of the algorithm stops.Tc::Vector{Int}:N × 1cluster membership vector.Tc[n] = kmeans that vertexnbelongs to thek-th discrete cluster. Each vertex belongs to exactly one.
Related
PortfolioOptimisers.BubbleMember — Function
BubbleMember(Rpm::MatNum, Mv::MatNum,
Mc::MatNum)Assign each vertex of a cluster to one bubble.
A vertex can be a vertex of more than one bubble. The function assigns such a vertex to one of them, from the edge weights that join the vertex to each candidate bubble. HierarchyConstruct4s calls it once for each cluster.
Mathematical definition
The function assigns a vertex that more than one bubble of the cluster holds to the bubble of the largest $\phi$.
\[\phi(v,\, b) = \frac{\displaystyle\sum_{u \in b} R_{u,\,v}}{\displaystyle\frac{1}{2}\sum_{u \in b} \sum_{u' \in b} R_{u,\,u'}}\,.\]
Where:
- $R_{u,\,v}$: Weight of the PMFG edge between vertices $u$ and $v$.
- $b$: Vertex set of a bubble.
- $\phi(v,\, b)$: Fraction of the internal weight of bubble $b$ that vertex $v$ draws.
The denominator has the factor one half because the PMFG weights are symmetric, and the double sum counts each edge two times. The $\chi$ of BubbleCluster8s is different. It divides by the edge count of a maximal planar bubble, and $\phi$ divides by the edge weight that the bubble holds.
Algorithm
- Split the vertices that
Mcmarks intov, the vertices that exactly one bubble holds, andvu, the vertices that more than one bubble holds. - Copy the rows of
McatvintoMvv. Each of these vertices has one bubble, so the copy assigns it. - For each vertex of
vu, read its candidate bubblesbuboff its row ofMc, score each with $\phi$, and mark the largest inMvv.
Arguments
Rpm:N × Nsparse weighted adjacency matrix of the PMFG.Mv:N × Nbbubble membership matrix of the vertices.Mv[n, bi] = 1means that vertexnis a vertex of bubblebi.Mc:N × Nbbubble membership matrix of the vertices of one cluster.Mc[n, bi] = 1means that vertexnis a vertex of bubblebiand that it belongs to the cluster. Every other entry is zero, so a bubble that holds no vertex of the cluster has an empty column.
Returns
Mvv::Matrix{Int}:N × Nbmatrix.Mvv[n, bi] = 1when the function assigns vertexnto bubblebi. Each row has at most one non-zero entry, so the assignment is discrete.
Related