学界|波尔多大学招募随机时态图博士

In a temporal graph each edge is only available at a specific time, and a walk must go ahead in time. For instance, temporal graphs can be used to model public transportation network with an exact knowledge of the timetable. Just like for the classical static graph setting, there is now a study of random temporal graphs and their properties.

One of the lines of research equivalent to temporal graphs is gossip propagation. In this model multiple agents have some pieces of information and can share them in one-to-one conversations. Naturally, one cannot share news that will be received later.

In the proposed project we seek to expand the fundamental understanding of general behaviour of random temporal graphs, often omitting the next-order-of-magnitude corrections necessary for finer asymptotic results or for modelling specific applications.

Many questions that are simple for static graphs (e.g. «what is the largest connected component?» — solvable in linear time) become much harder (in this case, NP-complete and hard to approximate) for temporal graphs.

Even the simplest notions become more nuanced. For example, if a graph has a vertex reachable from every vertex, and all vertices are reachable from that chosen vertex, it is not sufficient for every vertex to be reachable from each other vertex.

An example of a question that becomes harder is the maximum size of a connected component in the graph, i.e. how many vertices can all reach each other. In the static case graph setting, this can be solved in linear time, both for directed and for undirected graphs. In the dynamic graph setting, however, A reaching B and B reaching C is not enough for A reaching C. There is a possibility that the earliest walk from A to B arrives in B too late to be able to continue to C. In particular, the problem of the maximum connected component becomes as hard as the question of the maximum clique size, i.e. NP-complete (and NP-hard to approximate up to any constant factor).

Casteigts et al. have looked at the properties of the Erdős-Rényi random graphs with random edge orderings, and established various sharp thresholds for densities where some properties are achieved. These properties include temporal connectivity and existence of linear size temporal spanner, existence of a temporal source, etc. In further work with a larger group of the co-authors the sharp threshold for existence of a large temporal connected component has also been established. However, there are many more classical properties studied for random static graphs than there are properties studied for random temporal graphs.

More recently, Broutin et al. have studied diameter in terms of number of steps.

One part of the proposed direction is to study further properties such as, for example, k-connectivity, degree distribution, and frequency of small subgraphs. The behaviour of structural measures such as tree-width or path-width or chromatic number could also be of interest.

Another question is similar to the offline and online questions for static graphs; what we can tell about a graph if it is given to us at once and what we can tell about the graph if only a part of the edges is given. For example, for random temporal graphs we have a natural order of revealing the edges thus we can ask about the distributions of some random variables conditional on the edges already revealed. For example, instead of asking for the length of a temporal walk from A to B, we might be interested in the distribution of expected distances to B conditional on the edges revealed by some time T.

The candidate definitely needs to be comfortable with basic probability theory and the study of independence, and interested in developing intuition about approximate independence. The directions where a general understanding of the situation allows to obtain a proof without the use of fragile computations or exotic probabilistic tools will be prioritised.

Preliminary knowledge of graph theory is not necessary, but if there is knowledge and interest of some aspects of structural graph theory they can be leveraged in the project.

Similarly, if there is knowledge and interest, some work on algorithmic complexity of the properties in question could be integrated into the project.