The classical wavelet transform has been widely used in image and signal processing, where a signal is decomposed into a combination of basis signals. By analyzing the individual contribution of the basis signals, one can infer properties of the original signal. This dissertation presents an overview of the extension of the classical signal processing theory to graph domains. Specifically, we review the graph Fourier transform and graph wavelet transforms both of which based on the spectral graph theory, and explore their properties through illustrative examples. The main features of the spectral graph wavelet transforms are presented using synthetic and real-world data. Furthermore, we introduce in this dissertation a novel method for visual analysis of dynamic networks, which relies on the graph wavelet theory. Dynamic networks naturally appear in a multitude of applications from different domains. Analyzing and exploring dynamic networks in order to understand and detect patterns and phenomena is challenging, fostering the development of new methodologies, particularly in the field of visual analytics. Our method enables the automatic analysis of a signal defined on the nodes of a network, making viable the detection of network properties. Specifically, we use a fast approximation of the graph wavelet transform to derive a set of wavelet coefficients, which are then used to identify activity patterns on large networks, including their temporal recurrence. The wavelet coefficients naturally encode spatial and temporal variations of the signal, leading to an efficient and meaningful representation. This method allows for the exploration of the structural evolution of the network and their patterns over time. The effectiveness of our approach is demonstrated using different scenarios and comparisons involving real dynamic networks. / A transformada wavelet clássica tem sido amplamente usada no processamento de imagens e sinais, onde um sinal é decomposto em uma combinação de sinais de base. Analisando a contribuição individual dos sinais de base, pode-se inferir propriedades do sinal original. Esta tese apresenta uma visão geral da extensão da teoria clássica de processamento de sinais para grafos. Especificamente, revisamos a transformada de Fourier em grafo e as transformadas wavelet em grafo ambas fundamentadas na teoria espectral de grafos, e exploramos suas propriedades através de exemplos ilustrativos. As principais características das transformadas wavelet espectrais em grafo são apresentadas usando dados sintéticos e reais. Além disso, introduzimos nesta tese um método inovador para análise visual de redes dinâmicas, que utiliza a teoria de wavelets em grafo. Redes dinâmicas aparecem naturalmente em uma infinidade de aplicações de diferentes domínios. Analisar e explorar redes dinâmicas a fim de entender e detectar padrões e fenômenos é desafiador, fomentando o desenvolvimento de novas metodologias, particularmente no campo de análise visual. Nosso método permite a análise automática de um sinal definido nos vértices de uma rede, tornando possível a detecção de propriedades da rede. Especificamente, usamos uma aproximação da transformada wavelet em grafo para obter um conjunto de coeficientes wavelet, que são então usados para identificar padrões de atividade em redes de grande porte, incluindo a sua recorrência temporal. Os coeficientes wavelet naturalmente codificam variações espaciais e temporais do sinal, criando uma representação eficiente e com significado expressivo. Esse método permite explorar a evolução estrutural da rede e seus padrões ao longo do tempo. A eficácia da nossa abordagem é demonstrada usando diferentes cenários e comparações envolvendo redes dinâmicas reais.

Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique. / This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes.

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éral. / Huntington’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.

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.

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.

A spectral graph realization is an embedding of a finite simple graph into Euclidean space that is constructed from the eigenvalues and eigenvectors of the graph's adjacency matrix. It has previously been observed that some polytopes can be reconstructed from their edge-graphs by taking the convex hull of a spectral realization of this edge-graph. These polytopes, which we shall call spectral polytopes, have remarkable rigidity and symmetry properties and are a source for many open questions. In this thesis we aim to further the understanding of this phenomenon by exploring the geometric and combinatorial properties of spectral polytopes on several levels. One of our central questions is whether already weak forms of symmetry can be a sufficient reason for a polytope to be spectral. To answer this, we derive a geometric criterion for the identification of spectral polytopes and apply it to prove that indeed all polytopes of combined vertex- and edge-transitivity are spectral, admit a unique reconstruction from the edge-graph and realize all the symmetries of this edge-graph. We explore the same questions for graph realizations and find that realizations of combined vertex- and edge-transitivity are not necessarily spectral. Instead we show that we require a stronger form of symmetry, called distance-transitivity. Motivated by these findings we take a closer look at the class of edge-transitive polytopes, for which no classification is known. We state a conjecture for a potential classification and provide complete classifications for several sub-classes, such as distance-transitive polytopes and edge-transitive polytopes that are not vertex-transitive. In particular, we show that the latter class contains only polytopes of dimension d <= 3. As a side result we obtain the complete classification of the vertex-transitive zonotopes and a new characterization for root systems.

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égulier. / The 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.

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.

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

[pt] O estudo de desvios, e em particular grandes desvios, tem uma história longa na teoria de probabilidade. Nas últimas décadas muitos artigos consideraram essas questões no contexto de subgrafos de grafos aleatórios G(n, p) e G(n, m). Esta dissertação considera a cauda inferior para o número de triângulos no grafo aleatório G(n, m). Duas abordagens estão consideradas: Martingales, a partir artigo de Christina Goldschmidt, Simon Griffiths e Alex Scott; e Teoria Espectral de Grafos, a partir do artigo de Joe Neeman, Charles Radin e Lorenzo Sadun. Essas duas abordagens conseguem encontrar o comportamento da cauda em dois regimes diferentes. Na dissertação discutiremos a visão geral do artigo de Goldschmidt, Griffiths e Scott, e discutiremos em detalhes o artigo de Neeman, Radin e Sadun. Em particular, exploraremos a conexão entre a cauda inferior do número de triângulos e o comportamento dos autovalores mais negativos da matriz de adjacência. Veremos que a contagem tende a depender, essencialmente, do autovalor mais negativo. / [en] The study of deviations, and in particular large deviations, has a long history in Probability Theory. In recent decades many articles have considered these questions in the context of subgraphs of the random graphs G(n, p) and G(n, m). This dissertation considers the lower tail for the number of triangles in the random graph G(n, m). Two approaches are considered: Martingales, based on the article of Christina Goldschmidt, Simon Griffiths and Alex Scott; and Spectral Graph Theory, based on the article of Joe Neeman, Charles Radin and Lorenzo Sadun. These two approaches manage to find the behavior of the tail in two different regimes. In this dissertation we give an overview of the article of Goldschmidt, Griffiths and Scott, discuss in detail the article of artigo Neeman, Radin and Sadun. In particular, we shall explore the connection between the lower tail of the number of triangles and the behavior of the most negative eigenvalues of the adjacency matrix. We shall see that the triangle count tends to especially depend on the most negative eigenvalue.