Academic literature on the topic 'Labeled graph'

<p> 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.</p><p> 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.</p><p> 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.</p><p> 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. </p><p> 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. </p><p> 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. </p>

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.

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.

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.

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<br>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

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.

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.<br>Doctor of Philosophy<br>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.

Thesis (M.S. in Computer Science and M.S. in Applied Mathematics)--Naval Postgraduate School, September 2007.<br>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.