This project can be taken as a Bachelor, Master semester or Master thesis project.
Simulation and analysis of a stochastic evolution of bipartite graphs
Description:
Bipartite graphs are graphs with two disjoint sets A and B of nodes. The set of edges E connect nodes in A with nodes in B but there are no edges within A or within B. One is interested in large graphs where the number of edges and nodes tend to infinity. The graph is called sparse if the total number of edges is of the same order as the total number of nodes, and if the number of edges is much greater than the number of nodes it is called dense. Such graphical structures commonly arise in problems of computer science, coding theory, biological networks.Typicaly the set of A nodes can represent variables of an inference problem while the set of B nodes can represent constraints among these variables
Objective:
In this project one will study a very specific stochastic process (not explained here) which takes place in a space of bipartite graphs. The process starts with a sparse graph and and has a tendency to add edges to the graph. The goal is to investigate the evolution of the graph and notably to what extent it becomes dense or remains sparse. A program for doing experiments on a computer has already been developped. The goal of the project would be attempt, based on the experimental results, a theoretical analysis of the time evolution of the stochastic process. Emphasis will be on the assymptotic analysis in the limit where the graphs become large. The student will have to familiarize himself with the program as well with probabilistic tools such as the Wormald method. The Lovasz Local Lemma may also be of some use. Gaining insight into this specific stochastic process would be important for problems in coding theory.
Prerequisites:
A desire to learn probabilistic methods would be a plus.
References:
1) Navi Assad, Project Report and Simulation Program - Spring 2009.
2) N. C. Wormald, The differential equation method for random graph processes and greedy algorithms, Notes of the Summer School on Randomized Algorithms at Antonin, Poland in 1997
Supervision:
Dr. Nicolas Macris (LTHC) * Email: nicolas.macris#epfl.ch * Office: INR 134 *
Tel: 38114