Dissertations / Theses on the topic 'Laplacian matrix'

A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency / Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence.
Series: Research Report Series / Department of Statistics and Mathematics

We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD. Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas.
In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector. (author´s abstract)
Series: Research Report Series / Department of Statistics and Mathematics

A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. If a graph G is (2, r)-regular where p, s, and m are positive integers, and m ≥ 2, then when n is sufficiently large, then G is isomorphic to G = Ks+mKp, where 2(p-1)+s = r. A nested (2,r)-regular graph is constructed by replacing selected cliques with a (2,r)-regular graph and joining the vertices of the peripheral cliques. For example, in a nested 's' graph when n = s + mp, we obtain n = s1+m1p1+mp. The nested 's' graph is now of the form Gs = Ks1+m1Kp1+mKp. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs.

Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A..=2b, where A 2 Rnn is a large, sparse symmetric positive definite matrix and b 2 Rn is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations. Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods. Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations. In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LLT is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L..T z, with x = A..1=2z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form n = A..=2b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t..=2 and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form. A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A..=2b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.

Orientadores: Carlile Campos Lavor, Leonardo Silva de Lima
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
Made available in DSpace on 2018-08-26T08:31:47Z (GMT). No. of bitstreams: 1 Amaro_BrunoDias_D.pdf: 1369520 bytes, checksum: a36663d5fd23193d66bb22c83cb932aa (MD5) Previous issue date: 2014
Resumo: A Teoria Espectral de Grafos é um ramo da Matemática Discreta que se preocupa com a relação entre as propriedades algébricas do espectro de certas matrizes associadas a grafos, como a matriz de adjacência, laplaciana ou laplaciana sem sinal e a topologia dos mesmos. Os autovalores e autovetores das matrizes associadas a um grafo são os invariantes que formam o autoespaço de grafos. Em Teoria Espectral de Grafos a conjectura proposta por Brouwer e Haemers, que associa a soma dos k maiores autovalores da matriz Laplaciana de um grafo G com seu número de arestas mais um fator combinatório (que depende do valor k adotado) é uma das questões interessantes e que está em aberto na literatura. Essa mostra diversos trabalhos que tentam provar tal conjectura. Em 2013, Ashraf et al. estenderam essa conjectura para a matriz laplaciana sem sinal e provaram que ela é válida para a soma dos 2 maiores autovalores e que também é válida para todo k, caso o grafo seja regular. Nosso trabalho aborda a versão dessa conjectura para a matriz laplaciana sem sinal. Conseguimos obter uma família de grafos que satisfaz a conjectura para a soma dos 3 maiores autovalores da matriz laplaciana sem sinal e a família de grafos split completo mais uma aresta satisfaz a conjectura para todos os autovalores. Ainda, baseado na desigualdade de Schur, conseguimos mostrar que a soma dos k menores autovalores das matrizes laplaciana e laplaciana sem sinal são limitadas superiormente pela soma dos k menores graus de G
Abstract: The Spectral Graph Theory is a branch of Discrete Mathematics that is concerned with relations between the algebraic properties of spectrum of some matrices associated to graphs, as the Adjacency, Laplacian and signless Laplacian matrices and their respective topologies. The eigenvalues and eigenvectors of matrices associated to graphs are the invariants which constitute the eigenspace of graphs. On Spectral Graph Theory the conjecture proposed by Brouwer and Haemers, associating the sum of k largest eigenvalues of Laplacian matrix of a graph G with its edges numbers plus a combinatorial factor (which depends on the choosed k) is an open interesting question in the Literature. There are several works that attempt to prove this conjecture. In 2013, Ashraf et al. stretch the conjecture out to signless Laplacian matrix and proved that it is true for the sum of the 2 largest eigenvalues of signless Laplacian matrix and it is also true for all k if G is a regular graph. Our work approaches on the version of the conjecture concerning to signless Laplacian matrix. We could obtain a family of graphs which satisfies the conjecture for the sum of the 3 largest eigenvalues of signless Laplacian matrix and we prove that the family of complete split graphs plus one edge satisfies the Conjecture for all eigenvalues. Moreover, based on Schur's inequality, we could show that the sum of the k smallest eigenvalues of Laplacian and signless Laplacian matrices are bounded by the sum of the k smallest degrees of G
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada

