Relevant bibliographies by topics / Labeled graph

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Labeled graph'

Author: Grafiati
Published: 4 June 2021
Last updated: 15 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Labeled graph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Labeled graph"

1

MATSUMOTO, KENGO. "FACTOR MAPS OF LAMBDA-GRAPH SYSTEMS AND INCLUSIONS OF C*-ALGEBRAS." International Journal of Mathematics 15, no. 04 (June 2004): 313–39. http://dx.doi.org/10.1142/s0129167x04002351.

Full text
Abstract:
A λ-graph system is a labeled Bratteli diagram with shift transformation. It is a generalization of finite labeled graphs and presents a subshift. In [Doc. Math. 7 (2002), 1–30], the author introduced a C*-algebra [Formula: see text] associated with a λ-graph system [Formula: see text] as a generalization of the Cuntz–Krieger algebras. In this paper, we study a functorial property between factor maps of λ-graph systems and inclusions of the associated C*-algebras with gauge actions. We prove that if there exists a surjective left-covering λ-graph system homomorphism [Formula: see text], there exists a unital embedding of the C*-algebra [Formula: see text] into the C*-algebra [Formula: see text] compatible to its gauge actions. We also show that a sequence of left-covering graph homomorphisms of finite labeled graphs gives rise to a λ-graph system such that the associated C*-algebra is an inductive limit of the Cuntz–Krieger algebras for the finite labeled graphs.
APA, Harvard, Vancouver, ISO, and other styles
2

Ishii, Atsushi. "The Markov theorems for spatial graphs and handlebody-knots with Y-orientations." International Journal of Mathematics 26, no. 14 (December 2015): 1550116. http://dx.doi.org/10.1142/s0129167x15501165.

Full text
Abstract:
We establish the Markov theorems for spatial graphs and handlebody-knots. We introduce an IH-labeled spatial trivalent graph and develop a theory on it, since both a spatial graph and a handlebody-knot can be realized as the IH-equivalence classes of IH-labeled spatial trivalent graphs. We show that any two orientations of a graph without sources and sinks are related by finite sequence of local orientation changes preserving the condition that the graph has no sources and no sinks. This leads us to define two kinds of orientations for IH-labeled spatial trivalent graphs, which fit a closed braid, and is used for the proof of the Markov theorem. We give an enhanced Alexander theorem for orientated tangles, which is also used for the proof.
APA, Harvard, Vancouver, ISO, and other styles
3

Murugan, A. Nellai, and Shiny Priyanka. "TREE RELATED EXTENDED MEAN CORDIAL GRAPHS." International Journal of Research -GRANTHAALAYAH 3, no. 9 (September 30, 2015): 143–48. http://dx.doi.org/10.29121/granthaalayah.v3.i9.2015.2954.

Full text
Abstract:
Let G = (V,E) be a graph with p vertices and q edges. A Extended Mean Cordial Labeling of a Graph G with vertex set V is a bijection from V to {0, 1,2} such that each edge uv is assigned the label where ⌈ x ⌉ is the least integer greater than or equal to x with the condition that the number of vertices labeled with 0 and the number of vertices labeled with 1 differ by at most 1 and the number of edges labeled with 0 and the number of edges labeled with 1 differ by almost 1. The graph that admits an Extended Mean Cordial Labeling is called Extended Mean Cordial Graph. In this paper, we proved that tree related graphs Hdn, K 1,n, Tgn, <K1,n:n> are Extended Mean Cordial Graphs.
APA, Harvard, Vancouver, ISO, and other styles
4

Harlander, Jens, and Stephan Rosebrock. "Aspherical word labeled oriented graphs and cyclically presented groups." Journal of Knot Theory and Its Ramifications 24, no. 05 (April 2015): 1550025. http://dx.doi.org/10.1142/s021821651550025x.

Full text
Abstract:
A word labeled oriented graph (WLOG) is an oriented graph [Formula: see text] on vertices X = {x1,…,xn}, where each oriented edge is labeled by a word in X±1. WLOGs give rise to presentations which generalize Wirtinger presentations of knots. WLOG presentations, where the underlying graph is a tree, are of central importance in view of Whitehead's Asphericity Conjecture. We present a class of aspherical word labeled oriented graphs. This class can be used to produce highly non-injective aspherical labeled oriented trees and also aspherical cyclically presented groups.
APA, Harvard, Vancouver, ISO, and other styles
5

