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.

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.

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.

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.

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. / The thesis fits into the random matrix theory, in intersection with free probability and operator algebra. It is part of a general approach which is common since the last decades: using tools and concepts of non commutative probability in order to get general results about the spectrum of large random matrices. Where are interested here in generalization of Voiculescu's asymptotic freeness theorem. In Chapter 1 and 2, we show some results of strong asymptotic freeness for gaussian, random unitary and deterministic matrices. In Chapter 3 and 4, we introduce the notion of asymptotic false freeness for deterministic matrices and certain random matrices, Hermitian with independent sub-diagonal entries, interpolating Wigner and Lévy models.

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.