Página 1 dos resultados de 29087 itens digitais encontrados em 0.025 segundos

Graph construction based on labeled instances for semi-supervised learning

Berton, Lilian; Lopes, Alneu de Andrade
Fonte: International Association of Pattern Recognition - IAPR; Linköping University; Lund University; Uppsala University; Institute of Electrical and Electronics Engineers - IEEE; Stockholm Publicador: International Association of Pattern Recognition - IAPR; Linköping University; Lund University; Uppsala University; Institute of Electrical and Electronics Engineers - IEEE; Stockholm
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
36.56%
Semi-Supervised Learning (SSL) techniques have become very relevant since they require a small set of labeled data. In this context, graph-based algorithms have gained prominence in the area due to their capacity to exploiting, besides information about data points, the relationships among them. Moreover, data represented in graphs allow the use of collective inference (vertices can affect each other), propagation of labels (autocorrelation among neighbors) and use of neighborhood characteristics of a vertex. An important step in graph-based SSL methods is the conversion of tabular data into a weighted graph. The graph construction has a key role in the quality of the classification in graph-based methods. This paper explores a method for graph construction that uses available labeled data. We provide extensive experiments showing the proposed method has many advantages: good classification accuracy, quadratic time complexity, no sensitivity to the parameter k > 10, sparse graph formation with average degree around 2 and hub formation from the labeled points, which facilitates the propagation of labels.; Sao Paulo Research Foundation (FAPESP) (Grant 2011/21880-3 and 2011/22749-8)

Homomorfismos de grafos; Graph Homomorphisms

Sato, Cristiane Maria
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 25/04/2008 PT
Relevância na Pesquisa
36.59%
Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise.; Graph homomorphisms are functions from the vertex set of a graph to the vertex set of another graph that preserve adjacencies. The study of graph homomorphisms is very broad, and there are several lines of research about this topic. In this dissertation, we present results about graph homomorphisms related to convergence of graph sequences and connection matrices of graph parameters. This line of research has been proved to be very rich, not only for its results, but also for the proof techniques. In particular...

Metaheurísticas para o problema de agrupamento de dados em grafo; Metaheuristics for the graph clustering problem

Nascimento, Mariá Cristina Vasconcelos
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 26/02/2010 PT
Relevância na Pesquisa
36.53%
O problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta Tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto...

Classificação de dados estacionários e não estacionários baseada em grafos; Graph-based classification for stationary and non-stationary data

Bertini Júnior, João Roberto
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 24/01/2011 PT
Relevância na Pesquisa
36.59%
Métodos baseados em grafos consistem em uma poderosa forma de representação e abstração de dados que proporcionam, dentre outras vantagens, representar relações topológicas, visualizar estruturas, representar grupos de dados com formatos distintos, bem como, fornecer medidas alternativas para caracterizar os dados. Esse tipo de abordagem tem sido cada vez mais considerada para solucionar problemas de aprendizado de máquina, principalmente no aprendizado não supervisionado, como agrupamento de dados, e mais recentemente, no aprendizado semissupervisionado. No aprendizado supervisionado, por outro lado, o uso de algoritmos baseados em grafos ainda tem sido pouco explorado na literatura. Este trabalho apresenta um algoritmo não paramétrico baseado em grafos para problemas de classificação com distribuição estacionária, bem como sua extensão para problemas que apresentam distribuição não estacionária. O algoritmo desenvolvido baseia-se em dois conceitos, a saber, 1) em uma estrutura chamada grafo K-associado ótimo, que representa o conjunto de treinamento como um grafo esparso e dividido em componentes; e 2) na medida de pureza de cada componente, que utiliza a estrutura do grafo para determinar o nível de mistura local dos dados em relação às suas classes. O trabalho também considera problemas de classificação que apresentam alteração na distribuição de novos dados. Este problema caracteriza a mudança de conceito e degrada o desempenho do classificador. De modo que...

Impacto da geração de grafos na classificação semissupervisionada; Impact of graph construction on semi-supervised classification