Guirao, Juan, Sarfraz Ahmad, Muhammad Siddiqui, and Muhammad Ibrahim. "Edge Irregular Reflexive Labeling for Disjoint Union of Generalized Petersen Graph." Mathematics 6, no. 12 (December 5, 2018): 304. http://dx.doi.org/10.3390/math6120304.

Full text
Abstract:
A graph labeling is the task of integers, generally spoken to by whole numbers, to the edges or vertices, or both of a graph. Formally, given a graph G = ( V , E ) a vertex labeling is a capacity from V to an arrangement of integers. A graph with such a capacity characterized is known as a vertex-labeled graph. Similarly, an edge labeling is an element of E to an arrangement of labels. For this situation, the graph is called an edge-labeled graph. We examine an edge irregular reflexive k-labeling for the disjoint association of the cycle related graphs and decide the correct estimation of the reflexive edge strength for the disjoint association of s isomorphic duplicates of the cycle related graphs to be specific Generalized Peterson graphs.
APA, Harvard, Vancouver, ISO, and other styles
6

Matsumoto, Kengo. "C*-algebras associated with presentations of subshifts ii. ideal structure and lambda-graph subsystems." Journal of the Australian Mathematical Society 81, no. 3 (December 2006): 369–85. http://dx.doi.org/10.1017/s1446788700014373.

Full text
Abstract:
AbstractA λ-graph system is a labeled Bratteli diagram with shift transformation. It is a generalization of finite labeled graphs and presents a subshift. InDoc. Math.7 (2002) 1–30, the author constructed aC*-algebraO£associated with a λ-graph system £ from a graph theoretic view-point. If a λ-graph system comes from a finite labeled graph, the algebra becomes a Cuntz-Krieger algebra. In this paper, we prove that there is a bijective correspondence between the lattice of all saturated hereditary subsets of £ and the lattice of all ideals of the algebraO£, under a certain condition on £ called (II). As a result, the class of theC*-algebras associated with λ-graph systems under condition (II) is closed under quotients by its ideals.
APA, Harvard, Vancouver, ISO, and other styles
7

Zhang, Zhijun, Muhammad Awais Umar, Xiaojun Ren, Basharat Rehman Ali, Mujtaba Hussain, and Xiangmei Li. "Tree-Antimagicness of Web Graphs and Their Disjoint Union." Mathematical Problems in Engineering 2020 (April 9, 2020): 1–6. http://dx.doi.org/10.1155/2020/4565829.

Full text
Abstract:
In graph theory, the graph labeling is the assignment of labels (represented by integers) to edges and/or vertices of a graph. For a graph G=V,E, with vertex set V and edge set E, a function from V to a set of labels is called a vertex labeling of a graph, and the graph with such a function defined is called a vertex-labeled graph. Similarly, an edge labeling is a function of E to a set of labels, and in this case, the graph is called an edge-labeled graph. In this research article, we focused on studying super ad,d-T4,2-antimagic labeling of web graphs W2,n and isomorphic copies of their disjoint union.
APA, Harvard, Vancouver, ISO, and other styles
8

Bagheri Gh., Behrooz. "(G1,G2)-permutation graphs." Discrete Mathematics, Algorithms and Applications 07, no. 04 (December 2015): 1550051. http://dx.doi.org/10.1142/s1793830915500512.

Full text
Abstract:
Let [Formula: see text] and [Formula: see text] be two labeled graphs of order [Formula: see text]. For any permutation [Formula: see text] the [Formula: see text]-permutation graph of labeled graphs [Formula: see text] and [Formula: see text] is the union of [Formula: see text] and [Formula: see text] together with the edges joining the vertex [Formula: see text] to the vertex [Formula: see text]. This operation on graphs is useful to produce a large class of networks with approximately the same properties as one of the original networks or even smaller. In this work we consider some properties of the permutation graph [Formula: see text], for labeled graph [Formula: see text] and [Formula: see text] of the same order. We provide bounds for the parameters radius, diameter, total distance, connectivity, edge-connectivity, chromatic number, and edge-chromatic number.
APA, Harvard, Vancouver, ISO, and other styles
9

Madhawa, Kaushalya, and Tsuyoshi Murata. "Active Learning for Node Classification: An Evaluation." Entropy 22, no. 10 (October 16, 2020): 1164. http://dx.doi.org/10.3390/e22101164.

