A measure to evaluate the quality of community partitions based on link prediction
Knowing which community detection methods gives the most useful result is a common problem in community detection. I propose to adopt a without apriori/model free approach by considering that the best model is the one which is the most useful to predict hidden/future links. This raises a lot of questions, such as how to do this link prediction based on the partition, how many edges we should hide, etc.
Discovering spatial position of nodes using graph-embedding or bayesian inference
Imagine a spatial graph in which the probability to observe an edge depends on the distance between nodes. Now let's say that we remove the position information from the nodes. Would it be possible to re-infer the relative position of nodes from the graph? And/Or to know if the graph had a spatial structure to begin with? In theory, this is more or less what graph-embedding methods should do. But naive experiments show that it does not seem to work. I have some intuitions of why, and you will tackle this problem: can you show when it is possible and when it isn't, and/or propose a method to solve this problem?
Study the influence of random graph structure on network properties and/or diffusion on networks
In a recent work, we introduced Structify-Net
, a method and library to generate random graph with a customizable structure define by a function provided as parameters. This allows to generate networks with non-standard organization, beyond blocks and spatial structure. You will use this library to study the influence of the structure of random graphs on network properties and/or diffusion on networks. For instance, how does the robustness of a network to random failures depends on its structure? How does the convergence of an opinion dynamic model depends on the structure of the network? etc.