Let G be a connected graph with n vertices and let x=(x1, ..., xn) be a real vector. A positive (negative) sign graph of the vector x is a maximal connected subgraph of G on vertices xi>0 (xi<0). For an eigenvalue of a generalized Laplacian of a tree: We characterize the maximal number of sign graphs of an eigenvector. We give an O(n2) time algorithm to find an eigenvector with maximum number of sign graphs and we show that finding an eigenvector with minimum number of sign graphs is an NP-complete problem. (author's abstract)
Series: Preprint Series / Department of Applied Statistics and Data Processing

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to zero compared to the largest Fiedler coefficient of the graph. We propose a vertex-weighted spectral clustering algorithm which incorporates a vector of weights for each vertex of a given graph to form a vertex-weighted graph. The proposed algorithm predicts association of equidistant or nearly equidistant data points from both clusters while the unweighted clustering does not provide association. Finally, we implemented both the unweighted and the vertex-weighted spectral clustering algorithms on several data sets to show that the proposed algorithm works in general.

L'obiettivo di questo elaborato è di esporre alcuni principali teoremi riguardanti proprietà spettrali di particolari matrici usate per descrivere dati, dette matrici Laplaciane, costruite a partire da grafi, e la loro applicazione nello spectral clustering. In particolare, viene analizzata una proprietà detta "proprietà di interlacing". L'ultimo capitolo sarà dedicato ad esperimenti numerici, volti ad illustrare computazionalmente i risultati teorici.

This Master Thesis deals with the drawing algorithms of graphs known from the mathematical theory. These algorithms deals with an appropriate distribution of the graph vertices in order to obtain the most clear and readable graphs for human readers. The main objective of this work was also to implement the drawing algorithm in the application that would allow to edit the graph. This work deals also with graphs representation in computers.

Doutoramento em Matemática
Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.
Many optimization problems on graphs are reduced to the determination of a subset of vertices of maximum cardinality inducing a k-regular subgraph. Since the determination of the order of a k-regular induced subgraph of highest order is in general a NP-hard problem, new upper bounds, determined in polynomial time which in many cases are good approximations of the respective optimal solutions are deduced. Using convex programming techniques, spectral upper boundswere introduced jointly with necessary and sufficient conditions for those upper bounds be achieved. Additionally, upper bounds based on adjacency, Laplacian and signless Laplacian spectrum are introduced. Furthermore, a nonpolynomial time algorithm for determining a subset of vertices of a graph which induces a maximum k-regular induced subgraph for a particular class is presented. Finally, a comparative computational study is provided jointly with a few conclusions.

Questa tesi si occupa di analizzare attraverso un approccio algebrico la dinamica di sistemi complessi descrivibili da network. Dopo aver definito concetti fondamentali per lo studio di un grafo, come la matrice di adiacenza e la matrice Laplaciana (e il relativo spettro), si mettono in relazione questi ultimi con le caratteristiche della dinamica degli elementi del sistema, in particolare per un tipo di dinamica diffusiva detto random walk. Di tale processo, considerato di rilevante importanza per via della sua applicabilità a numerosi fenomeni, se ne studiano l'esistenza e l'unicità delle soluzioni stazionarie e la risposta a perturbazioni dell'equilibrio. I tipi di perturbazioni studiate sono di due categorie: perturbazioni della dinamica degli elementi del sistema rispetto allo stato stazionario, in cui viene tuttavia mantenuta fissa la struttura del network, oppure perturbazioni strutturali del network stesso, in cui sono gli stessi collegamenti tra i nodi a subire una modifica. Attraverso alcune simulazioni numeriche vengono confermati sperimentalmente i principali risultati e, infine, si implementa un sistema di controllo basato su un algoritmo di adaptive learning capace di reagire a perturbazioni strutturali e riportare il sistema all'equilibrio originario.

L'obiettivo di questa tesi è analizzare nel dettaglio un insieme di tecniche di analisi dei dati, volte alla selezione e al raggruppamento di elementi omogenei, in modo che si possano facilmente interfacciare tra di loro e fornire un utilizzo più semplice per chi opera nel settore.È introdotta la trattazione dei principali metodi di clustering: linkage, k-medie e in particolare spectral clustering, argomento centrale della mia tesi.

Scopo di questo elaborato è presentare la derivazione delle equazioni di Maxwell alla base dell'elettromagnetismo utilizzando le forme differenziali. Il primo capitolo è dedicato allo studio in R^n delle forme differenziali, che scriveremo in coordinate, e delle loro principali proprietà. Dopo aver definito il differenziale esterno, parleremo di chiusura ed esattezza di una forma, per poi dedicarci alla nozione di operatore di Hodge, grazie al quale introdurremo la divergenza e il rotore di un campo vettoriale. Successivamente lavoreremo in un opportuno spazio con coordinate spazio-temporali, in cui verranno trattate le equazioni di Maxwell, dotandolo della metrica minkowskiana. Nel secondo capitolo si definiscono le equazioni di Maxwell nel vuoto tramite l'uso di una scrittura sintetica che sfrutta i concetti precedentemente sviluppati e si dimostra la loro invarianza per trasformazioni di Lorentz. In particolare ricaveremo, sia in termini di forme differenziali sia di campi vettoriali, le quattro classiche equazioni dell'elettromagnetismo e le utilizzeremo per ottenere quelle che decrivono la propagazione delle onde nello spazio-tempo.

abstract: Social media has become the norm of everyone for communication. The usage of social media has increased exponentially in the last decade. The myriads of Social media services such as Facebook, Twitter, Snapchat, and Instagram etc allow people to connect with their friends, and followers freely. The attackers who try to take advantage of this situation has also increased at an exponential rate. Every social media service has its own recommender systems and user profiling algorithms. These algorithms use users current information to make different recommendations. Often the data that is formed from social media services is Linked data as each item/user is usually linked with other users/items. Recommender systems due to their ubiquitous and prominent nature are prone to several forms of attacks. One of the major form of attacks is poisoning the training set data. As recommender systems use current user/item information as the training set to make recommendations, the attacker tries to modify the training set in such a way that the recommender system would benefit the attacker or give incorrect recommendations and hence failing in its basic functionality. Most existing training set attack algorithms work with ``flat" attribute-value data which is typically assumed to be independent and identically distributed (i.i.d.). However, the i.i.d. assumption does not hold for social media data since it is inherently linked as described above. Usage of user-similarity with Graph Regularizer in morphing the training data produces best results to attacker. This thesis proves the same by demonstrating with experiments on Collaborative Filtering with multiple datasets.
Dissertation/Thesis
Masters Thesis Computer Science 2019

O objetivo principal desta dissertação é fazer uma introdução à teoria espectral de grafos. Abordaremos algumas propriedades dos grafos, nomeadamente o polinómio característico, os valores e vetores próprios de matrizes associadas aos grafos. Nesta dissertação iremos dar mais relevância à matriz de adjacência e à matriz laplaciana, fazendo uma análise de alguns tipos especí…cos de grafos e dos respetivos espectros. Iremos estudar o conceito de energia de um grafo e de medidas de centralidade associadas aos grafos e aos seus conceitos inerentes. Serão apresentadas duas aplicações no decorrer da dissertação, uma referente à Química e ao carbono quaternário, com o objetivo de descobrir se o carbono quaternário existe ou não na molécula em estudo e, outra referente às medidas de centralidade em que será feito a análise do jogo de futebol “Portugal vs França” a contar para a …nal do Europeu de 2016, com o intuito de descobrir as performances dos jogadores.
The main purpose of this dissertation is to make an introduction to the spectral graph theory. We will study some properties of graphs, namely the characteristic polynomial, the eigenvalues and the eigenvectors speci…c to matrices associated with graphs. In this dissertation, we will give more importance to the adjacency matrix and to the Laplacian matrix and we will do an analysis of some speci…c types of graphs and their respective spectra. We will study the energy of a graph and the measures of centrality associated to graphs and their inherent concepts. Two practical applications will be presented throughout the dissertation, one related to chemistry and quaternary carbon, in order to …nd out whether or not the quaternary carbon exists in the molecule under study, and another one related to the centrality measures in which the analysis of the football match “Portugal versus France”, that de…ned the European Champion of 2016 will be done, with the objective of sorting out the performances of the players on the …eld.