Full text
Abstract:
Current breakthroughs in the field of machine learning are fueled by the deployment of deep neural network models. Deep neural networks models are notorious for their dependence on large amounts of labeled data for training them. Active learning is being used as a solution to train classification models with less labeled instances by selecting only the most informative instances for labeling. This is especially important when the labeled data are scarce or the labeling process is expensive. In this paper, we study the application of active learning on attributed graphs. In this setting, the data instances are represented as nodes of an attributed graph. Graph neural networks achieve the current state-of-the-art classification performance on attributed graphs. The performance of graph neural networks relies on the careful tuning of their hyperparameters, usually performed using a validation set, an additional set of labeled instances. In label scarce problems, it is realistic to use all labeled instances for training the model. In this setting, we perform a fair comparison of the existing active learning algorithms proposed for graph neural networks as well as other data types such as images and text. With empirical results, we demonstrate that state-of-the-art active learning algorithms designed for other data types do not perform well on graph-structured data. We study the problem within the framework of the exploration-vs.-exploitation trade-off and propose a new count-based exploration term. With empirical evidence on multiple benchmark graphs, we highlight the importance of complementing uncertainty-based active learning models with an exploration term.
APA, Harvard, Vancouver, ISO, and other styles
10

JEONG, JA A., EUN JI KANG, and GI HYUN PARK. "Purely infinite labeled graph -algebras." Ergodic Theory and Dynamical Systems 39, no. 8 (December 4, 2017): 2128–58. http://dx.doi.org/10.1017/etds.2017.123.

Full text
Abstract:
In this paper, we consider pure infiniteness of generalized Cuntz–Krieger algebras associated to labeled spaces $(E,{\mathcal{L}},{\mathcal{E}})$. It is shown that a $C^{\ast }$-algebra $C^{\ast }(E,{\mathcal{L}},{\mathcal{E}})$ is purely infinite in the sense that every non-zero hereditary subalgebra contains an infinite projection (we call this property (IH)) if $(E,{\mathcal{L}},{\mathcal{E}})$ is disagreeable and every vertex connects to a loop. We also prove that under the condition analogous to (K) for usual graphs, $C^{\ast }(E,{\mathcal{L}},{\mathcal{E}})=C^{\ast }(p_{A},s_{a})$ is purely infinite in the sense of Kirchberg and Rørdam if and only if every generating projection $p_{A}$, $A\in {\mathcal{E}}$, is properly infinite, and also if and only if every quotient of $C^{\ast }(E,{\mathcal{L}},{\mathcal{E}})$ has property (IH).
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Labeled graph"

1

Park, Noseong. "Top-K Query Processing in Edge-Labeled Graph Data." Thesis, University of Maryland, College Park, 2016. http://pqdtopen.proquest.com/#viewpdf?dispub=10128677.

Full text
Abstract:

Edge-labeled graphs have proliferated rapidly over the last decade due to the increased popularity of social networks and the Semantic Web. In social networks, relationships between people are represented by edges and each edge is labeled with a semantic annotation. Hence, a huge single graph can express many different relationships between entities. The Semantic Web represents each single fragment of knowledge as a triple (subject, predicate, object), which is conceptually identical to an edge from subject to object labeled with predicates. A set of triples constitutes an edge-labeled graph on which knowledge inference is performed.

Subgraph matching has been extensively used as a query language for patterns in the context of edge-labeled graphs. For example, in social networks, users can specify a subgraph matching query to find all people that have certain neighborhood relationships. Heavily used fragments of the SPARQL query language for the Semantic Web and graph queries of other graph DBMS can also be viewed as subgraph matching over large graphs.

Though subgraph matching has been extensively studied as a query paradigm in the Semantic Web and in social networks, a user can get a large number of answers in response to a query. These answers can be shown to the user in accordance with an importance ranking. In this thesis proposal, we present four different scoring models along with scalable algorithms to find the top-k answers via a suite of intelligent pruning techniques. The suggested models consist of a practically important subset of the SPARQL query language augmented with some additional useful features.

The first model called Substitution Importance Query (SIQ) identifies the top-k answers whose scores are calculated from matched vertices' properties in each answer in accordance with a user-specified notion of importance. The second model called Vertex Importance Query (VIQ) identifies important vertices in accordance with a user-defined scoring method that builds on top of various subgraphs articulated by the user. Approximate Importance Query (AIQ), our third model, allows partial and inexact matchings and returns top-k of them with a user-specified approximation terms and scoring functions. In the fourth model called Probabilistic Importance Query (PIQ), a query consists of several sub-blocks: one mandatory block that must be mapped and other blocks that can be opportunistically mapped. The probability is calculated from various aspects of answers such as the number of mapped blocks, vertices' properties in each block and so on and the most top-k probable answers are returned.

