Search

As for single-label learning, feature selection has become a crucial data pre-processing tool for multi-label learning due to its ability to reduce the feature dimensionality to mitigate the influence of "the curse of dimensionality". In recent years, the multi-label feature selection (MFS) methods based on manifold learning and sparse regression have confirmed their superiority and gained more and more attention than other methods. However, most of these methods only consider exploiting the geometric structure distributed in the data manifold but ignore the geometric structure distributed in the feature manifold, resulting in incomplete information about the learned manifold. Aiming to simultaneously exploit the geometric information of data and feature spaces for feature selection, this paper proposes a novel MFS method named dual-graph based multi-label feature selection (DGMFS). In the framework of DGMFS, two nearest neighbor graphs are constructed to form a dual-graph regularization to explore the geometric structures of both the data manifold and the feature manifold simultaneously. Then, we combined the dual-graph regularization with a non-convex sparse regularization l2,1 − 2-norm to obtain a more sparse solution for the weight matrix, which can better deal with the redundancy features. Finally, we adopt the EM strategy to design an iterative updating optimization algorithm for DGMFS and provide the convergence analysis of the optimization algorithm. Extensive experimental results on ten benchmark multi-label data sets have shown that DGMFS is more effective than several state-of-the-art MFS methods. [ABSTRACT FROM AUTHOR]

We find all polyhedral graphs such that their complements are still polyhedral. These turn out to be all self-complementary. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization methods have been widely used in many applications in recent years. However, the clustering performances of such methods may deteriorate dramatically in the presence of non-Gaussian noise or outliers. To overcome this problem, in this paper, we propose correntropy-based dual graph regularized NMF with LP smoothness (CDNMFS) for data representation. Specifically, we employ correntropy instead of the Euclidean norm to measure the incurred reconstruction error. Furthermore, we explore the geometric structures of both the input data and the feature space and impose an Lp norm constraint to obtain an accurate solution. In addition, we introduce an efficient optimization scheme for the proposed model and present its convergence analysis. Experimental results on several image datasets demonstrate the superiority of the proposed CDNMFS method. [ABSTRACT FROM AUTHOR]

After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]

A planar Tangle is a smooth simple closed curve piecewise defined by quadrants of circles with constant curvature. We can enumerate Tangles by counting their dual graphs, which consist of a certain family of polysticks. The number of Tangles with a given length or area grows exponentially, and we show the existence of their growth constants by comparing Tangles to two families of polyominoes. [ABSTRACT FROM AUTHOR]

We compare one-dimensional representations for the isotopy stable dynamics of homeomorphisms in two dimensions. We consider the skeleton graph representative, which captures periodic behaviour, and the homotopy graph representative which captures homo-/heteroclinic behaviour. The main result of this paper is to show that the dual to the skeleton graph representative is the homotopy graph representative of the inverse map. This gives a strong link between different methods for computing the dynamics. [ABSTRACT FROM AUTHOR]

Principal component analysis is the most widely used method for linear dimensionality reduction, due to its effectiveness in exploring low-dimensional global geometric structures embedded in data. To preserve the intrinsic local geometrical structures of data, graph-Laplacian PCA (gLPCA) incorporates Laplacian embedding into PCA framework for learning local similarities between data points, which leads to significant performance improvement in clustering and classification. Some recent works showed that not only the high dimensional data reside on a low-dimensional manifold in the data space, but also the features lie on a manifold in feature space. However, both PCA and gLPCA overlook the local geometric information contained in the feature space. By considering the duality between data manifold and feature manifold, graph-dual Laplacian PCA (gDLPCA) is proposed, which incorporates data graph regularization and feature graph regularization into PCA framework to exploit local geometric structures of data manifold and feature manifold simultaneously. The experimental results on four benchmark data sets have confirmed its effectiveness and suggested that gDLPCA outperformed gLPCA on classification and clustering tasks. [ABSTRACT FROM AUTHOR]