Sousa, Celso André Rodrigues de
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 18/07/2013 PT
Relevância na Pesquisa
36.65%
Uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos e métodos de geração de grafos foram propostos pela comunidade científica nos últimos anos. Apesar de seu aparente sucesso empírico, a área de aprendizado semissupervisionado carece de um estudo empírico detalhado que avalie o impacto da geração de grafos na classificação semissupervisionada. Neste trabalho, é provido tal estudo empírico. Para tanto, combinam-se uma variedade de métodos de geração de grafos com uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos para compará-los empiricamente em seis bases de dados amplamente usadas na literatura de aprendizado semissupervisionado. Os algoritmos são avaliados em tarefas de classificação de dígitos, caracteres, texto, imagens e de distribuições gaussianas. A avaliação experimental proposta neste trabalho é subdividida em quatro partes: (1) análise de melhor caso; (2) avaliação da estabilidade dos classificadores semissupervisionados; (3) avaliação do impacto da geração de grafos na classificação semissupervisionada; (4) avaliação da influência dos parâmetros de regularização no desempenho de classificação dos classificadores semissupervisionados. Na análise de melhor caso...

Graph Laplacian for spectral clustering and seeded image segmentation; Estudo do Laplaciano do grafo para o problema de clusterização espectral e segmentação interativa de imagens

Casaca, Wallace Correa de Oliveira
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 05/12/2014 EN
Relevância na Pesquisa
36.56%
Image segmentation is an essential tool to enhance the ability of computer systems to efficiently perform elementary cognitive tasks such as detection, recognition and tracking. In this thesis we concentrate on the investigation of two fundamental topics in the context of image segmentation: spectral clustering and seeded image segmentation. We introduce two new algorithms for those topics that, in summary, rely on Laplacian-based operators, spectral graph theory, and minimization of energy functionals. The effectiveness of both segmentation algorithms is verified by visually evaluating the resulting partitions against state-of-the-art methods as well as through a variety of quantitative measures typically employed as benchmark by the image segmentation community. Our spectral-based segmentation algorithm combines image decomposition, similarity metrics, and spectral graph theory into a concise and powerful framework. An image decomposition is performed to split the input image into texture and cartoon components. Then, an affinity graph is generated and weights are assigned to the edges of the graph according to a gradient-based inner-product function. From the eigenstructure of the affinity graph, the image is partitioned through the spectral cut of the underlying graph. Moreover...

Object-oriented graph grammars

Ferreira, Ana Paula Ludtke
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
ENG
Relevância na Pesquisa
36.59%
Esta tese apresenta um modelo conceitual para modelagem e vericação de espe- cificações de sistemas orientados a objeto. Mais especificiamente, uma extensão da abordagem algébrica baseada em single-pushouts para gramáticas de grafos tipadas é desenvolvida, onde os morfismos de tipagem são compatíveis com as relações de ordem sobre os nodos e (hiper)arcos de um grafo, e que representam, respectivamente, as relações de herança entre classes e sobrescrita de métodos. O trabalho é dividido em trÊs linhas principais: especificações de sistemas, comportamento dinâmico de programas, e verificaçaõ formal de sistemas orientados a objeto. A hierarquia de classes de um sistema orientado a objetoé modelada por um hipergrafo rotulado chamado grafo de classes, cujos conjuntos de nodos e arcos possuem uma relação de ordem parcial restrita, com o objetivo de modelar herança e sobrescrita de métodos. Restrições adicionais garantem que grafos de classes provÊm um modelo fiel e adequado da maneira como as classes de um sistema orientado a objetos s~ao efetivamente organizadas e combinadas. Grafos orientados a objeto são hipergrafos tipados sobre um grafo de classes. O morfismo de tipagem exige que hiperarcos mapeados preservem as relações existentes entre os seus nodos de origem e destino. Esta característica modela a heran»ca de forma adequada...

Relational approach of graph grammars; Abordagem relacional de gramática de grafos

Cavalheiro, Simone André da Costa
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
ENG
Relevância na Pesquisa
36.56%
Gramática de grafos é uma linguagem formal bastante adequada para sistemas cujos estados possuem uma topologia complexa (que envolvem vários tipos de elementos e diferentes tipos de relações entre eles) e cujo comportamento é essencialmente orientado pelos dados, isto é, eventos são disparados por configurações particulares do estado. Vários sistemas reativos são exemplos desta classe de aplicações, como protocolos para sistemas distribuídos e móveis, simulação de sistemas biológicos, entre outros. A verificação de gramática de grafos através da técnica de verificação de modelos já é utilizada por diversas abordagens. Embora esta técnica constitua um método de análise bastante importante, ela tem como desvantagem a necessidade de construir o espaço de estados completo do sistema, o que pode levar ao problema da explosão de estados. Bastante progresso tem sido feito para lidar com esta dificuldade, e diversas técnicas têm aumentado o tamanho dos sistemas que podem ser verificados. Outras abordagens propõem aproximar o espaço de estados, mas neste caso não é possível a verificação de propriedades arbitrárias. Além da verificação de modelos, a prova de teoremas constitui outra técnica consolidada para verificação formal. Nesta técnica tanto o sistema quanto suas propriedades são expressas em alguma lógica matemática. O processo de prova consiste em encontrar uma prova a partir dos axiomas e lemas intermediários do sistema. Cada técnica tem argumentos pró e contra o seu uso...