An important distinguishing feature of our work is that we allow the user a huge amount of freedom in specifying: (i) what pattern and approximation he considers important, (ii) how to score answers - irrespective of whether they are vertices or substitution, and (iii) how to combine and aggregate scores generated by multiple patterns and/or multiple substitutions. Because so much power is given to the user, indexing is more challenging than in situations where additional restrictions are imposed on the queries the user can ask.

The proposed algorithms for the first model can also be used for answering SPARQL queries with ORDER BY and LIMIT, and the method for the second model also works for SPARQL queries with GROUP BY, ORDER BY and LIMIT. We test our algorithms on multiple real-world graph databases, showing that our algorithms are far more efficient than popular triple stores.

APA, Harvard, Vancouver, ISO, and other styles
2

Li, Jie. "Data integration for biological network databases MetNetDB labeled graph model and graph matching algorithm /." [Ames, Iowa : Iowa State University], 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Christensen, Robin. "An Analysis of Notions of Differential Privacy for Edge-Labeled Graphs." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-169379.

Full text
Abstract:
The user data in social media platforms is an excellent source of information that is beneficial for both commercial and scientific purposes. However, recent times has seen that the user data is not always used for good, which has led to higher demands on user privacy. With accurate statistical research data being just as important as the privacy of the user data, the relevance of differential privacy has increased. Differential privacy allows user data to be accessible under certain privacy conditions at the cost of accuracy in query results, which is caused by noise. The noise is based on a tuneable constant ε and the global sensitivity of a query. The query sensitivity is defined as the greatest possible difference in query result between the queried database and a neighboring database. Where the neighboring database is defined to differ by one record in a tabular database, there are multiple neighborhood notions for edge-labeled graphs. This thesis considers the notions of edge neighborhood, node neighborhood, QL-edge neighborhood and QL-outedges neighborhood. To study these notions, a framework was developed in Java to function as a query mechanism for a graph database. ArangoDB was used as a storage for graphs, which was generated by parsing data sets in the RDF format as well as through a graph synthesizer in the developed framework. Querying a database in the framework is done with Apache TinkerPop, and a Laplace distribution is used when generating noise for the query results. The framework was used to study the privacy and utility trade-off of different histogram queries on a number of data sets, while employing the different notions of neighborhood in edge-labeled graphs. The level of privacy is determined by the value on ε, and the utility is defined as a measurement based on the L1-distance between the true and noisy result. In the general case, the notions of edge neighborhood and QL-edge neighborhood are the better alternatives in terms of privacy and utility. Although, there are indications that node neighborhood and QL-outedges neighborhood are considerable options for larger graphs, where the level of privacy for edge neighborhood and QL-edge neighborhood appears to be negligible based on utility measurements.
APA, Harvard, Vancouver, ISO, and other styles
4

Shafie, Termeh. "Random Multigraphs : Complexity Measures, Probability Models and Statistical Inference." Doctoral thesis, Stockholms universitet, Statistiska institutionen, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-82697.

Full text
Abstract:
This thesis is concerned with multigraphs and their complexity which is defined and quantified by the distribution of edge multiplicities. Two random multigraph models are considered.  The first model is random stub matching (RSM) where the edges are formed by randomly coupling pairs of stubs according to a fixed stub multiplicity sequence. The second model is obtained by independent edge assignments (IEA) according to a common probability distribution over the edge sites. Two different methods for obtaining an approximate IEA model from an RSM model are also presented. In Paper I, multigraphs are analyzed with respect to structure and complexity by using entropy and joint information. The main results include formulae for numbers of graphs of different kinds and their complexity. The local and global structure of multigraphs under RSM are analyzed in Paper II. The distribution of multigraphs under RSM is shown to depend on a single complexity statistic. The distributions under RSM and IEA are used for calculations of moments and entropies, and for comparisons by information divergence. The main results include new formulae for local edge probabilities and probability approximation for simplicity of an RSM multigraph. In Paper III, statistical tests of a simple or composite IEA hypothesis are performed using goodness-of-fit measures. The results indicate that even for very small number of edges, the null distributions of the test statistics under IEA have distributions that are  well approximated by their asymptotic χ2-distributions. Paper IV contains the multigraph algorithms that are used for numerical calculations in Papers I-III.
APA, Harvard, Vancouver, ISO, and other styles
5

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Full text
Abstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
APA, Harvard, Vancouver, ISO, and other styles
6

Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.

