To see the other types of publications on this topic, follow the link: Spectral graph theory.
Dissertations / Theses on the topic 'Spectral graph theory'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Spectral graph theory.'
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.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Peng, Richard. "Algorithm Design Using Spectral Graph Theory." Research Showcase @ CMU, 2013. http://repository.cmu.edu/dissertations/277.
Full textAbstract:
Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.
In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory.
We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely.
Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.
2
Florkowski, Stanley F. "Spectral graph theory of the Hypercube." Thesis, Monterey, Calif. : Naval Postgraduate School, 2008. http://edocs.nps.edu/npspubs/scholarly/theses/2008/Dec/08Dec%5FFlorkowski.pdf.
Full textAbstract:
Thesis (M.S. in Applied Mathematics)--Naval Postgraduate School, December 2008.Thesis Advisor(s): Rasmussen, Craig W. "December 2008." Description based on title screen as viewed on January 29, 2009. Includes bibliographical references (p. 51-52). Also available in print.
3
Huang, Peng. "Spectral radius and signless Laplacian spectral radius of k-connected graphs /Huang Peng." HKBU Institutional Repository, 2016. https://repository.hkbu.edu.hk/etd_oa/373.
Full textAbstract:
The adjacency matrix of a graph is a (0, 1)-matrix indexed by the vertex set of the graph. And the signless Laplacian matrix of a graph is the sum of its adjacency matrix and its diagonal matrix of vertex degrees. The eigenvalues and the signless Laplacian eigenvalues of a graph are the eigenvalues of the adjacency matrix and the signless Laplacian matrix, respectively. These two matrices of a graph have been studied for several decades since they have been applied to many research field, such as computer science, communication network, information science and so on. In this thesis, we study k-connected graphs and focus on their spectral radius and signless Laplacian spectral radius. Firstly, we determine the graphs with maximum spectral radius among all k-connected graphs of fixed order with given diameter. As we know, when a graph is regular, its spectral radius and signless Laplacian spectral radius can easily be found. We obtain an upper bound on the signless Laplacian spectral radius of k-connected irregular graphs. Finally, we give some other results mainly related to the signless Laplacian matrix.
4
Rittenhouse, Michelle L. "Properties and Recent Applications in Spectral Graph Theory." VCU Scholars Compass, 2008. http://scholarscompass.vcu.edu/etd/1126.
Full textAbstract:
There are numerous applications of mathematics, specifically spectral graph theory, within the sciences and many other fields. This paper is an exploration of recent applications of spectral graph theory, including the fields of chemistry, biology, and graph coloring. Topics such as the isomers of alkanes, the importance of eigenvalues in protein structures, and the aid that the spectra of a graph provides when coloring a graph are covered, as well as others.The key definitions and properties of graph theory are introduced. Important aspects of graphs, such as the walks and the adjacency matrix are explored. In addition, bipartite graphs are discussed along with properties that apply strictly to bipartite graphs. The main focus is on the characteristic polynomial and the eigenvalues that it produces, because most of the applications involve specific eigenvalues. For example, if isomers are organized according to their eigenvalues, a pattern comes to light. There is a parallel between the size of the eigenvalue (in comparison to the other eigenvalues) and the maximum degree of the graph. The maximum degree of the graph tells us the most carbon atoms attached to any given carbon atom within the structure. The Laplacian matrix and many of its properties are discussed at length, including the classical Matrix Tree Theorem and Cayley's Tree Theorem. Also, an alternative approach to defining the Laplacian is explored and compared to the traditional Laplacian.
5
Morisi, Rita. "Graph–based techniques and spectral graph theory in control and machine learning." Thesis, IMT Alti Studi Lucca, 2016. http://e-theses.imtlucca.it/188/1/Morisi_phdthesis.pdf.
Full textAbstract:
Graphs are powerful data structure for representing objects
and their relationships. They are extremely useful in the study
of dynamical systems, evaluating how different agents interact
among each other and behave. An example is represented
by the consensus problem where a graph models a
set of agents that locally interact and exchange their opinions
with the aim of reaching a common opinion (consensus
state). At the same time, many learning techniques rely
on graphs exploiting their potentialities in modeling the relationships
between data and determining additional features
related to the data similarities. To study both the consensus
problem and specific machine learning applications based on
graphs, the study of the spectral properties of graphs reveals
fundamental. In the consensus problem, the convergence rate
to the consensus state strictly depends on the spectral properties
of the transition probability matrix associated to the
agents network. Whereas graphs and their spectral properties
are fundamental in determining learning algorithms able
to capture the structure of a dataset. We propose a theoretical
and numerical study of the spectral properties of a network
of agents that interact with the aim of increasing the rate of
convergence to the consensus state keeping as sparse as possible
the graph involved. Experimental results demonstrate
the capability of the proposed approach in reaching the consensus
state faster than a classical approach. We then investigate
the potentialities of graphs when applied in classification
problems. The results achieved highlight the importance
of graphs and their spectral properties handling with both
semi–supervised and supervised learning problems.
6
Johnson, Jamie L. "Software defined network monitoring scheme using spectral graph theory and phantom nodes." Thesis, Monterey, California: Naval Postgraduate School, 2014. http://hdl.handle.net/10945/43933.
Full textAbstract:
Approved for public release; distribution is unlimitedIn this thesis, we propose a new software defined network monitoring scheme that provides the controller with a method to determine network states for the purpose of updating flow rules for network control and management. Network centrality and nodal influence metrics derived from the dual basis concept of the graph theory are used to monitor changes in a network. The proposed scheme uses a phantom node and the concept of a reference node to determine changes in these metrics in order to identify disconnected, congested, underutilized, and attacked nodes. The phantom node establishes a congestion threshold in the dual basis that is used to determine changes in node health and capacity due to network traffic. Multiple phantom nodes are used to produce multiple congestion thresholds for network monitoring. A congestion estimation method is proposed to estimate a node’s capacity used when it crosses the congestion threshold. Simulations are used to validate the concept of reference node, identification of node disconnections, congestion, and attacks, and the congestion estimation method.
7
Lucas, Claire. "Trois essais sur les relations entre les invariants structuraux des graphes et le spectre du Laplacien sans signe." Phd thesis, Ecole Polytechnique X, 2013. http://pastel.archives-ouvertes.fr/pastel-00956183.
Full textAbstract:
Le spectre du Laplacien sans signe a fait l'objet de beaucoup d'attention dans la communauté scientifique ces dernières années. La principale raison est l'intuition, basée sur une étude des petits graphes et sur des propriétés valides pour des graphes de toutes tailles, que plus de graphes sont déterminés par le spectre de cette matrice que par celui de la matrice d'adjacence et du Laplacien. Les travaux présentés dans cette thèse ont apporté des éléments nouveaux sur les informations contenues dans le spectre cette matrice. D'une part, on y présente des relations entre les invariants de structure et une valeur propre du Laplacien sans signe. D'autre part, on présente des familles de graphes extrêmes pour deux de ses valeurs propres, avec et sans contraintes additionnelles sur la forme de graphe. Il se trouve que ceux-ci sont très similaires à ceux obtenus dans les mêmes conditions avec les valeurs propres de la matrice d'adjacence. Cela aboutit à la définition de familles de graphes pour lesquelles, le spectre du Laplacien sans signe ou une de ses valeurs propres, le nombre de sommets et un invariant de structure suffisent à déterminer le graphe. Ces résultats, par leur similitude avec ceux de la littérature viennent confirmer l'idée que le Laplacien sans signe détermine probablement aussi bien les graphes que la matrice d'adjacence.
8
Ghenciu, Eugen Andrei. "Dimension spectrum and graph directed Markov systems." Thesis, University of North Texas, 2006. https://digital.library.unt.edu/ark:/67531/metadc5226/.
Full textAbstract:
In this dissertation we study graph directed Markov systems (GDMS) and limit sets associated with these systems. Given a GDMS S, by the Hausdorff dimension spectrum of S we mean the set of all positive real numbers which are the Hausdorff dimension of the limit set generated by a subsystem of S. We say that S has full Hausdorff dimension spectrum (full HD spectrum), if the dimension spectrum is the interval [0, h], where h is the Hausdorff dimension of the limit set of S. We give necessary conditions for a finitely primitive conformal GDMS to have full HD spectrum. A GDMS is said to be regular if the Hausdorff dimension of its limit set is also the zero of the topological pressure function. We show that every number in the Hausdorff dimension spectrum is the Hausdorff dimension of a regular subsystem. In the particular case of a conformal iterated function system we show that the Hausdorff dimension spectrum is compact. We introduce several new systems: the nearest integer GDMS, the Gauss-like continued fraction system, and the Renyi-like continued fraction system. We prove that these systems have full HD spectrum. A special attention is given to the backward continued fraction system that we introduce and we prove that it has full HD spectrum. This system turns out to be a parabolic iterated function system and this makes the analysis more involved. Several examples have been constructed in the past of systems not having full HD spectrum. We give an example of such a system whose limit set has positive Lebesgue measure.
9
Behjat, Hamid. "Statistical Parametric Mapping of fMRI data using Spectral Graph Wavelets." Thesis, Linköpings universitet, Medicinsk informatik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-81143.
Full textAbstract:
In typical statistical parametric mapping (SPM) of fMRI data, the functional data are pre-smoothed using a Gaussian kernel to reduce noise at the cost of losing spatial specificity. Wavelet approaches have been incorporated in such analysis by enabling an efficient representation of the underlying brain activity through spatial transformation of the original, un-smoothed data; a successful framework is the wavelet-based statistical parametric mapping (WSPM) which enables integrated wavelet processing and spatial statistical testing. However, in using the conventional wavelets, the functional data are considered to lie on a regular Euclidean space, which is far from reality, since the underlying signal lies within the complex, non rectangular domain of the cerebral cortex. Thus, using wavelets that function on more complex domains such as a graph holds promise. The aim of the current project has been to integrate a recently developed spectral graph wavelet transform as an advanced transformation for fMRI brain data into the WSPM framework. We introduce the design of suitable weighted and un-weighted graphs which are defined based on the convoluted structure of the cerebral cortex. An optimal design of spatially localized spectral graph wavelet frames suitable for the designed large scale graphs is introduced. We have evaluated the proposed graph approach for fMRI analysis on both simulated as well as real data. The results show a superior performance in detecting fine structured, spatially localized activation maps compared to the use of conventional wavelets, as well as normal SPM. The approach is implemented in an SPM compatible manner, and is included as an extension to the WSPM toolbox for SPM.
10
Witt, Walter G. "Quantifying the Structure of Misfolded Proteins Using Graph Theory." Digital Commons @ East Tennessee State University, 2017. https://dc.etsu.edu/etd/3244.
Full textAbstract:
The structure of a protein molecule is highly correlated to its function. Some diseases such as cystic fibrosis are the result of a change in the structure of a protein so that this change interferes or inhibits its function. Often these changes in structure are caused by a misfolding of the protein molecule. To assist computational biologists, there is a database of proteins together with their misfolded versions, called decoys, that can be used to test the accuracy of protein structure prediction algorithms. In our work we use a nested graph model to quantify a selected set of proteins that have two single misfold decoys. The graph theoretic model used is a three tiered nested graph. Measures based on the vertex weights are calculated and we compare the quantification of the proteins with their decoys. Our method is able to separate the misfolded proteins from the correctly folded proteins.
11
Pieper, Hannah E. "Comparing Two Thickened Cycles: A Generalization of Spectral Inequalities." Oberlin College Honors Theses / OhioLINK, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1528367417905844.
Full text
12
Chen, Zhiqian. "Graph Neural Networks: Techniques and Applications." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/99848.
Full textAbstract:
Effective information analysis generally boils down to the geometry of the data represented by a graph. Typical applications include social networks, transportation networks, the spread of epidemic disease, brain's neuronal networks, gene data on biological regulatory networks, telecommunication networks, knowledge graph, which are lying on the non-Euclidean graph domain. To describe the geometric structures, graph matrices such as adjacency matrix or graph Laplacian can be employed to reveal latent patterns. This thesis focuses on the theoretical analysis of graph neural networks and the development of methods for specific applications using graph representation. Four methods are proposed, including rational neural networks for jump graph signal estimation, RemezNet for robust attribute prediction in the graph, ICNet for integrated circuit security, and CNF-Net for dynamic circuit deobfuscation.
For the first method, a recent important state-of-art method is the graph convolutional networks (GCN) nicely integrate local vertex features and graph topology in the spectral domain. However, current studies suffer from drawbacks: graph CNNs rely on Chebyshev polynomial approximation which results in oscillatory approximation at jump discontinuities since Chebyshev polynomials require degree $Omega$(poly(1/$epsilon$)) to approximate a jump signal such as $|x|$. To reduce complexity, RatioanlNet is proposed to integrate rational function and neural networks for graph node level embeddings. For the second method, we propose a method for function approximation which suffers from several drawbacks: non-robustness and infeasibility issue; neural networks are incapable of extracting analytical representation; there is no study reported to integrate the superiorities of neural network and Remez. This work proposes a novel neural network model to address the above issues. Specifically, our method utilizes the characterizations of Remez to design objective functions. To avoid the infeasibility issue and deal with the non-robustness, a set of constraints are imposed inspired by the equioscillation theorem of best rational approximation. The third method proposes an approach for circuit security. Circuit obfuscation is a recently proposed defense mechanism to protect digital integrated circuits (ICs) from reverse engineering. Estimating the deobfuscation runtime is a challenging task due to the complexity and heterogeneity of graph-structured circuit, and the unknown and sophisticated mechanisms of the attackers for deobfuscation. To address the above-mentioned challenges, this work proposes the first graph-based approach that predicts the deobfuscation runtime based on graph neural networks. The fourth method proposes a representation for dynamic size of circuit graph. By analyzing SAT attack method, a conjunctive normal form (CNF) bipartite graph is utilized to characterize the complexity of this SAT problem. To overcome the difficulty in capturing the dynamic size of the CNF graph, an energy-based kernel is proposed to aggregate dynamic features.Doctor of Philosophy
Graph data is pervasive throughout most fields, including pandemic spread network, social network, transportation roads, internet, and chemical structure. Therefore, the applications modeled by graph benefit people's everyday life, and graph mining derives insightful opinions from this complex topology. This paper investigates an emerging technique called graph neural newton (GNNs), which is designed for graph data mining. There are two primary goals of this thesis paper: (1) understanding the GNNs in theory, and (2) apply GNNs for unexplored and values real-world scenarios. For the first goal, we investigate spectral theory and approximation theory, and a unified framework is proposed to summarize most GNNs. This direction provides a possibility that existing or newly proposed works can be compared, and the actual process can be measured. Specifically, this result demonstrates that most GNNs are either an approximation for a function of graph adjacency matrix or a function of eigenvalues. Different types of approximations are analyzed in terms of physical meaning, and the advantages and disadvantages are offered. Beyond that, we proposed a new optimization for a highly accurate but low efficient approximation. Evaluation of synthetic data proves its theoretical power, and the tests on two transportation networks show its potentials in real-world graphs. For the second goal, the circuit is selected as a novel application since it is crucial, but there are few works. Specifically, we focus on a security problem, a high-value real-world problem in industry companies such as Nvidia, Apple, AMD, etc. This problem is defined as a circuit graph as apply GNN to learn the representation regarding the prediction target such as attach runtime. Experiment on several benchmark circuits shows its superiority on effectiveness and efficacy compared with competitive baselines. This paper provides exploration in theory and application with GNNs, which shows a promising direction for graph mining tasks. Its potentials also provide a wide range of innovations in graph-based problems.
13
Gkantsidis, Christos. "Algorithmic performance of large-scale distributed networks a spectral method approach /." Available online, Georgia Institute of Technology, 2006, 2006. http://etd.gatech.edu/theses/available/etd-12062005-141254/.
Full textAbstract:
Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2006.Mihail, Milena, Committee Chair ; Ammar, Mostafa, Committee Member ; Dovrolis, Constantinos, Committee Member ; Faloutsos, Michalis, Committee Member ; Zegura, Ellen, Committee Member.
14
Casaca, Wallace Correa de Oliveira. "Graph Laplacian for spectral clustering and seeded image segmentation." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-24062015-112215/.
Full textAbstract:
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, the image partitioning can be improved by changing the graph weights by sketching interactively. Visual and numerical evaluation were conducted against representative spectral-based segmentation techniques using boundary and partition quality measures in the well-known BSDS dataset. Unlike most existing seed-based methods that rely on complex mathematical formulations that typically do not guarantee unique solution for the segmentation problem while still being prone to be trapped in local minima, our segmentation approach is mathematically simple to formulate, easy-to-implement, and it guarantees to produce a unique solution. Moreover, the formulation holds an anisotropic behavior, that is, pixels sharing similar attributes are preserved closer to each other while big discontinuities are naturally imposed on the boundary between image regions, thus ensuring better fitting on object boundaries. We show that the proposed approach significantly outperforms competing techniques both quantitatively as well as qualitatively, using the classical GrabCut dataset from Microsoft as a benchmark. While most of this research concentrates on the particular problem of segmenting an image, we also develop two new techniques to address the problem of image inpainting and photo colorization. Both methods couple the developed segmentation tools with other computer vision approaches in order to operate properly.Segmentar uma image é visto nos dias de hoje como uma prerrogativa para melhorar a capacidade de sistemas de computador para realizar tarefas complexas de natureza cognitiva tais como detecção de objetos, reconhecimento de padrões e monitoramento de alvos. Esta pesquisa de doutorado visa estudar dois temas de fundamental importância no contexto de segmentação de imagens: clusterização espectral e segmentação interativa de imagens. Foram propostos dois novos algoritmos de segmentação dentro das linhas supracitadas, os quais se baseiam em operadores do Laplaciano, teoria espectral de grafos e na minimização de funcionais de energia. A eficácia de ambos os algoritmos pode ser constatada através de avaliações visuais das segmentações originadas, como também através de medidas quantitativas computadas com base nos resultados obtidos por técnicas do estado-da-arte em segmentação de imagens. Nosso primeiro algoritmo de segmentação, o qual ´e baseado na teoria espectral de grafos, combina técnicas de decomposição de imagens e medidas de similaridade em grafos em uma única e robusta ferramenta computacional. Primeiramente, um método de decomposição de imagens é aplicado para dividir a imagem alvo em duas componentes: textura e cartoon. Em seguida, um grafo de afinidade é gerado e pesos são atribuídos às suas arestas de acordo com uma função escalar proveniente de um operador de produto interno. Com base no grafo de afinidade, a imagem é então subdividida por meio do processo de corte espectral. Além disso, o resultado da segmentação pode ser refinado de forma interativa, mudando-se, desta forma, os pesos do grafo base. Experimentos visuais e numéricos foram conduzidos tomando-se por base métodos representativos do estado-da-arte e a clássica base de dados BSDS a fim de averiguar a eficiência da metodologia proposta. Ao contrário de grande parte dos métodos existentes de segmentação interativa, os quais são modelados por formulações matemáticas complexas que normalmente não garantem solução única para o problema de segmentação, nossa segunda metodologia aqui proposta é matematicamente simples de ser interpretada, fácil de implementar e ainda garante unicidade de solução. Além disso, o método proposto possui um comportamento anisotrópico, ou seja, pixels semelhantes são preservados mais próximos uns dos outros enquanto descontinuidades bruscas são impostas entre regiões da imagem onde as bordas são mais salientes. Como no caso anterior, foram realizadas diversas avaliações qualitativas e quantitativas envolvendo nossa técnica e métodos do estado-da-arte, tomando-se como referência a base de dados GrabCut da Microsoft. Enquanto a maior parte desta pesquisa de doutorado concentra-se no problema específico de segmentar imagens, como conteúdo complementar de pesquisa foram propostas duas novas técnicas para tratar o problema de retoque digital e colorização de imagens.
15
Kang, U. "Mining Tera-Scale Graphs: Theory, Engineering and Discoveries." Research Showcase @ CMU, 2012. http://repository.cmu.edu/dissertations/160.
Full textAbstract:
How do we find patterns and anomalies, on graphs with billions of nodes and edges, which do not fit in memory? How to use parallelism for such Tera- or Peta-scale graphs? In this thesis, we propose PEGASUS, a large scale graph mining system implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. PEGASUS includes algorithms which help us spot patterns and anomalous behaviors in large graphs.
PEGASUS enables the structure analysis on large graphs. We unify many different structure analysis algorithms, including the analysis on connected components, PageRank, and radius/diameter, into a general primitive called GIM-V. GIM-V is highly optimized, achieving good scale-up on the number of edges and available machines. We discover surprising patterns using GIM-V, including the 7-degrees of separation in one of the largest publicly available Web graphs, with 7 billion edges.
PEGASUS also enables the inference and the spectral analysis on large graphs. We design an efficient distributed belief propagation algorithm which infer the states of unlabeled nodes given a set of labeled nodes. We also develop an eigensolver for computing top k eigenvalues and eigenvectors of the adjacency matrices of very large graphs. We use the eigensolver to discover anomalous adult advertisers in the who-follows-whom Twitter graph with 3 billion edges. In addition, we develop an efficient tensor decomposition algorithm and use it to analyze a large knowledge base tensor.
Finally, PEGASUS allows the management of large graphs. We propose efficient graph storage and indexing methods to answer graph mining queries quickly. We also develop an edge layout algorithm for better compressing graphs.
16
Masum, Mohammad. "Vertex Weighted Spectral Clustering." Digital Commons @ East Tennessee State University, 2017. https://dc.etsu.edu/etd/3266.
Full textAbstract:
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.
17
Chakeri, Alireza. "Scalable Unsupervised Learning with Game Theory." Scholar Commons, 2017. http://scholarcommons.usf.edu/etd/6616.
Full textAbstract:
Recently dominant sets, a generalization of the notion of the maximal clique to edge-weighted graphs, have proven to be an effective tool for unsupervised learning and have found applications in different domains. Although, they were initially established using optimization and graph theory concepts, recent work has shown fascinating connections with evolutionary game theory, that leads to the clustering game framework. However, considering size of today's data sets, existing methods need to be modified in order to handle massive data. Hence, in this research work, first we address the limitations of the clustering game framework for large data sets theoretically. We propose a new important question for the clustering community ``How can a cluster of a subset of a dataset be a cluster of the entire dataset?''. We show that, this problem is a coNP-hard problem in a clustering game framework. Thus, we modify the definition of a cluster from a stable concept to a non-stable but optimal one (Nash equilibrium). By experiments we show that this relaxation does not change the qualities of the clusters practically.
Following this alteration and the fact that equilibriums are generally compact subsets of vertices, we design an effective strategy to find equilibriums representing well distributed clusters. After finding such equilibriums, a linear game theoretic relation is proposed to assign vertices to the clusters and partition the graph. However, the method inherits a space complexity issue, that is the similarities between every pair of objects are required which proves practically intractable for large data sets. To overcome this limitation, after establishing necessary theoretical tools for a special type of graphs that we call vertex-repeated graphs, we propose the scalable clustering game framework. This approach divides a data set into disjoint tractable size chunks. Then, the exact clusters of the entire data are approximated by the clusters of the chunks. In fact, the exact equilibriums of the entire graph is approximated by the equilibriums of the subsets of the graph. We show theorems that enable significantly improved time complexity for the model. The applications include, but are not limited to, the maximum weight clique problem, large data clustering and image segmentation. Experiments have been done on random graphs and the DIMACS benchmark for the maximum weight clique problem and on magnetic resonance images (MRI) of the human brain consisting of about 4 million examples for large data clustering. Also, on the Berkeley Segmentation Dataset, the proposed method achieves results comparable to the state of the art, providing a parallel framework for image segmentation and without any training phase. The results show the effectiveness and efficiency of our approach.
In another part of this research work, we generalize the clustering game method to cluster uncertain data where the similarities between the data points are not exactly known, that leads to the uncertain clustering game framework. Here, contrary to the ensemble clustering approaches, where the results of different similarity matrices are combined, we focus on the average utilities of an uncertain game. We show that the game theoretical solutions provide stable clusters even in the presence of severe uncertainties. In addition, based on this framework, we propose a novel concept in uncertain data clustering so that every subset of objects can have a ''cluster degree''. Extensive experiments on real world data sets, as well as on the Berkeley image segmentation dataset, confirm the performance of the proposed method.
And finally, instead of dividing a graph into chunks to make the clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs. The rand index is always at about 0.9 to 0.99 in our experiments even when lots of sparsification is done.
18
Pham, Hong Nhung. "Graph-based registration for biomedical images." Thesis, Poitiers, 2019. http://www.theses.fr/2019POIT2258/document.
Full textAbstract:
Le contexte de cette thèse est le recalage d'images endomicroscopiques. Le microendoscope multiphotonique fournit différentes trajectoires de balayage que nous considérons dans ce travail. Nous proposons d'abord une méthode de recalage non rigide dont l'estimation du mouvement est transformée en un problème d'appariement d'attributs dans le cadre des Log-Demons et d'ondelettes sur graphes. Nous étudions les ondelettes de graphe spectral (SGW) pour capturer les formes des images, en effet, la représentation des données sur les graphes est plus adaptée aux données avec des structures complexes. Nos expériences sur des images endomicroscopiques montrent que cette méthode est supérieure aux techniques de recalage d'images non rigides existantes. Nous proposons ensuite une nouvelle stratégie de recalage d'images pour les images endomicroscopiques acquises sur des grilles irrégulières. La transformée en ondelettes sur graphe est flexible et peut être appliquée à différents types de données, quelles que soient la densité de points et la complexité de la structure de données. Nous montrons également comment le cadre des Log-Demons peut être adapté à l'optimisation de la fonction objective définie pour les images acquises avec un échantillonnage irrégulierThe context of this thesis is the image registration for endomicroscopic images. Multiphoton microendoscope provides different scanning trajectories which are considered in this work. First we propose a nonrigid registration method whose motion estimation is cast into a feature matching problem under the Log-Demons framework using Graph Wavelets. We investigate the Spectral Graph Wavelets (SGWs) to capture the shape feature of the images. The data representation on graphs is more adapted to data with complex structures. Our experiments on endomicroscopic images show that this method outperforms the existing nonrigid image registration techniques. We then propose a novel image registration strategy for endomicroscopic images acquired on irregular grids. The Graph Wavelet transform is flexible to apply on different types of data regardless of the data point densities and how complex the data structure is. We also show how the Log-Demons framework can be adapted to the optimization of the objective function defined for images with an irregular sampling
19
Hamidouche, Mounia. "Analyse spectrale de graphes géométriques aléatoires." Thesis, Université Côte d'Azur, 2020. http://www.theses.fr/2020COAZ4019.
Full textAbstract:
Nous étudions le graphe géométrique aléatoire (GGA) afin d'aborder des problèmes clés dans les réseaux complexes. Un GAA est construit en distribuant uniformément n nœuds sur un tore de dimension d et en connectant deux nœuds si leur distance ne dépasse pas un seuil. Trois régimes pour GGA présentent un intérêt particulier. Le régime de connectivité dans lequel le degré moyen d'un nœud a_n croît de manière logarithmique avec n ou plus vite. Le régime dense dans lequel a_n est linéaire avec n. Le régime thermodynamique dans lequel a_n est une constante. On étudie le spectre du Laplacien normalisé (LN) et régularisé du GGA dans les trois régimes. Lorsque d est fixe et n tend vers l'infini, on prouve que la distribution spectrale limite (DSL) du LN converge vers la distribution de Dirac concentrée en 1 dans le régime de connectivité. Dans le régime thermodynamique, on propose une approximation pour DSL du LN régularisé et on fournit une borne d'erreur sur l'approximation. On montre que DSL du LN régularisé d'un GGA est approximée par DSL d'un graphe géométrique déterministe (GGD). On étudie DSL de la matrice d'adjacence d'un GGA dans le régime de connectivité. Sous des conditions sur a_n, on montre que DSL de la matrice d'adjacence du GGD est une bonne approximation du GGA pour n large. On détermine la dimension spectrale (DS) qui caractérise la distribution du temps de retour d'une marche aléatoire sur le GGA. On montre que DS dépend de la densité spectrale de LN au voisinage des valeurs propres minimales. On prouve que la densité spectrale au voisinage de la valeur minimale suit une loi de puissance et que DS du GGA est approximé par d dans le régime thermodynamiqueWe study random geometric graphs (RGGs) to address key problems in complex networks. An RGG is constructed by uniformly distributing n nodes on a torus of dimension d and connecting two nodes if their distance does not exceed a certain threshold. Three regimes for RGGs are of particular interest. The connectivity regime in which the average vertex degree a_n grows logarithmically with n or faster. The dense regime in which a_n is linear with n. The thermodynamic regime in which a_n is a constant. We study the spectrum of RGGs normalized Laplacian (LN) and its regularized version in the three regimes. When d is fixed and n tends to infinity we prove that the limiting spectral distribution (LSD) of LN converges to Dirac distribution at 1 in the connectivity regime. In the thermodynamic regime we propose an approximation for LSD of the regularized NL and we provide an error bound on the approximation. We show that LSD of the regularized LN of an RGG is approximated by LSD of the regularized LN of a deterministic geometric graph (DGG). We study LSD of RGGs adjacency matrix in the connectivity regime. Under some conditions on a_n we show that LSD of DGGs adjacency matrix is a good approximation for LSD of RGGs for n large. We determine the spectral dimension (SD) that characterizes the return time distribution of a random walk on RGGs. We show that SD depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the neighborhood of the minimum eigenvalues. Based on the analytical eigenvalues of the normalized Laplacian we show that ED in a neighborhood of the minimum value follows a power-law tail and we approximate SD of RGGs by d in the thermodynamic regime
20
Gkantsidis, Christos. "Algorithmic performance of large-scale distributed networks: A spectral method approach." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/10420.
Full textAbstract:
Complex networks like the Internet, peer-to-peer systems, and emerging sensor and ad-hoc networks are large distributed decentralized communication systems arising repeatedly in today's technology. In such networks it is critical to characterize network performance as the size of the network scales. The focus of my work is to relate basic network performance metrics to structural characteristics of underlying network topologies, and to develop protocols that reinforce and exploit desired structural characteristics. For the case of the Internet at the Autonomous System level, we relate the graph theoretic notions of conductance and spectrum to network clustering and network congestion. In particular, we show how spectral analysis can identify clusters, and how the presence of clusters affects congestion. This is important for network prediction and network simulation. For the case of peer-to-peer networks we relate conductance and spectral gap to the fundamental questions of searching and topology maintenance. We propose new protocols for maintaining peer-to-peer networks with good conductance and low network overhead. We compare the performance of the traditional method of search by flooding to searching by random walks. We isolate cases of practical interest, such as clustered and dynamic network topologies, where the latter have superior performance. The improvement in the performance can be directly quantified in terms of the conductance of the underlying topology. We introduce further hybrid search schemes, of which flooding and random walks are special instances, which aim to improve the performance of searching by using locally maintained information about the network topology.
21
Parra, Vogel Daniel Alejandro. "Théorie spectrale et de la diffusion pour les réseaux cristallins." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1001/document.
Full textAbstract:
Dans cette thèse les théories spectrale et de la diffusion sur des graphes périodiques sont investigué. Le chapitre 1 présente des résultats de préservation de la nature fine du spectre pour des opérateurs de Schrödinger perturbés dans le cadre de cristaux topologiques perturbés. Le chapitre 2 étend ses résultats à des opérateurs du première ordre connu sous le nom de opérateurs de Gauss-Bonnet discrets. Finalement, le chapitre 3 présente des résultats de continuité de composantes spectrales pour des familles de opérateurs de Schrödinger magnétiques sur Z^dIn this thesis we investigate the spectral and scattering theories for crystal lattices. In chapter one we present results concerning the preservation of the nature of the spectrum for perturbed Schrödinger operators acting con perturbed topological crystals. In Chapter 2 we extend this results to some first order operators knowns as discrete Gauss-Bonnet operators. Finally, in chapter 3 we give some results dealing with the continuity of the spectrum for a family of magnetic Schrödinger operators acting on Z^d
22
Farina, Sofia. "A physical interpretation of network laplacian: role of perturbations and masses." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16345/.
Full textAbstract:
Il presente elaborato si propone di studiare il laplaciano associato ad un network, oggetto di interesse sia perchè dalla sua analisi spettrale è possibile ricavare delle tecniche di ricostruzione e rappresentazione della rete efficienti e al contempo semplici da implementare, ma anche per la sua possibile intepretazione fisica.
Il lavoro si struttura in due sezioni: la prima, riguardante l'analisi numerica dello spettro del laplaciano di un network con particolari proprietà di simmetria e regolarità anche in seguito alla sua perturbazione in termini di rimozone casuale di nodi e di link; la seconda incentrata su un suo modello intepretativo in chiave fisica che ci permette di ragionare sul reticolo immaginandolo come una serie di masse collegate tra loro da molle, dotate di una lunghezza caratteristica e di una costante elastica, e di vedere la sua rappresentazione come la visualizzazione dello stato di equilibrio raggiunto da questo sistema.
23
Kruzick, Stephen M. "Optimal Graph Filter Design for Large-Scale Random Networks." Research Showcase @ CMU, 2018. http://repository.cmu.edu/dissertations/1165.
Full textAbstract:
Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.
24
Wappler, Markus. "On Graph Embeddings and a new Minor Monotone Graph Parameter associated with the Algebraic Connectivity of a Graph." Doctoral thesis, Universitätsbibliothek Chemnitz, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-115518.
Full textAbstract:
We consider the problem of maximizing the second smallest eigenvalue of the weighted Laplacian of a (simple) graph over all nonnegative edge weightings with bounded total weight.
We generalize this problem by introducing node significances and edge lengths.
We give a formulation of this generalized problem as a semidefinite program.
The dual program can be equivalently written as embedding problem. This is fifinding an embedding of the n nodes of the graph in n-space so that their barycenter is at the origin, the distance between adjacent nodes is bounded by the respective edge length, and the embedded nodes are spread as much as possible. (The sum of the squared norms is maximized.)
We proof the following necessary condition for optimal embeddings. For any separator of the graph at least one of the components fulfills the following property: Each straight-line segment between the origin and an embedded node of the component intersects the convex hull of the embedded nodes of the separator.
There exists always an optimal embedding of the graph whose dimension is bounded by the tree-width of the graph plus one.
We defifine the rotational dimension of a graph. This is the minimal dimension k such that for all choices of the node significances and edge lengths an optimal embedding of the graph can be found in k-space.
The rotational dimension of a graph is a minor monotone graph parameter.
We characterize the graphs with rotational dimension up to two.
25
Erdem, Ozge. "Computation And Analysis Of Spectra Of Large Undirected Networks." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612233/index.pdf.
Full textAbstract:
Many interacting complex systems in biology, in physics, in technology and social systems, can be represented in a form of large networks. These large networks are mathematically represented by graphs. A graph is represented usually by the adjacency or the Laplacian matrix. Important features of the underlying structure and dynamics of them
can be extracted from the analysis of the spectrum of the graphs. Spectral analysis of the so called normalized Laplacian of large networks became popular in the recent years. The Laplacian matrices of the empirical networks are in form of unstructured large sparse matrices. The aim of this thesis is the comparison of different eigenvalue solvers for large sparse symmetric matrices which arise from the graph theoretical epresentation of undirected networks. The spectrum of the
normalized Laplacian is in the interval [0 2] and the multiplicity of the eigenvalue 1 plays a particularly important role for the network analysis. Moreover, the spectral analysis of protein-protein interaction networks has revealed that these networks have a different distribution type than other model networks such as scale free networks. In this respect, the eigenvalue solvers implementing the well-known implicitly
restarted Arnoldi method, Lanczos method, Krylov-Schur and Jacobi Davidson methods are investigated. They exist as MATLAB routines and are included in some freely available packages. The performances of different eigenvalue solvers PEIG, AHBEIGS, IRBLEIGS, EIGIFP, LANEIG, JDQR, JDCG in MATLAB and the library SLEPc in C++ were tested for matrices of size between 100-13000 and are compared in
terms of accuracy and computing time. The accuracy of the eigenvalue solvers are validated for the Paley graphs with known eigenvalues and are compared for large empirical networks using the residual plots and spectral density plots are computed.
26
Reiß, Susanna. "Optimizing Extremal Eigenvalues of Weighted Graph Laplacians and Associated Graph Realizations." Doctoral thesis, Universitätsbibliothek Chemnitz, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-93599.
Full textAbstract:
This thesis deals with optimizing extremal eigenvalues of weighted graph Laplacian matrices. In general, the Laplacian matrix of a (weighted) graph is of particular importance in spectral graph theory and combinatorial optimization (e.g., graph partition like max-cut and graph bipartition). Especially the pioneering work of M. Fiedler investigates extremal eigenvalues of weighted graph Laplacians and provides close connections to the node- and edge-connectivity of a graph. Motivated by Fiedler, Göring et al. were interested in further connections between structural properties of the graph and the eigenspace of the second smallest eigenvalue of weighted graph Laplacians using a semidefinite optimization approach.
By redistributing the edge weights of a graph, the following three optimization problems are studied in this thesis: maximizing the second smallest eigenvalue (based on the mentioned work of Göring et al.), minimizing the maximum eigenvalue and minimizing the difference of maximum and second smallest eigenvalue of the weighted Laplacian. In all three problems a semidefinite optimization formulation allows to interpret the corresponding semidefinite dual as a graph realization problem. That is, to each node of the graph a vector in the Euclidean space is assigned, fulfilling some constraints depending on the considered problem.
Optimal realizations are investigated and connections to the eigenspaces of corresponding optimized eigenvalues are established.
Furthermore, optimal realizations are closely linked to the separator structure of the graph. Depending on this structure, on the one hand folding properties of optimal realizations are characterized and on the other hand the existence of optimal realizations of bounded dimension is proven. The general bounds depend on the tree-width of the graph. In the case of minimizing the maximum eigenvalue, an important family of graphs are bipartite graphs, as an optimal one-dimensional realization may be constructed.
Taking the symmetry of the graph into account, a particular optimal edge weighting exists.
Considering the coupled problem, i.e., minimizing the difference of maximum and second smallest eigenvalue and the single problems, i.e., minimizing the maximum and maximizing the second smallest eigenvalue, connections between the feasible (optimal) sets are established.
27
Sariaydin, Ayse. "Computation And Analysis Of Spectra Of Large Networks With Directed Graphs." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612249/index.pdf.
Full textAbstract:
Analysis of large networks in biology, science, technology and social systems have become very popular recently. These networks are mathematically represented as graphs. The task is then to extract relevant qualitative information about the empirical networks from the analysis of these graphs.
It was found that a graph can be conveniently represented by the spectrum of a suitable difference operator, the normalized graph Laplacian, which underlies diffusions and random walks on graphs. When applied to large networks, this requires computation of the spectrum of large matrices. The normalized Laplacian matrices representing large networks are usually sparse and unstructured.
The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetric large normalized Laplacian matrices describing directed graphs of empirical networks. The methods include several Krylov subspace algorithms like implicitly restarted Arnoldi method, Krylov-Schur method and Jacobi-Davidson methods which are freely available as standard packages written in MATLAB or SLEPc, in the library written C++.
The normalized graph Laplacian as employed here is normalized such that its spectrum is confined to the range [0, 2]. The eigenvalue distribution plays an important role in network analysis. The numerical task is then to determine the whole spectrum with appropriate eigenvalue solvers. A comparison of the existing eigenvalue solvers is done with Paley digraphs with known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computing
the residuals.
28
Shiping, Liu. "Synthetic notions of curvature and applications in graph theory." Doctoral thesis, Universitätsbibliothek Leipzig, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-102197.
Full textAbstract:
The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs.
In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz.
Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\'s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality.
The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\'s open problem in the finite graph setting.
In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges.
Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen.
We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1.
With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.
29
Goddet, Étienne. "Analyse spectrale et surveillance des réseaux maillés de retour de courant pour l'aéronautique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAT099/document.
Full textAbstract:
Depuis plusieurs années, l’aéronautique est confrontée à une mutation majeure due à l’émergence des matériaux composites. Ce changement, justifié par les excellentes propriétés mécaniques des matériaux composites et un gain de masse important, implique une révision complète des réseaux de retour de courant. Pour faciliter cette révision, la thèse propose de lier au travers de l’analyse spectrale des graphes les performances des réseaux électriques avec leur topologie. Deux objectifs couplés sont étudiés : un dimensionnement topologique visant un bon compromis masse/robustesse et une stratégie de surveillance de ces réseauxThe principles of the electrical system design in future aircrafts have to be reconsidered due to the emergence of new composite materials. The use of these materials for the aircraft structure has indeed implied a complete revision of on-board current return path networks. To facilitate this revision, it is proposed to link through the spectral graph analysis the performances of electrical networks with their topology. The aim of this thesis is to give topological drivers that could help the aeronautical engineers during the design process and then to propose a monitoring methodology
30
Behmo, Régis. "Visual feature graphs and image recognition." Phd thesis, Ecole Centrale Paris, 2010. http://tel.archives-ouvertes.fr/tel-00545419.
Full textAbstract:
La problèmatique dont nous nous occupons dans cette thèse est la classification automatique d'images bidimensionnelles, ainsi que la détection d'objets génériques dans des images. Les avancées de ce champ de recherche contribuent à l'élaboration de systèmes intelligents, tels que des robots autonomes et la création d'un web sémantique. Dans ce contexte, la conception de représentations d'images et de classificateurs appropriés constituent des problèmes ambitieux. Notre travail de recherche fournit des solutions à ces deux problèmes, que sont la représentation et la classification d'images. Afin de générer notre représentation d'image, nous extrayons des attributs visuels de l'image et construisons une structure de graphe basée sur les propriétés liées au relations de proximités entre les points d'intérêt associés. Nous montrons que certaines propriétés spectrales de ces graphes constituent de bons invariants aux classes de transformations géométriques rigides. Notre représentation d'image est basée sur ces propriétés. Les résultats expérimentaux démontrent que cette représentation constitue une amélioration par rapport à d'autres représentations similaires, mais qui n'intègrent pas les informations liées à l'organisation spatiale des points d'intérêt. Cependant, un inconvénient de cette méthode est qu'elle fait appel à une quantification (avec pertes) de l'espace des attributs visuels afin d'être combinée avec un classificateur Support Vecteur Machine (SVM) efficace. Nous résolvons ce problème en créant un nouveau classificateur, basé sur la distance au plus proche voisin, et qui permet la classification d'objets assimilés à des ensembles de points. La linéarité de ce classificateur nous permet également de faire de la détection d'objet, en plus de la classification d'images. Une autre propriété intéressante de ce classificateur est sa capacité à combiner différents types d'attributs visuels de manière optimale. Nous utilisons cette propriété pour formuler le problème de classification de graphes de manière différente. Les expériences, menées sur une grande variété de jeux de données, montrent les bénéfices quantitatifs de notre approche.
31
Braida, Arthur. "Analog Quantum Computing for NP-Hard Combinatorial Graph Problems." Electronic Thesis or Diss., Orléans, 2024. http://www.theses.fr/2024ORLE1017.
Full textAbstract:
L'objectif principal de cette thèse est de fournir un éclairage théorique de la complexité du calcul quantique en temps continu (QA et AQC), de la compréhension du phénomène physique (AC) qui conduit à l'échec de l'AQC jusqu'à des preuves de performance de QA en temps court et constant. Pour atteindre cet objectif, nous utilisons différents outils analytiques empruntés à la physique théorique, comme l'analyse perturbative des systèmes quantiques et la borne de Lieb-Robinson sur la vitesse de corrélation dans les systèmes quantiques. La manipulation des graphes et la théorie spectrale des graphes sont nécessaires pour obtenir des résultats sur des classes spécifiques de graphes. Nous avons également introduit une nouvelle version paramétrée du QA standard afin d'affiner l'analyse.Tout d'abord, nous souhaitons obtenir une définition mathématique d'un AC afin d'en faciliter la compréhension lors de l'étude d'une classe spécifique de graphes sur lesquels nous souhaitons résoudre le problème de Maximum Cut. En plus de l'appui analytique que nous développons, nous apportons une étude numérique pour justifier la nature plus générale de notre définition par rapport à la précédente. Grâce à une analyse perturbative, nous parvenons à montrer que sur les graphes bipartis, un gap de fermeture exponentielle peut apparaître si le graphe est suffisamment irrégulier. Notre nouvelle définition de l'AC nous permet de remettre en question l'efficacité de l'AQC pour le résoudre malgré le temps d'exécution exponentiellement long que le théorème adiabatique impose pour garantir la solution optimale. Le deuxième axe est consacré à la performance du QA en temps constant court. Bien que le QA soit intrinsèquement non-local, la borne de LR nous permet de l'approximer avec une évolution locale. Une première approche est utilisée pour développer la méthode et montrer la non trivialité du résultat, c'est-à-dire au-dessus du choix aléatoire. Ensuite, nous définissons une notion d'analyse locale en exprimant le ratio d'approximation avec la seule connaissance de la structure locale. Une borne LR fine et adaptative est développée, nous permettant de trouver une valeur numérique du ratio d'approximation surpassant les algorithmes quantiques et classiques (strictement) locaux. Tous ces travaux de recherche ont été poursuivis entre l'équipe QuantumLab d'Eviden et l'équipe Graphes, Algorithmes et Modèles de Calcul (GAMoC) du Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). Le travail numérique a été implémenté en utilisant le langage de programmation Julia ainsi que Python avec le logiciel QAPTIVA d'Eviden pour simuler efficacement l'équation de SchrödingerThe main objective of this thesis is to provide theoretical insight into the computational complexity of continuous-time quantum computing (QA and AQC), from understanding the physical phenomenon (AC) that leads to AQC failure to proving short constant-time QA efficiency. To achieve this goal, we use different analytical tools borrowed from theoretical physics like perturbative analysis of quantum systems and the Lieb-Robinson bound on the velocity of correlation in quantum systems. Graph manipulation and spectral graph theory are necessary to derive results on a specific class of graph. We also introduced a new parametrized version of the standard QA to tighten the analysis. First, we want to obtain a mathematical definition of an AC to be easier to grasp when studying a specific class of graph on which we want to solve the Maximum Cut problem. We support our new definition with a proven theorem that links it to exponentially small minimum gap and numerical evidence is brought to justify its more general nature compared to the previous one. With a perturbative analysis, we manage to show that on bipartite graphs, exponentially closing gap can arise if the graph is irregular enough. Our new definition of AC allows us to question the efficiency of AQC to solve it despite the exponentially long runtime the adiabatic theorem imposes to guarantee the optimal solution. The second axis is dedicated to the performance of QA at short constant times. Even though QA is inherently non-local, the LR bound allows us to approximate it with a local evolution. A first approach is used to develop the method and to show the non-triviality of the result, i.e. above random guess. Then we define a notion of local analysis by expressing the approximation ratio with only knowledge of the local structure. A tight and adaptive LR bound is developed allowing us to find a numerical value outperforming quantum and classical (strictly) local algorithms. All this research work has been pursued between Eviden QuantumLab team and the Graphes, Algorithmes et Modèles de Calcul (GAMoC) team at the Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). The numerical work has been implemented using Julia programming Language as well as Python with the QAPTIVA software of Eviden to efficiently simulate the Schrödinger equation
32
Samavat, Reza. "Mean Eigenvalue Counting Function Bound for Laplacians on Random Networks." Doctoral thesis, Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-159578.
Full textAbstract:
Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.
33
Raak, Fredrik. "Investigation of Power Grid Islanding Based on Nonlinear Koopman Modes." Thesis, KTH, Elektriska energisystem, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-136834.
Full textAbstract:
To view the electricity supply in our society as just sockets mountedin our walls with a constant voltage output is far from the truth. Inreality, the power system supplying the electricity or the grid, is themost complex man-made dynamical system there is. It demands severecontrol and safety measures to ensure a reliable supply of electric power.Throughout the world, incidents of widespread power grid failures havebeen continuously reported. The state where electricity delivery to customersis terminated by a disturbance is called a blackout. From a stateof seemingly stable operating conditions, the grid can fast derail intoan uncontrollable state due to cascading failures. Transmission linesbecome automatically disconnected due to power flow redirections andparts of the grid become isolated and islands are formed. An islandedsub-grid incapable of maintaining safe operation conditions experiencesa blackout. A widespread blackout is a rare, but an extremely costlyand hazardous event for society.During recent years, many methods to prevent these kinds of eventshave been suggested. Controlled islanding has been a commonly suggestedstrategy to save the entire grid or parts of the grid from a blackout.Controlled islanding is a strategy of emergency control of a powergrid, in which the grid is intentionally split into a set of islanded subgridsfor avoiding an entire collapse. The key point in the strategy is todetermine appropriate separation boundaries, i.e. the set of transmissionlines separating the grid into two or more isolated parts.The power grid exhibits highly nonlinear response in the case oflarge failures. Therefore, this thesis proposes a new controlled islandingmethod for power grids based on the nonlinear Koopman Mode Analysis(KMA). The KMA is a new analyzing technique of nonlinear dynamicsbased on the so-called Koopman operator. Based on sampled data followinga disturbance, KMA is used to identify suitable partitions of thegrid.The KMA-based islanding method is numerically investigated withtwo well-known test systems proposed by the Institute of Electrical andElectronics Engineers (IEEE). By simulations of controlled islanding inthe test system, it is demonstrated that the grid’s response following afault can be improved with the proposed method.The proposed method is compared to a method of partitioning powergrids based on spectral graph theory which captures the structural propertiesof a network. It is shown that the intrinsic structural propertiesof a grid characterized by spectral graph theory are also captured by theKMA. This is shown both by numerical simulations and a theoreticalanalysis.
34
Balestrini, Robinson Santiago. "A modeling process to understand complex system architectures." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29621.
Full textAbstract:
Thesis (Ph.D)--Aerospace Engineering, Georgia Institute of Technology, 2010.Committee Chair: Mavris, Dimitri; Committee Member: Bishop, Carlee; Committee Member: German, Brian; Committee Member: Nixon, Janel; Committee Member: Schrage, Daniel. Part of the SMARTech Electronic Thesis and Dissertation Collection.
35
Curado, Manuel. "Structural Similarity: Applications to Object Recognition and Clustering." Doctoral thesis, Universidad de Alicante, 2018. http://hdl.handle.net/10045/98110.
Full textAbstract:
In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD.Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)
36
Amaro, Bruno Dias 1984. "A soma dos maiores autovalores da matriz laplaciana sem sinal em famílias de grafos." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306808.
Full textAbstract:
Orientadores: Carlile Campos Lavor, Leonardo Silva de LimaTese (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
37
Oliveira, Alessandro Bof de. "Descritor de forma 2D baseado em redes complexas e teoria espectral de grafos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2016. http://hdl.handle.net/10183/134397.
Full textAbstract:
A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada.The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.
38
Kadavankandy, Arun. "L’analyse spectrale des graphes aléatoires et son application au groupement et l’échantillonnage." Thesis, Université Côte d'Azur (ComUE), 2017. http://www.theses.fr/2017AZUR4059/document.
Full textAbstract:
Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communautéIn this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure
39
Akkouche, Sofiane. "Sur la theorie spectrale des opérateurs de Schrödinger discrets." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14098/document.
Full textAbstract:
Cette thèse traite de la théorie spectrale des opérateurs de Schrödinger discrets H(λ) := - Δ + b sur Zd et plus généralement sur des graphes pondérés infinis. Plus précisément, nous étudions le comportement des fonctions spectrales qui représentent les bornes du spectre de ces opérateurs. Un des principaux résultats est l'obtention d'une condition nécessaire et suffisante sur le potentiel b pour que le bas du spectre soit strictement positif. L'étude du haut du spectre est également considérée.Nous étudions tout d'abord ces questions pour les opérateurs de Schrödinger discrets sur Zd. La régularité de cet espace permet alors d'obtenir des résultats spécifiques dans ce cas particulier. Nous généralisons ensuite nos travaux au cas des graphes infinis pondérés. Les techniques développées dans ce cadre nous permettent également d'étudier le comportement asymptotique du bas du spectre pour les grandes valeurs de λThis thesis deals with the spectral theory of discrete Schrödinger operators H(λ) := - Δ + b on Zd and more generally on in#nite weighted graphs. Precisely, we study the behavior of the spectral functions which represent the spectral bounds of these operators. One of the main results is the obtention of a necessary and sufficient condition on the potential b such that the bottom of the spectrum is stricly positive.The study of the top of the spectrum is also treated.We first study these questions for discrete Schrödinger operators on Zd. The regularity of this space provides specific results in this particular case. Then we extend our work to the case of infinite weighted graphs. Moreover, the technics developed in this framework allow us to study the asymptotic behavior of the bottom of the spectrum for large values of λ
40
Passey, Jr David Joseph. "Growing Complex Networks for Better Learning of Chaotic Dynamical Systems." BYU ScholarsArchive, 2020. https://scholarsarchive.byu.edu/etd/8146.
Full textAbstract:
This thesis advances the theory of network specialization by characterizing the effect of network specialization on the eigenvectors of a network. We prove and provide explicit formulas for the eigenvectors of specialized graphs based on the eigenvectors of their parent graphs. The second portion of this thesis applies network specialization to learning problems. Our work focuses on training reservoir computers to mimic the Lorentz equations. We experiment with random graph, preferential attachment and small world topologies and demonstrate that the random removal of directed edges increases predictive capability of a reservoir topology. We then create a new network model by growing networks via targeted application of the specialization model. This is accomplished iteratively by selecting top preforming nodes within the reservoir computer and specializing them. Our generated topology out-preforms all other topologies on average.
41
Ferreira, Anselmo Castelo Branco. "Um estudo comparativo de segmentação de imagens por aplicações do corte normalizado em grafos." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/267798.
Full textAbstract:
Orientador: Marco Antonio Garcia de CarvalhoDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia
Made available in DSpace on 2018-08-17T11:47:27Z (GMT). No. of bitstreams: 1 Ferreira_AnselmoCasteloBranco_M.pdf: 7338510 bytes, checksum: 593cb683d0380e0c894f0147a4129c77 (MD5) Previous issue date: 2011
Resumo: O particionamento de grafos tem sido amplamente utilizado como meio de segmentação de imagens. Uma das formas de particionar grafos é por meio de uma técnica conhecida como Corte Normalizado, que analisa os autovetores da matriz laplaciana de um grafo e utiliza alguns deles para o corte. Essa dissertação propõe o uso de Corte Normalizado em grafos originados das modelagens por Quadtree e Árvore dos Componentes a fim de realizar segmentação de imagens. Experimentos de segmentação de imagens por Corte Normalizado nestas modelagens são realizados e um benchmark específico compara e classifica os resultados obtidos por outras técnicas propostas na literatura específica. Os resultados obtidos são promissores e nos permitem concluir que o uso de outras modelagens de imagens por grafos no Corte Normalizado pode gerar melhores segmentações. Uma das modelagens pode inclusive trazer outro benefício que é gerar um grafo representativo da imagem com um número menor de nós do que representações mais tradicionais
Abstract: The graph partitioning has been widely used as a mean of image segmentation. One way to partition graphs is through a technique known as Normalized Cut, which analyzes the graph's Laplacian matrix eigenvectors and uses some of them for the cut. This work proposes the use of Normalized Cut in graphs generated by structures based on Quadtree and Component Tree to perform image segmentation. Experiments of image segmentation by Normalized Cut in these models are made and a specific benchmark compares and ranks the results obtained by other techniques proposed in the literature. The results are promising and allow us to conclude that the use of other image graph models in the Normalized Cut can generate better segmentations. One of the structures can also bring another benefit that is generating an image representative graph with fewer graph nodes than the traditional representations
Mestrado
Tecnologia e Inovação
Mestre em Tecnologia
42
Liu, Chenang. "Smart Additive Manufacturing Using Advanced Data Analytics and Closed Loop Control." Diss., Virginia Tech, 2019. http://hdl.handle.net/10919/91900.
Full textAbstract:
Additive manufacturing (AM) is a powerful emerging technology for fabrication of components with complex geometries using a variety of materials. However, despite promising potential, due to the complexity of the process dynamics, how to ensure product quality and consistency of AM parts efficiently during the process still remains challenging. Therefore, the objective of this dissertation is to develop effective methodologies for online automatic quality monitoring and improvement, i.e., to build a basis for smart additive manufacturing.
The fast-growing sensor technology can easily generate a massive amount of real-time process data, which provides excellent opportunities to address the barriers of online quality assurance in AM through data-driven perspectives. Although this direction is very promising, the online sensing data typically have high dimensionality and complex inherent structure, which causes the tasks of real-time data-driven analytics and decision-making to be very challenging.
To address these challenges, multiple data-driven approaches have been developed in this dissertation to achieve effective feature extraction, process modeling, and closed-loop quality control. These methods are successfully validated by a typical AM process, namely, fused filament fabrication (FFF). Specifically, four new methodologies are proposed and developed as listed below,
(1) To capture the variation of hidden patterns in sensor signals, a feature extraction approach based on spectral graph theory is developed for defect detection in online quality monitoring of AM. The most informative feature is extracted and integrated with a statistical control chart, which can effectively detect the anomalies caused by cyber-physical attack.
(2) To understand the underlying structure of high dimensional sensor data, an effective dimension reduction method based on an integrated manifold learning approach termed multi-kernel metric learning embedded isometric feature mapping (MKML-ISOMAP) is proposed for online process monitoring and defect diagnosis of AM. Based on the proposed method, process defects can be accurately identified by supervised classification algorithms.
(3) To quantify the layer-wise quality correlation in AM by taking into consideration of reheating effects, a novel bilateral time series modeling approach termed extended autoregressive (EAR) model is proposed, which successfully correlates the quality characteristics of the current layer with not only past but also future layers. The resulting model is able to online predict the defects in a layer-wise manner.
(4) To achieve online defect mitigation for AM process, a closed-loop quality control system is implemented using an image analysis-based proportional-integral-derivative (PID) controller, which can mitigate the defects by adaptively adjusting machine parameters during the printing process in a timely manner.
By fully utilizing the online sensor data with innovative data analytics and closed-loop control approaches, the above-proposed methodologies are expected to have excellent performance in online quality assurance for AM. In addition, these methodologies are inherently integrated into a generic framework. Thus, they can be easily transformed for applications in other advanced manufacturing processes.Doctor of Philosophy
Additive manufacturing (AM) technology is rapidly changing the industry; and online sensor-based data analytics is one of the most effective enabling techniques to further improve AM product quality. The objective of this dissertation is to develop methodologies for online quality assurance of AM processes using sensor technology, advanced data analytics, and closed-loop control. It aims to build a basis for the implementation of smart additive manufacturing. The proposed new methodologies in this dissertation are focused to address the quality issues in AM through effective feature extraction, advanced statistical modeling, and closed-loop control. To validate their effectiveness and efficiency, a widely used AM process, namely, fused filament fabrication (FFF), is selected as the experimental platform for testing and validation. The results demonstrate that the proposed methods are very promising to detect and mitigate quality defects during AM operations. Consequently, with the research outcome in this dissertation, our capability of online defect detection, diagnosis, and mitigation for the AM process is significantly improved. However, the future applications of the accomplished work in this dissertation are not just limited to AM. The developed generic methodological framework can be further extended to many other types of advanced manufacturing processes.
43
Gustavsson, Hanna. "Clustering Based Outlier Detection for Improved Situation Awareness within Air Traffic Control." Thesis, KTH, Optimeringslära och systemteori, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-264215.
Full textAbstract:
The aim of this thesis is to examine clustering based outlier detection algorithms on their ability to detect abnormal events in flight traffic. A nominal model is trained on a data-set containing only flights which are labeled as normal. A detection scoring function based on the nominal model is used to decide if a new and in forehand unseen data-point behaves like the nominal model or not. Due to the unknown structure of the data-set three different clustering algorithms are examined for training the nominal model, K-means, Gaussian Mixture Model and Spectral Clustering. Depending on the nominal model different methods to obtain a detection scoring is used, such as metric distance, probability and OneClass Support Vector Machine. This thesis concludes that a clustering based outlier detection algorithm is feasible for detecting abnormal events in flight traffic. The best performance was obtained by using Spectral Clustering combined with a Oneclass Support Vector Machine. The accuracy on the test data-set was 95.8%. The algorithm managed to correctly classify 89.4% of the datapoints labeled as abnormal and correctly classified 96.2% of the datapoints labeled as normal.Syftet med detta arbete är att undersöka huruvida klusterbaserad anomalidetektering kan upptäcka onormala händelser inom flygtrafik. En normalmodell är anpassad till data som endast innehåller flygturer som är märkta som normala. Givet denna normalmodell så anpassas en anomalidetekteringsfunktion så att data-punkter som är lika normalmodellen klassificeras som normala och data-punkter som är avvikande som anomalier. På grund av att strukturen av nomraldatan är okänd så är tre olika klustermetoder testade, K-means, Gaussian Mixture Model och Spektralklustering. Beroende på hur normalmodellen är modellerad så har olika metoder för anpassa en detekteringsfunktion används, så som baserat på avstånd, sannolikhet och slutligen genom One-class Support Vector Machine. Detta arbete kan dra slutsatsen att det är möjligt att detektera anomalier med hjälp av en klusterbaserad anomalidetektering. Den algoritm som presterade bäst var den som kombinerade spektralklustring med One-class Support Vector Machine. På test-datan så klassificerade algoritmen $95.8\%$ av all data korrekt. Av alla data-punkter som var märka som anomalier så klassificerade denna algoritm 89.4% rätt, och på de data-punkter som var märka som normala så klassificerade algoritmen 96.2% rätt.
44
Male, Camille. "Forte et fausse libertés asymptotiques de grandes matrices aléatoires." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00673551.
Full textAbstract:
Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy.
45
Humari, Juan Herbert Chuctaya. "Estudo do espectro Laplaciano na categorização de imagens." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/59/59135/tde-04072016-091446/.
Full textAbstract:
Uma imagem engloba informação que precisa ser organizada para interpretar e compreender seu conteúdo. Existem diversas técnicas computacionais para extrair a principal informação de uma imagem e podem ser divididas em três áreas: análise de cor, textura e forma. Uma das principais delas é a análise de forma, por descrever características de objetos baseadas em seus pontos fronteira. Propomos um método de caracterização de imagens, por meio da análise de forma, baseada nas propriedades espectrais do laplaciano em grafos. O procedimento construiu grafos G baseados nos pontos fronteira do objeto, cujas conexões entre vértices são determinadas por limiares T_l. A partir dos grafos obtêm-se a matriz de adjacência A e a matriz de graus D, as quais definem a matriz Laplaciana L=D -A. A decomposição espectral da matriz Laplaciana (autovalores) é investigada para descrever características das imagens. Duas abordagens são consideradas: a) Análise do vetor característico baseado em limiares e a histogramas, considera dois parâmetros o intervalo de classes IC_l e o limiar T_l; b) Análise do vetor característico baseado em vários limiares para autovalores fixos; os quais representam o segundo e último autovalor da matriz L. As técnicas foram testada em três coleções de imagens: sintéticas (Genéricas), parasitas intestinais (SADPI) e folhas de plantas (CNShape), cada uma destas com suas próprias características e desafios. Na avaliação dos resultados, empregamos o modelo de classificação support vector machine (SVM), o qual avalia nossas abordagens, determinando o índice de separação das categorias. A primeira abordagem obteve um acerto de 90 % com a coleção de imagens Genéricas, 88 % na coleção SADPI, e 72 % na coleção CNShape. Na segunda abordagem, obtém-se uma taxa de acerto de 97 % com a coleção de imagens Genéricas; 83 % para SADPI e 86 % no CNShape. Os resultados mostram que a classificação de imagens a partir do espectro do Laplaciano, consegue categorizá-las satisfatoriamente.An image includes information that needs to be organized to interpret and understand its contents. There are several computational techniques to extract the main information of images and are divided into three areas: color, texture and shape analysis. One of the main of them is shape analysis, since it describes objects getting main features based on reference points, usually border points. This dissertation proposes a shape analysis method based on the spectral properties of the Laplacian in graphs to represent images. The procedure builds G graphs based on object border points, whose connections between vertices are determined by thresholds T_l. From graphs G we obtain the adjacency matrix A and matrix degrees D, which define the Laplacian matrix L=D -A. Thus, spectral decomposition of the Laplacian matrix (eigenvalues) is investigated to describe image features. Two approaches are considered: a)Analysis of feature vector based on thresholds and histograms, it considers two parameters, classes range IC_l and threshold T_l; b) Analysis of feature vector based on multiple linear for fixed eigenvalues, which represents the second and final eigenvalue matrix L. The techniques were tested in three image datasets: synthetic (Generic), human intestinal parasites (SADPI) and plant leaves (CNShape), each of these with its own features and challenges. Afterwards to evaluate our results, we used the classification model Support Vector Machine (SVM) to evaluate our approaches, determining the percentage of separation of categories. The first approach achieved 90 % of precision with the Generic image dataset, 88 % in SADPI dataset, and 72 % in CNShape dataset. In the second approach, it obtains 97 % of precision with the Generic image dataset, 83 % for SADPI and 86 % in CNShape respectively. The results show that the classification of images from the Laplacian spectrum can categorize them satisfactorily.
46
Al-Doujan, Fawwaz Awwad. "Spectra of graphs." Thesis, University of East Anglia, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.306195.
Full text
47
Parmentier, Frédéric. "Modélisation et prédiction de la dynamique moléculaire de la maladie de Huntington par la théorie des graphes au travers des modèles et des espèces, et priorisation de cibles thérapeutiques." Thesis, Sorbonne Paris Cité, 2015. http://www.theses.fr/2015PA05T030.
Full textAbstract:
La maladie de Huntington est une maladie neurodégénérative héréditaire qui est devenue un modèle d'étude pour comprendre la physiopathologie des maladies du cerveau associées à la production de protéines mal conformées et à la neurodégénérescence. Bien que plusieurs mécanismes aient été mis en avant pour cette maladie, dont plusieurs seraient aussi impliqués dans des pathologies plus fréquentes comme la maladie d’Alzheimer ou la maladie de Parkinson, nous ne savons toujours pas quels sont les mécanismes ou les profils moléculaires qui déterminent fondamentalement la dynamique des processus de dysfonction et de dégénérescence neuronale dans cette maladie. De même, nous ne savons toujours pas comment le cerveau peut résister aussi longtemps à la production de protéines mal conformées, ce qui suggère en fait que ces protéines ne présentent qu’une toxicité modérée ou que le cerveau dispose d'une capacité de compensation et de résilience considérable. L'hypothèse de mon travail de thèse est que l'intégration de données génomiques et transcriptomiques au travers des modèles qui récapitulent différentes phases biologiques de la maladie de Huntington peut permettre de répondre à ces questions. Dans cette optique, l'utilisation des réseaux de gènes et la mise en application de concepts issus de la théorie des graphes sont particulièrement bien adaptés à l'intégration de données hétérogènes, au travers des modèles et au travers des espèces. Les résultats de mon travail suggèrent que l'altération précoce (avant les symptômes, avant la mort cellulaire) et éventuellement dès le développement cérébral) des grandes voies de développement et de maintenance neuronale, puis la persistance voire l'aggravation de ces effets, sont à la base des processus physiopathologiques qui conduisent à la dysfonction puis à la mort neuronale. Ces résultats permettent aussi de prioriser des gènes et de générer des hypothèses fortes sur les cibles thérapeutiques les plus intéressantes à étudier d'un point de vue expérimental. En conclusion, mes recherches ont un impact à la fois fondamental et translationnel sur l'étude de la maladie de Huntington, permettant de dégager des méthodes d'analyse et des hypothèses qui pourraient avoir valeur thérapeutique pour les maladies neurodégénératives en généralHuntington’s disease is a hereditary neurodegenerative disease that has become a model to understand physiopathological mechanisms associated to misfolded proteins that ocurs in brain diseases. Despite exciting findings that have uncover pathological mechanisms occurring in this disease and that might also be relevant to Alzheimer’s disease and Parkinson’s disease, we still do not know yet which are the mechanisms and molecular profiles that rule the dynamic of neurodegenerative processes in Huntington’s disease. Also, we do not understand clearly how the brain resist over such a long time to misfolded proteins, which suggest that the toxicity of these proteins is mild, and that the brain have exceptional compensation capacities. My work is based on the hypothesis that integration of ‘omics’ data from models that depicts various stages of the disease might be able to give us clues to answer these questions. Within this framework, the use of network biology and graph theory concepts seems particularly well suited to help us integrate heterogeneous data across models and species. So far, the outcome of my work suggest that early, pre-symptomatic alterations of signaling pathways and cellular maintenance processes, and persistency and worthening of these phenomenon are at the basis of physiopathological processes that lead to neuronal dysfunction and death. These results might allow to prioritize targets and formulate new hypotheses that are interesting to further study and test experimentally. To conclude, this work shall have a fundamental and translational impact to the field of Huntington’s disease, by pinpointing methods and hypotheses that could be valuable in a therapeutic perspective
48
Li, Yuemeng. "Spectral Analysis of Directed Graphs using Matrix Perturbation Theory." Thesis, The University of North Carolina at Charlotte, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10618933.
Full textAbstract:
The spectral space of the adjacency matrix contains important structural information of a given network (graph), where such information can be leveraged in developing a variety of algorithms in applications such as graph partition, structural hierarchy discovery, and anomaly detection. Although many prominent works have laid the foundation for studying the graph spectra, it is still challenging to analyze the spectral space properties for directed graphs due to possible complex valued decompositions. Matrix factorization techniques such as Laplacian and normalized Laplacian have been widely adopted to study the associated spectral spaces, but network structural properties may not be well preserved in those spectral spaces due to transformations.
In this dissertation work, we explore the adjacency eigenspace of directed graphs using matrix perturbation theory and examine the relationships between graph structures and the spectral projection patterns. We study how to detect dominant structures such as clusters or anomalous nodes by establishing a connection between the connectivity of nodes and the geometric relationships in the adjacency eigenspace. We leverage selected key results from perturbation theory, linear algebra and graph theory as our tools to derive theoretical results that help to elaborate observed graph spectral projection patterns. In order to validate our theoretical results, novel algorithms including spectral clustering for both signed and unsigned networks, asymmetry analysis for network dominance, and anomaly analysis for streaming network data are developed and tested on both synthetic and real datasets. The empirical evaluation results suggest that our algorithms performs better when compared with existing state-of-the-art methods.
49
Saade, Alaa. "Spectral inference methods on sparse graphs : theory and applications." Thesis, Paris Sciences et Lettres (ComUE), 2016. http://www.theses.fr/2016PSLEE024/document.
Full textAbstract:
Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matricesIn an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion
50
Ong, Beng Seong. "Spectral problems of optical waveguides and quantum graphs." Texas A&M University, 2006. http://hdl.handle.net/1969.1/4352.
Full textAbstract:
In this dissertation, we consider some spectral problems of optical waveguide and
quantum graph theories.
We study spectral problems that arise when considerating optical waveguides in photonic
band-gap (PBG) materials. Specifically, we address the issue of the existence of
modes guided by linear defects in photonic crystals. Such modes can be created for frequencies
in the spectral gaps of the bulk material and thus are evanescent in the bulk (i.e.,
confined to the guide).
In the quantum graph part we prove the validity of the limiting absorption principle
for finite graphs with infinite leads attached. In particular, this leads to the absence of a
singular continuous spectrum.
Another problem in quantum graph theory that we consider involves opening gaps
in the spectrum of a quantum graph by replacing each vertex of the original graph with a
finite graph. We show that such "decorations" can be used to create spectral gaps.