**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Matrice laplacienne

Résumé

En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe.
Définition
La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : L = D - A où D est la matrice des degrés de G et A la matrice d'adjacence de G. Formellement :
L_{i,j}:=\left{
\begin{matrix}
\deg(s_i) & \mbox{si } i = j\
-x & \mbox{ si } i \neq j \mbox{ avec }x \mbox{ le nombre d'ar}\hat{\mbox{e}}\mbox{tes reliant directement }i\grave{\mbox{ a }} j \
0 & \mbox{sinon}
\end{matrix}
\right.
Intuition
A la différence de la matrice d'adjacence d'un graphe, la matrice laplacienne a une interprétation algébrique ce qui rend son analyse spectrale fructueuse.
Plus précisément la matrice D^{-1}A
correspond à l'opérateur de diffusion sur le graphe. Si x \in \mathbb{R}^{n} correspond à la densité de particules d'un gaz en chacun des n s

Source officielle

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Personnes associées (3)

Cours associés (17)

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportunities offered by communication will be analyzed.

MICRO-455: Applied machine learning

Real-world engineering applications must cope with a large dataset of dynamic variables, which cannot be well approximated by classical or deterministic models. This course gives an overview of methods from Machine Learning for the analysis of non-linear, highly noisy and multi dimensional data

MATH-467: Probabilistic methods in combinatorics

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

Publications associées (27)

Chargement

Chargement

Chargement

Unités associées (6)

Concepts associés (16)

Théorie des graphes

vignette|Un tracé de graphe.
La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets

Lexique de la théorie des graphes**NOTOC**
A
; Acyclique : graphe ne contenant pas de cycle.
; Adjacence : une liste d'adjacence est une structure de données constituée d'un tableau dont le i-ème élément co

Matrice d'adjacence

En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal a{

Coupled dynamical systems are omnipresent in everyday life. In general, interactions between
individual elements composing the system are captured by complex networks. The latter
greatly impact the way coupled systems are functioning and evolving in time. An important
task in such a context, is to identify the most fragile components of a system in a fast and
efficient manner. It is also highly desirable to have bounds on the amplitude and duration
of perturbations that could potentially drive the system through a transition from one equi-
librium to another. A paradigmatic model of coupled dynamical system is that of oscillatory
networks. In these systems, a phenomenon known as synchronization where the individual
elements start to behave coherently may occur if couplings are strong enough. We propose
frameworks to assess vulnerabilities of such synchronous states to external perturbations. We
consider transient excursions for both small-signal response and larger perturbations that can
potentially drive the system out of its initial basin of attraction.
In the first part of this thesis, we investigate the robustness of complex network-coupled
oscillators. We consider transient excursions following external perturbations. For ensemble
averaged perturbations, quite remarkably we find that robustness of a network is given by
a family of network descriptors that we called generalized Kirchhoff indices and which are
defined from extensions of the resistance distance to arbitrary powers of the Laplacian matrix
of the system. These indices allow an efficient and accurate assessment of the overall vulnera-
bility of an oscillatory network and can be used to compare robustness of different networks.
Moreover, a network can be made more robust by minimizing its Kirchhoff indices. Then for
specific local perturbations, we show that local vulnerabilities are captured by generalized
resistance centralities also defined from extensions of the resistance distance. Most fragile
nodes are therefore identified as the least central according to resistance centralities. Based on
the latter, rankings of the nodes from most to least vulnerable can be established. In summary,
we find that both local vulnerabilities and global robustness are accurately evaluated with
resistance centralities and Kirchhoff indices. Moreover, the framework that we define is rather
general and may be useful to analyze other coupled dynamical systems.
In the second part, we focus on the effect of larger perturbations that eventually lead the sys-
tem to an escape from its initial basin of attraction. We consider coupled oscillators subjected
to noise with various amplitudes and correlation in time. To predict desynchronization and
transitions between synchronous states, we propose a simple heuristic criterion based on the
distance between the initial stable fixed point and the closest saddle point. Surprisingly, we
find numerically that our criterion leads to rather accurate estimates for the survival probability and first escape time. Our criterion is general and may be applied to other dynamical
systems.

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emerged in recent decades, such as processing the data in a stream, parallel processing, and data compression. The aim of this thesis is to apply these techniques to various important graph theoretical problems. Our contributions can be broadly classified into two categories: spectral graph theory, and maximum matching.Spectral Graph Theory. Spectral sparsification is a technique of rendering an arbitrary graph sparse, while approximately preserving the quadratic form of the Laplacian matrix. In this thesis, we extend the result of (Kapralov et al.), and propose a sketch and corresponding decoding algorithm for constructing a spectral sparsifier from a dynamic stream of edge insertions and deletions. The size of the resulting sparsifier, the size of the sketch, and the decoding time are all nearly linear in the number of vertices, and consequently nearly optimal.The concept of spectral sparsification has recently been generalized to hypergraphs (Soma and Yoshida) -- an analogue of graphs for modeling higher order relationships. As one of the main contributions of the thesis, we prove for the first time the existence of nearly-linear sized spectral sparsifiers for arbitrary hypergraphs, and provide a corresponding nearly-linear time algorithm for constructing them. Through a lower bound construction, we show that our sparsifiers achieve nearly-optimal compression of the hypergraph spectral structure.On the more applied side of spectral graph theory, we present a fully scalable MPC (massively parallel computation) algorithm which is capable of simulating a large number of independent random walks of length L from an arbitrary starting distribution in O(log(L)) rounds.Maximum Matching. We propose a novel randomized composable coreset for the problem of maximum matching, called the matching skeleton. The coreset achieves a 1/2 approximation, while having fewer than n edges.We also propose a new, highly space-efficient variant of a peeling algorithm for maximum matching. With this, we are able to approximate the maximum matching size of a graph to within a constant factor, using a stream of m uniformly random edges (where m is the total number of edges), in as little as O(log^2(n)) space. Conversely, we show that significantly fewer (that is m^(1-Omega(1))) samples do not suffice, even with unlimited space. Finally, we design a Local Computation Algorithm, which implicitly construct a constant-approximate maximum matching in time and space that is nearly linear in the maximum degree.

The objective of this PhD thesis is the approximate computation of the solutions of the Spectral Problem associated with the Laplace operator on a compact Riemann surface without boundaries. A Riemann surface can be seen as a gluing of portions of the Hyperbolic Plane made with suitable conditions to obtain a 2 dimensional manifold. The solutions of the Spectral Problem associated with the Laplace operator are to be understood as the eigenfunctions defined on the surface and their corresponding eigenvalues. This work is separated into two parts: the first part describes the method used to approximate the eigenvalues and eigenfunctions, the second focuses on the design of a program to compute these approximations. The approximation method is inspired by the Finite Element Method (FEM), in that it relies on the variational expression of the Spectral Problem and the definition of a finite subspace of functions in which the approximated eigenvalues and eigenfunctions are computed. However, it differs from the FEM in that it removes the euclidian basis of the FEM and is invariant under the isometries of the Hyperbolic Plane. To ful fill this objective, we begin by geodesically triangulating the surface as regularly as possible. This hyperbolic triangulation allows us to de ne the finite subspace of functions by using the concept of barycentric coordinates associated with each vertex of the triangulation (idea introduced by Whitney and taken up by Dodziuk). We then prove that the approximated solutions convergence to the exact ones when the diameter of the triangulation decreases, as well as the order of convergence. The program is a practical application of the theoretical work and allows the computation of the approximated eigenfunctions and eigenvalues.

Séances de cours associées (29)