Full text
Abstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance
Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph
APA, Harvard, Vancouver, ISO, and other styles
7

Adamský, Aleš. "Segmentace mluvčích s využitím statistických metod klasifikace." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2011. http://www.nusl.cz/ntk/nusl-219007.

Full text
Abstract:
The thesis discusses in detail some concepts of speech and prosody that can contribute to build a speech corpus for the speaker segmentation purpose. Moreover, the Elan multimedia annotator used for labeling is described. The theoretical part highlights some frequently used speech features such as MFCC, PLP and LPC and deals with currently most popular speech segmentation methods. Some classification algorithms are also mentioned. The practical part describes implementation of Bayesian information criterium algorithm in system for automatic speaker segmentation. For classification of speaker change point in speech, were used different speech features. The results of tests were evaluated by the graphic method of receiver operating characteristic (ROC) and his quantitative indices. As the best speech features for this system were provided MFCC and HFCC.
APA, Harvard, Vancouver, ISO, and other styles
8

Fan, Shuangfei. "Deep Representation Learning on Labeled Graphs." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/96596.

Full text
Abstract:
We introduce recurrent collective classification (RCC), a variant of ICA analogous to recurrent neural network prediction. RCC accommodates any differentiable local classifier and relational feature functions. We provide gradient-based strategies for optimizing over model parameters to more directly minimize the loss function. In our experiments, this direct loss minimization translates to improved accuracy and robustness on real network data. We demonstrate the robustness of RCC in settings where local classification is very noisy, settings that are particularly challenging for ICA. As a new way to train generative models, generative adversarial networks (GANs) have achieved considerable success in image generation, and this framework has also recently been applied to data with graph structures. We identify the drawbacks of existing deep frameworks for generating graphs, and we propose labeled-graph generative adversarial networks (LGGAN) to train deep generative models for graph-structured data with node labels. We test the approach on various types of graph datasets, such as collections of citation networks and protein graphs. Experiment results show that our model can generate diverse labeled graphs that match the structural characteristics of the training data and outperforms all baselines in terms of quality, generality, and scalability. To further evaluate the quality of the generated graphs, we apply it to a downstream task for graph classification, and the results show that LGGAN can better capture the important aspects of the graph structure.
Doctor of Philosophy
Graphs are one of the most important and powerful data structures for conveying the complex and correlated information among data points. In this research, we aim to provide more robust and accurate models for some graph specific tasks, such as collective classification and graph generation, by designing deep learning models to learn better task-specific representations for graphs. First, we studied the collective classification problem in graphs and proposed recurrent collective classification, a variant of the iterative classification algorithm that is more robust to situations where predictions are noisy or inaccurate. Then we studied the problem of graph generation using deep generative models. We first proposed a deep generative model using the GAN framework that generates labeled graphs. Then in order to support more applications and also get more control over the generated graphs, we extended the problem of graph generation to conditional graph generation which can then be applied to various applications for modeling graph evolution and transformation.
APA, Harvard, Vancouver, ISO, and other styles
9

Martinsen, Thor. "Refinement composition using doubly labeled transition graphs." Thesis, Monterey, Calif. : Naval Postgraduate School, 2007. http://bosun.nps.edu/uhtbin/hyperion-image.exe/07Sep%5FMartinsen.pdf.

Full text
Abstract:
Thesis (M.S. in Computer Science and M.S. in Applied Mathematics)--Naval Postgraduate School, September 2007.
Thesis Advisor(s): Dinolt, George ; Fredricksen, Harold. "September 2007." Description based on title screen as viewed on October 23, 2007. Includes bibliographical references (p.49-51). Also available in print.
APA, Harvard, Vancouver, ISO, and other styles
10

Johansson, Öjvind. "Graph Decomposition Using Node Labels." Doctoral thesis, KTH, Numerical Analysis and Computer Science, NADA, 2001. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3213.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Labeled graph"

1

