- Ranking on directed random graphs: I have been interested for some time in analyzing the typical behavior of ranking algorithms on complex networks, e.g., Google's PageRank. This type of algorithms allow us to identify the ``central" nodes in a graph, i.e., those who get visited more often, or those who are capable of reaching many other nodes in a few steps. In particular, we are interested in computing the distribution of the ranks, which, among other things, tells us the proportion of nodes in the graph that are highly important/relevant. Although it would be very difficult to answer the type of questions we are interested in on arbitrary graphs, the problem becomes tractable when we work with random graph models generating locally tree-like graphs (most mathematical models out there have this property). A rigorous analysis of the distributional properties of PageRank was recently done for graphs generated by the so-called configuration model. One of my ongoing projects consists in extending the analysis done for generalized PageRank to other popular random graph models, and also understand when such analysis fails.
- Simulation for branching recursions: A branching distributional equation is such that:
where the are i.i.d.copies of , independent of the vector , . These equations appear in a variety of problems, ranging from population models and free energy calculations in statistical physics, to the analysis of sorting algorithms, queueing networks, and the study of ranking algorithms on complex graphs. The random variable is called the solution to the branching stochastic fixed-point equation (SFPE), and many SFPEs have more than one solution. Depending on the problem where the SFPE comes from, it is usually the case that we can identify which solution we are interested in, and in many cases the relevant solution turns out to be the one we call the endogenous solution. Although this special solution can sometimes be analyzed asymptotically, there is no easy way to compute the body of its distribution, which leaves numerical approaches as the only option. An algorithm that seems to work very well for efficiently computing an approximation to the distribution of the endogenous solution is called the Population Dynamics algorithm, which is a sequential Monte Carlo method closely related to particle filtering. Although some of the basic convergence properties of the algorithm have recently been established, there are many open questions regarding its rate of convergence and the reduction/elimination of its bias.
I am currently looking for PhD students to work on problems related to these two themes. If you are interested, please send me an email to firstname.lastname@example.org.