Higher-order graph rewriting systems; Sistemas de reescrita de grafos de alta ordem

Machado, Rodrigo
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
ENG
Relevância na Pesquisa
36.64%
Programas sofrem diversas modificações ao longo das etapas de desenvolvimento, implantação e manutenção. A evolução de um software pode ter várias causas: correção de erros, inclusão de novas funcionalidades ou até mesmo, como é o caso de programas orientados a aspecto, transformações estruturais podem fazer parte da semântica do sistema. Apesar de modificações serem comuns, não é tarefa trivial prever como estas afetam o comportamento dos programas, já que os componentes de software normalmente interagem de forma complexa, o que faz com que mesmo pequenas alterações possam introduzir comportamentos indesejados. Transformação de grafos, também conhecida como reescrita de grafos, é um importante paradigma para modelagem e análise de sistemas. Modelos baseados em transformação de grafos, como gramáticas de grafos, permitem uma modelagem ao mesmo tempo intuitiva e com semântica precisa, permitindo a aplicação de técnicas de análise como verificação de modelos e análise de par crítico no estudo do comportamento de sistemas. A teoria por trás de transformação de grafos vem sendo desenvolvida a várias décadas, e atualmente está descrita de uma forma bastante abstrata. Contudo, ainda não possui uma definição natural de reescritas de alta ordem...

Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming

Harrison, Kyle Robert
Fonte: Brock University Publicador: Brock University
Tipo: Electronic Thesis or Dissertation
ENG
Relevância na Pesquisa
36.56%
A complex network is an abstract representation of an intricate system of interrelated elements where the patterns of connection hold significant meaning. One particular complex network is a social network whereby the vertices represent people and edges denote their daily interactions. Understanding social network dynamics can be vital to the mitigation of disease spread as these networks model the interactions, and thus avenues of spread, between individuals. To better understand complex networks, algorithms which generate graphs exhibiting observed properties of real-world networks, known as graph models, are often constructed. While various efforts to aid with the construction of graph models have been proposed using statistical and probabilistic methods, genetic programming (GP) has only recently been considered. However, determining that a graph model of a complex network accurately describes the target network(s) is not a trivial task as the graph models are often stochastic in nature and the notion of similarity is dependent upon the expected behavior of the network. This thesis examines a number of well-known network properties to determine which measures best allowed networks generated by different graph models, and thus the models themselves...

Object-Oriented Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Medland, Michael; Medland, Michael
Fonte: Brock University Publicador: Brock University
Tipo: Electronic Thesis or Dissertation
ENG
Relevância na Pesquisa
36.62%
Complex networks are systems of entities that are interconnected through meaningful relationships. The result of the relations between entities forms a structure that has a statistical complexity that is not formed by random chance. In the study of complex networks, many graph models have been proposed to model the behaviours observed. However, constructing graph models manually is tedious and problematic. Many of the models proposed in the literature have been cited as having inaccuracies with respect to the complex networks they represent. However, recently, an approach that automates the inference of graph models was proposed by Bailey [10] The proposed methodology employs genetic programming (GP) to produce graph models that approximate various properties of an exemplary graph of a targeted complex network. However, there is a great deal already known about complex networks, in general, and often specific knowledge is held about the network being modelled. The knowledge, albeit incomplete, is important in constructing a graph model. However it is difficult to incorporate such knowledge using existing GP techniques. Thus, this thesis proposes a novel GP system which can incorporate incomplete expert knowledge that assists in the evolution of a graph model. Inspired by existing graph models...

Graph separators - a parameterized view

Alber, Jochen; Fernau, Henning; Niedermeier, Rolf
Fonte: Universidade de Tubinga Publicador: Universidade de Tubinga
Tipo: Report (Bericht)
EN
Relevância na Pesquisa
36.58%
Graph separation is a well-known tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way of easily check wether a planar graph problem will allow for a fixed parameter algorithm of running time. Besides we introduce the novel cocept of "problem cores" that might serve as an alternative to problem kernels for devising parameterized algorithms. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. Our findings also give rise to studying further refinements of the complexity class FTP of fixed parameters tractable problems.