Chartrand, Gary, Cooroo Egan, and Ping Zhang. How to Label a Graph. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-16863-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Wiskott, Laurenz. Labeled graphs and dynamic link matching for face recognition and scene analysis. Thun: Deutsch, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kaplan, Simon M. Incremental attribute evaluation on node-label controlled graphs. Urbana, IL (1304 W. Springfield Ave., Urbana 61801): Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1987.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Pancer, Richard Norman. GED - a graph EDitor for labelled simple directed acyclic graphs. 1985.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Diamond, James Stuart. Edge deletion in labelled graphs. 1986.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Zhang, Ping, Cooroo Egan, and Gary Chartrand. How to Label a Graph. Springer, 2019.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Fan, Kuo-Chin. A feature-oriented label graph isomorphism algorithm and its applications. 1989.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Selvin, Steve. The Joy of Statistics. Oxford University Press, 2019. http://dx.doi.org/10.1093/oso/9780198833444.001.0001.

Full text
Abstract:
The Joy of Statistics consists of a series of 42 “short stories,” each illustrating how elementary statistical methods are applied to data to produce insight and solutions to the questions data are collected to answer. The text contains brief histories of the evolution of statistical methods and a number of brief biographies of the most famous statisticians of the 20th century. Also throughout are a few statistical jokes, puzzles, and traditional stories. The level of the Joy of Statistics is elementary and explores a variety of statistical applications using graphs and plots, along with detailed and intuitive descriptions and occasionally using a bit of 10th grade mathematics. Examples of a few of the topics are gambling games such as roulette, blackjack, and lotteries as well as more serious subjects such as comparison of black/white infant mortality rates, coronary heart disease risk, and ethnic differences in Hodgkin’s disease. The statistical description of these methods and topics are accompanied by easy to understand explanations labeled “how it works.”
APA, Harvard, Vancouver, ISO, and other styles
9

The New Encyclopedia of Wine: An illustrated guide to the vineyards of the world, the best grape varieties and the practicalities of buying, keeping, serving ... over 450 photographs, maps and wine labels. Lorenz Books, 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Labeled graph"

1

Binucci, Carla, Walter Didimo, Giuseppe Liotta, and Maddalena Nonato. "Computing Labeled Orthogonal Drawings." In Graph Drawing, 66–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36151-0_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Couëtoux, Basile, Elie Nakache, and Yann Vaxès. "The Maximum Labeled Path Problem." In Graph-Theoretic Concepts in Computer Science, 152–63. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-12340-0_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hurfin, Michel, and Michel Raynal. "Detecting diamond necklaces in labeled dags." In Graph-Theoretic Concepts in Computer Science, 211–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/3-540-62559-3_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Mohan, Anshuman, Wei Xiang Leow, and Aquinas Hobor. "Functional Correctness of C Implementations of Dijkstra’s, Kruskal’s, and Prim’s Algorithms." In Computer Aided Verification, 801–26. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81688-9_37.

Full text
Abstract:
AbstractWe develop machine-checked verifications of the full functional correctness of C implementations of the eponymous graph algorithms of Dijkstra, Kruskal, and Prim. We extend Wang et al.’s CertiGraph platform to reason about labels on edges, undirected graphs, and common spatial representations of edge-labeled graphs such as adjacency matrices and edge lists. We certify binary heaps, including Floyd’s bottom-up heap construction, heapsort, and increase/decrease priority.Our verifications uncover subtle overflows implicit in standard textbook code, including a nontrivial bound on edge weights necessary to execute Dijkstra’s algorithm; we show that the intuitive guess fails and provide a workable refinement. We observe that the common notion that Prim’s algorithm requires a connected graph is wrong: we verify that a standard textbook implementation of Prim’s algorithm can compute minimum spanning forests without finding components first. Our verification of Kruskal’s algorithm reasons about two graphs simultaneously: the undirected graph undergoing MSF construction, and the directed graph representing the forest inside union-find. Our binary heap verification exposes precise bounds for the heap to operate correctly, avoids a subtle overflow error, and shows how to recycle keys to avoid overflow.
APA, Harvard, Vancouver, ISO, and other styles
5

