No description available.

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.

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.

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.

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.

This dissertation solves variations of three mathematical problems for autonomous vehicle formations: (1) formation shape control in the plane, (2) robust information architecture design, and (3) formation attitude synchronization. An autonomous vehicle formation is a collection of vehicles, each with computation, communication, sensing, and control capabilities, that cooperate to achieve a common objective. Accelerating advancements are making possible a range of science and engineering applications, such as satellite formations for deep-space imaging, teams of unmanned aircraft for military reconnaissance and surveillance missions, and submarine swarms for oceanic exploration. The ubiquitous potential of these applications is driving theoretical work on autonomous vehicle formations across a range of disciplines. A major theoretical question in the field of control theory, and the main focus of this dissertation, is how the properties of the information architecture (i.e. a mapping of the information flow amongst the agents), relate to the stability properties of the desired shape and orientation under certain control laws. A secondary focus is how to design the information flow so that loss of an agent does not destroy the formation's ability to maintain a desired shape. As a motivating example, a solution to a coordinated standoff tracking problem is presented to demonstrate how an instance of a class of information architectures, which are called persistent and related to rigid graph theory, can be used to achieve a formation objective in a practical scenario involving a team of unmanned aircraft. A generalized formation shape control problem is then solved for a class of persistent architectures. This solution gives only local stability results; global stability is analyzed for a four-agent formation and several open problems are identified. The problem of agent loss is addressed by performing a self-repair operation in the event of agent loss and separately by designing robustness into the information architecture a priori. Finally, a rigid body attitude synchronization problem with communication time delays is solved for a class of information architectures based on spectral graph theory. / text

La capture du mouvement est un défi majeur dans le cadre de la modélisation d'objets articulés. Ce problème implique la recherche de correspondances entre objets vus dans des images différentes. On propose trois approches pour résoudre ce problème basé sur des techniques de vision par ordinateur et la théorie spectrale des graphes. La première consiste à modéliser une scène 3D à l'aide d'une collection de points. On propose deux extensions de l'algorithme de Lucas-Kanade pour tracker des caractéristiques de manière efficace et pour estimer le "scene-flow". La deuxième approche basée sur la théorie spectrale des graphes cherche à établir des correspondances entre des objets représentés par des graphes. Finalement on s'intéresse au problème de segmentation qui soit cohérente dans le temps et notre approche est basée sur une méthode de clustering spectral appliquée à une séquence temporelle.

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.

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.

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.