Orthogonal Graph Drawing with Constraints: Algorithms and Applications; Orthogonales Graphenzeichnen mit Nebenbedingungen: Algorithmen und Anwendungen

Siebenhaller, Martin
Fonte: Universidade de Tubinga Publicador: Universidade de Tubinga
Tipo: Dissertação
DE_DE
Relevância na Pesquisa
36.6%
Die Visualisierung ist ein bewährtes und probates Mittel für die Repräsentation von Daten. Aufgrund der kognitiven Fähigkeiten von Menschen erleichtert eine Visualisierung (graphische Darstellung) das Aufnehmen und Verstehen der in den Daten enthaltenen Informationen. Die vorliegende Arbeit beschäftigt sich mit der Graph-basierten Visualisierung, d. h. der Visualisierung von Daten, die durch Graphen beschrieben werden können. Ein Graph ist ein Konstrukt der Mathematik (Graphentheorie) und wird zur Modellierung von binären Relationen zwischen Objekten verwendet. Die Objekte werden dabei häufig als Knoten und die Relationen als Kanten bezeichnet. Das Forschungsgebiet, welches sich mit der Visualisierung von Graphen, im Speziellen mit dem automatischen Anordnen (Layout) von Knoten und Kanten beschäftigt, heißt Graphenzeichnen. Beim Zeichnen von Graphen werden Knoten üblicherweise als Punkte/Rechtecke und Kanten als Kurven repräsentiert. Außerdem werden verschiedene ästhetische Anforderungen berücksichtigt, z. B. soll die Anzahl der Kantenkreuzungen in der resultierenden Zeichnung möglichst gering sein. In orthogonalen Zeichnungen von Graphen werden die Kanten durch Polygonzüge dargestellt, die aus abwechselnd horizontalen und vertikalen Liniensegmenten bestehen. Das bekannteste Verfahren zur Erzeugung von orthogonalen Zeichnungen ist der Topology-Shape-Metrics Ansatz (TSM-Ansatz)...

Scalable graph kernels; Skalierbare Graphkerne

Shervashidze, Nino
Fonte: Universidade de Tubinga Publicador: Universidade de Tubinga
Tipo: Dissertação
EN
Relevância na Pesquisa
36.68%
Graph-structured data are becoming more and more abundant in many fields of science and engineering, such as social network analysis, molecular biology, chemistry, computer vision, or program verification. To exploit these data, one needs data analysis and machine learning methods that are able to efficiently handle large-scale graph data sets. Successfully applying machine learning and data analysis methods to graphs requires the ability to efficiently compare and represent graphs. Standard solutions to these problems are either NP-hard, not expressive enough, or difficult to adapt to a problem at hand. Graph kernels have attracted considerable interest in the machine learning community in the last decade as a promising solution to the above-mentioned issues. Despite significant progress in the design and improvement of graph kernels in the past few years, existing graph kernels do not measure up to the current needs of machine learning on large, labeled graphs: Even the most efficient existing kernels need O(n^3) runtime to compare a pair of graphs with n nodes, or cannot take into account node and edge labels. Our primary goal in this thesis is the design of efficient and expressive kernels for machine learning on graphs. We first focus on the design of generic graph kernels that can be applied to graphs with or without labels. Our main contributions to this end are the following: First...

Desarrollo de una herramienta business intelligence para el análisis de redes sociales almacenadas en grafos; Development of a Business Intelligence Tool for the Analysis of Social Networks Stored in Graph Databases

Ruiz Martínez, Noelia
Fonte: Universidade de Cantabria Publicador: Universidade de Cantabria
Tipo: Trabalho de Conclusão de Curso
SPA
Relevância na Pesquisa
36.56%
RESUMEN: En los últimos años se ha producido un gran crecimiento de los servicios basados en redes sociales como, por ejemplo, Twitter o Facebook. Si se visualiza la disposición de los datos que conforman estas redes, se asemeja en gran medida a un grafo en el que los nodos representan usuarios y las aristas que los unen las relaciones que se establecen entre ellos. Es por ello que, generalmente, estas aplicaciones utilizan gestores orientados a grafos para el almacenamiento de la información, como es el caso de Twitter, que hace uso del gestor FlockDB; o para soportar parte de su funcionalidad, como ocurre en el caso de Facebook que integra aplicaciones basadas en grafos a través del protocolo Open Graph. Esta importancia de las redes sociales en la actualidad se traduce también en la relevancia de la búsqueda de información interesante para el negocio a partir de los datos correspondientes a la actividad realizada por los usuarios y a las relaciones existentes entre ellos. Por estos motivos, este Proyecto Fin de Carrera ha tenido como objetivo el desarrollo de una herramienta Business Intelligence que incluyera la definición y el cálculo de indicadores de interés para analizar redes sociales. Con este propósito se utilizaron conjuntos de datos reales de diferentes características y tamaños y se almacenaron en un gestor de bases de datos orientadas a grafos...