Hassin, Refael, Jérôme Monnot, and Danny Segev. "The Complexity of Bottleneck Labeled Graph Problems." In Graph-Theoretic Concepts in Computer Science, 328–40. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-74839-7_31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Wu, Yang, Ada Wai-Chee Fu, Cheng Long, and Zitong Chen. "LSimRank: Node Similarity in a Labeled Graph." In Web and Big Data, 127–44. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-60259-8_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Nishimura, Naomi, Prabhakar Ragde, and Dimitrios M. Thilikos. "On Graph Powers for Leaf-Labeled Trees." In Algorithm Theory - SWAT 2000, 125–38. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44985-x_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Baste, Julien, Marc Noy, and Ignasi Sau. "On the Number of Labeled Graphs of Bounded Treewidth." In Graph-Theoretic Concepts in Computer Science, 88–99. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-68705-6_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Caldarola, Enrico Giacinto, Antonio Picariello, and Antonio M. Rinaldi. "Experiences in WordNet Visualization with Labeled Graph Databases." In Communications in Computer and Information Science, 80–99. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-52758-1_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Goetzke, K., H. J. Klein, and P. Kandzia. "Automatic crystal chemical classification of silicates using direction-labeled graphs." In Graph-Theoretic Concepts in Computer Science, 242–54. Berlin, Heidelberg: Springer Berlin Heidelberg, 1988. http://dx.doi.org/10.1007/3-540-19422-3_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Labeled graph"

1

Song, Chunyao, and Tingjian Ge. "Labeled Graph Sketches." In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 2018. http://dx.doi.org/10.1109/icde.2018.00138.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Wang, Lichen, Zhengming Ding, and Yun Fu. "Adaptive Graph Guided Embedding for Multi-label Annotation." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/388.

Full text
Abstract:
Multi-label annotation is challenging since a large amount of well-labeled training data are required to achieve promising performance. However, providing such data is expensive while unlabeled data are widely available. To this end, we propose a novel Adaptive Graph Guided Embedding (AG2E) approach for multi-label annotation in a semi-supervised fashion, which utilizes limited labeled data associating with large-scale unlabeled data to facilitate learning performance. Specifically, a multi-label propagation scheme and an effective embedding are jointly learned to seek a latent space where unlabeled instances tend to be well assigned multiple labels. Furthermore, a locality structure regularizer is designed to preserve the intrinsic structure and enhance the multi-label annotation. We evaluate our model in both conventional multi-label learning and zero-shot learning scenario. Experimental results demonstrate that our approach outperforms other compared state-of-the-art methods.
APA, Harvard, Vancouver, ISO, and other styles
3

Da Silva, Thiago Gouveia. "The Minimum Labeling Spanning Tree and Related Problems." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6333.

Full text
Abstract:
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph in which each edge has one label associated, by using a minimum number of labels. It is an NP-hard problem that has attracted substantial research attention in recent years. In its turn, the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of the MLSTP that allows the situation in which multiple labels can be assigned to an edge. Both problems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. The thesis addresses several connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in the work can be classified between theoretical and practical. On the theoretical side, it has introduced new useful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well as a polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics and new mathematical formulations and branch-and-cut algorithms. The new approaches introduced have achieved the best results for both heuristic and exact methods in comparison with the state-of-the-art.
APA, Harvard, Vancouver, ISO, and other styles
4

Shirui Pan, Xingquan Zhu, Chengqi Zhang, and P. S. Yu. "Graph stream classification using labeled and unlabeled graphs." In 2013 29th IEEE International Conference on Data Engineering (ICDE 2013). IEEE, 2013. http://dx.doi.org/10.1109/icde.2013.6544842.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Liang, De-Ming, and Yu-Feng Li. "Lightweight Label Propagation for Large-Scale Network Data." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/475.

Full text
Abstract:
Label propagation spreads the soft labels from few labeled data to a large amount of unlabeled data according to the intrinsic graph structure. Nonetheless, most label propagation solutions work under relatively small-scale data and fail to cope with many real applications, such as social network analysis, where graphs usually have millions of nodes. In this paper, we propose a novel algorithm named \algo to deal with large-scale data. A lightweight iterative process derived from the well-known stochastic gradient descent strategy is used to reduce memory overhead and accelerate the solving process. We also give a theoretical analysis on the necessity of the warm-start technique for label propagation. Experiments show that our algorithm can handle million-scale graphs in few seconds while achieving highly competitive performance with existing algorithms.
APA, Harvard, Vancouver, ISO, and other styles
6

Candao, Jhonatan, and Lilian Berton. "Combining active learning and graph-based semi-supervised learning." In Encontro Nacional de Inteligência Artificial e Computacional. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/eniac.2019.9326.

