Label Propagation through Linear Neighborhoods Wang, Fei; Zhang, Changshui
IEEE transactions on knowledge and data engineering,
2008-Jan., 2008, 2008-01-00, 20080101, Volume:
20, Issue:
1
Journal Article
Peer reviewed
In many practical data mining applications such as text classification, unlabeled training examples are readily available, but labeled ones are fairly expensive to obtain. Therefore, semi supervised ...learning algorithms have aroused considerable interests from the data mining and machine learning fields. In recent years, graph-based semi supervised learning has been becoming one of the most active research areas in the semi supervised learning community. In this paper, a novel graph-based semi supervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named linear neighborhood propagation (LNP), can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness. A theoretical analysis of the properties of LNP is presented in this paper. Furthermore, we also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit, and text classification tasks.
Let G→ be a directed graph of order n with no component of order less than 3, and let Γ be a finite Abelian group such that ∣Γ∣≥2n+2n or if n is large enough with respect to an arbitrarily fixed ε>0 ...then ∣Γ∣≥(1+ε)n. We show that there exists an injective mapping φ from V(G→) to the group Γ such that ∑x∈V(C→)φ(x)=0 for every connected component C→ of G→, where 0 is the identity element of Γ. Moreover we show some applications of this result to group distance magic labelings.
This paper will introduce the concept of vertex-magic edge labelings (VMEL) for digraphs. A digraph has a vertex-magic edge labeling if we can label the edges of the digraph such that the sum of the ...edges going in to any vertex equals the sum going out at any vertex and that sum is constant across all vertices in the digraph. Many examples will be given. The connections to sparse semi-magic squares are also given. Then, new sparse semi-magic squares are constructed that lead to both VMEL and magic labelings for various classes of digraphs.
MacDougall’s conjecture states that every regular graph of degree at least 2 has a vertex-magic total labeling (VMTL) with the lone exception of 2K3. Since there is enormous empirical evidence ...supporting this conjecture, it is reasonable to seek generalizations. Thus we ask the more general question: to what extent does the degree sequence of a graph determine the existence or nonexistence of a VMTL? We provide beginning steps towards answering this question, and related questions, by providing infinite families of degree sequences, and for each sequence, a graph with a VMTL and another graph without a VMTL.
In this article we admit Bi- Conditional for Duplicate graph of Quadrilateral Snake EDG(QSm)m ≥ 2, Double Quadrilateral SnakeGraphs EDG(DQSm)m ≥ 2, and Triangular ladder graph. EDG(TQLm)m ≥ 2.
The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., ...the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.
Metro maps are schematic diagrams of public transport networks that serve as visual aids for route planning and navigation tasks. It is a challenging problem in network visualization to automatically ...draw appealing metro maps. There are two aspects to this problem that depend on each other: the layout problem of finding station and link coordinates and the labeling problem of placing nonoverlapping station labels. In this paper, we present a new integral approach that solves the combined layout and labeling problem (each of which, independently, is known to be NP-hard) using mixed-integer programming (MIP). We identify seven design rules used in most real-world metro maps. We split these rules into hard and soft constraints and translate them into an MIP model. Our MIP formulation finds a metro map that satisfies all hard constraints (if such a drawing exists) and minimizes a weighted sum of costs that correspond to the soft constraints. We have implemented the MIP model and present a case study and the results of an expert assessment to evaluate the performance of our approach in comparison to both manually designed official maps and results of previous layout methods.
This paper considers the bandwidth reduction problem for large-scale matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix so ...that the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. In this regard, this paper proposes an ant colony hyperheuristic approach for the bandwidth reduction of symmetric and nonsymmetric matrices. The ant colony hyperheuristic approach evolves and selects graph theory bandwidth reduction algorithms for application areas. This paper evaluates the resulting heuristics for bandwidth reduction in each application area against the most promising low-cost heuristics for bandwidth reduction. This paper also includes a numerical examination of the current state-of-the-art metaheuristic algorithms for matrix bandwidth reduction. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed approach outperformed state-of-the-art low-cost heuristics for bandwidth reduction when applied to problem cases arising from several application areas, clearly indicating the promise of the proposal.
•Low-cost heuristics based on level set orderings for bandwidth reduction of matrices.•An ant colony hyperheuristic approach that evolves and selects heuristics.•A hyperheuristic approach that evolves heuristics for a specific application area.
PDF