Covering the de Bruijn graph

Bryant, Roy Dale
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
Tipo: Tese de Doutorado Formato: 102 p.
EN_US
Relevância na Pesquisa
36.56%
Approved for public release; distribution is unlimited; Random-like sequences of 0's and l's are generated efficiently by binary shift registers. The output of n-stage shift registers viewed as a sequence of binary n-tuples also give rise to a special graph called the de Bruijn graph B . The de Bruijn graph is a directed graph with 2n nodes. Each node has 2 arcs entering it and 2 arcs going out of it. Thus, there are a total of 2n+1 arcs in Bn. In this thesis, we define a cover of the de Bruijn graph, different from the usual graph theoretic cover. A cover S of the de Bruijn graph is defined as an independent subset of the nodes of Bn that satisfy the following J property. For each node x in Bn - S, there exists a node y in S such that either the arc or the arc is in Bn. Combinatorially, we are able to place both upper and lower bounds on the cardinality of S. We find examples of covers that approach these bounds in cardinality. Several algorithms are presented that produce either a maximal or a minimal cover. Among them are Frugal, Sequential Fill, Double and Redouble, Greedy and Quartering.; http://archive.org/details/coveringdebruijn00brya; Captain, United States Marine Corps

Fuzzy Multilevel Graph Embedding for Recognition, Indexing and Retrieval of Graphic Document Images

Muzzamil Luqman, Muhammad
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Artigo de Revista Científica Formato: application/pdf; application/pdf; application/pdf
Publicado em //2014 ENG
Relevância na Pesquisa
36.64%
Advisors: Jean-Yves Ramel, Josep Lladós and Thierry Brouard Date and location of PhD thesis defense: 2nd of March 2012 at University of Tours in France.; This thesis addresses the problem of lack of efficient computational tools for graph based structural pattern recognition approaches and proposes to exploit computational strength of statistical pattern recognition. It has two fold contributions. The first contribution is a new method of explicit graph embedding. The proposed graph embedding method exploits multilevel analysis of graph for extracting graph level information, structural level information and elementary level information from graphs. It embeds this information into a numeric feature vector. The method employs fuzzy overlapping trapezoidal intervals for addressing the noise sensitivity of graph representations and for minimizing the information loss while mapping from continuous graph space to discrete vector space. The method has unsupervised learning abilities and is capable of automatically adapting its parameters to underlying graph dataset. The second contribution is a framework for automatic indexing of graph repositories for graph retrieval and subgraph spotting. This framework exploits explicit graph embedding for representing the cliques of order 2 by numeric feature vectors...

Algorithms for the Reeb Graph and Related Concepts

Parsa, Salman
Fonte: Universidade Duke Publicador: Universidade Duke
Tipo: Dissertação
Publicado em //2014
Relevância na Pesquisa
36.63%

This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.

The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem.

The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph...

Interactive, tree-based graph visualization

Pavlo, Andrew
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
Tipo: Tese de Doutorado Formato: 299809 bytes; 2258646 bytes; application/pdf; application/pdf
EN_US
Relevância na Pesquisa
36.59%
We introduce an interactive graph visualization scheme that allows users to explore graphs by viewing them as a sequence of spanning trees, rather than the entire graph all at once. The user determines which spanning trees are displayed by selecting a vertex from the graph to be the root. Our main contributions are a graph drawing algorithm that generates meaningful representations of graphs using extracted spanning trees, and a graph animation algorithm for creating smooth, continuous transitions between graph drawings. We conduct experiments to measure how well our algorithms visualize graphs and compare them to another visualization scheme.

Graph Edit Distance from Spectral Seriation

Robles-Kelly, Antonio; Hancock, Edwin R
Fonte: Institute of Electrical and Electronics Engineers (IEEE Inc) Publicador: Institute of Electrical and Electronics Engineers (IEEE Inc)
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.63%
This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.