Computing k-cores is a fundamental and important graph problem, which can be applied in many areas, such as community detection, network visualization, and network topology analysis. Due to the complex relationship between different entities, dual graph widely exists in the applications. A dual graph contains a physical graph and a conceptual graph, both of which have the same vertex set. Given that there exist no previous studies on the k-core in dual graphs, we formulate a k-connected core (k-CCO) model in dual graphs. A k-CCO is a k-core in the conceptual graph, and also connected in the physical graph. Given a dual graph and an integer k, we propose a polynomial time algorithm for computing all k-CCOs. We also propose three algorithms for computing all maximum-connected cores (MCCO), which are the existing k-CCOs such that a (k+1)-CCO does not exist. We further study a subgraph search problem, which is computing a k-CCO that contains a set of query vertices. We propose an index-based approach to efficiently answer the query for any given parameter k. We conduct extensive experiments on six real-world datasets and four synthetic datasets. The experimental results demonstrate the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider a generating function of the domino tilings of an Aztec rectangle with several unit squares removed from the boundary. Our generating function involves two statistics: the rank of the tiling and half number of vertical dominoes as in the Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp. In addition, our work deduces a combinatorial explanation for an interesting connection between the number of lozenge tilings of a semihexagon and the number of domino tilings of an Aztec rectangle. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and $$x_1,x_2,x_3$$ are three points in $$X$$ , a geodesic triangle $$T=\{x_1,x_2,x_3\}$$ is the union of three geodesics $$[x_1x_2]$$ , $$[x_2x_3]$$ and $$[x_3x_1]$$ in $$X$$ . The space $$X$$ is $$\delta $$ - hyperbolic $$($$ in the Gromov sense $$)$$ if any side of $$T$$ is contained in a $$\delta $$ -neighborhood of the union of the two other sides, for every geodesic triangle $$T$$ in $$X$$ . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In this paper we obtain criteria which allow us to decide, for a large class of graphs, whether they are hyperbolic or not. We are especially interested in the planar graphs which are the 'boundary' (the $$1$$ -skeleton) of a tessellation of the Euclidean plane. Furthermore, we prove that a graph obtained as the $$1$$ -skeleton of a general CW $$2$$ -complex is hyperbolic if and only if its dual graph is hyperbolic. [ABSTRACT FROM AUTHOR]

Known asymptotic formulas are used to analyze the connectivity probability of graphs with highly reliable and poorly reliable edges. The conventional methods used to calculate the coefficients in these formulas require a number of arithmetic operations that grows geometrically with the growing number of graph edges. The adjacency matrix of the dual graph for highly reliable edges and the Kirchhoff matrix for poorly reliable edges result in algorithms of cubic complexity. [ABSTRACT FROM AUTHOR]

face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained. [ABSTRACT FROM AUTHOR]

The exceptional divisor component of the projective plane modified by a sequence of blow-ups determines filtration on the ring of polynomials in two variables. The set of such components determines the multi-index filtration on this ring. The Poincaré series of this filtration is calculated for some sets of components provided that the modification under study is the minimal resolution of a plane algebraic curve with one place at infinity. [ABSTRACT FROM AUTHOR]

The Jordan Curve Theorem referring to a simple closed curve in the plane has a particularly simple proof in the case that the curve is polygonal, called the “raindrop proof”. We generalize the notion of a simple closed polygon to that of a polyhedral ( d−1)-pseudomanifold ( d≥2) and prove a Jordan–Brouwer Separation Theorem for such a manifold embedded in ℝ d. As a by-product, we get bounds on the polygonal diameter of the interior and exterior of such a manifold which are almost tight. This puts the result within the frame of computational geometry. [ABSTRACT FROM AUTHOR]

3-D analysis in GIS is still one of the most challenging topics for research. With the goal being to model possible movement within the built environment, this paper, therefore, proposes a new approach to handling connectivity relationships among 3-D objects in urban environments in order to implement spatial access analyses in 3-D space. To achieve this goal, this paper introduces a 3-D network data model called the geometric network model (GNM), which has been developed by transforming the combinatorial data model (CDM), representing a connectivity relationship among 3-D objects using a dual graph. For the transformation, this paper presents (1) an O(n2) algorithm for computing a straight medial axis transformation (MAT), (2) the processes for transforming phenomena from 3-D CDM to 3-D GNM, and (3) spatial access algorithms for the 3-D geometric network based upon the Dijkstra algorithm. Using the reconstructed geometric network generated from the transformations, spatial queries based upon the complex connectivity relationships between 3-D urban entities are implemented using Dijkstra algorithm. Finally, the paper presents the results of an experimental implementation of a 3-D network data model (GNM) using GIS data of an area in downtown Columbus, Ohio. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of finding a closed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs in O(mn) time where m is the number of directed edges and n is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that are compact. We then build on this algorithm to obtain an O(n)-time sequential algorithm to solve the closed partition problem for a general planar digraph. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Classification is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)