In this paper, we investigate the statistical features of the weighted international-trade network. By finding the maximum weight spanning trees for this network we make the extraction of the truly relevant connections forming the network's backbone. We discuss the role of large-sized countries (strongest economies) in…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,341 papers · 148 categories
Trend · papers per month
48 results for “maximum spanning tree”
A new algorithm optimizes multi-way matching problems.
problem Consistent matching of multiple sets of elements.
method Directly optimizes the NP-hard objective using coordinate updates and graph-based initialization.
result Empirically outperforms existing methods on benchmark tasks.
This paper finds efficient algorithms for approximating Markov networks with k-tree topologies.
problem Efficiently approximating Markov networks with complex topologies.
method Developed O(n^{k+1})-time algorithms for finding maximum spanning k-trees (MSkT) that retain certain subgraphs.
result Optimal approximation of Markov networks with k-tree topology is achieved in polynomial time.
The problem of maximum-likelihood (ML) estimation of discrete tree-structured distributions is considered. Chow and Liu established that ML-estimation reduces to the construction of a maximum-weight spanning tree using the empirical mutual information quantities as the edge weights. Using the theory of large-deviations…
Sharp bounds for spanning tree entropy in planar lattices.
problem Estimating spanning tree entropy in planar lattice graphs.
method Using hyperbolic geometry and polyhedra volumes.
result Proved bounds are easy to compute and provide excellent estimates.
This paper shows neural networks can solve complex graph problems efficiently.
problem Solving exact maximum flow computation and minimum spanning tree problems.
method Introduces Max-Affine Arithmetic Programs and shows equivalence to neural networks.
result Two combinatorial optimization problems can be solved with polynomial-size neural networks.
The Jones polynomial can be expressed in terms of spanning trees of the graph obtained by checkerboard coloring a knot diagram. We show there exists a complex generated by these spanning trees whose homology is the reduced Khovanov homology. The spanning trees provide a filtration on the reduced Khovanov complex and a …
A new classification method based on Minimum Spanning Trees
problem Improving classification in supervised learning
method Proposing a classification algorithm based on Minimum Spanning Trees
result The proposed method is effective and computationally efficient
Alexander polynomial equals spanning tree count at t=1.
problem Alexander polynomial for spatial graphs.
method Combinatorial constructions generalized to weighted graphs.
result Value of Alexander polynomial at t=1 equals weighted spanning tree count.
A spanning tree model for Khovanov homology, Rasmussen's s-invariant and exotic discs in the -ballmath.GT
New spanning tree model connects knot homology, s-invariant, and exotic discs.
problem Understanding exotic discs in the 4-ball for knots.
method Explicitly defined differential in spanning tree complex, described Rasmussen's s-invariant.
result Identified new infinite family of knots bounding exotic discs.
For a spanning tree T of a connected graph G and for a labelling φ: E(T) \rightarrow {+, -}, φis called an alternating sign on a spanning tree T of a graph G if for any cotree edge e \in E(G)-E(T), the unique path in T joining both end vertices of e has alternating signs. In the present note, we prove that any graph ha…
We investigate the time series of the degree of minimum spanning trees obtained by using a correlation based clustering procedure which is starting from (i) asset return and (ii) volatility time series. The minimum spanning tree is obtained at different times by computing correlation among time series over a time windo…
Statistical uncertainty of different filtration techniques for market network analysis is studied. Two measures of statistical uncertainty are discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some import…
We use a spanning tree model to prove a result of E. S. Lee on the support of Khovanov homology of alternating knots.
Study examines insurance sector linkages and systemic risk using dynamic spanning trees.
problem Interlinkages and systemic risk in the European insurance sector.
method Analysis of linkage dynamics and systemic risk using correlation networks, copulas, and minimum spanning trees.
result Minimum spanning trees describe linkage dynamics in the European insurance sector.
Study asymptotic expansion of graph Laplacian on discretized surfaces, relating spanning trees and cycle-rooted forests.
problem Asymptotic expansion of graph Laplacian on discretized surfaces.
method Relate spanning trees and cycle-rooted spanning forests to zeta-regularized determinants.
result Explicit formula for limit of cycle-rooted spanning forest probability and topological observables.
New algorithm optimizes variational objective for marginal inference.
problem Optimizing the tree-reweighted variational objective over the marginal polytope.
method Barrier Frank-Wolfe algorithm based on conditional gradient method, leveraging MAP solvers.
result More accurate results than TRW algorithms that optimize over local consistency relaxation.
Oriented ribbon graphs (dessins d'enfant) are graphs embedded in oriented surfaces. A quasi-tree of a ribbon graph is a spanning subgraph with one face, which is described by an ordered chord diagram. We show that for any link diagram , there is an associated ribbon graph whose quasi-trees correspond bijectively to …
New algorithm for private minimum spanning tree release with improved accuracy.
problem Privacy-preserving minimum spanning tree release for graphs.
method Formal differential privacy definition for graphs, new MST algorithm, combining sanitizing mechanism and MST clustering.
result Improved accuracy in weight approximation compared to state of the art.
We analyze variational inference for highly symmetric graphical models such as those arising from first-order probabilistic models. We first show that for these graphical models, the tree-reweighted variational objective lends itself to a compact lifted formulation which can be solved much more efficiently than the sta…
Nonlinear dependencies on Brazilian equity network from mutual information minimum spanning treesphysics.soc-ph
Mutual info trees show higher risk in Brazilian equity network during transition.
problem Identifying nonlinear dependencies in Brazilian equity network.
method Used mutual information minimum spanning trees to compare with linear correlation.
result Mutual info trees indicate higher risk and power law tail in volatility transmission.
Optimal coupling among random vectors with known statistics and correlation structure found using minimum spanning tree over measure-valued vertices.
problem Finding the optimal coupling among random vectors with known statistics and correlation structure.
method Formulating the problem as a minimum spanning tree over measure-valued vertices and solving it in two steps.
result Optimal coupling found using the minimum spanning tree approach.
We introduce block-tree graphs as a framework for deriving efficient algorithms on graphical models. We define block-tree graphs as a tree-structured graph where each node is a cluster of nodes such that the clusters in the graph are disjoint. This differs from junction-trees, where two clusters connected by an edge al…
We iterate Manolescu's unoriented skein exact triangle in knot Floer homology with coefficients in the field of rational functions over . The result is a spectral sequence which converges to a stabilized version of delta-graded knot Floer homology. The page of this spectral sequence …
Tree density estimationmath.ST
Estimates tree-based density from random vectors.
problem Estimating the density of a random vector in high dimensions.
method Optimal spanning tree minimizes Kullback-Leibler divergence; tree density estimate constructed from i.i.d. data.
result Tree density estimate converges to true density as sample size increases.
Paper proposes an algorithm to reconstruct optimal model structure from graph adjacency matrix.
problem Optimal model structure reconstruction from weighted colored graph adjacency matrix.
method Uses prize-collecting Steiner tree algorithm to reconstruct minimum spanning tree.
result Demonstrates the effectiveness of the prize-collecting Steiner tree algorithm for model structure reconstruction.
A new method for one-class classifiers using spanning trees and sub-spaces.
problem Designing efficient one-class classifiers for various datasets.
method Ensemble-of-classifiers approach, spanning trees, sub-spaces, minimum distance.
result Comparable and state-of-the-art performance on benchmark datasets.
Proves bounds on spanning two-forests and random cut sizes.
problem Counting spanning two-forests and estimating random cut sizes.
method Uses pairwise effective resistances and potential theory.
result Establishes bounds on the number of spanning two-forests and average cut size.
Oriented ribbon graphs (dessins d'enfant) are graphs embedded in oriented surfaces. The Bollobás-Riordan-Tutte polynomial is a three-variable polynomial that extends the Tutte polynomial to oriented ribbon graphs. A quasi-tree of a ribbon graph is a spanning subgraph with one face, which is described by an ordered chor…
A new hierarchical clustering method selects representative points from sub-minimum-spanning-trees.
problem Selecting representative points for hierarchical clustering to improve robustness and reliability.
method Identify representative points using reciprocal nearest data points in sub-minimum-spanning-trees.
result The proposed algorithm outperforms other methods in accuracy and efficiency.
Analyzes how minimal networks behave under boundary set deformations.
problem Behavior of minimal networks under boundary set deformations.
method Analytic deformations of boundary sets.
result Preservation of network types (minimal spanning trees, minimal fillings, stable shortest trees) under analytic deformations.
A New Matrix-Tree Theoremmath.CO
The classical Matrix-Tree Theorem allows one to list the spanning trees of a graph by monomials in the expansion of the determinant of a certain matrix. We prove that in the case of three-graphs (that is, hypergraphs whose edges have exactly three vertices) the spanning trees are generated by the Pfaffian of a suitably…
Graph complexity and Mahler measure linked through spanning trees.
problem Linking graph complexity and Mahler measure.
method Analyzing spanning trees and Mahler measure of Laplacian polynomials.
result Growth rates of Mahler measure are asymptotic to log(2d) for grid graphs.
We use the spanning tree model for Khovanov homology to study Legendrian links. This leads to an alternative proof for Ng's Khovanov bound for the Thurston-Bennequin number and to both a necessary and a sufficient condition for this bound to be sharp.
Adaptive attention span extends Transformer's context size.
problem Limited context size in Transformers limits model performance.
method A self-attention mechanism that learns optimal attention span.
result State-of-the-art performance on character-level language modeling.
We consider the detection of activations over graphs under Gaussian noise, where signals are piece-wise constant over the graph. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with proveable theoretical guarantees for ge…
Exact Bayesian inference for off-line change-point detection in tree-structured graphical modelsstat.ML
Bayesian method detects changes in tree-structured graphs.
problem Change-point detection in multivariate time-series with graphical models.
method Exact Bayesian inference using spanning trees and dynamic programming.
result Efficient computation of posterior distributions for change-points and edge probabilities.
Exact Bayesian inference for tree-structured models without sampling.
problem Inference of tree-structured graphical models in Bayesian frameworks.
method Close-form posteriors for mixtures of spanning trees, using the Matrix-Tree theorem.
result Exact Bayesian inference can be achieved under specific prior conditions.
We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the g…
Forest Density Estimationstat.ML
We study graph estimation and density estimation in high dimensions, using a family of density estimators based on forest structured undirected graphical models. For density estimation, we do not assume the true distribution corresponds to a forest; rather, we form kernel density estimates of the bivariate and univaria…
We study relations between the Alexander-Conway polynomial and Milnor higher linking numbers of links from the point of view of finite-type (Vassiliev) invariants. We give a formula for the first non-vanishing coefficient of of an m-component link L all of whose Milnor numbers van…
Lumbermark clusters data robustly, slicing limbs of mutual reachability trees.
problem Detecting clusters of varying sizes, densities, and shapes in datasets.
method Iteratively chops limbs of a mutual reachability minimum spanning tree.
result Lumbermark produces partitions with user-specified sizes.
Correlation matrices of foreign exchange rate time series are investigated for 60 world currencies. Minimal Spanning Tree (MST) graphs for the gold, silver and platinum are presented. Inverse power like scaling is discussed for these graphs as well as for four distinct currency groups (major, liquid, less liquid and no…
Cryptocurrency market becomes more cross-correlated over time.
problem Understanding the inter-market dependencies of cryptocurrencies.
method Time series analysis, spectral analysis, topological analysis of minimal spanning trees.
result Cryptocurrency market becomes more cross-correlated with other markets over time.
New method estimates root-directed tree from extreme data.
problem Discovering causality in river networks from extreme flow data.
method Qualitative max-linear Bayesian network approach to estimate bivariate scores and root-directed spanning tree.
result The new estimator is consistent under max-linear Bayesian network model with noise.
We introduce a new class of lower bounds on the log partition function of a Markov random field which makes use of a reversed Jensen's inequality. In particular, our method approximates the intractable distribution using a linear combination of spanning trees with negative weights. This technique is a lower-bound count…
The paper characterizes chordal graphs via edge deletions and finds a local minimum spanning tree algorithm.
problem Characterizing chordal graphs and finding efficient minimum spanning trees.
method Focus on exposed edges, characterize chordal graphs via deletions, and use local properties to modify Kruskal's algorithm.
result A modified Kruskal's algorithm for weighted chordal graphs is local and efficient.
Topology of the correlation networks among major currencies using hierarchical structure methodsq-fin.GN
We studied the topology of correlation networks among 34 major currencies using the concept of a minimal spanning tree and hierarchical tree for the full years of 2007-2008 when major economic turbulence occurred. We used the USD (US Dollar) and the TL (Turkish Lira) as numeraires in which the USD was the major currenc…