Stochastic Processes on Graphs

In this project, we study how stochastic processes behave on graph. The main idea is to generate many random signals and to filter them (thanks to spectral graph theory). The output of this operation tells a lot about the graph itself. First, it gives local regularity information: is some node more connected to the other? Or isolated? Second, thanks to this technique, we can compute the density of the Laplacian’s eigenvalues of the graphs. This allows a graph classification for instance. Third, we can even perform this classification for a specific node. Finally, the algorithm used in this project scales to very large graphs. We should be able to analyze a big instance of a social network.

The project is separated into two different parts:

  Study of the graph topology thanks to random signals
      Convergence analysis of || T_i g ||_2 (theory + application )
      Local uncertainty on graph
      Multiscale graph analysis thanks to wavelets!
          Study of special graphs like fractal graphs / community graphs
  Spectral analysis via random signals
      Estimation of the spectrum density
          Application to very big graphs!
      Analysis of local graph features
      - Is a graph locally like a specific graph?
      - Analysis of the ||T_i g || curve instead of the ||g|| curve

What are you going to learn: Spectral graph theory, Stochastic processes, being stuck, write demonstrations

Theory: 5/5 Application: 3/5

Supervisors: Nathanael Perraudin, Olivier Lévêque, Pierre Vandergheynst