**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Jacques Saliba

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

People doing similar research

Related research domains

No results

No results

Related publications (2)

Loading

Loading

Courses taught by this person

No results

Related units (2)

Thomas Mountford, Jacques Saliba

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of verticesntends to infinity, in the case where the weight distributionGhas an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds.

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges.
We start by describing the asymptotic behavior of the diameter and the flooding time on the graph for a set of light-tailed edge-weights, and we prove that it is the largest class of densities for which these precise asymptotic expressions for the diameter/flooding time hold.
We then show how the weighted optimal path can be constructed using a particular positive recurrent Markov chain.
We finally study, in the last chapter, the noise sensitivity of the model by replacing every edge-weight independently by a new realization of the same distribution, with probability epsilon. We show that the optimal paths between two vertices before and after this modification are asymptotically ''independent'' conditioning on the graph, as the number of vertices tends to infinity.