Full text
Abstract:
The scarcity of labeled data is a common problem in many applications. Semi-supervised learning (SSL) aims to minimize the need for human annotation combining a small set of label data with a huge amount of unlabeled data. Similarly to SSL, Active Learning (AL) reduces the annotation efforts selecting the most informative points for annotation. Few works explore AL and graph-based SSL, in this work, we combine both strategies and explore different techniques: two graph-based SSL and two query strategy of AL in a pool-based scenario. Experimental results in artificial and real datasets indicate that our approach requires significantly less labeled instances to reach the same performance of random label selection.
APA, Harvard, Vancouver, ISO, and other styles
7

Cao, Guitao, and Zhi Zhang. "Schema Matching Based on Labeled Graph." In 2009 International Conference on Computational Intelligence and Software Engineering. IEEE, 2009. http://dx.doi.org/10.1109/cise.2009.5364747.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Shi, Min, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. "Multi-Class Imbalanced Graph Convolutional Network Learning." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/398.

Full text
Abstract:
Networked data often demonstrate the Pareto principle (i.e., 80/20 rule) with skewed class distributions, where most vertices belong to a few majority classes and minority classes only contain a handful of instances. When presented with imbalanced class distributions, existing graph embedding learning tends to bias to nodes from majority classes, leaving nodes from minority classes under-trained. In this paper, we propose Dual-Regularized Graph Convolutional Networks (DR-GCN) to handle multi-class imbalanced graphs, where two types of regularization are imposed to tackle class imbalanced representation learning. To ensure that all classes are equally represented, we propose a class-conditioned adversarial training process to facilitate the separation of labeled nodes. Meanwhile, to maintain training equilibrium (i.e., retaining quality of fit across all classes), we force unlabeled nodes to follow a similar latent distribution to the labeled nodes by minimizing their difference in the embedding space. Experiments on real-world imbalanced graphs demonstrate that DR-GCN outperforms the state-of-the-art methods in node classification, graph clustering, and visualization.
APA, Harvard, Vancouver, ISO, and other styles
9

Wang, Qifan, Gal Chechik, Chen Sun, and Bin Shen. "Instance-Level Label Propagation with Multi-Instance Learning." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/410.

Full text
Abstract:
Label propagation is a popular semi-supervised learning technique that transfers information from labeled examples to unlabeled examples through a graph. Most label propagation methods construct a graph based on example-to-example similarity, assuming that the resulting graph connects examples that share similar labels. Unfortunately, example-level similarity is sometimes badly defined. For instance, two images may contain two different objects, but have similar overall appearance due to large similar background. In this case, computing similarities based on whole-image would fail propagating information to the right labels. This paper proposes a novel Instance-Level Label Propagation (ILLP) approach that integrates label propagation with multi-instance learning. Each example is treated as containing multiple instances, as in the case of an image consisting of multiple regions. We first construct a graph based on instance-level similarity and then simultaneously identify the instances carrying the labels and propagate the labels across instances in the graph. Optimization is based on an iterative Expectation Maximization (EM) algorithm. Experimental results on two benchmark datasets demonstrate the effectiveness of the proposed approach over several state-of-the-art methods.
APA, Harvard, Vancouver, ISO, and other styles
10

Li, Chen, Xutan Peng, Hao Peng, Jianxin Li, and Lihong Wang. "TextGTL: Graph-based Transductive Learning for Semi-supervised Text Classification via Structure-Sensitive Interpolation." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/369.

Full text
Abstract:
Compared with traditional sequential learning models, graph-based neural networks exhibit excellent properties when encoding text, such as the capacity of capturing global and local information simultaneously. Especially in the semi-supervised scenario, propagating information along the edge can effectively alleviate the sparsity of labeled data. In this paper, beyond the existing architecture of heterogeneous word-document graphs, for the first time, we investigate how to construct lightweight non-heterogeneous graphs based on different linguistic information to better serve free text representation learning. Then, a novel semi-supervised framework for text classification that refines graph topology under theoretical guidance and shares information across different text graphs, namely Text-oriented Graph-based Transductive Learning (TextGTL), is proposed. TextGTL also performs attribute space interpolation based on dense substructure in graphs to predict low-entropy labels with high-quality feature nodes for data augmentation. To verify the effectiveness of TextGTL, we conduct extensive experiments on various benchmark datasets, observing significant performance gains over conventional heterogeneous graphs. In addition, we also design ablation studies to dive deep into the validity of components in TextTGL.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Labeled graph"

1

Li, Wenting. Robust Fault Location in Power Grids through Graph Learning at Low Label Rates. Office of Scientific and Technical Information (OSTI), February 2021. http://dx.doi.org/10.2172/1768426.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Labeled graph' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography