WAW 2015 - Invited Speakers

WAW 2015 - Invited Speakers

Invited Speakers

Paul Van Dooren, Catholic University of Louvain

Title: Judging the judges: iterative filtering and dynamic reputation systems.

Paul Van Dooren Abstract: The talk introduces a novel iterative method that assigns a reputation to n+m items: n judges and m objects. Each judge evaluates a subset of objects leading to a n x m rating matrix with a certain sparsity pattern. From this rating matrix we give a nonlinear formula to define the reputation of judges and objects. We also provide an iterative algorithm that superlinearly converges to the unique vector of reputations for any rating matrix. In contrast to classical outliers detection, no evaluation is discarded in this method but each one is taken into account with different weights for the reputation of the objects. The complexity of one iteration step is linear in the number of evaluations, making our algorithm efficient for large data set. Experiments show good robustness of the reputation of the objects against cheaters and spammers and good detection properties of cheaters and spammers.


Mariana Olvera-Cravioto, Columbia University

Title: Distances, clustering and PageRank on the directed configuration model.

Abstract: This talk will give an overview of recent results for directed configuration networks, including:

  1. A characterization of the typical distances between two randomly chosen nodes exhibiting an interesting behavior that depends on the level of correlation between the in-degree and out-degree;
  2. A description of a simple re-wiring mechanism to obtain various levels of clustering, capable of favoring different types of triangles.
  3. A rigorous analysis of the distribution of PageRank establishing its convergence to a distributional fixed point equation, which among other things can be used to explain why PageRank has a power-law distribution with the same index as the in-degree in the scale-free setting.

We will also discuss possible extensions to different random graph models and mention a few open problems.

[This is joint work with Ningyuan Chen, Nelly Litvak, Pim van der Hoorn, and Glen Kushta.]


Remco van der Hofstad, Eindhoven University

Title: Scale-free percolation.

remco.jpg Abstract: We propose and study a random graph model on the hypercubic lattice that interpolates between models of scale-free random graphs and long-range percolation. In our model, each vertex $x$ has a weight $W_x$, where the weights of different vertices are i.i.d. random variables. Given the weights, the edge between $x$ and $y$ is, independently of all other edges, occupied with probability $1-e^{-\lambda W_xW_y/|x-y|^{\alpha}}$, where

  1. $\lambda$ is the percolation parameter,
  2. $|x-y|$ is the Euclidean distance between $x$ and $y$, and
  3. $\alpha$ is a long-range parameter.

The most interesting behavior can be observed when the random weights have a power-law distribution, i.e., when $P(W_x>w)$ is regularly varying with exponent $1-\tau$ for some $\tau>1$. In this case, we see that the degrees are infinite a.s. when $\gamma =\alpha(\tau-1)/d <1$, while the degrees have a power-law distribution with exponent $\gamma$ when $\gamma>1$. Our main results describe phase transitions in the positivity of the critical value and in the graph distances in the percolation cluster as $\gamma$ varies. Let $\lambda_c$ denote the critical value of the model. Then, we show that $\lambda_c=0$ when $\gamma<2$, while $\lambda_c>0$ when $\gamma>2$. Further, conditionally on 0 and $x$ being connected, the graph distance between 0 and $x$ is of order $\log\log|x|$ when $\gamma<2$ and at least of order $\log|x|$ when $\gamma>2$. These results are similar to the ones in inhomogeneous random graphs, where a wealth of further results is known. We also discuss many open problems, inspired both by recent work on long-range percolation (i.e., $W_x=1$ for every $x$), and on inhomogeneous random graphs (i.e., the model on the complete graph of size $n$ and where $|x-y|=n$ for every $x\neq y$).

[This is joint work with Mia Deijfen and Gerard Hooghiemstra.]